Determinare il resto
Determinare il resto della divisione di 8049483^1327 per 15.
Per la risoluzione avevo pensato al teorema di Eulero però 8049483 e e 15 non sono coprimi, difatti 3 è un divisore comune e non posso usare il piccolo teorema di fermat poichè 15 non è primo. Ho provato a fare la riduzione di 8049483 modulo 15 ma mi resta 3^1327 e non so come andare avanti, avete qualche consiglio da darmi?
Per la risoluzione avevo pensato al teorema di Eulero però 8049483 e e 15 non sono coprimi, difatti 3 è un divisore comune e non posso usare il piccolo teorema di fermat poichè 15 non è primo. Ho provato a fare la riduzione di 8049483 modulo 15 ma mi resta 3^1327 e non so come andare avanti, avete qualche consiglio da darmi?
Risposte
Ciao 
Devi studiare come variano le potenze di $3$ modulo $15$:
$3 \equiv 3 \mod 15$
$3^2 \equiv 9 \mod 15$
$3^3 \equiv 27 \equiv 12 \mod 15$
$3^4 \equiv 3^3 \cdot 3 \equiv 36 \equiv 6 \mod 15$
$3^5 \equiv 18 \equiv 3 \mod 15$
Come vedi le potenze di $3$ si ripetono ogni $4$, quindi non ti resta che calcolare $1327 \mod 4$ che fa $3$ dunque: $3^{1327} \equiv 3^3 \equiv 12 \mod 15$.
In generale quando devi calcolare il resto di $a^k$ per $n$ si calcola $a \mod n$ e poi se ne studiano le potenze $\mod n$. Prova con $2^12345 \mod 12 $.
Devi studiare come variano le potenze di $3$ modulo $15$:
$3 \equiv 3 \mod 15$
$3^2 \equiv 9 \mod 15$
$3^3 \equiv 27 \equiv 12 \mod 15$
$3^4 \equiv 3^3 \cdot 3 \equiv 36 \equiv 6 \mod 15$
$3^5 \equiv 18 \equiv 3 \mod 15$
Come vedi le potenze di $3$ si ripetono ogni $4$, quindi non ti resta che calcolare $1327 \mod 4$ che fa $3$ dunque: $3^{1327} \equiv 3^3 \equiv 12 \mod 15$.
In generale quando devi calcolare il resto di $a^k$ per $n$ si calcola $a \mod n$ e poi se ne studiano le potenze $\mod n$. Prova con $2^12345 \mod 12 $.
il resto sarà 0 perchè studiando tutte le potenze 2^k è congruo a 0 mod 4 per ogni k appartenente ai naturali e k diverso da zero
"Aprofo":
il resto sarà 0 perchè studiando tutte le potenze 2^k è congruo a 0 mod 4 per ogni k appartenente ai naturali e k diverso da zero
scusami, non modulo 4 ma modulo 12! Che figura
Edit: comunque sì $2^k \equiv 0 \mod 4$ ma solo per $k >= 2$.
2 $-=$ 2 mod 12
$2^2$ $-=$ 4 mod 12
$2^3$ $-=$ 8 mod 12
$2^4$ $-=$ 4 mod 12
$2^5$ $-=$ 8 mod 12
quindi 2^k è congruo a 4 se k è pari, invece è congruo a 8 se k è dispari, quindi $2^12345$ è congruo a 8 mod 12
$2^2$ $-=$ 4 mod 12
$2^3$ $-=$ 8 mod 12
$2^4$ $-=$ 4 mod 12
$2^5$ $-=$ 8 mod 12
quindi 2^k è congruo a 4 se k è pari, invece è congruo a 8 se k è dispari, quindi $2^12345$ è congruo a 8 mod 12
:
Grazie mille
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo