Dimostrazioni del piccolo teorema di Fermat

Questa voce è stata proposta per il trasferimento al progetto Wikiversity.

---

Se non sei d'accordo con la proposta, leggi le regole per il trasferimento e partecipa alla discussione.
Vedi la guida al trasferimento e assicurati che la voce sia elencata qui. Se la proposta è molto vecchia, contatta il Bar di Wikiversità.

Se hai inserito questo avviso:

Se hai inserito questo avviso:

• segnala la proposta di trasferimento nella sottopagina del progetto di destinazione apponendo, sotto le altre eventualmente presenti, l'avviso:

{{Segnala trasferimento|giorno mese = {{subst:CURRENTDAY}} {{subst:CURRENTMONTHNAME}}|pagina = Dimostrazioni del piccolo teorema di Fermat |progetto = v|motivazione = |stato = |pagina trasferita = |firma = ~~~~}}

compilando successivamente il campo "motivazione";

• se entro 7 giorni non vengono espresse contrarietà, sposta la voce a questo titolo e compila il parametro "stato" con ok.

Qui di seguito troverete una collezione di dimostrazioni del Piccolo teorema di Fermat:

${\displaystyle \,a^{p}\equiv a}$ (mod ${\displaystyle p}$)

per ogni numero primo ${\displaystyle p}$ ed ogni intero ${\displaystyle a}$.

È da notare che basta provare

