素因数分解とは?算数・数学における最も美しい基本定理
素因数分解(Prime Factorization)とは、2以上の正の整数を「素数(1とその数自身でしか割り切れない整数)」の掛け算だけの形に分解することを指します。例えば、12 は $2 \times 2 \times 3 = 2^2 \times 3$、360 は $2^3 \times 3^2 \times 5$ と表現できます。
数学には「算術の基本定理(素因数分解の一意性)」という極めて重要な定理が存在します。それは「どのような合成数も、素因数の並び順の違いを除けば、ただ1通りの素数の積として表すことができる」というものです。素数はあらゆる整数を構成する「数の原子」であり、素因数分解はその原子構造を解き明かす操作と言えます。
素因数分解のやり方:すだれ算(連除法)のステップ
小学校・中学校で習う最も標準的で確実な計算手法が「すだれ算(連除法)」です。
- 最も小さい素数 2 で割れるか試す: 入力された数が偶数であれば、奇数になるまで 2 で割り続けます。
- 次の素数 3, 5, 7... で順次割る: 各桁の和が3の倍数なら3で割り、下一桁が0または5なら5で割ります。
- 商が素数になるまで繰り返す: 割り算を続け、商(割った結果)が素数になったら分解終了です。
- 累乗(指数)でまとめる: 同じ素数が複数回現れた場合は、$2 \times 2 \times 2 = 2^3$ のように指数表記で簡潔にまとめます。
素因数分解の応用:何に役立つのか?
- 約数の個数と総和の計算: $N = p^a \times q^b$ のとき、約数の個数は $(a+1)(b+1)$ 個という極めてシンプルな公式で求められます。
- 最大公約数(GCD)と最小公倍数(LCM)の決定: 複数の数を素因数分解し、共通する因数の最小指数を取れば最大公約数、すべての因数の最大指数を取れば最小公倍数が直ちに求まります。
- ルート(平方根)の外し方: 指数が偶数乗になっている因数はそのまま根号の外に出せます。
- 現代の暗号通信(RSA暗号): 巨大な素数同士を掛け算するのは一瞬ですが、掛け合わされた数千桁の合成数を素因数分解するにはスーパーコンピュータでも天文学的な時間がかかります。この「分解の困難性」が、インターネットのクレジットカード決済やセキュリティ通信の安全性を守っています。