Pseudoprimo de Fermat

Question

Sea $n=pq$ producto de dos primos diferentes. Sea $d=\gcd(p-1,q-1)$ . Demostrar que $n$ es un pseudoprimo de Fermat de base $a$ sólo si $a^d=1 \mod n$

Creo que entiendo: si $a^d=1 \mod n$ entonces $n$ es un pseudoprimo de la base $a$ .

Pero no consigo entender la otra implicación.

Answer 1

Porque $pq$ es un pseudoprimo, tenemos $a^{pq-1} \equiv 1 \mod pq$ .

Por el pequeño teorema de Fermat, $a^{q-1} \equiv 1 \mod q$ .

Combinando esto con $a^{pq-1} \equiv 1 \mod q$ obtenemos $a^{p-1} \equiv 1 \mod q$ .

Por lo tanto, $a^{\gcd(p-1,q-1)} \equiv 1 \mod q$ .

Del mismo modo $a^{\gcd(p-1,q-1)} \equiv 1 \mod p$ .

Por lo tanto, obtenemos $a^d = a^{\gcd(p-1,q-1)} \equiv 1 \mod pq$