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