Dubbio esercizio con teorema di Eulero.
salve,
ho il seguente esercizio svolto:
Calcolare le ultime due cifre di $237^250$.
Si tratta di lavorare modulo 100. $237 -= 37 (mod 100)$ e $MCD(37,100) = 1$. La funzione di Eulero di 100 vale 40.
In virtù del teorema di Eulero $37^40 -= 1 (mod 100)$.
Allora $37^242 = 37^(40*6+2) = (37^40)^6 * 37^2 -= 1 * 37^2 = 1369 -= 69 (mod 100)$.
vi pongo questa semplice e banale domanda:
$37^242$ da dove si ottiene?
spero possiate cortesemente aiutarmi,
mille grazie davvero.
ho il seguente esercizio svolto:
Calcolare le ultime due cifre di $237^250$.
Si tratta di lavorare modulo 100. $237 -= 37 (mod 100)$ e $MCD(37,100) = 1$. La funzione di Eulero di 100 vale 40.
In virtù del teorema di Eulero $37^40 -= 1 (mod 100)$.
Allora $37^242 = 37^(40*6+2) = (37^40)^6 * 37^2 -= 1 * 37^2 = 1369 -= 69 (mod 100)$.
vi pongo questa semplice e banale domanda:
$37^242$ da dove si ottiene?
spero possiate cortesemente aiutarmi,
mille grazie davvero.
Risposte
Effettivamente nemmeno io riesco a capire, sembra sbagliato.
Mi torna tutto il ragionamento, compreso il calcolo del periodo, ma poi riparte dall'esponente 242 invece di 250
Mi torna tutto il ragionamento, compreso il calcolo del periodo, ma poi riparte dall'esponente 242 invece di 250
infatti è proprio quell'esponente 242 che non so da dove esce!!
cmq posto qui il mio ragionamento che produce un risultato diverso da quello scritto nell'esercizio
così vediamo se nel caso si tratta di un errore dell'esercizio!
ultime due cifre di $237^250$
$237 -= 37 (mod 100)$
pongo $a = 37$, $n = 100$
secondo il teorema di eulero:
$a^(\phi(n)) -= 1 (mod n)$ e $(a,n) = 1$
$MCD(37, 100) = 1$ perciò eulero può essere applicato.
$37^(\phi(100)) -= 1 (mod 100)$
fattorizziamo $100$:
$100 = 2^2 * 5^2$.
secondo la definizione della funzione di eulero
$\phi(100) = \phi(2^2) * \phi(5^2) =$
$= (2^2 - 2) * (5^2 - 5) =$
$= (4-2)*(25-5) =$
$= 2*20 = 40$
applicandolo al teorema:
$37^40 -= 1 (mod 100)$
$37^250 = 37^210 * 37^40 = 37^10 * (37^40)^5 =$
$ 1*37^10 = 4808584372417849 -= 49 (mod 100)$
dal momento che il problema ora, se ho capito bene, è trovare le ultime due cifre di $37^10$
quindi potrebbe anche risolversi di nuovo con il teorema di eulero applicato per $37^10$ o sbaglio? se sì in che modo si fa?
e cmq il risultato ($37^10$ trovato con la calcolatrice, quindi poco pratico, perciò non è questa la strada migliore...) dovrebbe essere 49?
ancora grazie.
cmq posto qui il mio ragionamento che produce un risultato diverso da quello scritto nell'esercizio
così vediamo se nel caso si tratta di un errore dell'esercizio!
ultime due cifre di $237^250$
$237 -= 37 (mod 100)$
pongo $a = 37$, $n = 100$
secondo il teorema di eulero:
$a^(\phi(n)) -= 1 (mod n)$ e $(a,n) = 1$
$MCD(37, 100) = 1$ perciò eulero può essere applicato.
$37^(\phi(100)) -= 1 (mod 100)$
fattorizziamo $100$:
$100 = 2^2 * 5^2$.
secondo la definizione della funzione di eulero
$\phi(100) = \phi(2^2) * \phi(5^2) =$
$= (2^2 - 2) * (5^2 - 5) =$
$= (4-2)*(25-5) =$
$= 2*20 = 40$
applicandolo al teorema:
$37^40 -= 1 (mod 100)$
$37^250 = 37^210 * 37^40 = 37^10 * (37^40)^5 =$
$ 1*37^10 = 4808584372417849 -= 49 (mod 100)$
dal momento che il problema ora, se ho capito bene, è trovare le ultime due cifre di $37^10$
quindi potrebbe anche risolversi di nuovo con il teorema di eulero applicato per $37^10$ o sbaglio? se sì in che modo si fa?
e cmq il risultato ($37^10$ trovato con la calcolatrice, quindi poco pratico, perciò non è questa la strada migliore...) dovrebbe essere 49?
ancora grazie.
mi sa che ho sbagliato i passaggi, dovrebbe essere:
$37^10 * (37^40)^5 * 37^40 = 37^10$
se non ho sbagliato ancora.
e cmq il problema sussiste...
$37^10 * (37^40)^5 * 37^40 = 37^10$
se non ho sbagliato ancora.
e cmq il problema sussiste...
mi sono stati suggeriti da un erudito tali passaggi:
$37^10 -= (13^2)^5 -= -31^5 -= -(40 - 3^2)^5 -= 3^10 -= (3^5)^2 (mod 100)$
senza però ricevere alcuna spiegazione in merito ai passaggi e a come si ottengono perchè ritenuti troppo banali.
potreste aiutarmi voi? che passaggi sono questi sopra?
io comunque sono andato avanti in questo modo (più lungo purtroppo e penso giusti):
mi trovo le potenze dell'esponente:
$37^1 mod 100$
$37^2 mod 100$
$37^(2^2) mod 100$
$37^(2^3) mod 100$
mi fermo a $(2)^3$ altrimenti > $10$
scrivo 10 in base 2 = $(1010)_2$
scrivo $37^10$ come prodotto delle sole potenze $37^(2^h)$ corrispondenti ai valori 1 della scrittura in base 2 di $10$.
$37^10 = 37^(2^3) * 37^2$
perciò ottengo:
$37^10 -= 37^(2^3) * 37^2 (mod 100)$
via via procedo alla semplificazione manuale e dispendiosa
quindi a questo punto non so se c'è un metodo più veloce...
$37^10 = 37^(2^3) * 37^2 =$
$= 37^8 * 37^2 =$
$= 37^2 * 37^2 * 37^2 * 37^2 * 37^2 =$
$= 1369 * 1369 * 1369 * 1369 * 1369 = $
$= \bar{69} * \bar{69} * \bar{69} * \bar{69} * \bar{69} =$
$= \bar{61} * \bar{61} * \bar{69}=$
$= \bar{21} * \bar{69} = \bar{49}$
ed il risultato dovrebbe essere quello sperato.
mille grazie nuovamente.
$37^10 -= (13^2)^5 -= -31^5 -= -(40 - 3^2)^5 -= 3^10 -= (3^5)^2 (mod 100)$
senza però ricevere alcuna spiegazione in merito ai passaggi e a come si ottengono perchè ritenuti troppo banali.
potreste aiutarmi voi? che passaggi sono questi sopra?
io comunque sono andato avanti in questo modo (più lungo purtroppo e penso giusti):
mi trovo le potenze dell'esponente:
$37^1 mod 100$
$37^2 mod 100$
$37^(2^2) mod 100$
$37^(2^3) mod 100$
mi fermo a $(2)^3$ altrimenti > $10$
scrivo 10 in base 2 = $(1010)_2$
scrivo $37^10$ come prodotto delle sole potenze $37^(2^h)$ corrispondenti ai valori 1 della scrittura in base 2 di $10$.
$37^10 = 37^(2^3) * 37^2$
perciò ottengo:
$37^10 -= 37^(2^3) * 37^2 (mod 100)$
via via procedo alla semplificazione manuale e dispendiosa
quindi a questo punto non so se c'è un metodo più veloce...
$37^10 = 37^(2^3) * 37^2 =$
$= 37^8 * 37^2 =$
$= 37^2 * 37^2 * 37^2 * 37^2 * 37^2 =$
$= 1369 * 1369 * 1369 * 1369 * 1369 = $
$= \bar{69} * \bar{69} * \bar{69} * \bar{69} * \bar{69} =$
$= \bar{61} * \bar{61} * \bar{69}=$
$= \bar{21} * \bar{69} = \bar{49}$
ed il risultato dovrebbe essere quello sperato.
mille grazie nuovamente.
Ritorno sul problema. Da una rapida verifica numerica, la lunghezza del periodo di $37^x (mod 100)$ (che è uguale a $237^x (mod 100)$) è $p=20$. Ora:
$237^250(mod 100)=37^250(mod 100)=37^10(mod 100)=49$
$237^242(mod 100)=37^242(mod 100)=37^2(mod 100)=69$
Quindi uno dei due esponenti è errato.
$237^250(mod 100)=37^250(mod 100)=37^10(mod 100)=49$
$237^242(mod 100)=37^242(mod 100)=37^2(mod 100)=69$
Quindi uno dei due esponenti è errato.
si. [tex]237^{242}[/tex] è definitivamente errato!
e comunque un procedimento alternativo per sviluppare [tex]37^{10}[/tex] è il seguente:
considero [tex]37^{10} = (50-13)^{2} = (2 \cdot 5^2 - 13)^2[/tex] e sviluppo in questo modo
[tex]\sum_{i=0}^2 \binom{2}{i} (2 \cdot 5^2)^{2-i} \cdot 13^i[/tex]
tenendo conto della [tex]\binom{n}{k} = \frac{n!}{k! - (n-k)!}[/tex] quindi mi son calcolato via via i coefficienti binomiali,
sostituito dove c'è la i e sviluppato la sommatoria perciò, quindi anche qui un po' di tempo se ne và:
[tex]37^{10} \equiv (-31)^5 (mod 100)[/tex]
[tex]37^{10} \equiv -(40-3^2)^5 (mod 100)[/tex]
e lo stesso ho fatto per [tex](40-3^2)^5[/tex]:
[tex]\sum_{i=0}^5 \binom{5}{i} 40^{5-i} \cdot 3^{2i}[/tex]
ottengo: [tex]40^5 + 3^{10} = (4 \cdot 10)^5 + 3^{10} = 3^{10}[/tex]
quindi sostituisco nella precedente [tex]-(3^{10}) = -3^{10} = 3^{10}[/tex]
perciò [tex]37^{10} \equiv 3^{10} (mod 100)[/tex]
spero sia corretto come procedimento
e comunque, se si fanno i calcoli, esce [tex]\equiv 49 (mod 100)[/tex].
e comunque un procedimento alternativo per sviluppare [tex]37^{10}[/tex] è il seguente:
considero [tex]37^{10} = (50-13)^{2} = (2 \cdot 5^2 - 13)^2[/tex] e sviluppo in questo modo
[tex]\sum_{i=0}^2 \binom{2}{i} (2 \cdot 5^2)^{2-i} \cdot 13^i[/tex]
tenendo conto della [tex]\binom{n}{k} = \frac{n!}{k! - (n-k)!}[/tex] quindi mi son calcolato via via i coefficienti binomiali,
sostituito dove c'è la i e sviluppato la sommatoria perciò, quindi anche qui un po' di tempo se ne và:
[tex]37^{10} \equiv (-31)^5 (mod 100)[/tex]
[tex]37^{10} \equiv -(40-3^2)^5 (mod 100)[/tex]
e lo stesso ho fatto per [tex](40-3^2)^5[/tex]:
[tex]\sum_{i=0}^5 \binom{5}{i} 40^{5-i} \cdot 3^{2i}[/tex]
ottengo: [tex]40^5 + 3^{10} = (4 \cdot 10)^5 + 3^{10} = 3^{10}[/tex]
quindi sostituisco nella precedente [tex]-(3^{10}) = -3^{10} = 3^{10}[/tex]
perciò [tex]37^{10} \equiv 3^{10} (mod 100)[/tex]
spero sia corretto come procedimento
e comunque, se si fanno i calcoli, esce [tex]\equiv 49 (mod 100)[/tex].
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo