Let $n=pq$ product of two different primes. Let $d=\gcd(p-1,q-1)$. Prove that $n$ is a Fermat pseudoprime to the base $a$ if and only if $a^d=1 \mod n$
I believe that I get: if $a^d=1 \mod n$ then $n$ is a pseudoprime to the base $a$.
But I can not get the other implication.
Because $pq$ is a pseudoprime, we have $a^{pq-1} \equiv 1 \mod pq$.
By Fermat's little theorem, $a^{q-1} \equiv 1 \mod q$.
Combining this with $a^{pq-1} \equiv 1 \mod q$, we get $a^{p-1} \equiv 1 \mod q$.
Therefore, $a^{\gcd(p-1,q-1)} \equiv 1 \mod q$.
In the same way $a^{\gcd(p-1,q-1)} \equiv 1 \mod p$.
Hence we get $a^d = a^{\gcd(p-1,q-1)} \equiv 1 \mod pq$