Euler's phi function and the Chinese remainder theorem

 

정리1 Chinese remainder theorem

Let $m, n \in \mathbb{Z}$  s.t.  $gcd(m,n) =1$.

For $b,c \in \mathbb{Z}$, the following hold

1. There exists $x_{0} \in \mathbb{Z}$  s.t.  $x_{0} \equiv b \; (\mathrm{mod} \; m)$  and  $x_{0} \equiv c \; (\mathrm{mod} \; n)$

2. If $x_{1} \equiv b \; (\mathrm{mod} \; m)$  and  $x_{1} \equiv c \; (\mathrm{mod} \; n)$, then $x_{0} \equiv x_{1} \; (\mathrm{mod} \; mn)$ 

 

pf)

  $x \equiv b \; (\mathrm{mod} \; m)$

  $\Rightarrow$ $x = b+my$ for some $y \in \mathbb{Z}$

  $x \equiv c \; (\mathrm{mod} \; n)$

  $\Rightarrow$ $b+my \equiv c  \; (\mathrm{mod} \; n) $

  $\Rightarrow$ $my \equiv c - b \; (\mathrm{mod} \; n)$

 

  Since $gcd(m,n) = 1$,

  $my \equiv c - b \; (\mathrm{mod} \; n)$ has a solution for $y$. Call it $y_{0}$ and $x_{0} = b+my_{0}$.

 

  Then

  $x_{0} \equiv b+my_{0} \equiv b \; (\mathrm{mod} \; m)$

  $x_{0} \equiv b+my_{0} \equiv b + (c-b) \equiv c \; (\mathrm{mod} \; n)$

 

  Assumption : $\left\{\begin{matrix}
  x_{0} \equiv x_{1} \equiv b \; (\mathrm{mod} \; m) \\
  x_{0} \equiv x_{1} \equiv c \; (\mathrm{mod} \; n)\end{matrix}\right.$

  $x_{0} \equiv x_{1} \; (\mathrm{mod} \; m)$  $\Rightarrow$  $m|x_{0} - x_{1}$

  $x_{0} \equiv x_{1} \; (\mathrm{mod} \; n)$  $\Rightarrow$  $n|x_{0} - x_{1}$

 

  Since $gcd(m,n) = 1$, we get  $mn|x_{0} - x_{1}$

  $\therefore$  $x_{0} \equiv x_{1} \; (\mathrm{mod} \; mn)$ 

 

 

 

정리2 Phi function formula

1. $p$ is a prime

$\Rightarrow$ $\phi (p^{k}) = p^{k} - p^{k-1}$

 

2. $gcd(m,n) =1$ 

$\Rightarrow$ $\phi (mn) = \phi (m) \phi (n)$

 

pf)

  $1 \leq a \leq p^{k}$,  $gcd(a, p^{k}) \neq 1$

  $\Leftrightarrow$ $p|a$

  $\Leftrightarrow$ $a=p, 2p, 3p, \cdots, p^{k-1} \cdot p$

  So #$\left\{a \; | \;  1 \leq a \leq p^{k}, \; gcd(a, p^{k}) \neq 1 \right\} = p^{k-1}$

  $\therefore$  $\phi (p^{k}) = p^{k} - p^{k-1}$

 

  Recall

  $\phi(l) =$ #$\left\{x \in \mathbb{Z} \; | \; 1 \leq x \leq l, gcd(x, l)=1 \right\}$

            $=$ #$\left\{x \in \mathbb{Z}_{l} \; | \; gcd(x, l)=1 \right\}$

            $=$ #$\mathbb{U}_{l}$

---

  Since

  $\phi (mn) = \phi (m) \phi (n)$

  $\Leftrightarrow$ $\left|\mathbb{U}_{mn} \right| = \left|\mathbb{U}_{m} \right| \cdot \left|\mathbb{U}_{n} \right| =   \left|\mathbb{U}_{m} \times \mathbb{U}_{n} \right|$,

  show that $\left|\mathbb{U}_{mn} \right| = \left|\mathbb{U}_{m} \times \mathbb{U}_{n} \right|$

 

  Define a function $f: \mathbb{U}_{mn} \to \mathbb{U}_{m} \times \mathbb{U}_{n}$ by $f(x) = (x \; (\mathrm{mod} \;   m), x \; (\mathrm{mod} \; n))$

 

  Check $f(x) \in \mathbb{U}_{m} \times \mathbb{U}_{n}$

  Since $gcd(x,mn) = 1$, there exists $x', y' \in \mathbb{Z}$  s.t.  $xx' + mny' =1$

  $\Rightarrow$ $xx' + m(ny') =1$  and  $x', ny' \in \mathbb{Z}$

  $\Rightarrow$ $gcd(x,m) = 1$

  $\Rightarrow$ $gcd(x \; (\mathrm{mod} \; m) ,m) = 1$

 

  Similarly, $gcd(x \; (\mathrm{mod} \; n) ,n) = 1$

  $\therefore$  $f$ is well defined.

 

  Claim 1  : $f$ is 1-1 onto

  Let $(b, c) \in \mathbb{U}_{m} \times \mathbb{U}_{n} \subset \mathbb{Z}_{m} \times \mathbb{Z}_{n} $

  By the Chinese remainder theorem, there is a unique $x \in \mathbb{Z}_{mn}$  s.t. 

  $x \equiv b \; (\mathrm{mod} \;   m)$  and  $x \equiv c \; (\mathrm{mod} \; n)$

 

  Check such $x$ is in $ \mathbb{U}_{mn}$

  $x \equiv b \; (\mathrm{mod} \; m)$  and  $gcd(b, m) = 1$

  $\Rightarrow$ $gcd( x \; (\mathrm{mod} \; m) , m) = 1$

  $\Rightarrow$ $gcd(x,m)=1$

 

  Similarly $gcd(x,n) =1$

  $\therefore$  $gcd(x,mn) =1$  $\Rightarrow$  $x \in \mathbb{U}_{mn}$

  $\therefore$  $f$ is 1-1 onto.

  $\therefore$  $\left|\mathbb{U}_{mn} \right| = \left|\mathbb{U}_{m} \times \mathbb{U}_{n} \right|$

  $\therefore$  $\phi (mn) = \phi (m) \phi (n)$

 

 

 

따름정리

$m = p{_{1}}^{n_{1}} p{_{2}}^{n_{2}} \cdots p{_{r}}^{n_{r}}$

$\Rightarrow$ $\phi (m) = \prod_{i=1}^{r}(p{_{i}}^{n_{i}} - p{_{i}}^{n_{i} - 1})$

                 $= n \prod_{i=1}^{r}(1 - \frac{1}{p_{i}}) $