Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

if $N=pq$ where $p$ and $q$ are different primes. Given $e$ and $d$ in $\{1,\ldots,\phi(N)-1\}$ for which holds that $ed=1\pmod {\phi(N)}$.Then we have $a^{ed}=a\pmod N$ for all non-invertible $a$ in $\Bbb Z_n$.

Why is this?

I tried to go this way: $ed=1 \pmod {\phi(N)}$, so $ed-1=k\cdot \phi(N)$ , for some $k$. Then $a^{ed}=a^{k\cdot \phi(N)+1}=a^{k \cdot \phi(N)}a=(a^{\phi(N)})^ka$

but I can only use $a^{\phi(N)}=1$ if is a unit, right?

Do I have to use that $\phi(N)=(p-1)(q-1)$?

thanks very much

share|cite|improve this question
I edited, is everything OK? – Pedro Tamaroff Oct 2 '12 at 16:02
Yes, thank you very much! – Jobb Oct 2 '12 at 16:55

Hint: If $a$ is not invertible, then $a$ is divisible by $p$ or $q$ or both. Compute separately modulo $p$ and modulo $q$. And yes, you will be using the fact that $\varphi(pq)=(p-1)(q-1)$.

share|cite|improve this answer
Thank you for your hint. I can see with examples that the statement holds, but we have that a^{(p-1)} is divisible by p if a is divisible by p... so i am confused... – Jobb Oct 2 '12 at 23:09
Suppose that $a$ is divisible by $p$ but not by $q$. Then $a^{ed}\equiv a\pmod{p}$, since they are both congruent to $0$. Also, since $ed$ has shape $k(p-1)(q-1)+1$, $a^{ed}\equiv a \pmod{q}$ by Fermat's Theorem (tell me if you have trouble with this, probably not). Since $a^{ed}$ is congruent to $a$ modulo each of $p$ and $q$, it is congruent to $a$ modulo $pq$. The case $q$ divides $a$, $p$ does not is basically the same. The case $a$ divisible by both is easier. – André Nicolas Oct 2 '12 at 23:24

Your Answer


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.