What is the number of RSA fixed points, in other words how many $m$ are there such that
$$m^e\equiv m \pmod{n}$$
where $n=pq$, for primes $p,q$.
I know that the answer is $(1+\text{gcd}(e^n-1,p-1))\cdot (1+\text{gcd}(e^n-1,q-1))$, but I could use some help on proving it.
Best Answer
Using CRT, $$m^e \equiv m \pmod p \\ m^e \equiv m \pmod q$$
Mod p: Either $$m \equiv 0 \pmod{p}$$ or $$e \log m \equiv \log m \pmod{p-1} \iff \\ (e - 1) \log m \equiv 0 \pmod{p-1}$$ Now count the number of values of $\log m$. $\log m$ is any multiple of $\frac{p-1}{\gcd(e-1,p-1)}$. The number of multiples is $\gcd(e-1,p-1)$.
Same story mod q.
So it's $(1+\gcd(e-1,p-1))(1+\gcd(e-1,q-1))$.
[edit]
Included $m = 0$ case.