L'ultimo teorema di Fermat/Appendice: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
mNessun oggetto della modifica |
mNessun oggetto della modifica |
||
Riga 33:
Nel caso entrambi i numeri siano positivi, si può anche dire che ''a'' e ''b'' sono congruenti modulo ''n'' se hanno lo stesso resto nella divisione per ''n''. Quindi possiamo anche dire che 38 è congruo 14 modulo 12 poiché sia 38 sia 14 hanno resto 2 nella divisione per 12.
=== Proprietà della congruenza ====
La congruenza è una relazione di equivalenza tra numeri interi come si vede dalle seguenti proprietà:
*'''Proprietà riflessiva''': ogni numero è congruo a sé stesso modulo ''n'', per ogni ''n'' diverso da 0 fissato.
::<math> a \equiv a \pmod{n} \qquad \forall a \in \mathbb{N},\forall n \in \mathbb{N}_0 </math>
::''Dimostrazione'': si ha ''a - a'' = 0. Ma come è noto, ogni intero non nullo è divisore di 0. Quindi ''n'' divide ''(a - a)''
*'''Proprietà simmetrica''': se ''a'' è congruo a ''b'' modulo ''n'' allora ''b'' è congruo ad ''a'' modulo ''n''
::<math> a \equiv b \pmod{n} \Rightarrow b \equiv a \pmod{n} \qquad \forall a,b \in \mathbb{N},\forall n \in \mathbb{N}_0 </math>
::''Dimostrazione'': se ''n'' divide ''(a - b)'' , allora ''n'' divide anche l'opposto ''(b - a) = - (a - b)''
*'''Proprietà transitiva''': se ''a'' è congruo a ''b'' modulo ''n'' e ''b'' è congruo a ''c'' modulo ''n'' allora anche ''a'' è congruo a ''c'' modulo ''n''.
::<math> a \equiv b \pmod{n} \quad\land\quad b \equiv c \pmod{n} \Rightarrow a \equiv c \pmod{n} \qquad \forall a,b,c \in \mathbb{N},\forall n \in \mathbb{N}_0 </math>
::''Dimostrazione'': se ''n'' divide ''(a - b)'' e ''n'' divide ''(a - c)'' allora, per la proprietà distributiva della divisione rispetto alla sottrazione, ''n'' divide anche ''[(a - c) - (a - b)]=[a - c - a + b] = (b - c)''.
====Invarianza rispetto alle operazioni aritmetiche====
Un'altra importante caratteristica della relazione di congruenza è il fatto di essere preservata dalle usuali operazioni aritmetiche tra interi:
*'''Invarianza per addizione''': aumentando o diminuendo della stessa quantità due numeri congruenti modulo n, i nuovi numeri ottenuti sono ancora congruenti tra loro modulo ''n''. Più sinteticamente
::<math> a \equiv b \pmod{n} \Leftrightarrow (a + c ) \equiv (b + c) \pmod{n} \qquad \forall a,b,c \in \mathbb{N},\forall n \in \mathbb{N}_0 </math>
::''Dimostrazione'': scriviamo ''(a - b)'' = ''(a - b + c - c) = ''(a + c) - (b + c)
*'''Invarianza per moltiplicazione''': moltiplicando per una stessa quantità due numeri congruenti modulo ''n'', i nuovi numeri ottenuti sono ancora congruenti tra loro modulo ''n''.
::<math> a \equiv b \pmod{n} \Rightarrow a\cdot c \equiv b \cdot c \pmod{n} \qquad \forall a,b,c \in \mathbb{N},\forall n \in \mathbb{N}_0 </math>
::''Dimostrazione'': se ''n'' divide ''(a - b)'' allora ''n'' divide ''(a - b)×c''
::'''Nota''': Questa proprietà si può invertire solo se ''n'' non divide ''c'', cioè se ''c'' non è congruo a 0 (mod ''n'').
*'''Invarianza rispetto all'elevazione a potenza''': elevando due numeri congrui modulo ''n'' alla stessa potenza ''k'', i numeri ottenuti sono ancora congrui tra loro modulo ''n''.
::<math> a \equiv b \pmod{n} \Rightarrow a^{k} \equiv b^{k} \pmod{n} \qquad \forall a,b,c \in \mathbb{N},\forall k \in \mathbb{N},\forall n \in \mathbb{N}_0 </math>
::''Dimostrazione'': se ''a ≡ b ≡ 0 (mod n)'' la proposizione è banale. Se ''a ≡ b (mod n)'' non sono nulli, supponiamo di sapere che <math>a^{k-1}\equiv b^{k-1} \pmod{n}</math>. Moltiplicando entrambi i termini per ''a'' grazie all'invarianza per moltiplicazione, avremo <math>a^{k}\equiv b^{k-1}\cdot a \pmod{n}</math>. Partiamo ora dalla congruenza'' a ≡ b (mod n)'' e moltiplichiamo entrambi i membri per <math> b^{k-1} \pmod{n}</math>, sempre grazie all'invazianza per moltiplicazione. Otteniamo:<math>a\cdot b^{k-1}\equiv b^{k} \pmod{n}</math>. Confrontando le due espressioni, ed utilizzando le proprietà simmetrica e transitiva, si deduce che <math>a^{k}\equiv b^{k} \pmod{n}</math>. Poiché la proposizione è vera per ''k = 1'' e il fatto che sia vera per ''k-1'' implica che essa è vera per ''k'', per il principio di induzione la proposizione è vera per ogni ''k''.
:: '''Nota''': Questa proprietà si può invertire solo se ''k'' è diverso da 0.
== Teorema fondamentale dell'aritmetica ==
| |||