Resto divisione di un numero elevato

[sim951]

Ciao a tutti vorrei sapere come riuscire a risolvere questo esercizio che mi sta prendendo un sacco di tempo:
Calcolare il resto della divisione del numero $ (215437)^27 $ per 23.

[G.D.5]

Devi usare le congruenze e, se possibile, il Piccolo Teorema di Fermat. Conosci questi argomenti?

[sim951]

si si lo conosco, però non saprei come applicarlo

[G.D.5]

Per prima cosa potresti usare il fatto che \( \forall k \in \mathbb{N} \left ( a \equiv b \pmod{n} \iff a^{k} \equiv b^{k} \pmod{n} \right ) \) per lavorare con il resto di \( 215437 \) nella divisione per \( 23 \) (diciamo \( r \)) elevato a \( 27 \), anziché con \( 215437 \). Dopo potresti spezzare la potenza \( 27 \) in \( 23 + 4 \) e usare ancora le proprietà delle congruenze per lavorare su \( r^{23} \) usando il Piccolo Teorema di Fermat. Quindi ancora usando le proprietà delle congruenze potresti "combinare" il risultato ottenuto applicando il Piccolo Teorema di Fermat con \( r^{4} \), quindi scomporre la potenza e manipolarla ancora con le proprietà delle congruenze per ottenere il risultato finale.

EDIT
Attenzione all'errore fatto notare sotto da axpgn.

[axpgn]

@G.D.

Sei sicuro che questa \( \forall k \in \mathbb{N} \left ( a \equiv b \pmod{n} \iff a^{k} \equiv b^{k} \pmod{n} \right ) \) sia bidirezionale?

Per esempio:

$3^5-=7^5\ (mod 41)\ =>\ 243-=16807\ (mod 41)\ =>\ 38-=38 (mod 41)$

ma non è vero che $3-=7\ (mod 41)$

Cordialmente, Alex

[G.D.5]

@axpgn

Ovviamente hai ragione: la proprietà corretta è la seguente

\[
\forall k \in \mathbb{N} \left ( a \equiv b \pmod{n} \implies a^{k} \equiv b^{k} \pmod{n} \right )
\]
Ti ringrazio per avermelo fatto notare perché non avevo proprio fatto caso al fatto che avessi usato il bicondizionale al posto del condizionale.