Resto della divisione con teorema eulero

[cloe009]

Salve a tutti,

se ho il seguente esercizio:
Si calcoli il resto della divisione [tex]1212312125^{45456}[/tex] per [tex]14[/tex].


Mi è stato detto, forse erroneamente, che il risultato è 9.
Ma a me facendolo più volte esce sempre 1.
E' giusto il mio procedimento?


per praticità pongo:
[tex]a = 1212312125;[/tex]
[tex]n = 14[/tex]

mi trovo MCD tramite algoritmo euclideo e
dal momento che il [tex]MCD(a, n) = 1[/tex]
posso applicare il Teorema di Eulero.

perciò considero già da subito:
[tex]a^{\phi(n)} \equiv 1 \pmod{n}[/tex]

fattorizzo la [tex]n = 14 = 2 \cdot 7[/tex]
mi trovo [tex]\phi(n) = \phi(14) = (2-1) \cdot (7-1) = 6[/tex]
applico al teorema di Eulero:
[tex]a^{6} \equiv 1 \pmod{n}[/tex]

a questo punto considero l'esponente [tex]45456[/tex] e lo divido per [tex]\phi(14) = 6[/tex]
ottengo:
[tex]a^{45456} = a^{6 \cdot 7576} = \left ( a^6 \right )^{7576}[/tex]
ma da prima avevamo che [tex]a^{6} \equiv 1 \pmod{14}[/tex]
quindi sostituendo ottengo:
[tex]\equiv \left ( 1 \right )^{7576} \equiv 1 \pmod{14}[/tex]

quindi ottengo 1.
è giusto il mio procedimento o sbaglio sempre in qualche punto e perciò non ottengo 9?
grazie mille per la grande pazienza che avete!

[Lord K]

A me sembra tutto ok... hai la soluzione da qualche parte?