# Fermat pseudoprime

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$

• How do you know that $a^{pq-1}=1 mod(q)$? Apr 21 '17 at 15:20
• $a^{pq-1} \equiv 1 \mod pq$, because it is a pseudoprime. Hence also $a^{pq-1} \equiv 1 \mod q$. Apr 21 '17 at 15:21
• Later... $a^{gcd(p-1,q-1)}=1 mod q$, why? That power is less than $p-1$ and $q-1$ Apr 21 '17 at 15:33
• If $a^b \equiv 1 \mod k$ and $a^c \equiv 1 \mod k$, then $a^{\gcd(b,c)} \equiv 1 \mod k$. Apr 21 '17 at 15:35
• Uhmmm thank you very much! Apr 21 '17 at 15:39