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.