Congruenza

Enciclopedia della Scienza e della Tecnica (2008)

congruenza

Luca Tomassini

Relazione tra due elementi dell’insieme ℤ dei numeri interi relativi (cioè positivi, negativi o nulli) a e b della forma a=b+mk, con m,k∈ℤ rispettivamente fissato e arbitrario. In altri termini, la differenza ab deve essere divisibile per un intero positivo m, chiamato modulo della congruenza, ovvero a e b hanno resti identici quando divisi per m; a è detto allora un resto di b modulo m. Tale relazione è indicata con la scrittura ab (mod m). La congruenza modulo un intero m fissato stabilisce una relazione di equivalenza nell’insieme ℤ: è riflessiva, poiché aa (mod m); simmetrica, poiché da ab (mod m) segue ba (mod m); transitiva, poiché da ab (mod m) e bc (mod m) segue ac (mod m). Segue che la relazione ≡ (mod m) divide l’insieme ℤ in classi di equivalenza X1,X2,… mutualmente disgiunte, dette classi di residui. Naturalmente, due interi appartengono alla stessa classe di equivalenza se e solo se sono congruenti modulo m. Ogni intero è dunque congruente con uno e uno solo dei numeri 0,…,m−1, ciascuno dei quali appartiene a una classe distinta. Le distinte classi di residui così determinate sono quindi esattamente m. Le congruenze rispetto a un modulo fissato possono essere sommate, sottratte e moltiplicate e questo induce le corrispondenti operazioni sulle classi di residui, che formano quindi un anello. Sia ora F(x1,…,xν) un polinomio a coefficienti interi nelle n variabili x1,…,xν. Un’equazione della forma F(x1,…, xν)≡0 (mod m) è detta equazione alle congruenze. Se un qualunque insieme di interi a1,…,aν è soluzione dell’equazione e gli interi aι, 1≤in, appartengono rispettivamente alle classi di residui Xι, 1≤in, allora ogni altro insieme aιXι, 1≤in, è a sua volta soluzione. Per es., le soluzioni di una congruenza di primo grado axb (mod m) con a e m primi tra loro (il loro più grande divisore comune è 1) appartengono tutte a un’unica classe. Un celebre risultato concernente le equazioni alle congruenze è il piccolo teorema di Fermat: se p è un numero primo e a non è divisibile per p, allora aπ−1≡1 (mod p).

Numeri, teoria dei

CATEGORIE