約数

概要

前提知識: 整数, 素因数分解

$60$ を割り切る正の整数を小さい順に並べると
$$ 1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 10,\ 12,\ 15,\ 20,\ 30,\ 60 $$
の 12 個であり、その和は $168$ である。これらが $60$ の正の約数である。$d$ が $60$ の約数なら $60/d$ も約数なので、$1\cdot60=2\cdot30=3\cdot20=4\cdot15=5\cdot12=6\cdot10$ と、約数は積が $60$ になる 6 組に分かれる。一方 $36$ の正の約数 $1,2,3,4,6,9,12,18,36$ では、$6$ が $6\cdot6=36$ と自分自身と組になるので、約数の個数は奇数の $9$ になる。$60=2^2\cdot3\cdot5$ の約数の個数 $12=(2+1)(1+1)(1+1)$ と和 $168=(1+2+4)(1+3)(1+5)$ は、素因数分解の指数から計算できる。
約数は整数の割り算についての最も基本的な概念であり、素数（$2$ 以上で、正の約数が $1$ と自分自身だけの数）、最大公約数、完全数（自分以外の正の約数の和が自分に等しい数）などはすべて約数によって定義される。本記事では、整数の約数を定義し、割り切る関係の基本性質、素因数分解による約数の個数と総和の公式、約数を $d$ と $n/d$ の組に分ける考え方とその帰結を扱う。代数幾何学やRiemann面の理論で divisor の訳語として使われる「因子」（因子）は別の概念である（rem-div-other-meanings）。

定義

約数と倍数

$a,d$ を整数とする。$a=dk$ となる整数 $k$ が存在するとき、$d$ は $a$ を 割り切る といい、$d\mid a$ と書く。このとき $d$ を $a$ の約数（divisor）、$a$ を $d$ の倍数（multiple）という。$d$ が $a$ を割り切らないことを $d\nmid a$ と書く。

この定義では、約数は負でもよく、$0$ も対象になる。$6$ の約数は $\pm1,\pm2,\pm3,\pm6$ の 8 個である。$0=d\cdot0$ なので、すべての整数は $0$ の約数である。一方 $0$ を約数にもつのは $0$ だけである（$a=0\cdot k$ なら $a=0$）。$a$ の倍数全体は $a\mathbb{Z}=\{ak\mid k\in\mathbb{Z}\}$ である。
正の整数 $n$ について、$n$ の正の約数の個数を $\tau(n)$、正の約数の総和を $\sigma(n)$ と書く。
$$ \tau(n)=\sum_{d\mid n}1,\qquad \sigma(n)=\sum_{d\mid n}d $$
（和は $n$ の正の約数 $d$ にわたる）。$\tau(n)$ は $d(n)$ とも書かれる。より一般に、$k$ 乗の和 $\sigma_k(n)=\sum_{d\mid n}d^k$ を考えると $\tau=\sigma_0$、$\sigma=\sigma_1$ である（Mos11 Chapter 2、pp. 7–8。Cri24 Definition 19.1.1、p. 327）。$n$ 自身を除いた正の約数を $n$ の 真の約数（proper divisor）という。

直感

$n$ 個の正方形のタイルを長方形に並べる方法を考えると、横に $d$ 枚並べて縦 $n/d$ 段にできるのは、$d$ が $n$ の約数のときに限る。約数を列挙することは、面積 $n$ の整数辺の長方形を列挙することであり、長方形を $90$ 度回すと横と縦が入れ替わる（$d\leftrightarrow n/d$）。正方形になるのは $n$ が平方数のときだけで、そのとき回しても同じ長方形になる。これが冒頭の $60$ と $36$ の違いである（prop-div-pairing）。
割り切る関係は大小の関係とは別の「並び方」を整数に与える。$4<6$ だが $4\nmid6$ であり、$1$ はすべての正の整数を割り切るので最も「小さく」、$0$ はすべての整数で割り切られるので最も「大きい」。

例と反例

小さな数の約数の個数と総和

$n=1,\dots,12$ について $\tau(n)$ と $\sigma(n)$ は次のとおりである。

$n$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$12$
$\tau(n)$	$1$	$2$	$2$	$3$	$2$	$4$	$2$	$4$	$3$	$4$	$2$	$6$
$\sigma(n)$	$1$	$3$	$4$	$7$	$6$	$12$	$8$	$15$	$13$	$18$	$12$	$28$

