# RSA unconcealed messages

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?

-
Euler Project had problem 182 devoted exactly to the number of unconcealed messages in RSA scheme. Is your question motivated by it, or is it independent ? – Sasha Aug 18 '11 at 19:10
@Azoo: Does your response mean that you have no trouble with the proof that there are $\gcd(e-1,p-1)+1$ solutions modulo $p$? – André Nicolas Aug 19 '11 at 4:58

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.
Hm.. how do I calculate $x^e \pmod{n}$ given what $x$ is? – Jernej Aug 19 '11 at 18:30