Congruenza modulo n

congruenza modulo n

congruenza modulo n in algebra, relazione di equivalenza definita sull’insieme dei numeri interi Z come segue: se n è un fissato numero intero maggiore di 1, due interi a e b sono detti congruenti modulo n se n divide la differenza a − b. Si scrive a ≡ b (mod n) e si legge: a congruo b modulo n; n è detto modulo della congruenza. In modo equivalente: a ≡ b (mod n) se a e b danno lo stesso resto nella divisione intera per n. Per esempio, 22 ≡ 7 (mod 5) perché entrambi danno resto 2 nella divisione intera per 5. Mediante tale relazione, l’insieme Z risulta partizionato in n classi di equivalenza, dette in questo caso classi resto modulo n o anche classi di congruenza modulo n, ciascuna contenente tutti i numeri congrui tra loro modulo n: due interi appartengono alla stessa classe resto se e solo se sono congruenti modulo n. Se, come nell’esempio, il modulo è 5, si vengono così a formare cinque classi (tante quanti sono i possibili resti nella divisione per 5) così indicate: [0], [1], [2], [3], [4]. Per stabilire a quale classe appartiene un numero intero lo si divide per n: se il numero è positivo, il resto indica la classe, se esso è negativo, la classe è uguale alla somma del resto con n. L’insieme delle classi di congruenza modulo n, vale a dire il quoziente di Z rispetto alla relazione di congruenza modulo n, è indicato con il simbolo Z_n; esso eredita da Z le operazioni di addizione e moltiplicazione e acquisisce così la struttura di anello. Dotato di questa struttura, esso è detto l’anello delle classi resto modulo n (→ Z_n, insieme delle classi resto modulo n).