$\tau(n)=2$ となるのは $n$ が素数のときに限り、$\tau(n)$ が奇数になるのは $n=1,4,9$ の平方数のときである。$\sigma(6)=12=2\cdot6$ なので $6$ は完全数である。

反例：約数の個数は積を積に移すとは限らない

$\gcd(m,n)=1$ なら $\tau(mn)=\tau(m)\tau(n)$、$\sigma(mn)=\sigma(m)\sigma(n)$ が成り立つ（cor-div-multiplicative）。しかし $m=n=2$ では $\tau(4)=3\ne4=\tau(2)^2$、$\sigma(4)=7\ne9=\sigma(2)^2$ である。$2\cdot2=4$ の約数 $1,2,4$ は、「$2$ の約数と $2$ の約数の積」$1\cdot1,1\cdot2,2\cdot1,2\cdot2$ の 4 通りの中で $2$ が 2 回現れるので、3 個しかない。この例は $m$ と $n$ が互いに素という仮定を破っており、破れるのは「すべての $m,n$ について $\tau(mn)=\tau(m)\tau(n)$」という含意である。$\tau$ と $\sigma$ は乗法的（乗法的関数）であるが、完全乗法的ではない。

反例：0 の約数には大きさの上限がない

$b\neq0$ で $a\mid b$ なら $|a|\le|b|$ である（prop-div-basic の 6）が、$b=0$ ではすべての整数 $a$ が $a\mid0$ を満たすので、$|a|\le|b|=0$ は成り立たない。この例は $b\ne0$ という仮定を破っている。$\tau$ や $\sigma$ を正の整数だけで定義するのは、$0$ の約数が無限個あるからである。

性質

割り切る関係の基本性質

$a,b,c,x,y$ を整数とする。

$a\mid a$、$1\mid a$、$a\mid0$ である。
$0\mid a$ であることと $a=0$ であることは同値である。
$a\mid b$、$-a\mid b$、$a\mid -b$ は互いに同値である。
$a\mid b$ かつ $b\mid c$ なら $a\mid c$ である。
$a\mid b$ かつ $a\mid c$ なら $a\mid bx+cy$ である。
$a\mid b$ かつ $b\ne0$ なら $1\le|a|\le|b|$ である。
$a\mid b$ かつ $b\mid a$ なら $a=\pm b$ である。

定義に戻る

$a=a\cdot1$、$a=1\cdot a$、$0=a\cdot0$ である。
$a=0\cdot k$ なら $a=0$ であり、逆は 1 による。
$b=ak$ なら $b=(-a)(-k)$、$-b=a(-k)$ であり、逆も同様である。
$b=ak$、$c=bl$ なら $c=a(kl)$ である。
$b=ak$、$c=al$ なら $bx+cy=a(kx+ly)$ である。
$b=ak$ で $b\neq0$ なら $a\neq0$、$k\neq0$ なので $|a|\ge1$、$|k|\ge1$ であり、$|b|=|a||k|\ge|a|$ である。
$a=0$ なら $a\mid b$ と 2 から $b=0$ で、$a=b$ である。$b=0$ の場合も同様である。$a,b\ne0$ なら 6 により $|a|\le|b|\le|a|$ なので $|a|=|b|$、すなわち $a=\pm b$ である。$\square$

4 と 1 と 7 により、正の整数の上で割り切る関係は反射的・推移的・反対称的であり、半順序集合をなす。この順序（整除関係）では 2 つの正の整数 $a,b$ の下限が $\gcd(a,b)$、上限が $\operatorname{lcm}(a,b)$ であり（最大公約数の記事の定理「公約数と最大公約数の約数」と、最小公倍数の記事の定理「公倍数と最小公倍数の倍数」）、正の整数全体は割り切る関係について束になる。5 は、$a$ の倍数全体 $a\mathbb{Z}$ が足し算と整数倍で閉じていること（イデアルであること）を言っている（Sho08 Theorem 1.1・Theorem 1.2、pp. 1–2）。

素因数分解による約数の記述

以下、正の整数 $n$ の標準形を $n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$（$p_i$ は相異なる素数、$e_i\ge1$）とする。$n=1$ は $k=0$ の場合である。

約数の個数と総和の公式

