数論的関数
$\newcommand{\N}{\mathbb{N}}$ $\newcommand{\Z}{\mathbb{Z}}$ $\newcommand{\Q}{\mathbb{Q}}$ $\newcommand{\R}{\mathbb{R}}$ $\newcommand{\C}{\mathbb{C}}$ $\newcommand{\LCM}{\mathrm{LCM}}$ $\newcommand{\abs}[1]{\left\lvert#1\right\rvert}$ $\newcommand{\wenvert}[1]{\left\lvert\left\lvert#1\right\rvert\right\rvert}$ $\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}$ $\newcommand{\mathmod}[1]{\ \left(\mathrm{mod}\ #1\right)}$
正の整数に対して定義される関数を数論的関数という。本記事では、主要な数論的関数の基本的な性質および加法的関数と乗法的関数の概念について解説する。 数論的関数についてより詳しいことは、以下の項目を参照。
素因数の個数
正の整数 $N$ に対して $N$ の相異なる素因数の個数を $\omega(N)$, $N$ の重複も含めた素因数の個数を $\Omega(N)$ であらわす。 素因数分解の一意性から、ひとつの正の整数に対して、こうした素因数の個数は一意的に定まるので $\omega(N), \Omega(N)$ は数論的関数を定める。 $$N=p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r} (e_1, e_2, \ldots, e_r>0)$$ と素因数分解すると $$\omega(N)=r, \Omega(n)=e_1+e_2+\cdots +e_r$$ が成り立つ。
定理1.1
正の整数 $m, n$ に対し、$\Omega(mn)=\Omega(m)+\Omega(n)$. さらに $\gcd(m, n)=1$ ならば $\omega(mn)=\omega(m)+\omega(n)$.
Proof.
$$m=p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r}, n=p_1^{f_1} p_2^{f_2} \cdots p_r^{f_r}$$ と素因数分解すると（$e_i, f_j$ は $0$ でもよい） $$\begin{split} \Omega(mn)= & \Omega(p_1^{e_1+f_1}p_2^{e_2+f_2}\cdots p_r^{e_r+f_r}) \\ = & (e_1+f_1)+(e_2+f_2)+\cdots +(e_r+f_r) \\ = & (e_1+e_2+\cdots +e_r)+(f_1+f_2+\cdots +f_r)\\ = & \Omega(m)+\Omega(n). \end{split}$$
また $$m=p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r}, n=q_1^{f_1} q_2^{f_2} \cdots q_s^{f_s} (e_1, e_2, \ldots, e_r, f_1, f_2, \ldots, f_s>0)$$ と素因数分解すると、$\gcd(m, n)=1$ ならば $p_1, p_2, \ldots, p_r, q_1, q_2, \ldots, q_s$ は相異なる素数だから $$\omega(mn)=\omega(p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}q_1^{f_1} q_2^{f_2} \cdots q_s^{f_s})=r+s=\omega(m)+\omega(n).$$
□約数関数
$$d_k(N)=\sum_{d\mid N} d^k, d(N)=d_0(N), \sigma(N)=d_1(N)$$ とおくと $d(N)$ は $N$ の約数の個数、$\sigma(N)$ は $N$ の約数の総和となる。 $d_k(N)$ を約数関数という。$\sigma(N)$ は約数総和関数ということもある。なお $k$ は負の値や整数以外の実数、複素数の値をとってもよい。約数関数は次のようにして素因数分解から求められる。
$\sigma(N)$ について詳しいことは約数総和関数の記事も参照。
定理2.1
$$N=p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r}$$ と素因数分解すると $$d_k(N)=\prod_{i=1}^r d_k(p_i^{e_i})=\left\{\begin{array}{cl}\prod_{i=1}^r \frac{p_i^{k(e_i+1)}-1}{p_i^k-1} & (k\geq 1)\\ \prod_{i=1}^r (e_i+1) & (k=0)\end{array}\right.$$ が成り立つ。
Proof.
素因数分解の一意性から $$\begin{split} d_k(N)= & \sum_{d\mid N} d^k \\ = & \sum_{0\leq f_i\leq e_i (1\leq i\leq k)} p_1^{kf_1} p_2^{kf_2} \cdots p_r^{kf_r} \\ = & \prod_{i=1}^r \sum_{f_i=0}^{e_i} p_i^{kf_i} \\ \end{split}$$ より $$d_k(N)=\left\{\begin{array}{cl}\prod_{i=1}^r \frac{p_i^{k(e_i+1)}-1}{p_i^k-1} & (k\geq 1)\\ \prod_{i=1}^r (e_i+1) & (k=0)\end{array}\right.$$ が成り立つ。
□定理2.2
$\gcd(m, n)=1$ ならば $d_k(mn)=d_k(m)d_k(n)$.
Proof.
$$m=p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r}, n=q_1^{f_1} q_2^{f_2} \cdots q_s^{f_s} (e_1, e_2, \ldots, e_r, f_1, f_2, \ldots, f_s>0)$$ と素因数分解すると、$\gcd(m, n)=1$ ならば $p_1, p_2, \ldots, p_r, q_1, q_2, \ldots, q_s$ は相異なる素数だから $$\begin{split}d_k(mn)= & d_k(p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}q_1^{f_1} q_2^{f_2} \cdots q_s^{f_s}) \\ = & \prod_{i=1}^r d_k(p_i^{e_i}) \prod_{j=1}^s d_k(q_j^{f_j}) \\ = & d_k(m)d_k(n). \end{split}$$
□定理2.3
$$N=p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r}$$ と素因数分解すると $$\frac{d_k(N)}{N^k}=d_{-k}(N)=\prod_{i=1}^r \sum_{g_i=0}^{e_i} p_i^{-kg_i} =\left\{\begin{array}{cl}\prod_{i=1}^r \frac{1-p_i^{-k(e_i+1)}}{1-p_i^{-k}} & (k\neq 0)\\ \prod_{i=1}^r (e_i+1) & (k=0)\end{array}\right.$$ が成り立つ。
Proof.
定理2.1から $$\begin{split} \frac{d_k(N)}{N}= & \prod_{i=1}^r \frac{\sum_{f_i=0}^{e_i} p_i^{kf_i}}{p_i^{ke_i}} \\ = & \prod_{i=1}^r \sum_{f_i=0}^{e_i} p_i^{k(f_i-e_i)} \\ = & \prod_{i=1}^r \sum_{g_i=0}^{e_i} p_i^{-kg_i} \\ = & d_{-k}(N) \end{split}$$ が成り立つ。
□定理2.4
$k$ が実数で $M\mid N$ かつ $M<N$ のとき $$d_k(M)<d_k(N)$$ が成り立つ。
Proof.
$$M=p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r}, N=p_1^{f_1} p_2^{f_2} \cdots p_r^{f_r}$$ と素因数分解すると、$M\mid N$ より 各 $i$ について $0\leq e_i\leq f_i$ が成り立つ。 また $M<N$ だから $e_j<f_j$ となる $j$ が存在する。よって各 $i$ について $$1+p_i^k+\cdots +p_i^{ke_i}\leq 1+p_i^k+\cdots +p_i^{kf_i}$$ となり、かつ $$1+p_j^k+\cdots +p_j^{ke_j}<1+p_j^k+\cdots +p_j^{kf_j}$$ となる。よって $$d_k(M)=\prod_{i=1}^r (1+p_i^k+\cdots +p_i^{ke_i})<\prod_{i=1}^r (1+p_i^k+\cdots +p_i^{kf_i})=d_k(N)$$ が成り立つ。
□定理2.5
$k$ が $0$ 以上の整数のとき $d_k(N)$ が奇数 $\Longleftrightarrow$ $N$ は平方数か、平方数の$2$倍。
Proof.
$$N=p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r} (e_1, \ldots, e_r>0)$$ と素因数分解する。$p_i$ が奇数のとき $$1+p_i^k+\cdots +p_i^{ke_i}\equiv e_i+1 \mathmod{2}$$ である。また $p_i=2$ が偶数ならば $1+2^k+\cdots +2^{ke_i}$ は奇数である。 よって、定理2.1より$d_k(N)$ が奇数 $\Longleftrightarrow$ $1+p_i^k+\cdots +p_i^{ke_i} (i=1, \ldots, r)$ はすべて奇数 $\Longleftrightarrow$ $p_i\neq 2$ のとき $e_i$ は偶数、となることがわかる。 これは $N=2^e M^2$ （$e$ は $0$ 以上の整数で $M$ は奇数）の形にあらわされることを意味する。 つまり $N$ は平方数か、平方数の$2$倍である。
□Eulerの関数
$\varphi(N)$ をEulerの定理にあらわれたEuler関数とする。すなわち $1, 2, \ldots, N-1$ のうち $N$ と互いに素な整数の個数とする。 合同式:定理7.2で述べたように $$N=p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r}$$ と素因数分解すると $$\varphi(N)=\prod_{i=1}^r p_i^{e_i-1}(p_i-1)$$ となる。 このことは包含と除去の原理から証明することもできる。
Proof.
$S=\{0, 1, \ldots, N-1\}$ とし、$1\leq i\leq r$ に対して $$S_i=\{m\in S, p_i\mid m\}$$ を $0, 1, \ldots, N-1$ のうち $p_i$ の倍数全体の集合とする。 とおく。 $T$ を $0, 1, \ldots, N-1$ のうち、$N$ と互いに素な整数全体の集合とすると $$T=S\backslash \bigcup_{p\mid d}S_p$$ が成り立つ。一方 $$S_I=\bigcap_{i\in I}S_I$$ とおくと、$S_I$ は $\prod_{i\in I}p_i$ の倍数全体の集合だから $$\#S_I=\frac{N}{\prod_{i\in I}p_i}$$ が成り立つ。よって包含と除去の原理より $$\begin{split} \# T= & \sum_{I\in \{1, 2, \ldots, r\}}(-1)^{\# I}\frac{N}{\prod_{i\in I}p_i} \\ = & N\sum_{I\in \{1, 2, \ldots, r\}} \prod_{i\in I}\left(-\frac{1}{p_i}\right) \\ = & N\prod_{i=1}^r \left(1-\frac{1}{p}\right) \end{split}$$ となる。
□このことから、約数関数と同様に、次のことがわかる。
定理3.1
$\gcd(m, n)=1$ ならば $\varphi(mn)=\varphi(m)\varphi(n)$.
加法的関数と乗法的関数
$\gcd(M, N)=1$ のとき $f(MN)=f(M)+f(N)$ となる数論的関数 $f(N)$ を加法的関数、 正の整数 $M, N$ に対してつねに $f(MN)=f(M)+f(N)$ となる数論的関数 $f(N)$ を完全加法的関数という。
たとえば $\omega(N)$ は加法的関数、$\Omega(N)$ は完全加法的関数である。
これに対し、$\gcd(M, N)=1$ のとき $f(MN)=f(M)f(N)$ となる数論的関数 $f(N)$ を乗法的関数、 正の整数 $M, N$ に対してつねに $f(MN)=f(M)f(N)$ となる数論的関数 $f(N)$ を完全乗法的関数という。
たとえば $d_k(N) (k=0, 1, \ldots)$ は乗法的関数である。
一般的には、次のようなことが成り立つ。
定理4.1
$k$ を $0, \pm 1$ ではない実数とし、f(N), F(N)$ が $F(N)=k^{f(N)}$ となる数論的関数とする。 ただし $k$ が負のときは $f(N)$ は整数値をとるとする。このとき
- $f(N)$ が加法的関数 $\Longleftrightarrow$ $F(N)$ は乗法的関数
- $f(N)$ が完全加法的関数 $\Longleftrightarrow$ $F(N)$ は完全乗法的関数
Proof.
$f(N)$ が加法的ならば $\gcd(M, N)=1$ のとき（完全加法的ならば任意の正の整数 $M, N$ について） $$F(MN)=k^{f(MN)}=k^{f(M)+f(N)}=k^{f(M)}\times k^{f(N)}=f(M)f(N).$$ $F(N)$ が乗法的ならば $\gcd(M, N)=1$ のとき（完全乗法的ならば任意の正の整数 $M, N$ について） $$k^{f(MN)}=F(MN)=F(M)F(N)=k^{f(M)}\times k^{f(N)}=k^{f(M)+f(N)}$$ となるが、$k\neq 0, \pm 1$ より $$f(MN)=f(M)+f(N)$$ となる。
□定理4.2
正の整数に対して定義された関数 $f(N)$ が乗法的関数である必要十分条件は $N=p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r}$ と素因数分解すると $f(N)=\prod_{i=1}^r f(p_i^{e_i})$ となることである。
Proof.
$N=p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r}$ と素因数分解すると $f(N)=\prod_{i=1}^r f(p_i^{e_i})$ となるとする。このとき $\gcd(M, N)=1$ ならば $$M=p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r}, N=p_{r+1}^{e_{r+1}} p_{r+2}^{e_{r+2}} \cdots p_s^{e_s}$$ と素因数分解され、 $$f(MN)=\prod_{i=1}^s f(p_i^{e_i})=\left(\prod_{i=1}^r f(p_i^{e_i})\right)\left(\prod_{i=r+1}^s f(p_i^{e_i})\right)=f(M)f(N)$$ となり、$f(N)$ は乗法的関数であることがわかる。
逆に $f(N)$ が乗法的関数ならば $N=p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r}$ と素因数分解すると $$f(N)=f(p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r})=f(p_1^{e_1} p_2^{e_2} \cdots p_{r-1}^{e_{r-1}})f(p_r^{e_r})$$ となるから、$r$ あるいは $N$ に関する帰納法により $$f(N)=f(p_r^{e_r})\prod_{i=1}^{r-1} f(p_i^{e_i})=\prod_{i=1}^r f(p_i^{e_i})$$ であることがわかる。
□定理4.3
正の整数に対して定義された関数 $f(N)$ が加法的関数である必要十分条件は $N=p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r}$ と素因数分解すると $f(N)=\sum_{i=1}^r f(p_i^{e_i})$ となることである。
定理4.4
正の整数 $N$ に対して定義された関数 $f(N)$ が乗法的関数ならば $$g(N)=\sum_{d\mid N}f(d)$$ により定義される関数 $g(N)$ も乗法的関数で、 $$N=p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}$$ と素因数分解すると $$g(N)=\prod_{i=1}^r \sum_{g_i=0}^{e_i}f(p_i^{g_i})\ \ (*)$$ とあらわされる。
Proof.
$$N=p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}$$ と素因数分解する。 $r=0$ のときは $g(1)=f(1)$ となるので $(*)$ が成り立つ。 $r=1$ のとき明らかに $$g(N)=\sum_{d\mid N}f(d)=\sum_{g=0}^{e_1} f(p_1^g)$$ となるので、やはり $(*)$ は成り立つ。
$\omega(N)=k$ のとき $(*)$ が正しいとし、$r=k+1$ とする。 $$N_1=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$$ とおくと $N=N_1 p_{k+1}^{e_{k+1}}$ なので $$\begin{split} g(N)= & \sum_{d\mid N}f(d) \\ = & \sum_{d_1\mid N_1, d_2\mid p_{k+1}^{e_{k+1}}} f(d_1 d_2) \\ = & \left(\sum_{d_1\mid N_1} f(d_1)\right)\left(\sum_{d_2\mid p_{k+1}^{e_{k+1}}} f(d_2)\right) = & g(N_1)g(p_{k+1}^{e_{k+1}}) \\ = & \prod_{i=1}^{k+1} \sum_{g_i=0}^{e_i}f(p_i^{g_i}) \end{split}$$ となるので、$r=k+1$ のときも $(*)$ は成り立つ。
よって数学的帰納法より $(*)$ はすべての正の整数 $N$ に対して成り立つ。
□
Möbius関数
正の整数 $N$ が $$N=p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}, e_i>0$$ と素因数分解されるとき $$N=\left\{\begin{array}{cl} (-1)^r& (\forall i[e_i\leq 1])\\ 0 & (\exists i[e_i\geq 2])\end{array}\right.$$ によりMöbius関数を定義する。
定義よりMöbius関数は乗法的関数である。Möbius関数は有限半順序集合上のMöbius関数に一般化される。
定理5.1
$N>0$ に対して $$\sum_{d\mid N}\mu(d)=\left\{\begin{array}{cl} 1 & (N=1)\\ 0 & (N>1)\end{array}\right.$$ が成り立つ。
Proof.
$N=1$ ならば $$\sum_{d\mid N}\mu(d)=\mu(1)=1$$ となる。
$N>1$ のとき $$N=p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}$$ と素因数分解すると $\mu$ は乗法的関数なので定理4.4より $$\sum_{d\mid N}\mu(d)=\prod_{i=1}^r \sum_{f_i=0}^{e_i}\mu(p_i^{f_i})=\prod_{i=1}^r (\mu(1)+\mu(p_i))=0$$ となる。
□定理5.2（包含と除去の原理）
$S$ を有限集合、$P$ を素数の有限集合、$D$ を $P$ に属する相異なる素数の積であらわされる整数全体とする。 素数 $p\in P$ について $S$ の部分集合 $S_p$ が定まっているとし、 $d\in D$ に対して $S_d=\bigcap_{p\mid d}S_p$ とおく。このとき $T=S\backslash \bigcup_p S_p$ を、$S$ の要素でどの $S_p$ にも属さないもの全体の集合とすると、 $$\#T=\sum_{d\in D} \mu(d) \# S_d$$ となる。
Proof.
$x\mid S_d\Longleftrightarrow \forall (p\mid d)x\in S_p$ であるから、各 $x\in S$ について $N(x)=\prod_{x\in S_p} p$ を $S_p$ が $x$ を含んでいる素数 $p$ すべての積とすると、$N(x)\in D$ で $$x\in S_d\Longleftrightarrow d\mid N(x)$$ となる。 それで、$f(x)=\sum_{x\in S_d}\mu(d)$ とおくと $$f(x)=\sum_{d\mid N(x)}\mu(d)$$ より $$f(x)=1\Longleftrightarrow N(x)=1\Longleftrightarrow x\in T$$ となる。よって $$\#T=\sum_{x\in S}f(x)=\sum_{d\in D} \mu(d)\sum_{x\in S_d} 1=\sum_{d\in D} \mu(d)\# S_d$$ となる。
□この定理は有限半順序集合上の包含と除去の原理に一般化される。
参考文献
Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 6th Ed. revised by D. R. Heath-Brown and J. H. Silverman, Oxford University Press, 2008, Chapter 16.
