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