Dimostrazioni del piccolo teorema di Fermat

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

(mod )

per ogni numero primo ed ogni intero .

SemplificazioneModifica

È 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 interoModifica

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 EuleroModifica

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 gruppiModifica

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 induzioneModifica

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

 

NoteModifica

  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