CONGRUENZE

Il concetto di Congruenza è di fondamentale importanza nella Teoria dei Numeri.
L’espressione simbolica  a ≡ b (modulo n) ,  si legge: “a è congruo a b, modulo n ed indica che (a-b) è divisibile per n o, il che è lo stesso, che b è il resto della divisione di a diviso n.
Consideriamo un qualsiasi numero intero, per esempio 7, e scriviamo i resti della divisione di tutti i numeri naturali per 7. Otterremo:

1 2 3 4 5 6 0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 …………

Ciò vuol dire che, rispetto a 7, esistono 7 classi di numeri che, divisi per 7, danno lo stesso resto. Per esempio, la classe dei numeri che, divisi per 7, danno resto 5 sarà:

[5, 12, 19, 26, 33 …. ]

Tutti questi numeri sono soluzione della congruenza:  x ≡ 5 (mod. 7), ma, nella Teoria delle Congruenze, si considera la minima soluzione, per cui diremo che la soluzione di questa congruenza è 5.
In generale potremo affermare che, dato un numero n, ogni intero a è equivalente ad un intero r tra 0 e n-1: il resto della divisione di a per n.
La congruenza che abbiamo preso in esame è di primo grado, in quanto il massimo esponente della incognita x è 1. La forma generale di una congruenza di primo grado sarà  ax ≡ b (mod. n).
Alcuni Teoremi fodamentali della teoria dei Numeri possono essere espressi sotto forma di congruenza.
Useremo i simboli  ” ! ”  e  ” ^ ” per indicare rispettivamente “fattoriale” ed “elevato a”. Per esempio:

6! = 6x5x4x3x2x1 = 720
2^5 = 2x2x2x2x2 = 32

TEOREMA DI WILSON:
Se p è un numero primo, risulterà sempre:

(p-1)! ≡ -1 (mod p)

Cioè, se p è un numero primo, il resto della divisione di (p-1)! diviso p sarà sempre (p – 1).

Ad esempio, per il numero primo 7, avremo:

(p-1)! = (7 -1 )! = 6! = 720
720 : 7 = 102 col resto di 6 (e 6 = p – 1 = 7 – 1)

PICCOLO TEOREMA DI FERMAT:
Se p è un numero primo, allora per ogni intero a (che non divida p), risulterà:

a^p ≡ a (mod. p)

o, il che è lo stesso:

a^(p-1) ≡ 1 (mod p)

Ad esempio, per il numero primo 13, sceglendo come base 2, avremo:

a^(p-1) = 2^12 = 4096
4096 : 13 = 315  con il resto di 1.

Dato un numero intero a, si defisce inverso di a modulo n, quel numero b, se esiste, tale che:

ab ≡ 1 (mod. n)

Se p è un numero primo, tutti i numeri interi compresi tra 1 e (p – 1) si ditribuiscono in (p – 1)/2 coppie di inversi. Ad esempio, se scegliamo p = 13, avremo 6 coppie di inversi:

(1,1) (2,7) (3,9) (4,10) (5,8) (6,11)

L’inverso b di a modulo p (numero primo), si può trovare applicando il piccolo Teorema di Fermat:

a^(p-1) ≡ 1 (mod. p)
a*a^(p-2) ≡ 1 (mod.p)
b = a^(p-2)
o, meglio:
b ≡ a^(p-2) (mod. p)

La Congruenza di primo grado ha una sola soluzione. Consideriamo adesso la semplice congruenza quadratica:

x^2 ≡ b (mod. p) con p numero primo.

Questa congruenza o ha 2 soluzioni o nessuna. Se ha soluzioni, diremo che b è un residuo quadratico di p. In pratica, un residuo quadratico di un numero primo p è il resto della divisione di un quadrato esatto diviso p. Tutti i numeri primi p hanno (p-1)/2 residui quadratici e (p-1)/2 non residui quadratici. Si noti che se b1 e b2 sono una soluzione, risulterà sempre b1 + b2 = p.
Ad esempio la congruenza quadratica:

x^2 ≡ 7 (mod 29)

Ha le 2 soluzioni  6  e  23, infatti:

6^2 = 36 che diviso per 29 fa 1 col resto di 7.
23^2 = 529 che diviso per 29 fa 18 col resto di 7.

inoltre:  6 + 23 = 29.

Chiudiamo dando due importanti definizioni della teoria dei Numeri:

Si definisce Ordine di un intero a modulo p (numero primo) il minimo esponente x, tale che:

a^x ≡ 1 (mod.p)

L’ordine di a modulo p è sempre un divisore di (p-1) e, se coincide proprio con (p-1), a si definisce Radice Primitiva del numero primo p.