Divisione e semplificazione
Anche se tra i numeri interi è noto che non sempre esistono i reciproci (cioè i numeri del tipo 1/a), all’interno delle congruenze è possibile definirli in modo del tutto analogo a quanto avviene nei numeri razionali.
Dati a e m interi si dice quindi inverso di a (modulo m) quel numero a−1 = b tale per cui a · b ≡ 1 (mod m). Non sempre l’inverso esiste, ma se esiste è certamente unico.
Per esempio,
per il modulo 7 abbiamo che 2−1 = 4 e 3−1 = 5, infatti 2 · 4 = 8 ≡ 1 (mod 7), 3 · 5 = 15 ≡ 1 (mod 7).
Nella maggior parte dei casi, il miglior modo di trovare l’inverso è procedere per tentativi.
È facile verificare che
l’inverso esiste se e solo se il MCD(a,m) = 1. Infatti a · b ≡ 1 (mod m) =⇒ a ·b = 1 + k · m =⇒ a ·b − k · m = 1,
e per il Teorema di Bezout il primo membro è sempre multiplo di MCD(a,m) al variare di b e k .
In modo del tutto analogo si comporta la semplificazione. Infatti in una congruenza del tipo a · c ≡ b · c (mod m) si può semplificare per c e ottenere a ≡ b (mod m) solo se MCD(c ,m) = 1; risultato che si ottiene semplicemente moltiplicando i due membri per l’inverso di c.
In caso contrario, è comunque possibile una semplificazione, facendo attenzione a dividere però anche il modulo:
a · c ≡ b · c (mod m · c ) ⇒ a ≡ b (mod m)
ESEMPIO:
Riformulare l’espressione 2 · 4 ≡ 5 · 4 (mod 6).
Sebbene questa espressione sia certamente vera, se semplifichiamo per 4 otteniamola relazione scorretta
2 ≡ 5 (mod 6).
Possiamo però dividere tutto per 2, compreso il modulo, ottenendo
2 · 2 ≡ 5 · 2 (mod 3)
e poi semplificare per il 2 rimanente e ottenere la relazione corretta
2 ≡ 5 (mod 3)
Operazioni ripetute
Uno dei punti di forza delle congruenze è la facilità con la quale vengono calcolate le operazioni ripetute. Essendo infatti possibili soltanto m valori distinti, entro al più m passaggi si troverà un valore che è già comparso precedentemente. Da quel punto in poi, tutti i valori che si troveranno si ripeteranno ciclicamente tra quelli già trovati (infatti applicando l’operazione allo stesso numero si ottiene lo stesso risultato). In pratica, se iterando un’operazione i risultati si ripetono ogni k passi, allora possiamo ridurre il numero di volte in cui questa viene ripetuta facendo n mod k e considerando il risultato ottenuto.
ESEMPIO
Calcolare 2546321 mod 12.
Calcolare una potenza di 2 equivale a ripetere la moltiplicazione per 2 partendo da 1. Modulo 12 otterremo quindi la sequenza 1, 2, 4, 8, 4,…. Avendo ora trovato un elemento ripetuto (il 4), sappiamo che d’ora innanzi la sequenza proseguirà alternando il 4 e l’8, come si può facilmente verificare. Dato poi che i risultati si ripetono ogni 2 passi, e 546321 mod 2 = 1, immediatamente si ottiene che il valore cercato è 8.
Residui quadratici
Si dicono residui quadratici (o in generale n-esimi) modulo m tutte le possibili classi di resto che possono assumere i quadrati perfetti (o in generale le n-esime potenze) modulo m.
Se si escludono i casi m ≤ 2, non tutte le classi di resto sono possibili; per cui con questa tecnica in un equazione a valori interi spesso si riescono ad escludere alcuni casi ed è possibile così avvicinarsi alla soluzione.
Per esempio, modulo 4 abbiamo che 02 = 0; 12 = 1; 22 = 4 ≡ 0; 32 = 9 ≡ 1, quindi i soli resti possibili per le potenze sono effettivamente 0 e 1.
Vediamo ora alcuni esempi:
• I residui quadratici modulo 3 sono [0] e [1].
• I residui quadratici modulo 4 sono [0] e [1]. In particolare, il quadrato di un intero pari è congruo a 0, e quello di un intero dispari è congruo a 1.
• I residui quadratici modulo 5 sono [0], [1] e [−1] = [4]
• I residui quadratici modulo 8 sono [0], [1] e [4].
• I residui terzi modulo 7 sono [0], [1] e [−1] = [6].
• I residui quarti modulo 16 sono [0] e [1].
• I residui quinti modulo 11 sono [0], [1] e [−1] = [10].
È possibile estendere la lista ad altri casi che sono di interesse, semplicemente provando a svolgere i calcoli su tutti i possibili resti da 0 a m − 1.
(481)