Alice, Bob e Eva — Un teorema un po' più grande

“Il teorema di Fermat può essere usato per risolvere calcoli di questo tipo: 31⁴¹⁶ mod 11”.

“In che modo?”.

“Dato che 11 è un numero primo, e che 31 non è multiplo di 11, il teorema afferma che 31¹⁰ ≡ 1 mod 11”.

“Credo di capire: posso scrivere 31⁴¹⁶ come 31⁴⁰⁰ moltiplicato per 31¹⁶. Ora so che 31⁴⁰⁰ ≡ 1, quindi mi rimane da calcolare 31¹⁶”.

“Che è un numero più gestibile”.

“Bé, mica tanto”.

“Sì, non è facile da calcolare direttamente senza calcolatrice, ma puoi arrangiarti un po'”.

“In che modo?”.

“Comincia con il calcolo di 31 mod 11”.

“Questo è facile, viene 9”.

“Ok, ora sai che per calcolare 31² ti basta calcolare 9²”.

“Ah, giusto. Il risultato è 81, congruente a 4 modulo 11”.

“Bene, e siamo a 31². Ora puoi passare direttamente a 31⁴”.

“Calcolando 4², ottimo! Viene 16, congruente a 5”.

“Vai avanti”.

“Elevando ancora al quadrato trovo 31⁸, congruente a 25, cioè 3. Elevando ancora una volta trovo il risultato: 9”.

“Senza calcolatrice”.

“Bello, non credevo si potessero fare calcoli di questo tipo. Peccato si possano fare solo se p è primo, però. Non c'è modo di generalizzare?”.

“In effetti il modo c'è. Ricordi la dimostrazione del teorema di Fermat?”.

“Sì, bisognava moltiplicare a per tutti i numeri da 1 a p-1, poi c'era quella semplificazione a cui bisognava fare attenzione”.

“Esatto, il problema è proprio lì. Il teorema funziona perché si arriva a scrivere la formula seguente:”.

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

“Mi ricordo, sì”.

“E poi si fanno delle considerazioni che ci permettono di semplificare la quantità (p-1)!”.

“E non possiamo farle anche se p non è primo?”.

“No, se p non è primo allora è composto da fattori più piccoli di p, che potrebbero essere fattori della prima parte dell'espressione, o della seconda. Insomma, non lo sappiamo. Dobbiamo cambiare un po' le carte in tavola”.

“Come?”.

“Per prima cosa non possiamo più moltiplicare a per tutti i numeri da 1 a p-1, perché qualcuno di questi fattori potrebbe essere un fattore di p. Dobbiamo selezionare i moltiplicatori, prendendo solo i numeri minori o uguali a p e primi rispetto a p”.

“Ah, bene, in questo modo siamo sicuri che non ci siano fattori comuni. Però così mi perdo un po', possiamo fare come l'altra volta? Io faccio degli esempi numerici, e tu generalizzi?”.

“Va bene, prendi per esempio a = 2 e p = 15”.

“Ok. Allora, non devo moltiplicare a per tutti i numeri da 1 a 14, ma solo per i numeri che sono primi rispetto a 15. Dovrebbero essere questi:”.

1, 2, 4, 7, 8, 11, 13, 14.

“Giusto, sono loro. Li chiamiamo a_i, con i che varia da 1 fino a k. Con k ho indicato il numero di fattori primi rispetto a p, che nel tuo esempio sono 8”.

“Va bene. Faccio la moltiplicazione per a, allora. Dovrei ottenere questi altri numeri:”.

2, 4, 8, 14, 16, 22, 26, 28.

“Perfetto. Io li indicherò in questo modo:”.

a·a₁, a·a₂, …, a·a_k.

“Fin qua ci sono”.

“Andiamo avanti: ognuno di questi numeri sarà congruente, modulo p, a uno dei valori a_i”.

“Proprio a uno di quelli? Non può accadere che risulti uno dei valori non primi con p?”.

“Ottima domanda: non può accadere, e adesso lo dimostriamo. Supponi che esista un certo elemento a_i tale per cui il prodotto a·a_i sia congruente a un numero n che non è primo con p”.

