Eulero - Fermat
Salve a tutti, sto avendo qualche difficoltà nel determinare il resto delle divisioni utilizzando Eulero e il piccolo teorema Fermat.
Innanzitutto non ho ben capito quando utilizzare uno piuttosto che l'altro e nei vari esercizi che sto svolgendo, ce n'è uno che non riesco a svolgere ed è questo:
Determina il resto della divisione di $ 132575^2012 per 9 $
Grazie in anticipo.
PS. Il risultato su WolframAlpha è 7.
Innanzitutto non ho ben capito quando utilizzare uno piuttosto che l'altro e nei vari esercizi che sto svolgendo, ce n'è uno che non riesco a svolgere ed è questo:
Determina il resto della divisione di $ 132575^2012 per 9 $
Grazie in anticipo.
PS. Il risultato su WolframAlpha è 7.
Risposte
Ciao,
beh intanto iniziamo a semplificare $132575 \mod 9$. Nota che $10 \equiv 1 \mod 9$ dunque $10^k \equiv 1 \mod 9$ per ogni $k \in \mathbb{N}$, adesso: $132575 = 1*10^5 + 3*10^4 + 2*10^3 +5*10^2 + 7*10 + 5 \equiv 1+3+2+5+2 \equiv 4 \mod 9$, $4$ e $9$ sono coprimi, quindi possiamo applicare il teorema di eulero che ci dice che $4^{\phi(9)} \equiv 1 \mod 9$, $\phu(9) = 6$ e $2012 = 335*6 + 2$, allora: $132575^(2012) \equiv 4^(335*6 + 2) \equiv (4^(6))^(2012) * 4^2 \equiv 1^(2012)*16 \equiv 16 \equiv 7 \mod 9$.
beh intanto iniziamo a semplificare $132575 \mod 9$. Nota che $10 \equiv 1 \mod 9$ dunque $10^k \equiv 1 \mod 9$ per ogni $k \in \mathbb{N}$, adesso: $132575 = 1*10^5 + 3*10^4 + 2*10^3 +5*10^2 + 7*10 + 5 \equiv 1+3+2+5+2 \equiv 4 \mod 9$, $4$ e $9$ sono coprimi, quindi possiamo applicare il teorema di eulero che ci dice che $4^{\phi(9)} \equiv 1 \mod 9$, $\phu(9) = 6$ e $2012 = 335*6 + 2$, allora: $132575^(2012) \equiv 4^(335*6 + 2) \equiv (4^(6))^(2012) * 4^2 \equiv 1^(2012)*16 \equiv 16 \equiv 7 \mod 9$.
"Shocker":
Ciao,
beh intanto iniziamo a semplificare $132575 \mod 9$. Nota che $10 \equiv 1 \mod 9$ dunque $10^k \equiv 1 \mod 9$ per ogni $k \in \mathbb{N}$, adesso: $132575 = 1*10^5 + 3*10^4 + 2*10^3 +5*10^2 + 7*10 + 5 \equiv 1+3+2+5+2 \equiv 4 \mod 9$, $4$ e $9$ sono coprimi, quindi possiamo applicare il teorema di eulero che ci dice che $4^{\phi(9)} \equiv 1 \mod 9$, $\phu(9) = 6$ e $2012 = 335*6 + 2$, allora: $132575^(2012) \equiv 4^(335*6 + 2) \equiv (4^(6))^(2012) * 4^2 \equiv 1^(2012)*16 \equiv 16 \equiv 7 \mod 9$.
Ci siamo, ho capito il procedimento e ti ringrazio. L'unica cosa è che non ho capito perchè andiamo a semplificare il numero?
"fab97":
Ci siamo, ho capito il procedimento e ti ringrazio. L'unica cosa è che non ho capito perchè andiamo a semplificare il numero?
Di solito è più vantaggioso fare i calcoli con i rappresentanti canonici delle classi di resto modulo $n$, cioè, detto brutalmente, con i numeri compresi fra $0$ e $n-1$.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo