mercoledì 21 aprile 2010

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

“Il teorema di Fermat può essere usato per risolvere calcoli di questo tipo: 31416 mod 11”.

“In che modo?”.

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

“Credo di capire: posso scrivere 31416 come 31400 moltiplicato per 3116. Ora so che 31400 ≡ 1, quindi mi rimane da calcolare 3116”.

“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 312 ti basta calcolare 92”.

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

“Bene, e siamo a 312. Ora puoi passare direttamente a 314”.

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

“Vai avanti”.

“Elevando ancora al quadrato trovo 318, 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:”.

ap-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 ai, 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·a1, a·a2, …, a·ak.

“Fin qua ci sono”.

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

“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 ai tale per cui il prodotto a·ai 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·ai = ph + n, e in questo caso potrei raccogliere da p e da n il fattore comune, che dovrebbe essere un fattore anche di a·ai. Questo vorrebbe dire che p e a·ai hanno un fattore comune”.

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

“Inoltre, è anche impossibile che due diversi prodotti, diciamo che siano a·ai e a·aj (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(ai-aj)”.

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

“Impossibile, per ipotesi”.

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

“Impossibile anche questo, gli ai 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 ai 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·a1)(a·a2)·…·(a·ak).

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

aka1a2ak.

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

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

aka1a2aka1a2ak 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 a1a2ak(ak-1) è multiplo di p. Dato che tutti gli ai sono primi con p, possiamo concludere che è l'espressione ak-1 ad essere multipla di p. E cioè, concludendo:”.

ak ≡ 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”.

·

Nessun commento: