Congruenza modulo n

Osserviamo il quadrante di un orologio analogico: è suddiviso in dodici ore e allo scoccare delle dodici si ricomincia dall'ora zero, ovvero il numero dodici equivale allo zero. L'orologio è quindi composto da un insieme di 12 ore {0,1,2,3,4,5,6,7,8,9,10,11} con le quali possiamo pure fare delle operazioni. Sono le 8 del mattino, ci apprestiamo a fare un viaggio che sappiamo durerà 7 ore, per cui arriveremo a destinazione alle 15, ma, a quell'ora la lancetta dell'orologio sarà sulle 3, potremo scrivere quindi 15≡3. In pratica, basta dividere il 15 per 12 e il resto che si ottiene dalla divisione è il numero che lo rappresenta sul quadrante cioè 3.

Storicamente l'operazione di modulo è nata per utilizzare i resti. Sempre legato all'orologio analogico un altro esempio potrebbe essere il seguente: trasformare 95 minuti in ore e minuti. Il quoziente della divisione intera ci darà il numero di ore, ma il resto della divisione per 60 ci dà il numero dei minuti, 95 min corrispondono quindi ad 1h e 35 minuti. In questo caso 95 equivale a 35 modulo 60. Altri esempi di applicazione dei moduli è la trigonometria dove, se l'unità di misura è espressa in gradi, allora la misura degli angoli è in modulo 360. Per questi ed altri motivi ancora, possiamo pensare anche ad un orologio con un numero qualsiasi di ore, indicheremo questo insieme con il simbolo Z_n lo chiameremo classi di resti modulo n.

Definizione: siano x e y due interi e m∈N: m≥0. Si dice che x e y sono congruenti modulo n, in simboli a ≡ b se n divide x-y .

In altre parole, possiamo dire che x è congruente a y modulo m se x e y differiscono per un multiplo di m, cioè x ≡ y se m divide(x-y), ovvero se esiste un p∈Z tale che x-y = pm, ovvero x = y+pm, con p∈Z.

In particolare possiamo affermare che m divide x è come dire che x è congruente a 0 (basta porre y=0 nelle equivalenze sopra).

La relazione così definita è una relazione di equivalenza infatti, gode delle seguenti proprietà:

proprietà riflessiva: x ≡ x ∀ x≡Z; infatti x-x=0 è sempre divisibile per ogni intero m diverso da zero;

proprietà simmetrica: se x ≡ y, allora y ≡ x; infatti se m divide (x-y), allora m divide (y-x), per le proprietà della divisibilità fra interi;

proprietà transitiva: se x ≡ y e y ≡ z, allora x ≡ z. infatti se m divide(x-y) e m divide(z-y), allora esistono due interi p, q tali che x-y = pm e z-y = qm, quindi se consideriamo z-x = z-y-x+y = pm+qm = (p+q)m abbiamo che m divide(z-x).

Quindi se nell'insieme degli interi è definita una relazione di equivalenza modulo n, avremo un insieme quoziente costituito da n classi di equivalenza, ovvero tante quanti sono i possibi resti della divisione per n (da n-1 a 0). Come rappresentante della classe di equivalenza si pone il più piccolo della classe, ma le operazioni non cambiano se si pone uno qualsiasi dei rappresentanti della classe di equivalenza

Si può dimostrare che se:

x ≡ y (mod n) e se z ≡ w (mod n), allora (x+z) ≡ (y+w) (mod n). Da ciò si ricava la regola: [x]_n + [y]_n = [x + y]_n