2

Let $p_1,...,p_s$ be distinct prime number, and put $N = p_1 \cdots p_s$. Let $e$ a positive integer such that $gcd(e,\phi(N)) = 1$. Show that the map $f_e : \mathbb{Z}/N\mathbb{Z} \rightarrow \mathbb{Z}/N\mathbb{Z} , f_e(x) = x^e$ is bijective.

I know the proof should be related to Chinese Reminder Theorem. But I'm still confused about how to prove it. I'm thinking about there exists a positive integer $d$, such that $de≡1 (\phi(N))$, thus $f_d*f_e=f_e*f_d$

lisyarus
  • 15,517
Haley
  • 71

1 Answers1

0

It suffices to prove that $f_e$ is surjective.

  • If $p$ divides $N$, then $x \mapsto x^e$ is bijective in $\mathbb Z/ p\mathbb Z$ because $\gcd(e,\phi(p))=1$ since $\phi(p)$ divides $\phi(N)$. This follows from Fermat and $0 \mapsto 0$.

  • Let $a \in \mathbb Z/ N\mathbb Z$. Then $(a \bmod p_1, \dots, a \bmod p_s)=(a_1^e \bmod p_1, \dots, a_s^e \bmod p_s)$. By the Chinese Reminder Theorem, there is $b$ such that $(b \bmod p_1, \dots, b \bmod p_s)=(a_1 \bmod p_1, \dots, a_s \bmod p_s)$. Therefore, $b^e \equiv a \bmod N$.

lhf
  • 216,483