Euler-Phi Function

 

 

 

[Thm 1] For integers $m$, $n$, $x$, if $m$ and $n$ are coprime, then the followings are equivalent.

(a) $gcd(mn,x)=1$

(b) $gcd(m,x)=1$ and $gcd(n,x)=1$

(c) $gcd(m,a)=1$ and $gcd(n,b)=1$ where $a$ and $b$ are remainders of $x$ divided by $m$ and $n$, respectively.

---

[Def] ${\mathbb{U}}_n:=\{x\in \mathbb{Z}|0\le x<n,gcd(n,x)=1\}$

---

Given two coprime positive integers $m$, $n$, define a function

$$\begin{array}{rl}f:{\mathbb{U}}_{mn}& \to {\mathbb{U}}_m\times {\mathbb{U}}_n\\ x& \mapsto (a,b)\end{array}$$

where

$x=q_{1}m+a$ for some $q_1\in \mathbb{Z}$

$x=q_{2}n+b$ for some $q_2\in \mathbb{Z}$

Claim: $f$ is bijective.

1) onto

Pick any $(a,b)$ from ${\mathbb{U}}_m\times {\mathbb{U}}_n$. Define

$A:=\{a+qm|q\in \mathbb{Z}\}$

$B:=\{b+qn|q\in \mathbb{Z}\}$

We have to find a nonnegative integer $x\in A\cap B$ which is smaller than $mn$. Because $gcd(m,n)=1$, $ms+nt=1$ for some $s,t\in \mathbb{Z}$. Then,

$$ms(a-b)+nt(a-b)=a-b$$

Define an integer $X$ as

$$X:=a+ms(b-a)=b+nt(a-b)$$

which is in $A\cap B$. Now define $x$ as the remainder of $X$ divided by $mn$, i.e.,

$$X=q(mn)+x$$

for some $q\in \mathbb{Z}$. Because the remainder of $x$ divided by $m$ is $a$, and the remainder of $x$ divided by $n$ is $b$, $x$ is in $A\cap B$. By Thm 1, $gcd(mn,x)=1$.

 

2) 1-1

Let us assume $x_1,x_2\in {\mathbb{U}}_{mn}$, $x_1\ne x_2$, and $f(x_1)=f(x_2)=(a,b)$. Then

$$\begin{array}{r}{x}_1=m{q}_1+a\\ x_2=m{q}_2+a\end{array}$$

for some $q_1,q_2\in \mathbb{Z}$. So $m|x_1-x_2$. Similarly $n|x_1-x_2$. Since $m$ and $n$ are coprime, $mn|x_1-x_2$. It contradicts the fact that $x_1,x_2\in {\mathbb{U}}_{mn}$.