[현대대수학-환, 체론] 3. 페르마와 오일러의 정리

[현대대수학-환, 체론] 3. 페르마와 오일러의 정리

덧셈군으로서 $\mathbb{Z}_{n}$과 $\mathbb{Z}/n\mathbb{Z}$는 동형이다. $a\in\mathbb{Z}_{n}$을 $a+n\mathbb{Z}\in\mathbb{Z}/n\mathbb{Z}$로 대응시키면 동형이라는 것을 확인할 수 있다. 

$\mathbb{Z}/n\mathbb{Z}$에서 임의의 $a+n\mathbb{Z},\,b+n\mathbb{Z}\in\mathbb{Z}/n\mathbb{Z}$에 대하여 $$(a+n\mathbb{Z})\cdot(b+n\mathbb{Z})=ab+n\mathbb{Z}$$ 로 정의하자. 그러면 이 곱셈연산은 잘 정의되고, 곱셈의 결합법칙과 분배법칙이 $\mathbb{Z}/n\mathbb{Z}$에서 성립한다. 따라서 $\mathbb{Z}/n\mathbb{Z}$는 환이 되고, $\mathbb{Z}_{n}$과 환으로서 동형이다.

임의의 체 $F$에 대하여, $(F-\{0\},\,\cdot)$는 곱셈에 대한 군이다. 특히 $\mathbb{Z}_{p}$, $\mathbb{Z}_{p}-\{0\}$($p$는 소수)는 $p$를 법으로 하는 곱셈 연산에 대해 위수가 $p-1$인 군이다. 군에 있는 임의의 원소들의 위수는 군의 위수를 나눌 수 있기 때문에, 임의의 $b(\neq0)\in\mathbb{Z}_{p}$에 대하여 $\mathbb{Z}_{p}$에서 $b^{p-1}=1$이다. 환으로서 $\mathbb{Z}_{p}\simeq\mathbb{Z}/p\mathbb{Z}$라는 사실로부터 $a+p\mathbb{Z}(\neq0+p\mathbb{Z})\in\mathbb{Z}/p\mathbb{Z}$는 $$(a+p\mathbb{Z})^{p-1}=a^{p-1}+p\mathbb{Z}=1+p\mathbb{Z}$$ 이므로 $\mathbb{Z}/p\mathbb{Z}$에서 곱셈항등원이다. 즉, $p$의 배수가 아닌 임의의 $a\in\mathbb{Z}$에 대하여 $a^{p-1}\equiv1\,(\text{mod}\,p)$이다. 이것은 페르마의 작은 정리(Little theorem of Fermat)의 증명이고 이 정리를 다음과 같이 나타낼 수 있다:

$a\in\mathbb{Z}$, $p$를 소수, $a$는 $p$의 배수가 아니라고 하자. 그러면 임의의 $a\not\equiv0\,(\text{mod}\,p)$에 대하여 $a^{p-1}\equiv1\,(\text{mod}\,p)$이다. 이 결과로부터 다음이 성립한다: $a\in\mathbb{Z}$이면, 임의의 소수 $p$에 대하여 $a^{p}\equiv a\,(\text{mod}\,p)$이다.

페르마의 작은 정리를 이용하여 $8^{103}$을 $13$으로 나눈 나머지를 어렵지 않게 찾을 수 있다. 페르마의 작은 정리로부터 $8^{13-1}=8^{12}\equiv1\,(\text{mod}\,13)$이므로, $$\begin{align*}8^{103}&\equiv8^{96+7}\equiv8^{96}\cdot8^{7}\equiv(8^{12})^{8}(8^{7})\equiv1^{8}\cdot8^{7}\\&\equiv8^{7}\equiv(-5)^{7}\equiv((-5)^{2})^{3}(-5)\equiv25^{3}(-5)\equiv(-1)^{3}(-5)\\&\equiv5\,(\text{mod}\,13)\end{align*}$$ 이므로 따라서 나머지는 $5$이다.

또한 $2^{11213}-1$이 $11$의 배수가 아님을 확인할 수 있다. 페르마의 작은 정리로부터 $2^{10}\equiv1\,(\text{mod}\,11)$이므로 $$\begin{align*}2^{11213}-1&\equiv[(2^{10})^{1121}\cdot2^{3}]-1\equiv[1^{1121}\cdot2^{3}]-1\\&\equiv2^{3}-1\equiv7\,(\text{mod}\,11)\end{align*}$$ 이고 따라서 $11$의 배수가 아니다.

(11213은 소수이고, $2^{11213}-1$은 소수이다. 이러한 소수를 메르센 소수(Mersenne primes)라고 한다.)

임의의 $n\in\mathbb{Z}$에 대하여, $15$는 $n^{33}-n$의 배수이다. 우선 $n^{33}-n=n(n^{32}-1)$이고

$n$이 $3$의 배수이면, $n(n^{32}-1)$은 $3$의 배수가 된다. 만약 $n$이 $3$의 배수가 아니면, 페르마의 작은 정리로부터 $n^{2}\equiv1\,(\text{mod}\,3)$이고, $n^{32}-1\equiv(n^{2})^{16}-1\equiv1^{16}-1\equiv0\,(\text{mod}\,3)$이 되어 $n^{32}-1$은 $3$의 배수이고 따라서 $n(n^{32}-1)$은 $3$의 배수이다.

