[현대대수학-환, 체론] 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