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
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.
추후에 채울 예정