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