$n$ の正の約数は、$0\le f_i\le e_i$（$i=1,\dots,k$）を満たす整数の組 $(f_1,\dots,f_k)$ によって $d=p_1^{f_1}\cdots p_k^{f_k}$ と書ける数全体であり、異なる組は異なる約数を与える。
$\displaystyle\tau(n)=\prod_{i=1}^k(e_i+1)$ である。
$\displaystyle\sigma(n)=\prod_{i=1}^k\bigl(1+p_i+p_i^2+\cdots+p_i^{e_i}\bigr)=\prod_{i=1}^k\frac{p_i^{e_i+1}-1}{p_i-1}$ である。

積を展開すると約数が 1 回ずつ現れる

正の整数 $d$ が $n$ を割り切ることは、すべての素数 $p$ について $p$ の指数が $d$ で $n$ 以下であることと同値である（最大公約数の記事の定理「素因数分解による最大公約数と最小公倍数」の 1）。したがって $d$ は $p_1,\dots,p_k$ 以外の素数を含まず、$d=p_1^{f_1}\cdots p_k^{f_k}$、$0\le f_i\le e_i$ と書ける。逆にこの形の数は $n$ を割り切る。異なる組が同じ数を与えないことは、素因数分解の一意性（素因数分解の記事の定理「素因数分解の存在と一意性」）による。
1 により、$n$ の正の約数は組 $(f_1,\dots,f_k)$ と 1 対 1 に対応する。$f_i$ の選び方は $e_i+1$ 通りなので、組の個数は $\prod_i(e_i+1)$ である。
積 $\prod_{i=1}^k(1+p_i+\cdots+p_i^{e_i})$ を分配法則（環）で展開すると、各因子から 1 項 $p_i^{f_i}$ を選んで掛けた $p_1^{f_1}\cdots p_k^{f_k}$ の、すべての組 $(f_1,\dots,f_k)$ にわたる和になる。1 によりこれは $n$ の正の約数のちょうど 1 回ずつの和、すなわち $\sigma(n)$ である。最後の等号は等比数列の和 $(p-1)(1+p+\cdots+p^e)=p^{e+1}-1$ による。$\square$

冒頭の $60=2^2\cdot3\cdot5$ では $\tau(60)=3\cdot2\cdot2=12$、$\sigma(60)=7\cdot4\cdot6=168$ である（Mos11 Chapter 2、p. 8 に同じ計算がある）。$720=2^4\cdot3^2\cdot5$ なら $\tau(720)=5\cdot3\cdot2=30$、$\sigma(720)=31\cdot13\cdot6=2418$ である。同じ公式は Cri24 Theorem 19.2.5（p. 329）にある。

約数の個数と総和の乗法性

正の整数 $m,n$ が互いに素なら $\tau(mn)=\tau(m)\tau(n)$、$\sigma(mn)=\sigma(m)\sigma(n)$ である。

素因数が重ならない

$m$ と $n$ は共通の素因数をもたないので、$m$ の標準形と $n$ の標準形を並べたものが $mn$ の標準形であり、$mn$ の素因数の集合は $m$ の素因数の集合と $n$ の素因数の集合の交わらない和になる。thm-div-formula の 2 と 3 の積は、この 2 つの部分に分けて計算した積の積に等しい。$\square$

$\sigma$ の乗法性の、約数を組 $(\gcd(d,m),\gcd(d,n))$ に対応させる別の証明は完全数の記事の補題「約数の和の乗法性」にある。ex-div-not-completely-multiplicative のとおり、互いに素の仮定は外せない。

約数を組にする

約数の組 $d$ と $\frac{n}{d}$

$n$ を正の整数とする。

写像 $d\mapsto n/d$ は、$n$ の正の約数全体からそれ自身への全単射で、2 回繰り返すと元に戻る。
$\tau(n)$ が奇数であることと、$n$ が平方数であることは同値である。
$n$ の正の約数全体の積は $n^{\tau(n)/2}$ である。
$\tau(n)\le2\sqrt n$ である。

組を数える

