군론(group theory)를 이용한 정수론의 정리 증명

정수론에서 합동(modular)의 개념을 정의하고 나서 바로 배우는 세 가지의 정리가 있다. 이들은 각각 페르마의 소정리(Fermat's little theorem), 오일러의 정리(Euler's theorem), 그리고 윌슨의 정리(Wilson's theorem)를 말하는데, 이 정리를 기반으로 합동식에 대한 다양한 결론를 이끌어 낼 수 있다. 이 세 가지 정리의 증명은 합동식의 성질을 이용해서 증명할 수도 있지만, 대수학에서의 군(group)의 성질을 이용함으로써 단 몇 줄로도 증명이 가능하다. 이를 자세히 살펴 보면 다음과 같다.

$$

우선 세 양의 정수 $a,b,m$에 대하여, $a$와 $b$가 모두 $m$과 서로소(coprime)라 하자. 그러면 정수 $x_1,y_1,x_2,y_2$가 존재하여 $$1=a{x}_1+m{y}_1,1=b{x}_2+m{y}_2$$ 을 만족한다 따라서 위 두 식을 변변끼리 곱해 주면 $$1=(a{x}_1+m{y}_1)(b{x}_2+m{y}_2)=ab{x}_1{x}_2+m(a{x}_1{y}_2+b{x}_2{y}_2+m{y}_1{y}_2)$$ 따라서 $ab$ 또한 $m$과 서로소가 된다. 이 사실로부터 $m$과 서로소이고 $m$보다 작은 양의 정수들의 집합은 곱셈에 의해 군(group)을 이룬다는 사실을 알 수 있다. 특히 $p$가 소수라면, 집합 $\{1,2,\dots ,p-1\}$은 곱셈에 의해 군을 이룬다.

$$

이제 이 사실을 바탕으로 위에서 언급한 세 가지 정리들을 각각 증명해 보자.

$$

정리. 페르마의 소정리(Fermat's little theorem)

$p$가 소수라 하자. 그러면 $p$의 배수가 아닌 모든 양의 정수 $a$에 대하여 $a^{p-1}\equiv 1(\mathrm{mod}p)$가 성립한다.

$$

증명. $p$가 소수이기 때문에, $p$의 배수가 아닌 모든 정수들은 $p$와 서로소이다. 따라서 집합 $G=\{1,2,\dots ,p-1\}$은 곱셈에 대하여 군을 이룬다. 그러면 라그랑주 정리(Lagrange's theorem)에 의해서 $G$의 모든 원소들의 차수(order)는 $p-1$을 나눠야 한다. 따라서 $p$의 배수가 아닌 모든 정수 $a$에 대하여 $a^{p-1}\equiv 1(\mathrm{mod}p)$임을 알 수 있다. .

$$

정리. 오일러의 정리(Euler's theorem)

두 양의 정수 $a$와 $m$이 서로소라 하자. 그리고 $\varphi (m)$을 $m$과 서로소이고 $m$보다 작은 양의 정수의 개수로 정의하자. 그러면 $a^{\varphi (m)}\equiv 1(\mathrm{mod}m)$이 성립한다.

$$

증명. $m\ge 2$라 가정하자. 그러면 $m$과 서로소인 모든 양의 정수들의 집합은 곱셈에 의해 군(group)을 이룬다. 이 군을 $G$라고 하면 $G$ 차수는 $\varphi (m)$이다. 그러면 라그랑주 정리(Lagrange's theorem)에 의해서 $G$의 모든 원소들의 차수(order)는 $\varphi (m)$을 나눠야 한다. 따라서 $m$과 서로소인 모든 양의 정수$a$에 대하여 $a^{\varphi (m)}\equiv 1(\mathrm{mod}m)$임을 알 수 있다. .

$$

참고. 라그랑주의 정리를 이용하지 않고도 오일러의 정리(따라서 페르마의 소정리)를 직접 증명하는 것이 가능하다.

$$

$m$과 서로소인 모든 양의 정수들로 이루어진 군을 $G$라 하자. 위에서 살펴 보았듯이 $G$의 차수는 $\varphi (m)$이다. 또한 $G$의 임의의 원소 $a$에 대하여, 다음과 같이 정의된 사상 $g\mapsto ag$는 $G$의 자기동형사상(automorphism)이 된다. 따라서 $G$의 모든 원소들의 곱은 $aG$의 모든 원소들의 곱과 같다. 즉, $$\prod _{g\in G}g\equiv \prod _{g\in G}(ag)\equiv a^{\varphi (m)}\prod _{g\in G}g(\mathrm{mod}m)$$ 이 성립한다. 이제 위 합동식의 양변에 $\prod _{g\in G}g$의 역원을 곱해 주면, $1\equiv a^{\varphi (m)}(\mathrm{mod}m)$임을 알 수 있다..

$$

정리. 윌슨의 정리(Wilson's theorem)

임의의 소수 $p$에 대하여, $(p-1)!\equiv -1(\mathrm{mod}p)$가 성립한다.

$$

증명. 집합 $G=\{1,2,\dots ,p-1\}$은 곱셈에 대하여 군을 이룬다. 따라서 이 집합의 모든 원소 $x$는 역원 $x^{-1}$를 가진다. 따라서 집합 $G$를 $\{x,x^{-1}\}$ 형태의 부분집합들로 분할할 수 있다. 이 때, 이 부분집합의 모든 원소들의 곱은 $1$이다. 또한 각각의 부분집합들은 $x=x^{-1}$가 아니라면, 정확히 두개의 원소를 가진다. 만약 $x=x^{-1}$인 경우, $x^2\equiv 1(\mathrm{mod}p)$여야 하고, $p$가 소수라는 사실로부터 $x\equiv \pm 1(\mathrm{mod}p)$라는 결론을 얻는다. 이제 $(p-1)!$은 $\{1\}$과 $\{-1\}$, 그리고 $\{x,x^{-1}\}$ 형태의 부분집합들의 모든 원소들의 곱이고, 이는 $-1$과 같다. 그러므로 $(p-1)!\equiv -1(\mathrm{mod}p)$가 성립한다. .

$$

참고. 위와 같은 논리를 적용하면, 임의의 양의 정수 $m$에 대하여 $m$과 서로소이고 $m$보다 작은 모든 양의 정수들의 곱은 법 $m$에 대하여 $1$ 또는 $-1$과 합동임을 보일 수 있다.

$$

우선 $m$이 $1$이거나 $2$인 경우는 위 명제가 자명하게 성립하므로, $m\ge 2$라 가정하자. 이제 $m$과 서로소인 모든 양의 정수들로 이루어진 군을 $G$라 하면 $G$의 모든 원소 $x$는 역원 $x^{-1}$를 가지므로 집합 $G$를 $\{x,x^{-1}\}$ 형태의 부분집합들로 분할할 수 있다. 이제 위의 논의와 같이 $\{x,x^{-1}\}$이 한원소집합(singleton set)인 경우만 따로 고려해 주면 충분하다. 만약 어떤 $y\in G$가 존재하여 $y^2\equiv 1(\mathrm{mod}m)$이라 하자. 그러면 $(-y{)}^2\equiv 1(\mathrm{mod}m)$이 성립한다. 또한 $y$와 $-y$는 서로 같은 원소일 수 없다. 만약 $y\equiv -y(\mathrm{mod}m)$이라면, $2y\equiv 0(\mathrm{mod}m)$가 되어 $2y$가 $m$의 약수가 되어야 하는데, $m\ge 3$을 가정했으므로 $y$와 $m$이 서로소라는 사실에 모순이 발생하기 때문이다. 또한 집합 $\{y,-y\}$의 모든 원소의 곱은 $-y^2\equiv -1(\mathrm{mod}m)$이다.

$$

이제 군 $G$는 $x^2\not\equiv 1(\mathrm{mod}m)$인 경우 $\{x,x^{-1}\}$ 형태의 부분집합과, $y^2\equiv 1(\mathrm{mod}m)$인 경우 $\{y,-y\}$ 형태의 부분집합들로 분할이 가능하다. 따라서 $G$의 모든 원소의 곱은 $1$ 또는 $-1$이다.