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

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)\)