整数の約数の定義と、約数の簡単な性質を紹介します。
約数
整数 \(m, n\) に対して, ある整数 \(l\) が存在して \(n=lm\) となるとき,
\(m\) は \(n\) の約数(divisor)であるといい, \(m\mid n\) と表す.
\(m\) が \(n\) の約数でないとき \(m\not\mid n\) と表すこともある.
また, このとき逆に \(n\) は \(m\) の倍数であるという.
\(0\) の約数は整数全体とみることが出来ますが, \(0\) を \(0\) の約数から外すこともあります。
基本性質
任意の整数 \(m\) に対して
- \(\pm1\mid m\).
- \(m\mid 0\)
- \(\pm m\mid \pm m\) (複合任意) (特に反射律 \(m\mid m\) )
証明
\(m=1\cdot m=(-1)\cdot(-m)\), \(0=0\cdot m\) などより分かる.
例
- \(12=3\cdot4\) なので、 \(3, 4\) は \(12\) の約数です。 \(3\mid12,\ 4\mid12\).
- \(-35=-5\cdot7\) なので、 \(-5, 7\) は \(-35\) の約数です。 \(-5\mid-35,\ 7\mid-35\).
約数関係と演算
整数 \(a, b, c\) に対して
- \(a\mid b\) かつ \(a\mid c\) のとき \(a\mid (b\pm c)\).
- \(a\mid b\) ならば, 任意の整数 \(k\) に対して \(a\mid bk\).
- \(a\mid b\) ならば, 任意の整数 \(k\) に対して \(ak\mid bk\).
- \(0\) でない整数 \(k\) に対して \(ak\mid bk\) ならば \(a\mid bk\).
- \(0\) でない整数 \(k\) に対して \(ak\mid bk\) ならば \(a\mid b\).
証明
\(a\mid b\) ならば \(b=an\), \(a\mid c\) ならば \(c=am\) と書ける
- \(b\pm c=an\pm am=a(n\pm m)\) より \(a\mid (b\pm c)\).
- \(bk=ank=a(nk)\) より \(a\mid bk\).
- \(bk=ank\) より \(ak\mid bk\).
- \(ak\mid bk\) より, \(bk=akn=a(kn)\) なので \(a\mid bk\).
- \(ak\mid bk\) より, \(bk=akn\) なので \(b=an\). よって \(a\mid b\).
約数関係の推移性
整数 \(a, b, c\) に対して \(b\mid a\) かつ \(c\mid b\) ならば \(c\mid a\).
証明
\(b\mid a\) かつ \(c\mid b\) ならば \(a=bn, b=cm\) と書けるが, \(a=cmn=c(mn)\) なので \(c\mid a\).
約数の個数
正の整数 \(n\) に対して, \(n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}\) と素因数分解されるとき, \(n\) の正の約数の個数を \(d(n)\) とすると\[d(n)=(e_1+1)(e_2+1)\cdots(e_k+1)
\] が成り立つ.
証明
\(D(n)=\{\ p_1^{f_1}p_2^{f_2}\cdots p_k^{f_k}\ |\ 0\leq f_1\leq e_1,\ 0\leq f_2\leq e_2,\ \ldots,\ 0\leq f_k\leq e_k\ \}\) と置くと,
\(d(n)=\# D(n)\) である.
素因数分解の一意性より, 組 \((f_1, f_2, \ldots, f_k)\) が異なれば \(p_1^{f_1}p_2^{f_2}\cdots p_k^{f_k}\) は異なるので,
\(\#D(n)=(e_1+1)(e_2+1)\cdots(e_k+1)\).
ゆえに \(d(n)=(e_1+1)(e_2+1)\cdots(e_k+1)\).
約数の総和
正の整数 \(n\) に対して, \(n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}\) と素因数分解されるとき, \(n\) の正の約数の個数を \(\sigma(n)\) とすると\[
\begin{align*}
\sigma(n)&=(1+p_1+\cdots+p_1^{e_1})(1+p_2+\cdots+p_2^{e_2})\cdots(1+p_k+\cdots+p_k^{e_k})\\
&=\frac{p_1^{e_1+1}-1}{p_1-1}\frac{p_2^{e_2+1}-1}{p_2-1}\cdots\frac{p_k^{e_k+1}-1}{p_k-1}
\end{align*}
\] が成り立つ.
証明
\(n\) の約数は全て \(p_1^{f_1}p_2^{f_2}\cdots p_k^{f_k}\ (0\leq f_1\leq e_1,\ 0\leq f_2\leq e_2,\ \ldots,\ 0\leq f_k\leq e_k)\) の形をしているので
\[\begin{align*}
\sigma(n)
&=\sum_{f_1=0}^{e_1}\sum_{f_2=0}^{e_2}\cdots\sum_{f_k=0}^{e_k}p_1^{f_1}p_2^{f_2}\cdots p_k^{f_k}\\
&=\left(\sum_{f_1=0}^{e_1}p_1\right)\left(\sum_{f_2=0}^{e_2}p_2\right)\cdots\left(\sum_{f_k=0}^{e_k}p_k\right)\\
&=(1+p_1+\cdots+p_1^{e_1})(1+p_2+\cdots+p_2^{e_2})\cdots(1+p_k+\cdots+p_k^{e_k})
\end{align*}
\]
自然数における約数関係
自然数 \(a, b, c\) に対して
- \(a\mid b\) ならば \(a\leq b\).
- \(a\mid b\) かつ \(b\mid a\) ならば \(a=b\) (反対称性)
証明
１. \(a=0\) ならば明らかに \(a\leq b\) であり, \(a\neq 0\) ならば \(b=an\) となる自然数 \(n\) が存在するので \(a\leq b\).
２. １より \(a\leq b\) かつ \(b\leq a\) なので \(a=b\).
自然数において約数関係は、反射律・推移律・反対称律が成立するので半順序関係となっています。
コメント