Per chi non avesse dimestichezza con le congruenze, consigliamo di leggere prima questo articolo:
https://giuseppemerlino.wordpress.com/2011/02/17/congruenze/
In questa breve nota useremo il simbolo ^ per denotare “elevato a” ed il simbolo * per denotare “moltiplicato per”.
Operando con carta e penna, si può risolvere la congruenza Ax ≡ B modulo N, agendo in questo modo:
Si tratta la congruenza come se fosse un’eguaglianza e si ricava la x:
x = B / A
Poi si somma al numeratore B il numero N tante volte fino a che (B + kN) sia divisibile per A. La soluzione della congruenza sarà (B + kN) / A.
Facciamo un esempio pratico:
Si voglia risolvere la congruenza:
5x ≡ 11 (modulo 41)
Dobbiamo aggiungere ad 11 tante volte 41 finchè non si ottenga un numero divisibile per 5:
11 + 41 = 52
52 + 41 = 93
93 + 41 = 134
134 + 41 = 175 divisibile per 5.
175 : 5 = 35
Dunque la nostra congruenza avrà soluzione x = 35, infatti:
5x ≡ 11 (modulo 41)
5x = 5*35 = 175
e
175 : 41 = 4 con resto 11.
Qualora il numero N sia un numero primo P, esiste una soluzione rigorosa per la congruenza Ax ≡ B modulo P, cioè una formula per x.
Il piccolo Teorema di Fermat asserisce che, se P è un numero primo, allora:
A^(P-1) ≡ 1 (modulo P)
per ogni A compreso tra A e (P-1) e, più in generale, per ogni A che sia primo con P.
Rielaboriamo questa espressione:
A*A^(P-2) ≡ 1 (modulo P)
Moltiplichiamo ambo i membri per B:
A*B*A^(P-2) ≡ B (modulo P)
Confrontando questa espressione con la congruenza Ax ≡ B modulo P, otteniamo immediatamente:
x = B*A^(P-2) (modulo P)
Diciamo subito che questa soluzione algebrica coinvolge numeri molto grandi, ma esiste un semplice algoritmo (usato nei programmi al computer) per superarlo.
Facciamo prima un esempio con numeri “piccoli”.
Si voglia risolvere la congruenza:
5x ≡ 2 (modulo 13)
13 è un numero primo, per cui possiamo applicare la nostra soluzione:
x = B*A^(P-2) = 2*5^11 = 2 * 48828125 = 97656250 (modulo P)
La minima soluzione della congruenza (detta radice) è il resto della divisione di 97656250 diviso 13:
97656250 : 13 = 7512019 col resto di 3.
Dunque la soluzione della congruenza 5x ≡ 2 (modulo 13) sarà x= 3, infatti (5*3 -2) è divisibile per 13, come si può facilmente verificare.
Ovviamente, con coefficienti e modulo così piccoli, avremmo fatto prima a risolvere la congruenza per tentativi, ma non lo avremmo certo potuto fare per una congruenza con coefficienti e modulo appena più grandi.
Abbiamo accennato prima ad un algoritmo per calcolare il termine B*A^(P-2) (modulo P)
Si procede in questo modo:
Si moltiplica A per se stesso tante volte fino a giungere al primo termine che supera P.
Si calcola il valore di questo prodotto modulo P e lo si moltiplica per A tante volte, sempre fermandosi al primo termine che supera P.
Si continua fino ad aver moltiplicato in tutto (P-2) termini e si calcola il risultato modulo P.
Infine si moltiplica per B e, se necessario, si calcola il risultato modulo P.
Questo metodo che, effettuato con carta e penna, è estremamente laborioso (immaginatelo con numeri grandi), è velocissimo al computer, se programmato in linguaggio C o CPP o anche in Basic. Il risultato si ottiene in una frazione di secondo.
Facciamo un esempio pratico.
Si voglia risolvere la congruenza:
5x ≡ 11 (modulo 41)
41 è un numero primo, quindi sarà valida la soluzione: x = B*A^(P-2) = 11*5^39 (modulo 41).
Calcoliamo, con l’algoritmo che abbiamo appena esposto, il termine 5^39 (modulo 41).
5*5*5 = 125 ; 125 modulo 41 = 2
2*5*5 = 50 ; 50 modulo 41 = 9
9*5 = 45 ; 45 modulo 41 = 4
4*5*5 = 100 ; 100 modulo 41 = 18
18*5 = 90 ; 90 modulo 41 = 8
8*5*5 = 200 ; 200 modulo 41 = 36
36*5 = 180 ; 180 modulo 41 = 16
16*5 = 80 ; 80 modulo 41 = 39
39*5 = 195 ; 195 modulo 41 = 31
31*5 = 155 ; 155 modulo 41 = 32
32*5 = 160 ; 160 modulo 41 = 37
37*5 = 185 ; 185 modulo 41 = 21
21*5 = 105 ; 105 modulo 41 = 23
23*5 = 115 ; 115 modulo 41 = 33
33*5 = 165 ; 165 modulo 41 = 1
1*5*5*5 = 125 ; 125 modulo 41 = 2
2*5*5 = 50 ; 50 modulo 41 = 9
9*5 = 45 ; 45 modulo 41 = 4
4*5*5 = 100 ; 100 modulo 41 = 18
18*5 = 90 ; 90 modulo 41 = 8
8*5*5 = 200 ; 200 modulo 41 = 36
36*5 = 180 ; 180 modulo 41 = 16
16*5 = 80 ; 80 modulo 41 = 39
39*5 = 195 ; 195 modulo 41 = 31
31*5 = 155 ; 155 modulo 41 = 32
32*5 = 160 ; 160 modulo 41 = 37
37*5 = 185 ; 185 modulo 41 = 21
21*5 = 105 ; 105 modulo 41 = 23
23*5 = 115 ; 115 modulo 41 = 33
Ci fermiamo in quanto abbiamo moltiplicato 5 per se stesso 39 volte. Dunque:
5^39 modulo 41 = 33
poichè x = 11*5^39, dobbiamo ancora moltiplicare per 11:
x = 11*33 = 363 ; 363 modulo 41 = 35.
Dunque 35 sarà la soluzione della nostra congruenza, come si può facilmente verificare:
5x ≡ 11 (modulo 41)
5*35 = 175
175 : 41 = 4 con resto appunto 11.
La soluzione della congruenza Ax ≡ B modulo N è utile anche per risolvere l’equazione diofantea di primo grado in due incognite:
Ax + By = C
Nella quale A, B e C sono numeri interi e le soluzioni (x,y) sono costituite da numeri interi.
Infatti questa equazione può essere facilmente trasformata in una congruenza di primo grado:
Si ricavi dall’equazione indifferentemente x o y:
y = (C – Ax) / B (1)
Affinchè y sia un numero intero, (C – Ax) dovrà essere divisibile per B e cioè:
C – Ax ≡ 0 (modulo B)
C ≡ Ax (modulo B)
Ax ≡ C (modulo B)
Risolvendo questa congruenza si trova la x e, ponendo la x nella (1), si trova la y. Sia x che y risulteranno numeri interi.
Consideriamo, ad esempio, l’equazione diofantea:
9x + 7y = 200
y = (200 – 9x) / 7 (2)
200 – 9x ≡ 0 (modulo 7)
9x ≡ 200 (modulo 7)
Poichè 7 è un numero primo, possiamo applicare la formula:
x = B*A^(P-2) (modulo P)
x = 200*9^5 (modulo 7)
x = 200*59049 (modulo 7)
x = 11809800 (modulo 7)
x = 2
Poniamo questo valore della x nella (2) per ricavare la y:
y = (200 – 9x) / 7 = (200 – 18) / 7 = 182 / 7 = 26.
Dunque una soluzione dell’equazione diofantea 9x + 7y = 200 sarà:
x = 2 ; y = 26
Infatti:
9x + 7y = 9*2 + 7*26 = 18 + 182 = 200
Giuseppemerlino's Blog 