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