[정수론] 오일러의 정리, 페르마의 소정리, 중국인의 나머지 정리, 윌슨의 정리

 

정수론 4대 정리: 오일러의 정리, 페르마의 소정리, 중국인의 나머지 정리, 윌슨의 정리

 

Generated by GPT-4

 

정수론 4대정리에 대해 간단히 정리한다. 

자세한 내용이나 증명은 이후 포스팅 할 예정이다.

여기서는 정리의 내용과 간단한 활용방법에 대해 알아본다.

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

정수 $a$, 소수 $p$에 대하여 다음이 성립한다.
\[ a^p \equiv p \pmod{p} \]

$a$가 $p$로 나누어지지 않는 경우에(즉 $p \nmid a$, $\gcd(p, a)=1$) 다음이 성립한다.
\[ a^{p-1} \equiv 1 \pmod{p} \]

 

역은 성립하지 않는다. 즉, 소수가 아닌 합성수 $p$인 경우에도 $a^{p-1} \equiv 1 \pmod{p}$인 경우가 존재한다.

이런 $p$를 유사소수(pseudoprime) 또는 페르마 유사소수(Fermat pseudoprime)라고 부른다.

페르마 유사소수 중에서도 ($p$가 합성수임에도) 모든 $a$에 대하여 $a^{p} \equiv a \pmod{p}$를 만족하는 $p$를 카마이클 수(Carmichael number)라고 한다. 따라서 페르마의 소정리 만으로는 소수 판정이 불가능하다.

단, 페르마의 소정리의 대우 명제를 이용하여 합성수 판정에 사용할 수 있다.

오일러의 정리 (Euler's theoerm)

$n \ge 1$이고 $\gcd(a, n)=1$이면, $a^{\phi(n)} \equiv 1 \pmod{n}$ 이다.

이때 $\phi(n)$은 $1$부터 $n$까지의 정수 중 $n$과 서로소인 정수의 개수를 구하는 오일러 피 함수이다.

 

소수 $p$에 대하여 $\phi(p)=p-1$이므로, 페르마의 소정리는 오일러의 정리의 특수한 경우이다.

 

중국인의 나머지 정리(Chinese remainder theorem, CRT)

$1$보다 큰 $k$개의 정수 $n_1, n_2, \dots, n_k$가 쌍마다 서로소($\gcd(n_i, n_j) = 1$)이고 $N = n_1 n_2 \cdots n_k$라 하자. 이때 다음 연립 합동식
\begin{align} x &\equiv a_1 \pmod{n_1} \\ x &\equiv a_2 \pmod{n_2} \\ \quad \vdots \\ x &\equiv a_k \pmod{n_k} \end{align}
은 $\mod N$에 대하여 유일한 해를 갖는다.

연립합동식의 해의 존재성, 유일성 모두 보장하는 정리이다.

중국인의 나머지 정리 그 자체는 해를 구하는 방법을 알려주지 않는다.

그러나 이 정리를 증명하는 과정과 유사한 방식으로 해를 구할 수 있다.

 

1. $N = n_1 n_2 \cdots n_k$를 구한다.
2. (부분 곱) 각 $i$에 대하여 $N_i = \cfrac{N}{n_i}$를 구한다.
3. (역원) $N_i x \equiv 1 \pmod{n_i}$를 만족하는 해를 $M_i$라 한다. (즉, $N_i M_i \equiv 1 \pmod{n_i}$)
4. (해) $x = \sum_{i=1}^{k} a_i N_i M_i$ 이다.

모듈러가 서로소가 아닌 경우에는 CRT를 직접 적용할 수 없다. (해가 존재하지 않을 수도 있다.)

$gcd(n_i, n_j) \neq 1$인 경우에는 두 식을 합쳐서 새로운 합동식을 만들어낸다.

 

중국인의 나머지 정리를 활용하여 모듈러가 큰 합동식의 해도 구할 수 있다.

$N = n_1 n_2 \cdots n_k$이고 $\gcd(n_i, n_j)=1$이면 다음이 성립한다.
\[ f(x) \equiv 0 \pmod{N} \iff f(x) \equiv 0 \pmod{n_i} \text{ for all }1 \le i \le k \]

합동식 $17x \equiv 9 \pmod{276}$은 직접 풀지 않고 CRT를 이용하여 풀 수 있다.

$276 = 3 \cdot 4 \cdot 23$이기 때문에 

\[ 17x \equiv 9 \pmod{3}, \quad 17x \equiv 9 \pmod{4}, \quad 17x \equiv 9 \pmod{23}\]

즉

\[ x \equiv 0 \pmod{3}, \quad x \equiv 1 \pmod{4}, \quad x \equiv 10 \pmod{23} \]

의 연립합동식을 푸는 것과 동일하다. 해는 $x \equiv 309 \equiv 33 \pmod{276}$이다. (풀이 생략)

윌슨의 정리 (Wilson's theorem)

$2$ 이상의 자연수 $p$가 소수이기 위한 필요충분조건은 $(p-1)! \equiv -1 \pmod{p}$ 이다.

 

소수판별에 사용할 수 있다. 그러나 팩토리얼 계산보다는 에라토스테네스의 체를 이용하는 편이 낫다.

윌슨의 정리를 이용하여 특수한 합동식의 해를 구할 수 있다.

예를 들어, "홀수인 소수 $p$에 대하여 $x^2 + 1 \equiv 0 \pmod{p}$의 해가 존재하기 위한 필요충분조건은 $p \equiv 1 \pmod{4}$이다." 등에 활용된다.