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