素因数分解

方針

解答

⓪ 発想 — どう考え始めるか。 素因数分解は、小さい素数から順に、割り切れなくなるまで割る。手順は決まっている。

$$2\to 3\to 5\to 7\to 11\to \dots$$

$2$ で割れるだけ割ってから $3$ へ、$3$ で割れるだけ割ってから $5$ へ — 飛ばさず、戻らず。

急所は $2$ つ。

$1$ つ目: 素数でない数で割らない。 $4$ や $6$ で割ると、分解が途中で止まったり、素因数を見落としたりする。

$2$ つ目: 最後に残った数が素数かどうか、必ず確かめる。 $49$ を「もう割れない」と思って素数扱いすると、$7^2$ を見逃す。$49=7\times 7$ である。

どこまで試せばよいか。割る素数が $\sqrt{(\text{残った数})}$ を超えたら、残りは素数だと分かる。

(1) 小さい素数から順に割る。

$$360=2\times 180=2\times 2\times 90=2\times 2\times 2\times 45$$

$45$ はもう $2$ で割れない。次は $3$:$45=3\times 15=3\times 3\times 5$。$5$ は素数。まとめると

$$360=2^3\times 3^2\times 5$$

(2) 同じように $2$ から。

$$1176=2\times 588=2\times 2\times 294=2\times 2\times 2\times 147$$

$147$ は $2$ で割れない。$3$ で割ると $147=3\times 49$、そして $49=7\times 7$。よって

$$1176=2^3\times 3\times 7^2$$

(検算:$2^3\times 3\times 7^2=8\times 3\times 49=1176$。組み立て直して元に戻るか確かめると安心だ。)

発展 — 一歩先へ。 「どんな分解の道を通っても同じ答えになる」— この当たり前に見える事実には、素因数分解の一意性(算術の基本定理)という立派な名前がついている。

$$2\text{以上のどんな整数も、素数の積として、順序を除いてただ 1 通りに書ける}$$

当たり前だと思うだろうか。 しかし、少し違う数の世界を作ると、この性質はあっさり壊れる。たとえば「偶数だけの世界」を考えると、$60=2\times 30=6\times 10$ となり、$2,30,6,10$ はどれもその世界ではそれ以上分解できない数(この世界に $3$ や $5$ はいない)。分解が $2$ 通りできてしまうのだ。

整数の世界で一意性が成り立つのは、$1$ つの定理として証明されるべき事実であって、当たり前ではない。そしてこの一意性こそが、約数の個数の公式も、最大公約数の求め方も、すべてを支えている。

現代の暗号技術は、この定理を逆手にとっている。 「$2$ つの巨大な素数を掛けるのは一瞬でできるが、その積を素因数分解するのは天文学的に難しい」— インターネットの通信を守っている仕組みは、この非対称性の上に立っている。

$300$ 桁の合成数を素因数分解するのは、現在の計算機では数万年かかる。素因数分解は、簡単そうに見えて、実は人類最強クラスの難問なのだ。$1176$ を割っている手つきの先に、そんな世界が広がっている。

別解

知っている掛け算から分解していくやり方も紹介しよう。慣れると、小さい素数で順に割るより速い。そして「どこまで試し割りすればよいか」の理屈も押さえる。

別ルート: 覚えている積に分けて、そこから枝を伸ばす(樹形図)。

(1) $360$。 「$360=36\times 10$」はすぐ思いつく。あとはそれぞれを分解する。

$$360=36\times 10=(4\times 9)\times (2\times 5)=(2^2\times 3^2)\times (2\times 5)=2^3\times 3^2\times 5$$

$2$ の個数を数え間違えないこと。 $4$ から $2$ 個、$10$ から $1$ 個で、合わせて $3$ 個 → $2^3$ ✓。

どんな道を通っても、たどり着く答えは同じ。 $360=8\times 45=2^3\times (9\times 5)=2^3\times 3^2\times 5$ でも同じである。これは偶然ではなく、素因数分解の一意性という定理が保証している(下の発展を参照)。

(2) $1176$。 こちらは目星がつきにくいので、素直に $2$ で割っていく。

$$1176÷2=588,588÷2=294,294÷2=147$$

$147$ は奇数なので $2$ では止まり。次は $3$。各位の和が $1+4+7=12$ で $3$ の倍数だから割れる。

$$147÷3=49$$

ここが山場。$49$ を「割れない」と早合点しない。 $49=7^2$ である。

$$1176=2^3\times 3\times 7^2$$

どこまで試し割りすればよいか。

$1176$ を分解するとき、$2,3,5,7,11,13,\dots$ とどこまで試せばよいのだろう。答えは $\sqrt{1176}\approx 34.3$ まで。$34$ 以下の素数($2,3,5,\dots ,31$)で全部割り切れなければ、残った数は素数だと確定する。

なぜ $\sqrt{n}$ で足りるのか。 もし $n$ が合成数なら $n=a\times b$($a\leqq b$、どちらも $2$ 以上)と書ける。ここで $a$ と $b$ の両方が $\sqrt{n}$ より大きいことはありえない(もしそうなら $a\times b>\sqrt{n}\times \sqrt{n}=n$ となって矛盾)。

つまり、合成数なら必ず $\sqrt{n}$ 以下の約数を持つ。 $\sqrt{n}$ まで探して見つからなければ、それは素数だ。

この事実は実用的に大きい。$1176$ を調べるのに $1175$ 回割る必要はなく、$34$ までの素数 $11$ 個を試すだけでよい。探索範囲が劇的に縮む — 素数判定のアルゴリズムは、まずこの一手から始まる。

検算の習慣。 分解できたら、必ず掛け戻す。

$$2^3\times 3\times 7^2=8\times 3\times 49=24\times 49=1176✓$$