Alice, Bob e Eva — Un piccolo teorema

“La domanda era: è sempre possibile trovare una potenza che, in modulo, risulti uguale a 1?”.

“E la risposta è?”.

“Dipende”.

“Ah, gran risposta. Da cosa dipende?”.

“Te lo spiego con un esempio. Prima vediamo un caso particolare, poi vediamo cosa dice il teorema”.

“Va bene”.

“Prendiamo due numeri: uno lo chiamiamo a, e diciamo che è uguale a 4, l'altro lo chiamiamo p e diciamo che è uguale a 7”.

“Ok, a = 4, p = 7. Poi?”.

“Poi consideriamo tutti i prodotti del tipo a·1, a·2, a·3, …, a·(p-1)”.

“Cioè prendo a e lo moltiplico per tutti i numeri da 1 a p-1. Nel nostro esempio prendo 4 e lo moltiplico per tutti i numeri da 1 a 6”.

“Fai pure i conti, scrivili”.

“Ok, eccoli qua:”.

4·1
4·2
4·3
4·4
4·5
4·6

“Prima domanda: questi 6 numeri possono avere lo stesso resto quando li dividi per p (cioè per 7)?”.

“Dovrei fare i calcoli, vediamo un po':”.

4·1 ≡ 4
4·2 ≡ 8 ≡ 1
4·3 ≡ 12 ≡ 5
4·4 ≡ 16 ≡ 2
4·5 ≡ 20 ≡ 6
4·6 ≡ 24 ≡ 3

“Bene, cosa deduci?”.

“Deduco che i numeri non hanno lo stesso resto. Vedo anche che non risulta mai 0. Ah, certo, non può risultare 0 perché 4 (cioè a) non è divisibile per 7 (cioè p), e perché tutti i fattori per cui ho moltiplicato 4 sono minori di 7”.

“Molto bene. Ora proviamo a generalizzare, e consideriamo la seguente lista di prodotti:”.

a·1
a·2
a·3
…
a·(p-1)

“Uh, ora mi pare più difficile”.

“Proseguiamo come prima. La domanda è sempre la stessa: è possibile che due qualsiasi di questi numeri diano lo stesso resto quando vengono divisi per p?”.

“Come faccio a saperlo? Qua non ho effettivamente i numeri, non posso provare”.

“Ricorda la prima regola che abbiamo visto: se due numeri sono congruenti modulo p, allora la loro differenza è un multiplo di p”.

“Giusto! Allora la tua domanda potrebbe essere trasformata in questa: la differenza tra due di questi numeri è un multiplo di p oppure no?”.

“Perfetto. Calcola la differenza tra due di quei numeri scelti a caso”.

“Diciamo che uno dei due è a·h e l'altro a·k?”.

“Sì, va benissimo”.

“La differenza risulta a(h-k)”.

“Bene. È un multiplo di p?”.

“Certamente p non può dividere (h-k)”.

“Perché?”.

“Perché sia h che k sono minori di p: anche se non so quanto vale la differenza, questa è certamente minore di p”.

“Molto bene. Per quanto riguarda a, invece?”.

“Mi pare che non si possa dire niente: p potrebbe dividere a”.

“Giusto. Siccome abbiamo bisogno del fatto che i resti di quella sequenza di numeri siano tutti diversi, dobbiamo aggiungere una ipotesi. Da ora in poi dobbiamo presumere che a sia un intero non multiplo di p”.

“Se è così, allora è vero che due qualsiasi di quei numeri non danno lo stesso resto quando vengono divisi per p”.

“Osserva che non possono nemmeno dare 0, come resto”.

“Certo, con le ipotesi che abbiamo non è possibile: p non divide a, e non divide nemmeno nessun numero da 1 fino a (p-1)”.

“Quindi, se i resti sono tutti diversi, sono p-1, e 0 è escluso, significa che otterremo tutti i possibili resti, nessuno escluso”.

“Vero. In effetti, nell'esempio numerico che hai fatto compaiono proprio tutti i resti da 1 fino a 6”.

“Ok, questo è il primo punto. Ora moltiplichiamo tra loro tutti i numeri della sequenza”.

“Così?”.

(4·1)(4·2)(4·3)(4·4)(4·5)(4·6)

“Sì. In generale avremo questa espressione:”.

(a·1)(a·2)(a·3)…(a·(p-1))

“Bene. Io continuo i conti sull'esempio, e tu generalizzi?”.

“Sì, facciamo così. Come puoi scrivere l'espressione in modo più compatto?”.

“Vedo che il 4 compare in tutte le parentesi, e quindi posso scriverlo come potenza. Poi compaiono i numeri da 1 a 6, potrei usare il fattoriale. Vediamo, va bene così?”.

4⁶·6!

“Perfetto. Te le generalizzo in questo modo:”.

a^p-1·(p-1)!

“Va bene, ci sono. Adesso?”.

“Adesso ci chiediamo a cosa è congruente quella espressione, modulo p. Non fare troppi calcoli, però: usa tutte le proprietà che abbiamo visto finora. Ricordati che puoi moltiplicare e fare potenze come ti pare”.

“Allora, vediamo. All'inizio ho calcolato tutte le congruenze, so che il primo prodotto è congruente a 4, il secondo a 1, il terzo a 5, poi ho 2, 6 e infine 3. Posso moltiplicarli tutti e ottengo il risultato. Ehi!”.

“Cosa?”.

“Non è importante l'ordine con cui prendo quei numeri. Abbiamo detto prima che otteniamo tutti i resti, nessuno escluso, a parte 0. Quindi il numero che ottengo è 6 fattoriale”.

“Proprio così. Il primo punto di questa dimostrazione è servito proprio per dire che, quando calcolo a·1, a·2, …, a·(p-1) e ne faccio le congruenze modulo p, ottengo tutti i possibili resti. Quindi il prodotto di tutti quei numeri è uguale a (p-1)!. Ti scrivo la formula completa:”.

a^p-1(p-1)! ≡ (p-1)! mod p

“Bello, adesso semplifichiamo a destra e sinistra e…”.

“Piano, piano”.

“Cosa c'è?”.

“Non abbiamo mai detto che si può semplificare così. Non era una delle proprietà che abbiamo considerato”.

“Uh, già. Allora come facciamo? Lasciamo così?”.

“No, utilizziamo le proprietà note. Ricordi che abbiamo detto che se due numeri sono congruenti modulo p, allora la loro differenza è un multiplo di p?”.

“Sì, certo. È stata la prima proprietà che abbiamo visto. Se la applichiamo a quella congruenza, risulta che”.

a^p-1(p-1)! - (p-1)! è multiplo di p.

“Molto bene. Raccogliendo il fattore comune, possiamo scrivere che:”.

(p-1)!(a^p-1-1) è multiplo di p.

“Sì, vero. Mi pare però che (p-1)! non sia multiplo di p. È impossibile, contiene solo fattori minori di p”.

“Qui bisogna fare attenzione. Se p fosse composto da più fattori, qualche suo fattore potrebbe dividere (p-1)!, e qualche altro fattore potrebbe dividere (a^p-1-1), e non potremmo dire niente. Quindi abbiamo bisogno di un'altra ipotesi: p deve essere un numero primo. Se è così, il tuo ragionamento è corretto. Cosa puoi dedurre, quindi?”.

“Che sarà a^p-1-1 ad essere multiplo di p”.

“Bene. Quindi possiamo dire che a^p-1 ≡ 1 mod p”.

“Ehi, è come se avessimo fatto la semplificazione che dicevo io!”.

“Sì, ma in questo modo abbiamo dimostrato che si può fare. Non sempre si può, qui ci siamo basati sul fatto che (p-1)! non può essere multiplo di p: se al suo posto avessimo avuto un numero multiplo di p, o se p non fosse primo, non avremmo potuto concludere niente. Ti faccio un esempio: 2·5 e 2·2 sono congruenti modulo 6, ma non puoi semplificare e concludere che 2 è congruente a 5 modulo 6”.

“Ok, ho capito. Tornando al teorema, alla fine cosa abbiamo trovato?”.

“Abbiamo risposto alla domanda iniziale: è possibile trovare una potenza che risulti uguale a 1? E la risposta è: se p è un numero primo e a è un intero non multiplo di p, allora a^p-1 ≡ 1 mod p”.

“Bello”.

“E questo si chiama piccolo teorema di Fermat”.

“Ce n'è anche uno grande?”.

“Sì, ma questa è un'altra storia”.

⇐ · ⇒