이 글의 내용은 성균관대학교 권순학 교수님의 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)
$$
정의역이 자연수인 함수 $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)\)