Resto divisione intera ( Piccolo Teorema di Fermat/ Eulero )

[claw91]

Ragazzi, avrei bisogno di una mano: determinare il resto della seguente divisione intera:

$ 29354^362971 // 6 $

Chiaramente da risolvere utilizzando il piccolo teorema di Fermat e il teorema di Eulero: stando ai miei calcoli il resto dovrebbe essere 5 .

Tuttavia è evidente che non è possibile utilizzare la calcolatrice del computer per numeri così grandi al fine di verificare l'esattezza del mio calcolo: esiste un modo alternativo per verificare la bontà del mio svolgimento?

Grazie come al solito.

Se necessario, posso postare la mia risoluzione.

[Gi81]

Sì, anche se in questo caso particolare non ce n'è bisogno... ci si arriva subito

[zabby995]

grazie ancora..in un esercizio analizzato precedentemente ho provato ad utilizzare lo stesso metodo di scomposizione, però sembra non sia corretto..allora l'esercizio è:
$43816^20321$ mod10
43816$-=$6(mod10)

M.C.D(6,10)= 2 quindi il piccolo teorema di fermat non è applicabile
10=$5*2$
e ora abbiamo $43816^29345$ $-=$1(mod5) e $43816^29345$ $-=$0(mod2)

$ {(x-=1 (mod 5)),(x-=0 (mod 2)):} $

il risultato però dovrebbe essere 6..dove sbaglio?

ho provato a risolverlo con il teorema cinese dei resti e mi esce 16..uff

[Gi81]

Ma $16 -=6 (mod 10)$

[zabby995]

che stupido è vero.. grazie mille per il tuo aiuto

[zabby995]

c'è un altro problema adesso...$3020173^31$(mod1000)

ho utilizzato il teorema di Eulero e alla fine mi trovo $173^400$ $-=$ 1(mod1000)

ora dovrei dividere 31 per 400..possibile???