CONGRUENZA MODULO n IN Z
Parlando di CONGRUENZA abbiamo detto che dato un NUMERO INTERO POSITIVO n, si dice che due NUMERI INTERI RELATIVI a e b sono CONGRUI TRA LORO MODULO n se, divisi per n, danno lo STESSO RESTO, cioè se:
a = nk + r
b = nk' + r.
In questo caso si scrive:
che si legge
a congruo b modulo n.
Nell'approfondimento precedente abbiamo detto che la RELAZIONE di CONGRUENZA MODULO n può essere definita anche così:
se a congruo b modulo n allora esiste un numero q appartenente a Z tale che a meno b è uguale a q per n e viceversa.
Potremmo anche dire che
se a congruo b modulo n allora esiste un numero q appartenente a Z tale che a è uguale alla somma tra b e il prodotto di q per n e viceversa.
E' facile comprendere, infatti, che se
a - b = q·n
allora
a = b + qn
che si ottiene dalla precedente portando b a secondo membro e cambiando di segno.
Un ulteriore modo per esprime la CONGRUENZA MODULO n IN ZETA è il seguente:
se a congruo b modulo n allora n divide a meno b.
Il simbolo
si legge
n divide a meno b
e indica, per l'appunto che, dividendo a - b per n il resto è zero, che è esattamente la stessa cosa che dire:
a - b = kn.
Inoltre possiamo scrivere anche che:
se a congruo b modulo n allora esiste un numero h appartenente a zeta tale che b meno a è uguale ad h per n.
Vediamo se è vera tale affermazione.
Se a è congruo b modulo n significa che dividendo a e b per n, il resto delle due operazioni (che chiamiamo r) è lo stesso. Quindi:
a = nk + r
b = nk' + r.
Ora vediamo a cosa è uguale
b - a.
Sostituiamo a b il suo valore e ad a il suo valore:
b - a = nk' + r - (nk + r) = nk' + r - nk - r = nk' - nk = n (k' - k).
Ora poniamo
k' - k = h.
Quindi possiamo dire che
b - a = hn.
Abbiamo dimostrato che
se a è congruo b modulo n allora esiste un numero h appartenente a Z tale che b meno a è uguale ad h per n.
Ora dobbiamo dimostrare che è vero anche il contrario.
Partiamo da
b - a = hn.
Portiamo b a secondo membro cambiando di segno
- a = hn - b.
Cambiamo di segno:
a = - hn + b
a = b - hn.
Noi sappiamo che
b = nk' + r.
Sostituiamo nella precedente e abbiamo:
a = nk' + r - hn.
Mettiamo in evidenza la n:
a = n (k' - h) + r.
Nella prima dimostrazione avevamo posto
k' - k = h
quindi
k' - h = k .
Quindi possiamo dire che
a = kn + r.
Quindi abbiamo dimostrato anche che
se esiste un numero h appartenente a Z tale che b meno a è uguale ad h per n allora a è congruo b modulo n.
