# 정수론 Chapter 7.1 - Euler phi function



이 글의 내용은 성균관대학교 권순학 교수님의 2019년 4월 30일 수업 내용을 재구성한 것입니다.

## Definition: arithmetic function

정의역이 자연수인 함수를 arithmetic function이라고 부른다.

## Definition: multiplicative function

정의역이 자연수인 함수 \\(f\\)가 \\((m, n) = 1\\)인 모든 \\(m, n\\)에 대해 \\(f(mn) = f(m) f(n)\\)을 만족할 때,
함수 f를 multiplicative 하다고 한다.

### 예시: 자연수 n의 양의 약수의 개수

$$
d(n) = \\{\\textrm{n의 양의 약수의 개수}\\}
$$

로 정의하면 \\((m, n) = 1\\)일 때 \\(d(mn) = d(m) d(n)\\)이다.

#### 증명

$$
(m, n) = 1
\\\\ m = \\prod p_i^{a_i}
\\\\ n = \\prod q_j^{b_j}
$$

$$
mn = \\prod_i p_i^{a_i} \\prod_s q_j^{b_j}
$$

$$
d(mn) = \\prod_i (1 + a_i) \\prod_j (1 + b_j) = d(m) d(n)
$$

<!-- ### Example: 자연수 n의 양의 약수의 합 -->

## Remark: totally multiplicative function

정의역이 자연수인 함수 \\(f\\)가 모든 \\(m, n\\)에 대해 \\(f(mn) = f(m) f(n)\\)을 만족할 때,
함수 f를 totally multiplicative, 또는 completely multiplicative 하다고 한다.

### 예시: \\(f(n) = n\\)

$$
f(n) = n,
\\\\ \\forall m, n \;\; f(mn) = f(m) f(n)
$$

f는 totally multiplicative 한 함수이다.

## \\(\\phi(p) = p -1 \\Leftrightarrow p: \\textrm{prime}\\)

### \\(\\Leftarrow\\) 증명

$$
S = \\{ 0 \\le a \\lt n \\mid (a, p) = 1\\}
$$

\\(|S| = |\\{1, 2, \\dots , p-1 \\}| = p - 1\\)

### \\(\\Rightarrow\\) 증명

대우를 증명한다.

$$
S = \\{ 0 \\le a \\lt n \\mid (a, n) = 1\\}
$$

\\(n\\)이 소수가 아니라면, \\(|S| \\lt n - 1\\)이다.

## Theorem 7.3: \\(\\phi(p^a) = p^a - p^{a-1}\\)

$$
p: \\textrm{prime}
\\\\ a: \\textrm{a positive integer}
$$

### 증명

\\(a = 1\\)일 때는 자명하다.

$$
\\phi(p^a) = \\mid S \\mid
\\\\ S = \\{0 \\le j \\lt p^a \\mid (j, p^a) = 1 \\}
\\\\ S = \\{0 \\le j \\lt p^a \\mid (j, p) = 1 \\}
$$

\\(S\\)의 원소의 개수를 세는 것보다, \\(p^a\\)에서 \\(p\\)의 배수의 개수를 빼는 것이 더 쉽다.

$$
\\phi(p^a) = p^a - \\mid A \\mid
\\\\ A = \\{0 \\le j \\lt p^a \\mid (j, p) = p \\}
$$

$$
j \\in A \\Leftrightarrow j = 0, p, \\dots, (p^{a-1} - 1)p
$$

\\(p^{a-1}\\)개의 \\(j\\)가 있으므로,

$$
\\mid A \\mid = p^{a-1},
\\\\ \\phi(p^a) = p^a - p^{a-1}
$$

## Theorem 7.4: \\(\\phi(mn) = \\phi(m) \\phi(n) \\)

Euler \\(\\phi\\) 함수는 multiplicative 하다.

### 증명: \\(\\phi(mn) = |S\_{mn}| = |S_m \\times S_n|\\)

$$
\\theta: S_{mn} \\rightarrow S_m \\times S_n
\\\\ a \\longmapsto (a \\textrm{ mod } m, a \\textrm{ mod } n)
$$

#### \\(\\theta\\): well-defined

$$
a = q_1m + r_1 \;\; (r_1 = a \; (\\textrm{mod} \; m))
\\\\ a = q_2n + r_2 \;\;  (r_2 = a \; (\\textrm{mod} \; n))
\\\\ (a, m) = (m, r_1) = 1 \; \\Rightarrow r_1 \\in S_m
\\\\ (a, n) = (n, r_2) = 1 \; \\Rightarrow r_2 \\in S_n
$$

#### \\(\\theta\\): one-to-one

