約数の個数と総和

方針

解答

⓪ 発想 — どう考え始めるか。 約数を $1$ つずつ探すのは効率が悪い。素因数分解して、約数の「作り方」から数える。

$$72=2^3\times 3^2$$

$72$ の約数とは、$2$ を何個か・$3$ を何個か掛け合わせたもの。$2$ の個数は $0,1,2,3$ の $4$ 通り、$3$ の個数は $0,1,2$ の $3$ 通り。

この $2$ つを独立に選べるので、積の法則で

$$4\times 3=12(\text{個})$$

急所は「$0$ 個」を数え忘れないこと($2$ を $0$ 個使うのも立派な選択で、それが奇数の約数になる)。だから指数に $+1$ する。

総和も同じ発想で、「$2$ の使い方の合計」と「$3$ の使い方の合計」を掛ける。

まず素因数分解する。

$$72=2^3\times 3^2$$

72の約数は、2を $a$ 個、3を $b$ 個かけた $2^a\times 3^b$ の形で全部表せる。$a$ は $0,1,2,3$ の4通り、$b$ は $0,1,2$ の3通りだ。

(1) 「2を何個使うか」の4通りと、「3を何個使うか」の3通りは、別々に選べる。だからかけ算で

$$(3+1)(2+1)=4\times 3=12(\text{個})$$

指数に $+1$ するのは、「0個(その素数を使わない)」という選び方を数えるためだ。ここを忘れやすい。

(2) 約数の総和は、次のかけ算を計算すると求まる。

$$(2^0+2^1+2^2+2^3)(3^0+3^1+3^2)$$

なぜこれで総和になるかというと、このカッコを展開すると、$2^a\times 3^b$ の形の約数が1個ずつ全部、ちょうど1回ずつ出てくるからだ。たとえば $2^2\times 3^1=12$ も、この展開の中に必ず現れる。

$$(1+2+4+8)(1+3+9)=15\times 13=195$$

発展 — 一歩先へ。 約数の個数が奇数になるのは、どんな数のときだろうか。

上で見たように、約数は「掛けて $n$ になるペア」で作られる。だから普通は偶数個。ペアの相手が自分自身になるとき、つまり $n$ が平方数のときだけ、$1$ 個あまって奇数個になる($36$ なら $6\times 6$ の $6$ が相方なし)。

公式で見ても同じだ。$n=p^a{q}^b$ の約数の個数 $(a+1)(b+1)$ が奇数 $⟺$ $a$ も $b$ も偶数 $⟺$ $n$ は平方数。$2$ つの説明が同じ結論に着く。

この事実は有名なパズルの答えにもなっている。「$100$ 個のロッカーが閉じている。$1$ 番目の人が全部開け、$2$ 番目の人が $2$ の倍数を切り替え、$3$ 番目の人が $3$ の倍数を切り替え $\cdots$ $100$ 番目まで終わったとき、開いているロッカーは?」— 答えは番号が平方数のロッカー($1,4,9,\dots ,100$ の $10$ 個)。切り替えられた回数が約数の個数で、奇数回切り替わったものだけが開いているからだ。

約数の個数という素朴な量が、パズルの構造を丸ごと決めている。

別解

全部書き出して、公式が本当に正しいことを確かめよう。 そのうえで「なぜ総和の公式があの形になるのか」の種明かしをする。

約数を小さい順に全部書く。

$$1,2,3,4,6,8,9,12,18,24,36,72$$

数えると $12$ 個 ✓。足すと

$$1+2+3+4+6+8+9+12+18+24+36+72=195$$

✓ 公式の答えと一致した。

書き出すときのコツは、ペアで探すこと。$1\times 72$、$2\times 36$、$3\times 24$、$4\times 18$、$6\times 12$、$8\times 9$ — 掛けて $72$ になる組を小さいほうから順に見つける。$8\times 9$ で $\sqrt{72}\approx 8.5$ を越えたので終わり。$6$ 組できたから、約数は $12$ 個。この探し方なら、もれも重複も起きない。

さて、種明かし。なぜ総和が $(1+2+4+8)(1+3+9)$ になるのか。 この積を、そのまま展開してみる。

$$(1+2+4+8)(1+3+9)=1\cdot 1+1\cdot 3+1\cdot 9+2\cdot 1+2\cdot 3+2\cdot 9+4\cdot 1+\cdots +8\cdot 9$$

展開して出てくる項は $12$ 個。それを計算すると

$$1,3,9,2,6,18,4,12,36,8,24,72$$

これは、さっき書き出した約数の一覧と完全に同じ集合だ(順番が違うだけ)。

つまり 「約数を全部足す」$=$「$(2$ の使い方の合計$)\times (3$ の使い方の合計$)$ を展開する」。展開の各項が、約数 $1$ つずつときれいに $1$ 対 $1$ で対応しているのである。

$$\underset{2\text{をどう使うか}}{\underbrace{(1+2+2^2+2^3)}}\times \underset{3\text{をどう使うか}}{\underbrace{(1+3+3^2)}}=15\times 13=195$$

公式は暗記事項ではない。 「約数 $=$ 素因数の選び方」という $1$ つの見方から、個数($4\times 3$)も総和($15\times 13$)も同時に出てくる。同じ絵を、数えるか、足すかの違いだけなのだ。

なお $1+2+4+8=15$ は等比数列の和 $\frac{2^4-1}{2-1}$、$1+3+9=13$ は $\frac{3^3-1}{3-1}$ である。指数が大きい数(たとえば $2^{10}$)でも、等比数列の和の公式で一発だ。