素因数の個数
本ページでは、素因数の個数に関する数論的関数の基本的な性質について解説する。
素因数の個数
素因数の個数を数えるときは重複も含めて数えるかどうかで、2通りの数え方がある。正の整数 $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$$
が成り立つ。
正の整数 $m, n$ に対し、$\Omega(mn)=\Omega(m)+\Omega(n)$.
さらに $\gcd(m, n)=1$ ならば $\omega(mn)=\omega(m)+\omega(n)$.
$$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).$$
参考文献
本ページについてはHardy and Wright, Chapter 16 を参照。
参考文献
