Dimostrazioni del piccolo teorema di Fermat

Da Wikipedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca

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

(mod )

per ogni numero primo ed ogni intero .

Semplificazione

[modifica | modifica wikitesto]

È da notare che basta provare

per ogni intero primo con . Moltiplicando ambo i membri dell'ultima espressione per si ottiene la versione esposta a inizio pagina del teorema. Se non fosse primo con allora ed il teorema risulterebbe vero in ogni caso.

Dimostrazione sfruttando i multipli del numero intero

[modifica | modifica wikitesto]

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

si avrebbe

Ma questo è impossibile, perché allora dovrebbe dividere uno dei due fattori. Ma è primo con , e , essendo ed numeri naturali compresi tra e , è . Per cui i multipli considerati hanno un resto nella divisione per differente per ciascuno di essi, e differente da . Siccome consideriamo multipli, tali multipli devono essere necessariamente congrui (modulo ) ai numeri in un certo ordine. Ne segue, per il prodotto di tutti questi multipli:

da cui, ponendo , si ha

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

Ma non è divisibile per , perché non lo è nessuno dei suoi fattori; quindi deve essere

Dimostrazione sfruttando il Teorema di Eulero

[modifica | modifica wikitesto]

Questo teorema può essere visto come un corollario del Teorema di Eulero. Osserviamo che per ogni primo (dove indica la Funzione φ di Eulero). Per il Teorema di Eulero abbiamo che (mod ) per ogni . Si ha quindi la tesi.

Dimostrazione come corollario del teorema di Lagrange sui gruppi

[modifica | modifica wikitesto]
Lo stesso argomento in dettaglio: Teorema di Lagrange (teoria dei gruppi).

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

Dimostrazione per induzione

[modifica | modifica wikitesto]

Dimostriamo il teorema con per induzione su : per allora . Sia vera la tesi per , cioè (mod ). Vogliamo mostrare che essa è vera per . Per il teorema binomiale, abbiamo che

I coefficienti binomiali sono tutti numeri interi e quindi, dato che possono essere riscritti come per , si ha che è divisibile per (); in particolare (dal momento che è un numero primo e quindi non divide ) pure il fattore binomiale residuo , anch'esso intero, è multiplo di (); pertanto è pure un numero intero; ne segue che i coefficienti binomiali sono (per ) divisibili per (essendo, come appena dimostrato, un numero intero) ossia:

Otteniamo quindi che

dove la prima equivalenza () si ottiene eliminando dai addendi della sommatoria tutti quelli (dal secondo al penultimo) per cui (essendo tutti, come abbiamo dimostrato, divisibili per ) e la seconda (ultima) equivalenza è data dall'ipotesi di induzione. Si ha la tesi.

Se fosse negativo, allora è positivo e per quanto detto sopra

ma . Se è dispari allora e quindi otteniamo che implica la tesi (moltiplicando per entrambi i membri), altrimenti l'unico primo pari è ma in tal caso e quindi

  1. ^ Questo stesso ragionamento è applicabile all'insieme dei numeri interi positivi minori di un qualsiasi intero positivo , per dimostrare il Teorema di Eulero utilizzato nel paragrafo soprastante: quest'ultimo è infatti un'estensione del piccolo teorema di Fermat.
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica