素因数分解を学ぼう！

$1$. 素因数分解ってなんだろう？

素因数分解（そいんすうぶんかい）とは、$1$より大きい自然数を、素数だけの掛け算の形に分解することです。一見すると複雑な計算に思えるかもしれませんが、これは数の「設計図」を明らかにするような、とても面白い作業です。すべての建物がレンガや木材といった基本的な材料からできているように、すべての合成数（素数でない数）は素数という基本的なブロックの組み合わせでできています。

まず、この「素数」という言葉が鍵になります。素数とは、$2, 3, 5, 7, 11, \dots$ のように、「$1$とその数自身以外に約数を持たない、$1$より大きい自然数」のことです。素数は、これ以上分解できない数の最小単位と考えることができます。

例えば、数字の$12$を素因数分解すると、次のようになります。

$12 = 2 \times 2 \times 3 = 2^2 \times 3$

この結果が意味するのは、「$12$という数は、$2$という素数$2$個と、$3$という素数$1$個の掛け算で成り立っている」ということです。そして、とても重要な事実として、どんな合成数も、掛け合わせる素数の順番を無視すれば、その分解方法はただ一通りしかありません。これを数学の世界では「算術の基本定理」と呼びます。この性質があるからこそ、素因数分解は数学の様々な場面で強力なツールとなるのです。

豆知識 $1$：素因数分解はネット社会の縁の下の力持ち

私たちが普段使っているインターネットのセキュリティは、素因数分解が「非常に難しい」という性質を利用しています。特に「RSA暗号」という技術では、$2$つの巨大な素数を掛け合わせるのは簡単ですが、その掛け合わされた数から元の$2$つの素数を探り当てる（素因数分解する）のは、スーパーコンピュータを使っても天文学的な時間がかかります。この性質のおかげで、私たちの個人情報やクレジットカード情報は安全に守られているのです。

$2$. 「すだれ算」で素因数分解してみよう！

素因数分解を効率的に、そして間違いなく行う方法として「すだれ算（連除法）」が広く使われます。やり方はとてもシンプルです。

分解したい数を書きます。
その数を割り切れる最も小さい素数で割ります。($2$で割れるか、$3$で割れるか、$5$で割れるか…と順番に試すのがコツです)
計算結果（商）を下に書きます。
計算結果が素数になるまで、$2$と$3$の手順を繰り返します。

ポイント：なぜ小さい素数から試すのが良いのでしょうか？それは、小さい素数で割り切れるだけ割っておけば、後からその倍数（例えば$4$や$6$など）で割れるかどうかを考える必要がなくなり、常に素数だけで割り進めることができるからです。これにより、ミスが減り、効率的に分解を進められます。

それでは、$84$を素因数分解してみましょう。

$$ \begin{array}{r|l} 2 & 84 \\ \hline 2 & 42 \\ \hline 3 & 21 \\ \hline & 7 \end{array} $$

すだれの左側に出てきた割る数（$2, 2, 3$）と、最後に残った素数（$7$）をすべて掛け合わせれば、素因数分解の完成です。

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

$3$. 素因数分解の便利な使い道

素因数分解は、それ自体が目的というより、他の問題を解くための強力な道具として真価を発揮します。ここでは主な$3$つの応用例を見てみましょう。

最大公約数（GCD）と最小公倍数（LCM）

複数の数の最大公約数や最小公倍数を探すとき、素因数分解は絶大な威力を発揮します。例えば、$36$と$48$で考えてみましょう。

$36 = 2^2 \times 3^2$

$48 = 2^4 \times 3^1$

最大公約数 (GCD): 両方に共通する素因数を抜き出し、指数の小さい方を取って掛け合わせます。
共通するのは$2$と$3$。指数は$2$が$\min(2, 4)=2$、$3$が$\min(2, 1)=1$なので…
$GCD = 2^2 \times 3^1 = 4 \times 3 = 12$
最小公倍数 (LCM): 両方に登場するすべての素因数を抜き出し、指数の大きい方を取って掛け合わせます。
登場するのは$2$と$3$。指数は$2$が$\max(2, 4)=4$、$3$が$\max(2, 1)=2$なので…
$LCM = 2^4 \times 3^2 = 16 \times 9 = 144$

平方根の簡略化

ルート（$\sqrt{\phantom{x}}$）の中の数字をできるだけ小さくする際にも、素因数分解が役立ちます。ルートの中から外に出せるのは「$2$乗」のペアになっている数です。

例えば、$\sqrt{72}$を簡単にしてみましょう。

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

ここで、$2^2$と$3^2$はペアになっているのでルートの外に出せます。

$\sqrt{72} = \sqrt{2^2 \times 3^2 \times 2} = \sqrt{2^2} \times \sqrt{3^2} \times \sqrt{2} = 2 \times 3 \times \sqrt{2} = 6\sqrt{2}$

豆知識 $2$：現在知られている最大の素数

素数は無限に存在することが証明されていますが、人間が発見した「最大の素数」の記録は常に更新されています。$2024$年$10$月に、新しい最大の素数が発見されました。その数はなんと...

$2^{136,279,841} - 1$

...という数で、十進法で書くと$41,024,320$桁にもなります。これは「メルセンヌ素数」と呼ばれる特別な形の素数で、「GIMPS」というプロジェクトによって発見されました。

豆知識 $3$：素因数分解と完全数

「完全数」という数を知っていますか？完全数とは、「その数自身を除く約数の和が、その数自身と等しくなる自然数」のことです。例えば、最小の完全数は$6$です。$6$の約数は$1, 2, 3, 6$ですが、自分自身（$6$）を除いた約数の和は $1+2+3=6$ となり、元の数に戻ります。

実は、この完全数はメルセンヌ素数と深い関係があります。$2^p-1$がメルセンヌ素数であるとき、$2^{p-1}(2^p-1)$は必ず偶数の完全数になります。これまでに見つかっている完全数は、すべてこの形をしています。（奇数の完全数が存在するかどうかは、未解決問題です！）

$4$. 練習問題

問題数: $25$