정수론 Chapter 6.3 - Euler's Theorem
이 글의 내용은 성균관대학교 권순학 교수님의 2019년 4월 18일 수업 내용을 재구성한 것입니다.
Reduced residue system (RRS) {#rrs}
$$ n: \\textrm{자연수} $$
$$ S_n = \\{0 \\le a \\le n\\ \\mid \\gcd(a, n) = 1 \\} $$
집합 $T$가 \(T \\equiv S_n \; (\\textrm{mod} \; n)\)을 만족할 때, $T$를 Reduced residue system modulo n이리고 부른다
예시 {#rrs-example}
$$ n = 4 \\\\ \\Rightarrow T = \\{1, 3\\}, \\{-1, 1\\}, \\{5, 8\\} $$
$$ n = 5 \\\\ \\Rightarrow T = \\{1, 2, 3, 4\\}, \\{-2, -1, 1, 2\\} $$
Remark: \(\\gcd(a, n) = 1\)이면 $aT$도 RRS이다
증명
1. 모두 다르다 \((\\textrm{mod} \; n)\)
$$ ar_i \\equiv ar_j (\\textrm{mod} \; n) \\\\ \\Leftrightarrow n \\mid (ar_i - ar_j) \\\\ \\Leftrightarrow n \\mid a(r_i - r_j) \\\\ \\Leftrightarrow n \\mid (r_i - r_j) \;\;\; (\\because \\gcd(a, n) = 1) \\\\ \\Leftrightarrow r_i \\equiv r_j \;\; (\\textrm{mod} \; n) \\\\ \\Leftrightarrow i = j \;\;\; (\\because r_j, r_i \\in S_n) $$
2. \(\\gcd(ar_i, n) = 1\)
$$ \\gcd(a, n) = 1 $$
$$ \\gcd(r_i, n) = 1 \;\;\; (\\because r_i \\in S_n) $$
예시: \(n = 8\)
$$ T = \\{1, 3, 5, 7\\} $$
a = 2
$$ aT = \\{2, 4, 6, 8\\} \\equiv \\{0, 2, 4, 6\\} \; (\\textrm{mod} \; 8) $$
$$ \\therefore aT \; \\textrm{is not a RRS modulo} \; 8 $$
a = 3
$$ aT = \\{3, 9, 15, 21\\} \\equiv \\{1, 3, 5, 7\\} \; (\\textrm{mod} \; 8) $$
$$ \\therefore aT \; \\textrm{is a RRS modulo} \; 8 $$
The Euler \(\\phi\) function {#euler-phi-function}
$$ \\phi(n) = |S_n| \;\; \\textrm{where} \; S_n \;\\textrm{is a RRS modulo n} $$
예시 {#euler-phi-function-examples}
$$ \\phi(1) = |\\{0\\}| = 1 $$
$$ \\phi(2) = |\\{1\\}| = 1 $$
$$ \\phi(3) = |\\{1, 2\\}| = 2 $$
$$ \\phi(7) = |\\{1, 2, 3, 4, 5, 6\\}| = 6 $$
$$ \\phi(8) = |\\{1, 3, 5, 7\\}| = 4 $$
The Euler's Theorem
\(\\gcd(a, n) = 1\)인 자연수 $a$에 대하여,
$$ a^{\\phi(n)} \\equiv 1 \; (\\textrm{mod} \; n) \\\\ \\textrm{where }\\phi(n) \\textrm{ is number of elements in RRS} $$
증명 {#proof-of-eulers-theorem}
$$ T: \\textrm{a RRS} \; (\\textrm{mod} \; n) $$
$$ T \\equiv aT \; (\\textrm{mod} \; n) $$
$$ \\Rightarrow r_1 r_2 \\cdots r_k \\equiv a^{k} r_1 r_2 \\cdots r_k \;\;\; where \; k = \phi(n) $$
$$ \\Rightarrow n \\mid (a^k - 1) r_1 r_2 \\cdots r_k $$
$$ \\Rightarrow n \\mid (a^{\\phi(n)} - 1) \;\;\;(\\because r_i \\in T) $$
$$ \\Rightarrow a^{\\phi(n)} \\equiv 1 \; (\\textrm{mod} \; n) $$
Collorary: The Fermat's Little Theorem
$n$이 소수인 경우, \(a^{\\phi(n)} \\equiv a^{p-1} \\equiv 1 \; (\\textrm{mod} \; n) \)