Qualcuno, durante il PreIMO, nella mattina di Teoria dei numeri, un simpatico alunno, dimostrando il numero 6, mise tra parentesi un lemmino "ovvio" (per lui forse...) che dopo annosi controlli mi resi conto che era vero. Il lemmino era questo:
"ovviamente $ 2 $ è un generatore modulo $ 5^k $ con $ k $ qualsiasi intero positivo."
Vi esorto a dimostrarlo perchè è simpatico e può risultare utile....
Simpatici lemmini ovvi...
-
Simo_the_wolf
- Moderatore
- Messaggi: 1053
- Iscritto il: 01 gen 1970, 01:00
- Località: Pescara
Proviamo per induzione
Poiché 2 è un generatore modulo 5 (si fa per verifica diretta) non esiste nessun divisore di 4 ( che è $ \varphi(5) $) tale che 2 elevato a quel numero sia $ \equiv 1 \pmod{5} $ Quindi condizione necessaria (ma non sufficiente) perché una potenza di 2 sia $ \equiv 1 \pmod{5^k} $ è che l'esponente sia multiplo di 4
Quello che voglio dimostrare per induzione (per k maggiori o uguali a 2) è che $ 2^{4\cdot 5^{k-2}}-1 $ non è mai multiplo di $ 5^k $
Il passo base è che $ 2^4-1 $ non è multiplo di 25
Supponiamo sia valido per k e dimostriamolo per k+1
Innanzitutto $ 2^{4\cdot 5^{k-2}}-1 $ è multiplo di $ 5^{k-1} $, poichè $ 4\cdot 5^{k-2}=\varphi(5^{k-1}) $, e non è multiplo di $ 5^k $ per ipotesi induttiva. Quindi $ 2^{4\cdot 5^{k-2}}-1=5^{k-1}\alpha $ dove $ \alpha $ non è multiplo di 5
Per passare da $ 2^{4\cdot 5^{k-2}}-1 $ a $ 2^{4\cdot 5^{k-1}}-1 $ devo aggiungere 1, elevare alla 5 e togliere 1. Applicheremo il tutto non a $ 2^{4\cdot 5^{k-2}}-1 $ ma a $ 5^{k-1}\alpha $ che abbiamo visto essere uguale
$ {(5^{k-1}\alpha+1)}^5-1= $
$ {(5^{k-1}\alpha)}^5 + 5{(5^{k-1}\alpha)}^4 +10{(5^{k-1}\alpha)}^3 + $
$ + 10{(5^{k-1}\alpha)}^2 + 5(5^{k-1}\alpha)+1-1 $
Ora levo tutto il folklore (dove per folklore intendo cose non divisibili per 5 di ogni addendo) facendolo confluire nei singoli $ \alpha $, che non saranno quindi più lo stesso $ \alpha $, ma non saranno comunque multipli di 5, e considererò solo più le potenze di 5 che dividono i vari termini della somma
$ 5^{5k-5}\alpha + 5^{4k-3}\alpha +5^{3k-2}\alpha + 5^{2k-1}\alpha + 5^k\alpha $
Questa roba è ovviamente multipla di $ 5^k $ (trattandosi di $ 2^{4\cdot 5^{k-1}}-1 $ scritta in forma diversa per evidenziare le potenze di 5, e visto che $ 4\cdot 5^{k-1}=\varphi(5^k) $), ma non è multipla di $ 5^{k+1} $ poiché raccogliendo $ 5^k $ si ottiene una roba $ \equiv\alpha\pmod{5} $, quindi senza fattori 5 nella scomposizione. Quindi anche il passo induttivo è dimostrato
Poiché 2 è un generatore modulo 5 (si fa per verifica diretta) non esiste nessun divisore di 4 ( che è $ \varphi(5) $) tale che 2 elevato a quel numero sia $ \equiv 1 \pmod{5} $ Quindi condizione necessaria (ma non sufficiente) perché una potenza di 2 sia $ \equiv 1 \pmod{5^k} $ è che l'esponente sia multiplo di 4
Quello che voglio dimostrare per induzione (per k maggiori o uguali a 2) è che $ 2^{4\cdot 5^{k-2}}-1 $ non è mai multiplo di $ 5^k $
Il passo base è che $ 2^4-1 $ non è multiplo di 25
Supponiamo sia valido per k e dimostriamolo per k+1
Innanzitutto $ 2^{4\cdot 5^{k-2}}-1 $ è multiplo di $ 5^{k-1} $, poichè $ 4\cdot 5^{k-2}=\varphi(5^{k-1}) $, e non è multiplo di $ 5^k $ per ipotesi induttiva. Quindi $ 2^{4\cdot 5^{k-2}}-1=5^{k-1}\alpha $ dove $ \alpha $ non è multiplo di 5
Per passare da $ 2^{4\cdot 5^{k-2}}-1 $ a $ 2^{4\cdot 5^{k-1}}-1 $ devo aggiungere 1, elevare alla 5 e togliere 1. Applicheremo il tutto non a $ 2^{4\cdot 5^{k-2}}-1 $ ma a $ 5^{k-1}\alpha $ che abbiamo visto essere uguale
$ {(5^{k-1}\alpha+1)}^5-1= $
$ {(5^{k-1}\alpha)}^5 + 5{(5^{k-1}\alpha)}^4 +10{(5^{k-1}\alpha)}^3 + $
$ + 10{(5^{k-1}\alpha)}^2 + 5(5^{k-1}\alpha)+1-1 $
Ora levo tutto il folklore (dove per folklore intendo cose non divisibili per 5 di ogni addendo) facendolo confluire nei singoli $ \alpha $, che non saranno quindi più lo stesso $ \alpha $, ma non saranno comunque multipli di 5, e considererò solo più le potenze di 5 che dividono i vari termini della somma
$ 5^{5k-5}\alpha + 5^{4k-3}\alpha +5^{3k-2}\alpha + 5^{2k-1}\alpha + 5^k\alpha $
Questa roba è ovviamente multipla di $ 5^k $ (trattandosi di $ 2^{4\cdot 5^{k-1}}-1 $ scritta in forma diversa per evidenziare le potenze di 5, e visto che $ 4\cdot 5^{k-1}=\varphi(5^k) $), ma non è multipla di $ 5^{k+1} $ poiché raccogliendo $ 5^k $ si ottiene una roba $ \equiv\alpha\pmod{5} $, quindi senza fattori 5 nella scomposizione. Quindi anche il passo induttivo è dimostrato
Presidente della commissione EATO per le IGO