“Sì, ti seguo, stai facendo una dimostrazione per assurdo”.

“Esatto. Se fosse così, vorrebbe dire che a·a_i = ph + n, e in questo caso potrei raccogliere da p e da n il fattore comune, che dovrebbe essere un fattore anche di a·a_i. Questo vorrebbe dire che p e a·a_i hanno un fattore comune”.

“E questo è impossibile, ho capito: avevamo scelto a e tutti gli a_i in modo tale che non avessero fattori comuni con p”.

“Inoltre, è anche impossibile che due diversi prodotti, diciamo che siano a·a_i e a·a_j (con i diverso da j) siano congruenti”.

“Anche questo si dimostra per assurdo?”.

“Sì. Se fossero congruenti, la loro differenza dovrebbe essere un multiplo di p”.

“Differenza che possiamo scrivere così, se non sbaglio: a(a_i-a_j)”.

“Sì. Se quella espressione fosse multiplo di p, vorrebbe dire o che a è multiplo di p…”.

“Impossibile, per ipotesi”.

“…o che (a_i-a_j) è multiplo di p. In altri termini, a_i dovrebbe essere congruente a a_j”.

“Impossibile anche questo, gli a_i sono tutti diversi”.

“Esatto”.

“Aspetta che faccio una prova: calcolo la congruenza modulo 15 di tutti i numeri che ho elencato prima. Mantenendo l'ordine, ottengo:”.

2, 4, 8, 14, 1, 7, 11, 13.

“Come vedi, sono tutti i tuoi a_i riordinati”.

“Ok, ci sono. Come andiamo avanti?”.

“Procediamo come nella dimostrazione del teorema di Fermat: moltiplichiamo tra loro tutti quei fattori”.

“Bene, proviamo. Dovrebbe risultare così:”.

(a·a₁)(a·a₂)·…·(a·a_k).

“Che puoi scrivere, in forma un po' più abbreviata, così:”.

a^ka₁a₂…a_k.

“E questa espressione, grazie alla dimostrazione che hai appena fatto, è congruente al prodotto di tutti gli a_i”.

“Proprio così. L'espressione finale è questa:”.

a^ka₁a₂…a_k ≡ a₁a₂…a_k mod p.

“Ora, se si potesse semplificare a destra e a sinistra…”.

“Ma si può, grazie alle ipotesi che abbiamo fatto, proprio come avevamo fatto nella dimostrazione del teorema di Fermat. Quella congruenza significa che a₁a₂…a_k(a^k-1) è multiplo di p. Dato che tutti gli a_i sono primi con p, possiamo concludere che è l'espressione a^k-1 ad essere multipla di p. E cioè, concludendo:”.

a^k ≡ 1 mod p.

“Ecco la congruenza uguale a 1 che tanto mi piace. Ha un nome, questo teorema?”.

“Sì: si chiama teorema di Eulero, anche se non è un nome molto felice”.

“Perché?”.

“Perché Eulero ne ha fatti a montagne, di teoremi. Qualcuno lo chiama anche teorema di Eulero-Fermat, giusto per connotarlo un po' di più, dato che è una generalizzazione del teorema di Fermat. Te lo enuncio per bene:”.

Dato p intero maggiore di 1, esiste un intero positivo φ(p) tale che, per ogni a primo con p, accade che

a^φ(p) ≡ 1 mod p.

“Addirittura una lettera greca?”.

“Sì. Se ricordi, nella dimostrazione abbiamo indicato con k il numero di interi positivi minori di p e primi rispetto a p. Questo numero è naturalmente funzione di p”.

“Certo, al variare di p cambia il numero di numeri minori di p e primi rispetto ad esso”.

“Bene: questo numero viene indicato con il simbolo φ(p), e la funzione φ viene detta funzione toziente”.

“Che razza di nome”.

“Già. Ho fatto un po' di ricerche: Eulero non ha mai usato quel termine. È stato inventato da J.J. Sylvester, un matematico inglese al quale piaceva inventare parole nuove”.

⇐ · ⇒