Determinare il resto di una divisione tra numeri grandi

[Ishima1]

Salve,l'esercizio mi chiede di determinare:
\( 35267^(1000) \equiv ?? mod9 \)
Io l'ho svolto in questa maniera:
\( 35267\equiv 5 mod9 \)
Per il corollario del piccolo teorema di Fermat si ha che:
\( MCD(5,9)=1\rightarrow 5^8\equiv 1 mod9 \)
dunque:
\( 35267^(1000)\equiv 5^(1000)=(5^8)^(125)\equiv 1mod9 \)
I valori in parentesi sarebbero gli esponenti.
Ma il risultato,controllando con un tool online,dovrebbe essere 4.
Che cosa ho sbagliato?

[axpgn]

$5^6-=1\ MOD\ 9$

$(5^6)^166-=1^166\ MOD\ 9$

$5^996-=1\ MOD\ 9$

$5^996*5^4-=1*5^4\ MOD\ 9$

$5^1000-=5^4=625\ MOD\ 9$

$5^1000-=4\ MOD\ 9$

[Ishima1]

perchè 5^6) e non 5^8? Il piccolo teorema di fermat non dice a^(p-1) ecc..?

[axpgn]

Primo perché funziona ... e secondo perché mi pare che $p$ debba essere primo e $9$ non lo è ...

[Ishima1]

quindi qual è la regola generale?

[axpgn]

Non lo chiedere a me ...