Piccolo teorema di Fermat problema

[Max.8911]

Non capisco come applicare il piccolo teorema di Fermat.
Es 1:
Calcolare il resto della divisione tra 11^68 e 13.
Es 2 :
Calcolare il resto della divisione tra 5^38 e 11.

O meglio ho fatto questi esercizi seguendo la soluzione e riesco a farli venire più o meno ma non capisco quello che sto facendo e quindi non mi è chiaro.

Per esempio nel es 1 il divisore è primo.
Quindi per il teorema di Fermat la classe di 11^12 è uguale alla classe di 1.
Poi se ho capito bene devo scomporre 11^68 fino a trovare una classe tra 0<= r < 13.
Mi potete elencare meglio i diversi passaggi e spiegarmi perchè sono così?
Grazie.

[Lord K]

Es 1) Come dici giustamente hai che:

$11^12 \equiv 1 (13)$

Ma allora:

$11^68 = (11^12)^5*11^8 \equiv 11^8 (13)$

Da qui poi hai che:

$11^8 \equiv (-2)^8 \equiv 2^8 (13)$

Abbiamo che:

$2^4 = 16 \equiv 3 (13)$

ovvero:

$11^8 \equiv 2^8 \equiv 3^2 \equiv 9 (13)$

ovvero la soluzione al problema.

Es 2) Anche qui $11$ è primo e quindi $x^10\equiv 1(11)$ quale che sia $x!=0(11)$ procedo come sopra.

$5^38 \equiv (5^10)^3*5^8 \equiv 5^8 \equiv 25^4 \equiv 3^4 \equiv 81 \equiv 4(11)$

[Sk_Anonymous]

Potresti operare come segue.
Essendo 13 primo,hai:
(1) $(11)^(12)-=1 (mod 13)$
Ora è:
$11^(68)=(11^(12))^5*11^8$
e quindi per la (1) hai:
$11^(68)-=(11)^8 ( mod 13)$
e pertanto il resto cercato è quello della divisione di $11^8$ per 13
Operando in modulo 13 si ha:
$(11)^2=121-=4 $
$(11)^4-=4^2=16-=3 $
$(11)^8-=3^2=9<13$
Il resto è dunque uguale a 9.

[Max.8911]

Se il divisore non fosse primo semplicemente il teorema di Fermat non si può applicare giusto?

[Lord K]

Il teorema di Fermat fa uso in realtà della funzione totiente $phi(n)$ , (ovvero il conteggio dei numeri tra $0
$a^(phi(n)) \equiv 1 (n)$

Se $n=p$ è primo si riporta alla formulazione:

$a^(p-1) \equiv 1 (p)$

visto che $phi(p)=p-1$. inportantissimo quindi che $gcd(a,n)=1$ altrimenti ci sono dei problemi!