$n$이 $5$의 배수이면, $n(n^{32}-1)$은 $5$의 배수가 된다. 만약 $n$이 $5$의 배수가 아니면, 페르마의 작은 정리로부터 $n^{4}\equiv1\,(\text{mod}\,5)$이고, $n^{32}-1\equiv(n^{4})^{8}-1\equiv1^{8}-1\equiv0\,(\text{mod}\,5)$이므로 $n^{32}-1$은 $5$의 배수이고 따라서 $n(n^{32}-1)$은 $5$의 배수이다.

이 사실로부터 $n(n^{32}-1)$은 $3$과 $5$의 배수이고 따라서 $15$의 배수이다. 

$G_{n}=\{m\in\mathbb{Z}_{n}-\{0\}\,|\,m\,\text{is not divisor 0 in}\,\mathbb{Z}_{n}\}$이라 하자. 그러면 $G_{n}$은 $n$을 법으로 하는 곱셈에 대해 군이 된다.

(1) 임의의 $a,\,b\in G_{n}$에 대하여, $ab\in G_{n}$이 됨을 보이자. 만약 $ab\notin G_{n}$이면, $c(\neq0)\in\mathbb{Z}_{n}$가 존재해서 $(ab)c=0$이고 $a(bc)=0$이다.

$b\neq0$이기 때문에 $b$는 $0$의 약수가 아니고, $c\neq0$이므로 $bc\neq0$이다. 또한 $a\neq0$, $bc\neq0$, $a(bc)=0$이므로 $a$는 $0$의 약수가 되는데 이는 $a\in G_{n}$에 모순이다.

결합법칙이 성립하는 것과 항등원이 존재하는 것은 분명하다. 이제 역원을 가짐을 보이자. $G_{n}=\{1,\,a_{1},\,\cdots,\,a_{r}\}$이라 하자. 임의의 $a\in G_{n}$에 대하여 $a1,\,aa_{1},\,\cdots,\,aa_{r}$은 서로 다른 원소들이다. $a\in G_{n}$이기 때문에, $a$는 $0$의 약수가 아니고 $(a_{i}-a_{j})=0$이 되고, 따라서 $a_{i}=a_{j}$이다. 이는 $a1=1$이거나 어떤 $a_{i}$에 대하여 $aa_{i}=1$임을 뜻하고 따라서 $a$는 역원을 가진다.(QED)

$n\in\mathbb{Z}^{+}$라 하자. $\phi:\,\mathbb{Z}^{+}\,\rightarrow\,\mathbb{Z}^{+}$를 $n$보다 작거나 같은 $n$과 서로소인 양의 정수들의 개수 $\phi(n)$으로 정의하자. 이 함수를 오일러-피 함수(Euler-phi-function)라고 하고 $\phi(1)=1$로 정의한다.

$12$보다 작거나 같은 $12$와 서로소인 수는 $1,\,5,\,7,\,11$이다. 그러므로 $\phi(12)=4$이다.

(오일러 정리) $\text{gcd}(a,\,n)=1$이라 하자. 그러면 $a^{\phi(n)}\equiv1\,(\text{mod}\,n)$이다.

$\text{gcd}(a,\,n)=1$이라 하자. 그러면 잉여류 $a+n\mathbb{Z}$는 $b<n$이고 $\text{gcd}(b,\,n)=1$인 정수 $b$를 포함하고 $a+n\mathbb{Z}=b+n\mathbb{Z}$이다. 그러면 $\mathbb{Z}/n\mathbb{Z}$에서 $(a+n\mathbb{Z})^{\phi(n)}\equiv(b+n\mathbb{Z})^{\phi(n)}$이고, $a^{\phi(n)}\equiv b^{\phi(n)}\,(\text{mod}\,n)$이다. $\text{gcd}(b,\,n)=1$이고 $b\in G_{n}$, $G_{n}$은 위수가 $\phi(n)$이므로 $b^{\phi(n)}\equiv1\,(\text{mod}\,n)$이고 따라서 $a^{\phi(n)}\equiv1\,(\text{mod}\,n)$이다.(QED)

$\phi(12)=4$이므로, $\text{gcd}(a,\,12)=1$인 임의의 $a$에 대하여 오일러 정리에 의해 $a^{4}\equiv1\,(\text{mod}\,12)$이다.

$m\in\mathbb{Z}^{+}$, $a\in\mathbb{Z}_{n}$, $\text{gcd}(a,\,m)=1$이라 하자. 그러면 임의의 $b\in\mathbb{Z}_{n}$에 대하여 방정식 $ax=b$는 유일한 해를 갖는다.

$a\in G_{m}$이므로, $a$는 곱셈역원을 갖고 따라서 $x=a^{-1}ax=a^{-1}b$이므로 $x=a^{-1}b$는 방정식 $ax=b$의 유일한 해이다.(QED)

참고자료:

A First Course in Abstract Algebra 7th edition, Fraleigh, Addison Wesley