
算数・数学で最初につまずきやすい「素因数分解」「最大公約数」「最小公倍数」。言葉は知っていても、なぜそう求めるのか・どう使うのかがピンと来ていない方も少なくないでしょう。この記事では仕組みをイチから丁寧に解説するとともに、答えと途中式を即座に確認できる無料計算機を用意しました。手を動かしながら理解を深めていただけると嬉しいです。
素因数分解とは
素数とは
素因数分解を理解するためには、まず素数の概念を押さえておく必要があります。
素数とは、1と自分自身以外に約数を持たない、2以上の整数のことです。具体的には 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 … と無限に続きます。
いくつかポイントを確認しておきましょう。
- 2は唯一の偶数の素数。3以上の素数はすべて奇数です
- 1は素数ではない。素数は「ちょうど2つの約数(1と自分自身)を持つ整数」と定義されますが、1の約数は1個だけなので該当しません
- 4, 6, 8, 9, 10 などは合成数(素数でない2以上の整数)と呼ばれます
素因数分解の定義
素因数分解とは、ある正の整数を素数の積(かけ算)で表すことです。
たとえば 12 を素因数分解すると次のようになります。
12 = 2 × 2 × 3 = 2² × 3
この「2」や「3」のように、ある整数を素数の積で表したときに現れる素数を素因数と呼びます。
算術の基本定理(一意分解定理)によれば、1より大きいすべての整数は素数の積として、順序を除いて一意に(ただ1通りに)表せることが証明されています。つまり、どんな整数でも素因数分解の結果は必ず同じになります。12 を 3 × 4 と分解しても、4 = 2² に分解すれば最終的に 2² × 3 と同じ結果が得られます。
試し割り法で素因数分解する手順
最も基本的な素因数分解の方法が試し割り法です。小さい素数から順に割っていく方法で、次の手順で進めます。
① 2で割り切れるなら、商に 2 で割る操作を繰り返す
② 2で割り切れなくなったら、3 で試す
③ 3でも割り切れなくなったら、次の素数(5, 7, 11 …)で試す
④ 商が 1 になったら完了
例題①:60 を素因数分解する
60 ÷ 2 = 30
30 ÷ 2 = 15
15 ÷ 3 = 5
5 ÷ 5 = 1
よって 60 = 2² × 3 × 5 です。
例題②:252 を素因数分解する
252 ÷ 2 = 126
126 ÷ 2 = 63
63 ÷ 3 = 21
21 ÷ 3 = 7
7 ÷ 7 = 1
よって 252 = 2² × 3² × 7 です。
いつまで割り算を続けるか
「割り切れる素数がなくなったときに商が残っていれば、その商自体が素数」というルールがあります。また、√n(nの平方根)を超えた素数で割り切れなければ、その時点の商は素数と判断できます。たとえば 100 を素因数分解するとき、√100 = 10 なので 11 以上の素数でテストする必要はなく、2と 5 で割れば 2² × 5² と分かります。
最大公約数(GCD)とは
最大公約数(Greatest Common Divisor・GCD、またはGCFとも)は、2つ以上の整数に共通する約数のうち最大のものです。
たとえば 12 と 18 の場合を考えます。
- 12 の約数:1, 2, 3, 4, 6, 12
- 18 の約数:1, 2, 3, 6, 9, 18
- 共通の約数(公約数):1, 2, 3, 6
最大のものは 6 なので GCD(12, 18) = 6 です。
素因数分解を使ったGCDの求め方
両方を素因数分解して、共通する素因数を取り出します。それぞれの素因数のうち指数が小さい方を採用し、掛け合わせたものがGCDです。
12 = 2² × 3¹
18 = 2¹ × 3²
GCD = 2^min(2,1) × 3^min(1,2) = 2¹ × 3¹ = 6
GCDの実用例
- 分数の約分:12/18 は GCD=6 で割ると 2/3 になります
- 正方形で敷き詰め:縦12cm・横18cmの長方形を、隙間なく正方形で埋めるには一辺6cmの正方形が使えます(6がGCDのため)
- 荷物の配分:12個と18個の品物を、余りなく同じ数ずつ袋に分けるときの最大袋数が6袋
最小公倍数(LCM)とは
最小公倍数(Least Common Multiple・LCM)は、2つ以上の整数に共通する倍数のうち最小のもの(0を除く)です。
12 と 18 の場合、
- 12 の倍数:12, 24, 36, 48, 60, 72 …
- 18 の倍数:18, 36, 54, 72, 90 …
- 共通の倍数(公倍数):36, 72, 108 …
最小のものは 36 なので LCM(12, 18) = 36 です。
素因数分解を使ったLCMの求め方
それぞれの素因数のうち指数が大きい方を採用し、掛け合わせたものがLCMです。
12 = 2² × 3¹
18 = 2¹ × 3²
LCM = 2^max(2,1) × 3^max(1,2) = 2² × 3² = 4 × 9 = 36
LCMの実用例
- 分数の通分:1/12 + 1/18 を計算するには、LCM(12,18) = 36 を共通分母にして 3/36 + 2/36 = 5/36 と求めます
- 周期が重なるタイミング:12秒ごとに光るランプAと18秒ごとに光るランプBが同時に光るのは36秒ごとです
- 歯車の回転:歯数12と歯数18の歯車が同じ位置に戻るのは、LCMである36歯分だけ動いたとき
GCDとLCMの関係式
GCDとLCMには次の重要な関係式が成り立ちます。
a × b = GCD(a, b) × LCM(a, b)
たとえば 12 × 18 = 216 で、GCD × LCM = 6 × 36 = 216 と一致します。この式を使えば「GCDが分かれば LCM = (a×b)÷GCD で求められる」ことが分かります。
ユークリッドの互除法
大きな数のGCDを求めるとき、いちいち素因数分解するのは手間がかかります。そこで活躍するのがユークリッドの互除法です。
原理は「a と b のGCDは、b と (a÷bの余り) のGCDに等しい」という性質です。割り算のたびに数が小さくなり、余りが0になった時点でのぞいた数(除数)がGCDです。
手順:GCD(252, 105) を求める
252 ÷ 105 = 2 余り 42 → GCD(252, 105) = GCD(105, 42)
105 ÷ 42 = 2 余り 21 → GCD(105, 42) = GCD(42, 21)
42 ÷ 21 = 2 余り 0 → 余りが0 → GCD = 21
よって GCD(252, 105) = 21 です。
ユークリッドの互除法はプログラムでもよく使われるアルゴリズムで、計算ステップ数は入力数の桁数に比例(対数オーダー)するため非常に高速です。紀元前300年頃にユークリッドが記した「原論」に記載されており、現代まで使われ続ける歴史ある手法です。
互いに素とは
GCD(a, b) = 1 のとき、つまり共通する素因数が1つもないとき、a と b は互いに素(coprime / relatively prime)といいます。
たとえば 8 と 9 は、8 = 2³・9 = 3² で共通する素因数がないので互いに素です(GCD = 1)。
互いに素な2つの整数のLCMは a × b に等しくなります。また、暗号理論(RSA暗号など)や中国剰余定理など現代数学・情報科学でも「互いに素」という条件が頻繁に登場します。
素因数分解・最大公約数・最小公倍数 計算機
整数を入力すると素因数分解の途中式とともに、GCDとLCMを即座に表示します。数を1つ入力すると素因数分解の結果だけを、数を2つ入力するとGCDとLCMも一緒に求めます。
手計算の確認や、学習・復習にご活用いただけると嬉しいです。
まとめ
今回は素因数分解・最大公約数・最小公倍数の仕組みと求め方を解説しました。
- 素因数分解:整数を素数の積で表すこと。試し割り法で小さい素数から順に割っていく
- 最大公約数(GCD):共通する約数の最大値。共通する素因数の指数の小さい方を採用
- 最小公倍数(LCM):共通する倍数の最小値。各素因数の指数の大きい方を採用
- 関係式:a × b = GCD(a, b) × LCM(a, b)
- ユークリッドの互除法:余りを使ってGCDを高速に求めるアルゴリズム(紀元前から使われる古典手法)
- 互いに素:GCD = 1 の関係。暗号理論など現代の情報科学でも活躍
小学校の約分・通分から大学の整数論・暗号理論まで幅広く使われる基礎概念です。上の計算機で実際に手を動かしながら、感覚を掴んでみてください。数学のおもしろさについては数学の定理・法則108選もあわせてご覧いただけると嬉しいです。