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.

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|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
add comment

1 Answer

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|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
add comment

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.