이 글의 내용은 성균관대학교 권순학 교수님의 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)
$$
증명
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 $$