数学A / 整数の性質

約数の個数から数を決める

★★ 標準約数の個数

問題

正の約数がちょうど $15$ 個ある自然数のうち、最小のものを求めよ。

ヒントを見る

約数の個数は『(各指数 $+ 1$ )の積』。まず $15$ を積の形( $15 = 15$ 、 $3 \times 5$ )に分ける → 指数の組がわかる。数を小さくするには、大きい指数を小さい素数に割り当てる。

解答・解説

『約数の個数 $=$ (各指数 $+ 1$ )の積』を逆に使う。 $15$ を『(指数 $+ 1$ )の積』に分解して指数の組を出し、いちばん小さくなる数を作る。

⓪ 発想 — どう考え始めるか。 「約数の個数 =(各指数 $+ 1$ )の積」を、今回は逆向きに使う。

個数 $15$ を「(指数 $+ 1$ )の積」に分解する。 $15 = 15$ と $15 = 3 \times 5$ の2通りだ。ここから指数の組( $p^{14}$ 型と $p^{2} q^{4}$ 型)が決まる。

最小の数を作る仕上げは「大きい指数ほど小さい素数に割り当てる」。候補どうしを比べて最小を選ぶ。

公式約数の個数は(各指数

+ 1

)の積 → 逆に個数を「(指数

+ 1

)の積」に分解する

約数の個数は『(各指数 $+ 1$ )をかけたもの』。だから $15$ を『(指数 $+ 1$ )の積』に分ける。

$15 = 15$ または $15 = 3 \times 5$ 。

$15 = 15$ の場合:指数 $+ 1 = 15$ 、つまり指数 $14$ の素数 $1$ つ。最小は $2^{14}$ で、これはとても大きい。

$15 = 3 \times 5$ の場合:指数が $2$ と $4$ の素因数 $2$ つ。数を小さくするには、大きい指数 $4$ を小さい素数 $2$ に、指数 $2$ を次の素数 $3$ に割り当てる。

$2^{4} \times 3^{2} = 16 \times 9 = 144$

( $2^{2} \times 3^{4} = 4 \times 81 = 324$ よりこちらが小さい。『大きい指数ほど小さい素数へ』が最小化のコツだ。) $2^{14}$ は $144$ よりはるかに大きいので、答えは

$144$

発展 — 一歩先へ。 「約数の個数が奇数 ⟺ 平方数」には有名な応用がある。100枚のロッカーの開閉問題(1番から100番の人が自分の倍数番のロッカーを反転していくと、最後に開いているのは平方数番だけ)は、まさにこの事実の言い換えだ。

「個数ちょうど $k$ 個の最小数」は、 $k$ の分解が増えるほど候補の比較が本格化する( $k = 12$ なら分解が4通り)。「大きい指数を小さい素数へ」の原理だけでは足りず、実際に数を比べる検分が最後に必要になる。

答

$144$

計算の前に、答えの「正体」を1つ予言できる。約数の個数 $15$ は奇数。実は、約数の個数が奇数になる数は平方数だけだ。

理由はペアの構造にある。約数は $d$ と $\frac{n}{d}$ のペアで現れるから、ふつうは偶数個。ペアが崩れるのは $d = \frac{n}{d}$ 、つまり $n = d^{2}$ となる相方が自分自身の約数があるときだけ。それが平方数だ。

だから答えは平方数のはず。実際、候補の $2^{14} = 12 8^{2}$ 、 $2^{4} \times 3^{2} = 144 = 1 2^{2}$ 、 $2^{2} \times 3^{4} = 324 = 1 8^{2}$ はすべて平方数で、最小は $144$ 。

「個数が奇数 ⟺ 平方数」は、それ自体が頻出の知識でもある。答えの形を先に知ってから計算に入ると、指数の割り当てミスにも気づきやすい。