Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

1 Answer 1

up vote 0 down vote accepted

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.

share|improve this answer
    
Hm.. how do I calculate $x^e \pmod{n}$ given what $x$ is? –  Jernej Aug 19 '11 at 18:30
    
Added the general idea. –  Gadi A Aug 19 '11 at 21:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.