# RSA fixed point

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.

• I think it's $(1+\gcd(e-1,p-1))(1+\gcd(e-1,q-1))$. Do you have a citation that shows otherwise? – ogogmad May 25 '15 at 21:48
• @user3491648 Yours seems OK, see link. – mvw May 25 '15 at 21:56
• OP's versions seems to be for a slightly different version, see link at the bottom. – mvw May 25 '15 at 21:57
• @mvw Makes sense, thanks. If that's the case, it should be $m^{e^n}≡m \pmod N$, and $N=pq$ (capital N). The method in that case would be the same as in my answer. – ogogmad May 25 '15 at 22:14

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)$.
So it's $(1+\gcd(e-1,p-1))(1+\gcd(e-1,q-1))$.
Included $m = 0$ case.