# 정수론 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 $$