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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I know that decryption in the RSA cryptosystem works because$$D\left(C\right)\equiv C^d\equiv \left(P^e\right)^d\equiv P^{ed}\equiv P^{k\phi\left(n\right)+1}\equiv \left(P^{\phi\left(n\right)}\right)^kP\equiv P\pmod n,$$where $ed=k\phi\left(n\right)+1$ for some integer $k$, because $ed\equiv1\pmod{\phi\left(n\right)}$, and by Euler's theorem, we have that $P^{\phi\left(n\right)}\equiv1\pmod n$, because $\left(P,n\right)=1$.

However, it also works when $\left(P,n\right)\neq1$, and I am not sure how to show this. I know that if $\left(P,n\right)\neq1$, then either $P=p$ or $P=q$, where $n=pq$, but that does not seem to help much. Could someone shed some light on this for me? Thanks in advance!

share|cite|improve this question
$(P,n) \neq 1$ implies that $P$ is a multiple of $p$, $q$ or $n$. – Yuval Filmus Mar 25 '12 at 17:26
This might help:… – mikeazo Feb 28 '13 at 15:19

Your Answer


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

Browse other questions tagged or ask your own question.