2014/11/08

約数の個数の公式と平方数の性質

分野: 整数問題  レベル: 基本公式

約数の個数の公式:正の整数 $n$ が,$n=p_1^{a_1} p
_2^{a_2}\cdots p_k^{a_k}$ と素因数分解できるとき,$n$ の約数の個数は$(a_1+1)(a_2+1)\cdots (a_k+1)$ 個である。

基本的ですが重要な公式です。公式の証明およびこの公式から導ける平方数に関する重要な定理を解説します。

約数の個数の公式の使用例

例1

$12$ は $2^2\cdot 3$ と素因数分解できるので,約数の個数は$(2+1)(1+1)=6$ 個。

例2

素数 $p$ に対して $p^k$ という数の約数の個数は $k+1$ 個。

例3

$2^{99}3^{199}$ という数は大き過ぎてよく分からないが,約数の個数は$(99+1)(199+1)=20000$ 個と分かる。

このように,「素因数分解して指数を見れば約数の個数が分かる」というわけです。

約数の個数の公式の証明

$n$ の素因数分解をもとに「 $p_i$ たちの指数を決めれば約数が一つ定まる」ことが理解できればほとんど当たり前な公式です。

約数の個数

例えば $12=2^2\cdot 3$ の場合,$2$ の指数を $0,1,2$ の中から一つ,$3$ の指数を $0,1$ の中から一つ選ぶと約数が決まります。よって約数の個数は $3\times 2=6$ 個です。

一般的に書くと以下のようになります。

証明

$n$ の約数は $p_1^{b_1} p
_2^{b_2}\cdots p_k^{b_k}$(ただし,各 $i$ に対して $b_i$ は $0\leq b_i\leq a_i$ を満たす整数)という形の整数だけであり,これで全ての約数を表せる。
そのような $b_i$ の選び方は$(a_1+1)(a_2+1)\cdots (a_k+1)$ 通りである。

平方数の約数の個数は奇数

約数の個数の公式から導ける重要な定理を解説します。

正の整数 $n$ について,
$n$ が平方数 $\iff$ $n$ の約数の個数は奇数

$16$ は平方数である。約数は $1,\:2,\:4,\:8,\:16$ の五個(奇数個)

$12$ は平方数でない。約数は $1,\:2,\:3,\:4,\:6,\:12$ の六個(偶数個)

証明

$n=p_1^{a_1} p
_2^{a_2}\cdots p_k^{a_k}$ と素因数分解されているとき,$n$ が平方数であるというのは,平方数の定義より $a_1,\:a_2,\cdots,\:a_k$ がいずれも偶数であることと同値。

一方,$n$ の約数の個数が奇数であるというのは,約数の個数の公式より$(a_1+1)(a_2+1)\cdots (a_k+1)$ が奇数であることと同値。
これは $a_1,\:a_2,\cdots,\:a_k$ がいずれも偶数であることと同値。

平方数の約数の個数の証明2

上記のように約数の個数の公式を使えば鮮やかに証明できますが,この公式を使わずとも以下のように証明できます。

約数の公式

証明

$m$ が $n$ の約数のとき,$\dfrac{n}{m}$ も $n$ の約数である。このことに注意すると,$n$ の約数を小さい順に $1=d_1,\:d_2,\cdots, d_N=n$ と並べたとき,$d_1d_N=n,\:d_2d_{N-1}=n$ などが成立する。つまり,大きい方と小さい方から一つずつとってくるとかけて $n$ になるペアができる。

$n$ が平方数のときは $m=\dfrac{n}{m}$ となる約数 $m$ が存在するので真ん中で一つ余る。それ以外は全てペアになる。よって約数の個数は奇数。
$n$ が平方数でないときは $m=\dfrac{n}{m}$ となる正の整数 $m$ が存在しないので,全てペアになる。よって約数の個数は偶数。

なお,この考え方を使う問題が国際数学オリンピックで出題されたこともあります。

「約数の個数の公式の証明」って「の」が三つも入っていてなんか不格好ですね。すみませんm(__)m

Tag: 数学Aの教科書に載っている公式の解説一覧

分野: 整数問題  レベル: 基本公式