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