정수론 Chapter 6.1 - Wilson's Theorem and Fermat's Little Theorem

이 글의 내용은 성균관대학교 권순학 교수님의 2019년 4월 9일, 11일 수업 내용을 재구성한 것입니다.

Wilson's Theorem

소수 $p$에 대하여,

$$ (p - 1)! \equiv -1 (\textrm{mod}\ p) $$

Lemma: \(a \\bar{a} \\equiv 1 (\textrm{mod}\ p)\)인 \(\\bar{a}\) 존재

소수 p에 대해 \(S = \\{1, 2, 3, ..., p - 1\\}\) 는 congruent residue system \( (\textrm{mod}\ p)\)이다.

S에 속한 임의의 원소 $a$에 대해, \(a \\bar{a} \\equiv 1 (\textrm{mod}\ p)\)인 \(\\bar{a}\)가 존재한다.

증명

$$ \\exists \; x \\in Z \;\; \\textrm{s.t.} \;\; ax \\equiv 1 (\textrm{mod}\ p) \\\\ x = qp + \\bar{a} \; (1 \\leq \\bar{a} < p) $$

$$ ax \\equiv aqp + a \\bar{a} \\equiv a \\bar{a} \\equiv 1 (\textrm{mod}\ p) $$

이러한 \(\\bar{a}\)는 유일하다.

증명

\(p = 2\)인 경우 \(1! \\equiv -1 (\textrm{mod}\ 2) \)

\(p \neq 2\)인 경우 $1$부터 \(p - 1\)까지의 짝수 개의 숫자 중 두 개씩 묶여서 \(a \bar{a} \\equiv 1 (\textrm{mod}\ p)\)가 되고 \(1, p - 1\)만 남는다.

$$ (p-1)! \\equiv 1 (p - 1) \\equiv -1 (\textrm{mod}\ p) $$

역

역도 성립한다.

$$ (n-1)! \\equiv -1 (\textrm{mod}\ n) $$

이면 $n$은 소수이다.

역의 증명

n이 합성수라고 가정하자. 그러면 \( n = ab \;\;(1 < a, b < n) \)로 표현할 수 있다. $a < n$이므로, \(a \\mid (n - 1)!\)이다. 조건에서 \(a \\mid (n - 1)! + 1\)이므로, \(a \\mid (n - 1)! + 1 - (n - 1)! \\Rightarrow a \\mid 1 \) 이므로 모순이다. 따라서 n은 소수이다.

Fermat's Little Theorem

소수 $p$와 \(p \\nmid a\)인 정수 $a$에 대해서

$$ a^{p-1} \\equiv 1 (\textrm{mod}\ p) $$

Lemma: \( S \equiv aS (\textrm{mod}\ p)\) if \(\\gcd(a, p) = 1\)

소수 p에 대해 \(S = \\{1, 2, 3, ..., p - 1\\}\) 는 congruent residue system \( (\textrm{mod}\ p)\)이다. \(\\gcd(a, p) = 1\)이면, \( aS = \\{ ai \\mid i \in S \\} \) 도 congruent residue system \( (\textrm{mod}\ p)\)이다.

증명

이를 증명하기 위해선, modulo $p$로 봤을 때 $ aS $의 원소가 모두 서로 다르고 어느 것도 0이 아니라는 것을 보이면 된다.

1. 모두 서로 다르다

$$ ai = aj (\textrm{mod}\ p)\\\\ \\Rightarrow p \\mid a (i - j) \\\\ \\Rightarrow p \\mid (i - j) \; (\\because \\gcd(a, p) = 1)\\\\ \\Rightarrow i = j \; (\\because i,\; j < p) $$

2. 어느 것도 0이 아니다

$$ ai \equiv 0 (\textrm{mod}\ p) \\\\ \\Rightarrow p \\mid ai \\\\ \\Rightarrow p \\mid i \; (\\because \\gcd(a, p) = 1) $$

이는 $ i < p $에 모순이다. 따라서 \(ai \not\equiv 0 (\textrm{mod}\ p) \)

증명

$$ S \\equiv aS \; (\textrm{mod}\ p) $$

이므로, 원소를 모두 곱한 값도 \( (\textrm{mod}\ p) \)로 보면 같다.

$$ (p - 1)! \\equiv a^{p-1} (p-1)! \; (\textrm{mod}\ p) $$

$$ \\Rightarrow p \\mid (p - 1)! (a^{p-1} - 1) $$

$$ \\Rightarrow p \\mid (a^{p-1} - 1) $$

