2
$\begingroup$

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

  • 0
    Yes, thank you very much!2012-10-02

1 Answers 1

1

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)$.

  • 0
    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.2012-10-02