$d\mid n$ なら $n=d\cdot(n/d)$ なので $n/d$ も $n$ の正の約数であり、$n/(n/d)=d$ である。
1 の写像で $d$ と $n/d$ を組にする。$d=n/d$ となるのは $d^2=n$ のとき、すなわち $n$ が平方数で $d=\sqrt n$ のときに限る。それ以外の約数は $d\ne n/d$ の 2 個ずつの組に分かれる。よって $\tau(n)$ は、$n$ が平方数なら（2 の倍数）$+1$ で奇数、そうでなければ偶数である。
$P:=\prod_{d\mid n}d$ とおく。1 により $d$ を $n/d$ に置き換えても積は同じなので $P=\prod_{d\mid n}(n/d)$ であり、2 つを掛けると $P^2=\prod_{d\mid n}\bigl(d\cdot\frac nd\bigr)=n^{\tau(n)}$ である。$P>0$ なので $P=n^{\tau(n)/2}$ である。
$n$ の正の約数 $d$ で $d>\sqrt n$ なら $n/d<\sqrt n$ である。したがって、正の約数全体は「$\sqrt n$ 以下の約数」と「$\sqrt n$ 以下の約数 $d$ に対する $n/d$」で尽くされ、$\tau(n)$ は $\sqrt n$ 以下の正の約数の個数の 2 倍以下である。$\sqrt n$ 以下の正の整数は $\sqrt n$ 個以下なので、$\tau(n)\le2\sqrt n$ である。$\square$

$60$ では約数の積は $60^6$ であり、$36$ では $36^{9/2}=6^9$ である。2 は、素因数分解の指数で言えば「$\prod(e_i+1)$ が奇数 $\iff$ すべての $e_i$ が偶数」ということであり、平方数の記事の命題「素因数の指数による特徴づけ」と合わせても得られる。4 の評価はおおまかで、実際には $\tau(n)$ は $\sqrt n$ よりずっと小さいことが多い。平均的には $\tau(n)$ は $\log n$ 程度である（prop-div-average）。

約数の個数の平均

すべての正の整数 $n$ について
$$ \log(n+1)-1<\frac1n\sum_{k=1}^n\tau(k)\le1+\log n $$
である。ここで $\log$ は自然対数である。

床関数で数え直す

床関数の記事の命題「約数の個数の和」により $\sum_{k=1}^n\tau(k)=\sum_{d=1}^n\lfloor n/d\rfloor$ である（$\lfloor x\rfloor$ は $x$ 以下の最大の整数）。各 $d$ について $n/d-1<\lfloor n/d\rfloor\le n/d$ なので、$H_n:=\sum_{d=1}^n1/d$ とおくと
$$ nH_n-n<\sum_{k=1}^n\tau(k)\le nH_n $$
である。調和級数の記事の命題「積分による上下の評価」により $\log(n+1)< H_n\le1+\log n$ なので、$n$ で割って主張を得る。$\square$

たとえば $n=10$ では $\sum_{k=1}^{10}\tau(k)=27$ で平均は $2.7$ であり、評価は $1.39\ldots<2.7\le3.30\ldots$ となる。個々の $\tau(n)$ は、素数では $2$ と小さく、$720$ のように小さい素数を多く含む数では $30$ と大きく、大きく揺れ動くが、平均をとると $\log n$ の程度に落ち着く。

補足

環の元の約数と、同じ名前の別の概念

約数の定義はそのまま一般の可換環 $A$ に移せる。$a,d\in A$ について $a=dk$ となる $k\in A$ があるとき $d\mid a$ と書き、$d$ を $a$ の約元（約数）という。たとえば体 $K$ 上の多項式環 $K[x]$ では $x-1\mid x^2-1$ である。環では $1$ を割り切る元が単元であり、整数では $\pm1$ である。互いに割り切り合う 2 元を同伴（一意分解整域）といい、整数では $a=\pm b$ にあたる（prop-div-basic の 7）。
日本語では整数の約数を「因数」と呼ぶこともあり、「素因数」「因数分解」はこの用法である。英語の divisor は代数幾何学・Riemann面の理論では「因子」と訳され、点や部分多様体の整数係数の形式和という別の概念を指す（因子）。有理関数の零点と極から作る主因子は、素因数分解の類似として定義される。

文献

割り切る関係の定義と基本性質は Ste17 Definition 1.1.1（p. 2）、Sho08 §1.1 の Theorem 1.1・Theorem 1.2（pp. 1–2）にある。$\tau,\sigma,\sigma_k$ の定義、素因数分解による公式、$\tau(60)=12$、$\sigma(60)=168$ の計算は Mos11 Chapter 2（pp. 7–8）にあり、同じ公式の約数和関数としての扱いは Cri24 Chapter 19（Definition 19.1.1、p. 327。Fact 19.2.3 と Theorem 19.2.5、p. 329）にある。約数を $d$ と $n/d$ の組に分けて $\tau(n)\le2\sqrt n$ を得る議論は Cri24 §20.2 の Example 20.2.4 の前後（p. 350）にある。