${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$

per ogni intero ${\displaystyle a}$ primo con ${\displaystyle p}$. Moltiplicando ambo i membri dell'ultima espressione per ${\displaystyle a}$ si ottiene la versione esposta a inizio pagina del teorema. Se ${\displaystyle a}$ non fosse primo con ${\displaystyle p}$ allora ${\displaystyle a^{p}\equiv 0\equiv a{\pmod {p}}}$ ed il teorema risulterebbe vero in ogni caso.

Sfruttando la semplificazione proposta nel precedente paragrafo, si considerino i multipli di ${\displaystyle a}$ che vanno da ${\displaystyle a}$ stesso fino a ${\displaystyle (p-1)a}$. Nessuno di questi multipli può dare resto ${\displaystyle 0}$ diviso per ${\displaystyle p}$ perché né ${\displaystyle p-1}$ né ${\displaystyle a}$ sono multipli interi di ${\displaystyle p}$. Inoltre non può esistere una coppia di questi multipli che sia congrua modulo ${\displaystyle p}$, perché, se fosse per esempio

${\displaystyle ra\equiv sa{\pmod {p}}}$

si avrebbe

${\displaystyle (r-s)a\equiv 0{\pmod {p}}}$

Ma questo è impossibile, perché allora ${\displaystyle p}$ dovrebbe dividere uno dei due fattori. Ma ${\displaystyle a}$ è primo con ${\displaystyle p}$, e ${\displaystyle r-s}$, essendo ${\displaystyle r}$ ed ${\displaystyle s}$ numeri naturali compresi tra ${\displaystyle 1}$ e ${\displaystyle p}$, è ${\displaystyle (r-s)<p}$. Per cui i multipli considerati hanno un resto nella divisione per ${\displaystyle p}$ differente per ciascuno di essi, e differente da ${\displaystyle 0}$. Siccome consideriamo ${\displaystyle p-1}$ multipli, tali multipli devono essere necessariamente congrui (modulo ${\displaystyle p}$) ai numeri ${\displaystyle 1,2,3,\dots ,p-1}$ in un certo ordine. Ne segue, per il prodotto di tutti questi multipli:

${\displaystyle a(2a)(3a)...(p-1)a=1\cdot 2\cdot 3\cdot \dots \cdot (p-1)a^{p-1}\equiv 1\cdot 2\cdot 3\cdot \dots \cdot (p-1){\pmod {p}}}$

da cui, ponendo ${\displaystyle K=1\cdot 2\cdot 3\cdot \dots \cdot (p-1)}$, si ha

${\displaystyle K(a^{p-1}-1)\equiv 0{\pmod {p}}.}$

Dato che ${\displaystyle p}$ è primo, l'unico modo affinché ciò avvenga è che o K o il secondo fattore sia divisibile per ${\displaystyle p}$. (con ${\displaystyle p}$ primo le classi di modulo n costituiscono un dominio di integrità).

Ma ${\displaystyle K}$ non è divisibile per ${\displaystyle p}$, perché non lo è nessuno dei suoi fattori; quindi deve essere

${\displaystyle a^{p-1}-1\equiv 0{\pmod {p}}.}$

Questo teorema può essere visto come un corollario del Teorema di Eulero. Osserviamo che ${\displaystyle \,\phi (p)=p-1}$ per ogni ${\displaystyle p}$ primo (dove ${\displaystyle \phi }$ indica la Funzione φ di Eulero). Per il Teorema di Eulero abbiamo che ${\displaystyle \,a^{\phi (p)}\equiv 1}$ (mod ${\displaystyle p}$) per ogni ${\displaystyle a}$. Si ha quindi la tesi.

Lo stesso argomento in dettaglio: Teorema di Lagrange (teoria dei gruppi).

L'insieme dei numeri interi positivi minori di ${\displaystyle p}$ costituisce un gruppo (che chiameremo ${\displaystyle G}$) rispetto alla moltiplicazione modulo ${\displaystyle p}$, avente come elemento identità il numero ${\displaystyle 1}$. L'ordine (ossia il numero di elementi) di questo gruppo, che indichiamo come ${\displaystyle o(G)}$, è esattamente ${\displaystyle p-1}$. Se ${\displaystyle a\in G}$, si definisce ordine di ${\displaystyle a}$ il più piccolo intero positivo ${\displaystyle m}$ tale che ${\displaystyle a^{m}}$ sia l'identità. Un'immediata conseguenza del teorema di Lagrange sui gruppi afferma che ${\displaystyle o(a)}$ divide ${\displaystyle o(G)}$. Da questo segue che ${\displaystyle a^{o(G)}}$ dà necessariamente l'elemento identità del gruppo, essendo ${\displaystyle a^{o(G)}=a^{k(o(a))}}$. Nel caso specifico, quindi, risulterà ${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$.^[1]

Dimostriamo il teorema con ${\displaystyle a\geq \ 1}$ per induzione su ${\displaystyle a}$: per ${\displaystyle a=1}$ allora ${\displaystyle 1=1^{p}\equiv 1}$. Sia vera la tesi per ${\displaystyle a}$, cioè ${\displaystyle a^{p}\equiv a}$ (mod ${\displaystyle p}$). Vogliamo mostrare che essa è vera per ${\displaystyle a+1}$. Per il teorema binomiale, abbiamo che

${\displaystyle (a+1)^{p}=\sum _{i=0}^{p}{p \choose i}a^{i}.}$

I coefficienti binomiali ${\displaystyle {p \choose i}={\frac {p!}{i!(p-i)!}}}$ sono tutti numeri interi e quindi, dato che possono essere riscritti come ${\displaystyle {\frac {p}{i}}{p-1 \choose i-1}}$ per ${\displaystyle 0<i<p}$, si ha che ${\displaystyle {p}{p-1 \choose i-1}}$ è divisibile per ${\displaystyle i}$ (${\displaystyle 0<i<p}$); in particolare (dal momento che ${\displaystyle p}$ è un numero primo e quindi ${\displaystyle i}$ non divide ${\displaystyle p}$) pure il fattore binomiale residuo ${\displaystyle {p-1 \choose i-1}}$, anch'esso intero, è multiplo di ${\displaystyle i}$ (${\displaystyle 0<i<p}$); pertanto ${\displaystyle {\frac {p-1 \choose i-1}{i}}}$ è pure un numero intero; ne segue che i coefficienti binomiali ${\displaystyle {p \choose i}}$ sono (per ${\displaystyle 0<i<p}$) divisibili per ${\displaystyle p}$ (essendo, come appena dimostrato, ${\displaystyle {\frac {p \choose i}{p}}={\frac {p-1 \choose i-1}{i}}}$ un numero intero) ossia:

${\displaystyle {p \choose i}\equiv 0{\pmod {p}},\qquad 0<i<p.}$

Otteniamo quindi che

${\displaystyle (a+1)^{p}=\sum _{i=0}^{p}{p \choose i}a^{i}\equiv a^{p}+1\equiv a+1{\pmod {p}},}$

dove la prima equivalenza (${\displaystyle \equiv }$) si ottiene eliminando dai ${\displaystyle p+1}$ addendi della sommatoria tutti quelli (dal secondo al penultimo) per cui ${\displaystyle 0<i<p}$ (essendo tutti, come abbiamo dimostrato, divisibili per ${\displaystyle p}$) e la seconda (ultima) equivalenza è data dall'ipotesi di induzione. Si ha la tesi.

Se ${\displaystyle a}$ fosse negativo, allora ${\displaystyle -a}$ è positivo e per quanto detto sopra

${\displaystyle (-a)^{p}\equiv -a{\pmod {p}},}$

ma ${\displaystyle (-a)^{p}=(-1)^{p}a^{p}}$. Se ${\displaystyle p}$ è dispari allora ${\displaystyle (-1)^{p}=-1}$ e quindi otteniamo ${\displaystyle -a^{p}\equiv -a{\pmod {p}}}$ che implica la tesi (moltiplicando per ${\displaystyle -1}$ entrambi i membri), altrimenti l'unico primo pari è ${\displaystyle p=2}$ ma in tal caso ${\displaystyle -1\equiv 1{\pmod {2}}}$ e quindi

${\displaystyle (-a)^{2}=a^{2}\equiv -a\equiv a{\pmod {2}}.}$

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica