정수론에서 합동_(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 = ax_1 + my_1, \quad 1 = bx_2 + my_2 \] 을 만족한다 따라서 위 두 식을 변변끼리 곱해 주면 \[ 1 = (ax_1 + my_1)(bx_2 + my_2) = abx_1x_2 + m(ax_1y_2 + bx_2y_2 + my_1y_2) \] 따라서 $ab$ 또한 $m$과 서로소가 된다. 이 사실로부터 $m$과 서로소이고 $m$보다 작은 양의 정수들의 집합은 곱셈에 의해 군을 이룬다는 사실을 알 수 있다. 특히 $p$가 소수라면, 집합 $\{1,\,2,\, \ldots,\, p-1\}$은 곱셈에 의해 군을 이룬다.

$ $

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

$ $

$ $

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

$ $

$ $

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

$ $

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

$ $

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

$ $

$ $

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

$ $

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

$ $

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

$ $

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