Aritmetica modulare/La relazione di congruenza: differenze tra le versioni

m
typo
m (cambio avanzamento a 100%)
m (typo)
È di facile verifica che la relazione <math>\equiv_n</math> così definita è di equivalenza:
*è riflessiva: ''a'' - ''a''=0, e 0 è divisibile per ''n'';
*è simmetrica: se ''a'' - ''b'' = ''kn'', allora ''b'' - ''a'' = -(''a'' -' ''b'')=-''kn''=(-''k'')''n'', e -''k'' è ancora un intero;
*è transitiva: se ''a'' - ''b'' = ''kn'' e ''b'' - ''c'' = ''jn'', allora
:<math>a-c=a-b+b-c=kn-jn=(k-j)n</math>
 
A volte è conveniente usare, anziché i valori -1, -2, e così via, al posto di ''n'' -1, ''n'' -2, eccetera. In questo senso, è possibile anche parlare di modulo:
:<math>|a| \mod n=\begin{cases}a & \text{se}~a<\leq n/2\\ n-a & \text{se}~a>n/2\end{cases}</math>
 
== Le operazioni ==
La relazione di congruenza è ''compatibile'' con l'addizione e la moltiplicazione nel senso seguente: dati due numeri ''a'' e ''b'', si ha che la classe di equivalenza cui appartiene la somma (rispettivamente il prodotto) non cambia se si variano i rappresentanti delle classi di equivalenza.
 
Infatti, siano ''a''<nowiki>'</nowiki> e ''b''<nowiki>'</nowiki> due interi rispettivamente nelle classi di equivalenza di ''a'' e di ''b'', ovvero tali che
:<math>a'=a+kn \mathrm{~~~e~~~} b'=b+kn</math>
Si ha allora
66

contributi