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
oppure
a è congruo a b modulo n.
In alcuni testi la RELAZIONE di CONGRUENZA MODULO n viene definita in modo diverso.
Dato l'insieme Z dei NUMERI INTERI RELATIVI e a e b appartenenti a Z ed n NUMERO INTERO POSITIVO si dice a congruo b modulo n se esiste un numero q tale che q appartiene all'insieme dei numeri interi relativi e che a -b è uguale a q per n.
Ovvero:
Z = {NUMERI INTERI RELATIVI}
n = NUMERO INTERO POSITIVO
se a è congruo a b modulo n allora esiste un numero q appartenente a Z tale che a-b è uguale a q per n e viceversa
In parole povere a è congruo b modulo n se la differenza tra a e b è uguale al prodotto tra n è un altro numero relativo che chiamiamo q.
O volendolo dire ancora in altri termini, se dividiamo a - b per n otteniamo q e la divisione non ha resto.
Tornando all'esempio visto nella lezione nella quale abbiamo parlato di congruenza possiamo verificare quanto detto. Infatti:
n = 3
a = 14
b = -13
14 = 3 · (+4) + 2
-13 = 3 · (-5) + 2
a - b = 14 - (-13) = 14 + 13 = 27 = 9 · (+3).
Ora vogliamo dimostrare che esprimere i concetti in un modo o nell'altro è indifferente.
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
a - b.
Sostituiamo ad a il suo valore e a b il suo valore:
a - b= nk + r - (nk' + r) = nk + r - nk' - r = nk - nk' = n (k - k').
Ora poniamo
k - k' = q.
Quindi possiamo dire che
a - b = qn.
Abbiamo dimostrato che
se a è congruo b modulo n allora esiste un numero q appartenente a Z tale che a-b è uguale a q per n.
Ora dobbiamo dimostrare che è vero anche il contrario.
Partiamo da
a - b = qn.
Portiamo b a secondo membro cambiando di segno
a = qn + b.
Noi sappiamo che
b = nk' + r.
Sostituiamo nella precedente e abbiamo:
a = qn + nk' + r.
Mettiamo in evidenza la n:
a = n (q + k') + r.
Nella prima dimostrazione avevamo posto
k - k' = q
quindi
- q - k' = - k
q + k' = k .
Quindi possiamo dire che
a = kn + r.
Abbiamo dimostrato che
se esiste un numero q appartenente a Z tale che a-b è uguale a q per n allora a è congruo b modulo n.
Esistono anche altri modi di esprimere la RELAZIONE di CONGRUENZA MODULO n: li vedremo nel prossimo approfondimento.
