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{align}
f: \mathbb{U}_{mn} &\to \mathbb{U}_m \times \mathbb{U}_n \\
x &\mapsto (a, b)
\end{align}

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 \neq x_2$, and $f(x_1) = f(x_2) = (a, b)$. Then

\begin{align}
x_1 = mq_1 + a \\
x_2 = mq_2 + a
\end{align}

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