Criteri di congruenza
Per calcolare il risultato dell’operazione modulo esistono alcuni utili criteri che sveltiscono i calcoli:
• Ogni intero modulo 2n è uguale alle sue ultime n cifre modulo 2n . Quindi, un numero è divisibile per 2n solo se lo sono le sue ultime n cifre.
Per esempio, 3367882 mod 8 = 882 mod 8 = 2.
• Analogamente, ogni intero modulo 5n è uguale alle sue ultime n cifre modulo 5n ; ed è divisibile per 5n solo se lo sono le sue ultime n cifre.
Per esempio, 3367882 mod 25 = 82 mod 25 = 7.
• Ogni intero modulo 3 o 9 è uguale alla somma delle sue cifre modulo 3 o 9.
Per esempio, 3367882 mod 9 = 37 mod 9 = 10 mod 9 = 1.
• Ogni intero modulo 11 è uguale alla somma delle sue cifre di posto dispari meno la somma delle sue cifre di posto pari modulo 11.
Per esempio, 3367882 mod 11 = [(2 + 8 + 6 +3)−(8+7+3)] mod 11 = (19−18) mod 11 = 1. Notare che la cifra di posto 1 è quella delle unità.
• Un intero n è divisibile per 7, cioè n mod 7 = 0, se e solo se lo è il numero ottenuto dall’intero iniziale senza la cifra delle unità sottraendo due volte la cifra delle unità.
Per esempio, 3367882 mod 7 = 0 in quanto 336788−2·2 = 336784, e ripetendo 33678−2·4 = 33670, 3367−2·0 = 3367, 336−2·7 = 322, 32−2·2 = 28; ma dato che l’ultimo è divisibile per 7, lo sono anche tutti gli altri e in particolare il numero di partenza. Inoltre 394 mod 7 ≠ 0 in quanto 39 − 2 · 4 = 31 mod 7 = 3 ≠ 0. Notare che questo criterio non è un criterio di congruenza: infatti 394 mod 7 = 2 e non 3.
• Un intero n è divisibile per un numero a non primo se e solo se è divisibile per ciascuno dei fattori pα della scomposizione in fattori primi di a.
Qui trovi tutti i criteri di divisibilità
Numeri congrui
Definizione
Due interi a e b si dicono congrui modulo m (in formule a ≡ b (mod m)) se divisi per m danno lo stesso resto. Equivalentemente, due interi sono congrui modulo m se m | (a −b).
Notare che una congruenza non è altro che un’uguaglianza tra resti, quindi dire
a ≡ b (mod m)
equivale a
a mod m = b mod m.
Pertanto tutte le proprietà delle congruenze si rifletteranno in analoghe proprietà dell’operazione modulo.
È facile verificare che la congruenza rispetto a un modulo fissato è una relazione di equivalenza, e cioè che valgono le tre proprietà
riflessiva (a ≡ a (mod m)),
simmetrica (se a ≡ b(mod m), allora b ≡ a (mod m))
transitiva (se a ≡ b (mod m) e b ≡ c (mod m), allora a ≡ c(mod m)).
Per questo motivo è possibile definire il concetto di classe di congruenza: si definisce classe di congruenza di a modulo m (e si indica con [a] o a ) l’insieme di tutti gli interi che divisi per m danno lo stesso resto di a. poiché i resti possibili sono tutti gli interi tra 0 ed m −1, avremo m differenti classi di congruenza.
Per esempio, modulo 4 avremo le classi:
0 = {…,−8,−4, 0, 4, 8,…}
1 = {…,−7,−3, 1, 5, 9,…}
2 = {…,−6,−2, 2, 6, 10,…}
3 = {…,−5,−1, 3, 7, 11,…}
Notare che ogni classe può essere chiamata con infiniti nomi diversi, uno per ogni elemento che contiene; per esempio nel caso precedente avevamo [1] = [9] = ….
Comportamento delle congruenze rispetto a somma e prodotto
Le congruenze si comportano bene rispetto a somma, sottrazione e prodotto. Infatti:
a ≡ b, c ≡ d (mod m) ⇒ a + c ≡ b + d , a · c ≡ b · d , −a ≡ −b (mod m)
In altre parole, ogni qualvolta in una congruenza abbiamo una somma, una sottrazione o un prodotto, possiamo sostituire i termini che lo compongono con altri termini che ci rendono più facili i calcoli, a patto che questi abbiano lo stesso resto modulo m.
Esempio
Per calcolare (324 · 231) mod 10 non è necessario svolgere effettivamente il prodotto, ma si possono sostituire i fattori con i termini equivalenti 4 ≡ 324 (mod 10) e 1 ≡ 231(mod 10), ottenendo immediatamente il risultato 4 · 1 = 4.
Notare che queste proprietà si applicano anche nel caso dell’elevamento a potenza fissato l’esponente, essendo esso una moltiplicazione ripetuta:
a ≡ b (mod m) ⇒ an ≡ bn(mod m)
Esempio
Calcolare 49314931 mod 9.
Possiamo sfruttare il fatto che 4931 mod 9 = (4 + 9 + 3 + 1) mod 9 = 8, e che quindi 4931 ≡ 8 ≡ −1 (mod 9), per cui 49314931 mod 9 = (−1)
4931 mod 9 = −1 mod 9 = 8.
Notare che questo metodo ci consente di ridurre la base a valori più comodi, ma non ugualmente l’esponente che non può essere sostituito. Siamo stati quindi fortunati a trovare proprio il resto −1, del quale è semplice calcolare le potenze anche molto grandi.
(86)