I would like to show that given that $(n,e)$ is the public key as defined in the RSA encription ($n = pq$ for primes $p,q$) then the number of solutions to the equation $$ x^e \equiv x \pmod n$$ equals to $(\gcd(e-1,p-1)+1)(\gcd(e-1,q-1)+1)$.
The textbook I am using also has a hint that one could use CRT but I do not see how to combine the solution to $x^{e-1} \equiv 1 \pmod p$ into a solution to the original equation.
Could someone please explain how to prove this identity?
Best Answer
Let's say $a$ is a solution mod p, i.e. $a^e\equiv a\ (\text{mod}\ p)$, and $b^e\equiv b\ (\text{mod}\ q)$. Now use CRT to obtain $x$ such that $x\equiv a\ (\text{mod}\ p)$ and $x\equiv b \ (\text{mod}\ q)$. What is $x^e$ mod n?
The hard part of this question, IMO, is proving that the number of solutions mod p is $\gcd(e-1,p-1)+1$.
(Supplement: to show that $x^e-x=0$ mod n it's enough to show that n divides $x^e-x$. Since $n=pq$ and $p,q$ are primes, it's enough to show that p divides $x^e-x$ and q divides $x^e-x$ (this is basic number theory). This follows from $x$'s CRT property.