Number of integers $a$ that satisfy $a^n \equiv a \pmod{b}$, where $b = pq$?

Question

Prove that the number of $a$ which satisfy:

$$ a^n \equiv a \pmod{b}, $$where $b = pq$, $\quad$$p,q$ primes.

is $[\text{gcd}(n-1,p-1)+1] \cdot [\text{gcd}(n-1,q-1)+1]$

Attempt: Since $p,q$ are coprime, then it is equivalent to find the number of $a$ which satisfy: \begin{align} a^n &\equiv a \pmod{p} \iff a^{n-1} \equiv 1 \pmod{p} \tag{1}\\ a^n &\equiv a \pmod{q} \iff a^{n-1} \equiv 1 \pmod{q}\tag{2} \end{align}

From here, I can't figure out why the number of $a$ which satisfy $(1)$ for example, is $\text{gcd}(n-1,p-1)$ (the $+1$ part in the result must be that you have to count $0$). Any help would be appreciated.

Answer 1

Hint: Suppose that $p \nmid a$. Since $a^{p-1} \equiv 1 \pmod p$, if $a^{n-1} \equiv 1 \pmod p$, then $a^{(n-1)r + (p-1)s} \equiv 1 \pmod p$ for every $r,s \in \mathbb Z$. Take $r,s$ as in Bézout's Thm, so that $a^{\gcd(n-1,p-1)} \equiv 1 \pmod p$. Since $\mathbb Z_p$ is a field, there are exactly $\gcd(n-1,p-1)$ solutions for $a^{n-1} \equiv 1 \pmod p$.

Answer 2

If you know some basic field theory: Since $\mathbb{F}_p=\mathbb{Z}/p\mathbb{Z}$ is a finite field, $\mathbb{F}_p^{\times}$ is cyclic. Let $\alpha$ be a generator and let $d= \gcd(n-1,p-1)$. Then, by Bezout's identity, $a^{n-1}\equiv 1 \pmod{p}$ if and only if $a^d \equiv 1 \pmod{p}$. Now, note that $\beta=\alpha^{\frac{p-1}{d}}$ has order exactly $d$. That is, the subgroup $<\beta>$ has exactly $d$ elements, each a solution of $x^d\equiv 1$. So, we have at least $\gcd(p-1,n-1)$ solutions. Suppose $a$ is any other solution of $x^d\equiv 1$. Let the order of $a$ be $r$; so $<a>$ is a subgroup of order $r$. But since $r$ must divide $d$, there exists a subgroup of order $r$ within $<\beta>$. Since a cyclic group contains a unique subgroup of each order, it must be that $a\in <\beta>$. Thus, there are exactly $\gcd(n-1,p-1)$ solutions.