$$ \\Rightarrow a^{p-1} \\equiv 1 \; (\textrm{mod}\ p) $$

Remark: 합성수 \(n \neq 4 \)에 대해 \((n - 1)! \\equiv 0 \; (\textrm{mod}\ n) \)

증명

case 1. \( n \\neq p^2 \)

$$ \\exists \; a, b \;\; \\textrm{s.t.} \;\; n = ab, 1 \lt a \lt b \lt n $$

$$ (n - 1)! \\equiv 1 \times 2 \times \ldots \times a \times \ldots \times b \times \ldots \times (n - 1) \\equiv 0 \; (\textrm{mod}\ ab) $$

case 2. \( n = p^2 \)

$$ (n - 1)! \\equiv 1 \times 2 \times \ldots \times p \times \ldots \times 2p \times \ldots \times (n - 1) \\equiv 0 \; (\textrm{mod}\ p^{p-1}) $$

\((n - 1)!\)을 전개하면 $p$가 \(p - 1\)번 나타난다. \( p \\ge 3\)일 때,

$$ (n - 1)! \\equiv 0 \; (\textrm{mod}\ p^{2}) $$

Theorem 6.4

소수 $p$와 임의의 정수 $a$에 대하여

$$ a^{p} \\equiv a \; (\textrm{mod}\ p) $$

증명

case 1. \(\\gcd(a, p) = 1\)

$$ a^{p-1} \\equiv 1 \; (\textrm{mod}\ p) $$

$$ \\Rightarrow a^{p} \\equiv a \; (\textrm{mod}\ p) $$

case 2. \(\\gcd(a, p) = p\)

$$ a^{p} \\equiv 0 \\equiv a \; (\textrm{mod}\ p) $$

Theorem 6.5

소수 $p$와 \( p \\nmid a \)인 정수 $a$에 대하여 \(a^{p-2}\)는 $p$의 arithmetic inverse이다.

증명

\( p \\nmid a \)이므로, Fermat's Little Theorem에 의해 \(a a^{p-2} \\equiv a^{p-1} \\equiv 1 \; (\textrm{mod}\ p) \)

The Pollard \(p - 1\) Factorization Method

일반적으로 소인수분해는 매우 어렵다. 하지만 특수한 경우엔 쉽게 인수분해를 할 수 있는데, 이때 The Pollard \(p - 1\) Factorization Method가 쓰인다.

\(\\exists \; p\) : unknown prime s.t. \( p \\mid n \)

만약 \( p - 1 \)이 작은 소수들의 곱인 경우, \( p - 1 \\mid k! \)을 만족하는 작은 $k$를 선택할 수 있다.

$$ N \\equiv 2^{k!} - 1 \; (\textrm{mod}\ n) \;\; (0 \\le N \lt n) $$

$$ 2^{k!} \\equiv 2^{(p-1)q} \\equiv 1^{q} \\equiv 1 \; (\textrm{mod}\ p) $$

$$ \\Rightarrow p \\mid 2^{k!} - 1 = Qn + N $$

$$ \\Rightarrow p \\mid N \;\; (\\because p \\mid n) $$

$$ \\Rightarrow p \\mid \\gcd(N, n) $$

예시: $5157437$의 소인수분해

$$ n = 5157437 \\\\ r_1 = 2 \; (\textrm{mod}\ n) \\\\ r_2 \\equiv r_1^2 \\equiv 4 \; (\textrm{mod}\ n) \\\\ r_3 \\equiv r_2^3 \\equiv 64 \; (\textrm{mod}\ n) \\\\ r_4 \\equiv r_3^4 \\equiv 1304905 \; (\textrm{mod}\ n) \\\\ r_5 \\equiv r_4^5 \\equiv 404913 \; (\textrm{mod}\ n) \\\\ r_6 \\equiv r_5^6 \\equiv 2157880 \; (\textrm{mod}\ n) \\\\ r_7 \\equiv r_6^7 \\equiv 4879227 \; (\textrm{mod}\ n) \\\\ r_8 \\equiv r_7^8 \\equiv 4379778 \; (\textrm{mod}\ n) \\\\ r_9 \\equiv r_8^9 \\equiv 4381440 \; (\textrm{mod}\ n) $$

각 단계에서, \( \\gcd(r_k - 1, n) \)을 계산하면 \( k = 9 \)일 때, \( \\gcd(r_9 - 1, n) = 2269 \)이다.

$$ \\therefore 2269 \\mid n $$