Euler’s Theorem

2020-2학기, 대학에서 ‘현대대수1’ 수업을 듣고 공부한 바를 정리한 글입니다. 지적은 언제나 환영입니다 :)

좀더 간단한 형태인 Fermat’s Little Theorem은 이곳에서 확인할 수 있다!!

---

Euler phi function

Theorem.

$\mathbb{Z}_n$에서 zero-divisor가 아닌 non-zero elt들을 모아 set $G_n$을 정의하자.

그러면, $G_n$은 multiplication modulo $n$에 대해 Group을 이룬다.

이때, $\mathbb{Z}_n$에서 $(a, n) \ne 1$이 아닌 원소들은 모두 zero-divisor가 됨을 기억하라!

그렇다면 $G_n$를 아래와 같이 정의할 수 있다.

\[G_n = \{ a \in \mathbb{Z}_n \mid (a, n) = 1\}\]

proof.

We will show $G_n = \{ a \in \mathbb{Z}_n \mid (a, n) = 1\}$

($\supseteq$) Let $a \in \mathbb{Z}_n$ s.t. $(a, n) = 1$.

Supp. $ab \equiv 0$, then show $b = 0$; i.e. $a$ is not zero-divisor.

\[\begin{aligned} n \mid ab &\implies n \mid b \quad (\because (a, n) = 1) \\ &\implies b \equiv 0 \quad (\textrm{mod} \; n) \end{aligned}\]

따라서 $a$는 zero-divisor가 아니다!

($\subseteq$) Let $a$ be a not zero-divisor in $\mathbb{Z}_n$.

We will show $(a, n) = 1$.

Let $d = (a, n)$

Supp. $d \ne 1$, (proof by contradiction)

then $a(\frac{n}{d}) = (\frac{a}{n})n \equiv 0$

This means $a$ is a zero-divisor. (모순!)

따라서 $d = (a, n) = 1$. $\blacksquare$

즉, $G_n$은 non zero-divisor 원소의 집합임과 동시에, $(a, n) = 1$인 원소의 집합이다.

Goal: $G_n$ is group under mutliplicative modulo $n$.

(1) closed under opr

if $(a, n) = 1$, $(b, n) = 1$,

then $(ab, n) = 1$.

(2) identity

$(1, n) = 1$

(3) inverse

For $a \in G_n$, we will find $b$ s.t. $ab = 1$.

Since $(a, n) = 1$, $< a, n > = \mathbb{Z}$

By Bezout's Identity, there exist $x, y \in \mathbb{Z}$

\[ax + ny = 1\]

양변에 (mod $n$)을 취하면,

\[ax \equiv 1 \quad (\textrm{mod} \; n)\]

따라서 이때의 $x$가 $a \in G_n$의 multiplicative inverse다!

By (1) ~ (3)에 의해 $G_n$은 group w.r.t. multiplicative modulo $n$.

---

Definition. Eulder phi function $\varphi(n)$

Let $n \ge 1$ be a natural number.

$\varphi(n)$ := (# of integers $m$ s.t. $(m, n) = 1$)

즉, $\varphi(n) = \lvert G_n \rvert$인 것이다!!

Examples.

• $\varphi(12) = \lvert \{ 1, 5, 7, 11 \} \rvert = 4$
• $\varphi(p) = p-1 = \lvert \mathbb{Z}^{*}_p \rvert$

---

Euler’s Theorem

Theorem. Euler’s generalization of FLT

If $a \in \mathbb{Z}$ and $(a, n) = 1$,

then

\[a^{\varphi(n)} \equiv 1 \quad (\textrm{mod} \; n)\]

FLT에선 $n = p$인 경우를 다뤘다.

proof.

만약 $(a, n) = 1$이라면, $a$가 속한 $n\mathbb{Z}$의 coset $a + n\mathbb{Z}$ 안에는 $n$보다 작으면서 $n$과 서로소인 자연수 $b$가 존재한다.

즉, $a \equiv b$ (mod $n$) $\iff$ $a + n\mathbb{Z} = b + n\mathbb{Z}$.

이때, modulo multiplication이 well-defined이므로

$a^{\varphi(n)} \equiv b^{\varphi(n)}$ (mod $n$)이다.

$b$는 coset $b + n\mathbb{Z}$의 representative이므로 $b \in \mathbb{Z}_n$이며,
$(b, n) = 1$이므로 $b \in G_n$이다.

이때, $< b > \le G_n$이므로 $\lvert < b > \rvert \mid \lvert G_n \rvert$이다.

$< b >$이 cyclic group이므로 $b^{\lvert < b > \rvert} \equiv 1$ (mod $n$)이다.

이때 $\lvert < b > \rvert \mid \lvert G_n \rvert$이므로 아래가 성립한다.

\[b^{\varphi(n)} \equiv 1 \quad (\textrm{mod} \; n)\]

즉,

\[a^{\varphi(n)} \equiv 1 \quad (\textrm{mod} \; n)\]

이다.

Example.

$\varphi(12) = 4$, then

\[\begin{aligned} 7^{\varphi(12)} &\equiv 1 \quad (\textrm{mod} \; 12) \\ 7^4 &\equiv 1 \quad (\textrm{mod} \; 12) \end{aligned}\]

---

Application: solve modulo equation

$a$, $b$, $n$ are given
Solve $ax \equiv b$ (mod $n$)

Theorem.

If $(a, n) = 1$,

then $\forall \; b \in \mathbb{Z}$, $ax \equiv b$ (mod $n$) has an “unique solution” in $\mathbb{Z}_n$.

$(a, n) = 1$ means $a$ has a multiplicative inverse.

Therefore

\[\begin{aligned} ax &\equiv b \qquad (\textrm{mod} \; n) \\ a^{-1}(ax) &\equiv a^{-1}(b) \quad (\textrm{mod} \; n) \\ x &\equiv a^{-1}b \quad (\textrm{mod} \; n) \end{aligned}\]

Theorem.

추후에 채울 예정