$$
\\theta(a)= \\theta(b)
\\\\ \\Rightarrow a \\equiv b \; (\\textrm{mod} \; m), \;\; a \\equiv b \; (\\textrm{mod} \; n)
\\\\ \\Rightarrow m \\mid a - b, \;\; n \\mid a - b
\\\\ \\Rightarrow mn \\mid a - b \;\; (\\because (m, n) = 1)
\\\\ \\Rightarrow a \\equiv b \; (\\textrm{mod} \; mn)
\\\\ \\Rightarrow a = b \\in S_{mn}
$$

#### \\(\\theta\\): onto

$$
\\forall (s, t) \\in S_{m} \\times S_n
$$

$$
\\\\ \\exists \; a \\in S_{mn} \;\; \\textrm{s.t.}
\\\\ a \\equiv s \; (\\textrm{mod} \; m)
\\\\ a \\equiv t \; (\\textrm{mod} \; n)
\\\\ \\because \\textrm{Chiniese remainder theorem}
$$

## Theorem 7.5: \\(\\phi(n) = n \\prod (1-{\\frac 1 {p_i^{a_i}}})\\)

$$
n = \\prod_i p_i^{a_i}
$$

### 증명

$$
\\phi(n)
$$

$$
= \\phi(p_1^{a_1}) \\phi(p_2^{a_2}) \\cdots \\phi(p_k^{a_k})
$$

$$
= (p_1^{a_1} - p_1^{a_1 - 1}) (p_2^{a_2} - p_2^{a_2 - 1}) \\cdots (p_k^{a_k} - p_k^{a_k - 1})
$$

$$
= n \\prod_i (1-{\\frac 1 {p_i^{a_i}}})
$$

## Definition: summation function

arithmetic function인 함수 \\(f\\)에 대하여

$$
F(n) = \\sum_{d \\mid n} f(d)
$$

일 때, 함수 \\(F\\)를 함수 \\(f\\)의 summation function이라고 한다.
이때 \\(d\\)는 \\(n\\)의 양의 약수이다.

## Theorem 7.7: \\(\\sum\_{d|n} {\\phi(d)} = n\\)

### 증명

$$
C_d =\\{ 0 \\le x \\lt n \\mid (x, n) = d \\}
$$

$$
0 \\le \\forall x \\lt n, \;\; d = (x, n)
\\\\ \\Rightarrow x \\in C_d
$$

이를 만족하는 \\(d\\)는 유일하다.

#### \\( \\{0 \\le x \\lt n\\} = \\bigcup C_d \\)

##### 예시: \\(n = 6\\)

$$
C_1 = \\{1, 5\\}, C_2 = \\{2, 4\\}, C_3 = \\{3\\}, C_6 = \\{6\\}
$$

$$
C_1 \\cup C_2 \\cup C_3 \\cup C_6 = \\{1, 2, 3, 4, 5, 6\\}
$$

#### \\( n =\\sum\_{d \\mid n} \\mid C_d \\mid \\)

$$
\\because \\{0 \\le x \\lt n\\} = \\bigcup C_d
$$

#### \\( |C_d| = \\phi(\\frac n d) \\)

##### 증명

$$
S_{\\frac n d} = \\{0 \\le y \\lt {\\frac n d} \\mid (y, \\frac n d) = 1 \\}
$$

\\(S\\)는 reduced residue system modulo \\( \\frac n d \\) 이다.

$$
f: C_d \\rightarrow S\_{\\frac n d}
\\\\ x \\mapsto {\\frac x d}
\\\\ g: S\_{\\frac n d} \\rightarrow C_d
\\\\ y \\mapsto {yd}
$$

\\(f\\)와 \\(g\\)는 역함수 관계에 있다. 따라서 \\(\\mid C_d \\mid = \\mid S\_{\\frac n d} \\mid = \\phi({\\frac n d}) \\)

##### \\(f\\)의 Well-definedness 증명

$$
x \\in C_d
$$

$$
\\Rightarrow (x, n) = d
$$

$$
\\Rightarrow (\\frac x d, \\frac n d) = 1
$$

$$
\\Rightarrow \\frac x d \\in S_{\\frac n d}
$$

#### \\( \\sum\_{d \\mid n} \\phi(\\frac n d) = \\sum\_{d \\mid n} \\phi(d)\\)

##### 예시: \\(n = 6\\)

$$
\\{1, 2, 3, 6\\} = \\{6, 3, 2, 1\\}
$$

#### \\( n =\\sum\_{d \\mid n} C_d = \\sum\_{d \\mid n} \\phi(\\frac n d) = \\sum\_{d \\mid n} \\phi(d)\\)