最大公約数・最小公倍数 | 高校数学まるごと解説

要点整理

前提知識として、すでに「約数」(ある整数を割り切る整数)と「倍数」(ある整数を整数倍してできる数)の意味は学習済みですね。ここでは、その約数・倍数を2つの数で「共通に」考えたときに出てくる、最大公約数と最小公倍数について整理していきます。

最大公約数(GCD)とは

たとえば、12と18という2つの数を考えます。

12の約数を全部書き出すと、$1, 2, 3, 4, 6, 12$ です。

18の約数を全部書き出すと、$1, 2, 3, 6, 9, 18$ です。

この2つの数の約数のうち、両方に共通しているものを「公約数」といいます。12の約数リストと18の約数リストを見比べると、共通しているのは $1, 2, 3, 6$ です。

この公約数の中で一番大きい数、つまり $6$ のことを、12と18の「最大公約数」といいます。英語では Greatest Common Divisor なので、GCDと略すこともあります。

最小公倍数(LCM)とは

今度は倍数のほうを考えます。

12の倍数を小さい順に書き出すと、$12, 24, 36, 48, 60, 72, \ldots$ です。

18の倍数を小さい順に書き出すと、$18, 36, 54, 72, 90, \ldots$ です。

この2つの数の倍数のうち、両方に共通しているものを「公倍数」といいます。上のリストを見比べると、共通しているのは $36, 72, \ldots$ で、これは無限に続いていきます。

この公倍数の中で一番小さい数、つまり $36$ のことを、12と18の「最小公倍数」といいます。英語では Least Common Multiple なので、LCMと略すこともあります。

素因数分解を使った求め方

さきほどは約数・倍数を全部書き出して求めましたが、数が大きくなると書き出すのは大変です。そこで実際には「素因数分解」(整数を素数だけの掛け算の形に分解すること)を使って求めます。

12と18をそれぞれ素因数分解すると、次のようになります。

$12 = 2^2 \times 3$

$18 = 2 \times 3^2$

最大公約数(GCD)を求めるときは、共通して現れる素因数について、指数が小さいほうを選んで掛け合わせます。

$2$ について、指数は $2$ と $1$ なので、小さいほうの $2^1$ を選びます。
$3$ について、指数は $1$ と $2$ なので、小さいほうの $3^1$ を選びます。

これらを掛け合わせると、

$\text{GCD} = 2^1 \times 3^1 = 2 \times 3 = 6$

となり、さきほど書き出して求めた最大公約数 $6$ と一致します。

最小公倍数(LCM)を求めるときは、現れるすべての素因数について、指数が大きいほうを選んで掛け合わせます(片方にしか現れない素因数があれば、その素因数もそのまま使います)。

$2$ について、大きいほうの $2^2$ を選びます。
$3$ について、大きいほうの $3^2$ を選びます。

これらを掛け合わせると、

$\text{LCM} = 2^2 \times 3^2 = 4 \times 9 = 36$

となり、こちらもさきほどの結果 $36$ と一致します。

最大公約数と最小公倍数の関係

ここで、GCDとLCMの間に成り立つ、とても便利な関係を紹介します。2つの自然数を $a, b$ とし、その最大公約数を $G$、最小公倍数を $L$ とすると、次の関係が必ず成り立ちます。

$a \times b = G \times L$

先ほどの例で確かめてみましょう。$a=12, b=18$ のとき、$a \times b = 12 \times 18 = 216$ です。一方、$G=6, L=36$ なので、$G \times L = 6 \times 36 = 216$ となり、たしかに一致しています。

この関係は、片方の数が分からないときに、もう片方の数から逆算する場面でとても役に立ちます。

互いに素

最大公約数が $1$ になる、つまり共通の約数が $1$ しかない2つの整数のことを「互いに素である」といいます。たとえば $8$ と $15$ を考えると、$8=2^3$、$15=3 \times 5$ で共通する素因数がないので、最大公約数は $1$ です。したがって $8$ と $15$ は互いに素です。この考え方は、次の例題でも使っていきます。

例題

例題1(基本)

問題

$36$ と $48$ の最大公約数と最小公倍数を、それぞれ素因数分解を利用して求めなさい。

解答・解説を見る

まず、$36$ と $48$ をそれぞれ素因数分解します。

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

$48 = 2^4 \times 3$

最大公約数を求める

共通する素因数について、指数が小さいほうを選びます。

$2$ については、指数 $2$ と $4$ のうち小さいほうの $2^2$
$3$ については、指数 $2$ と $1$ のうち小さいほうの $3^1$

これらを掛け合わせます。

$\text{GCD} = 2^2 \times 3^1 = 4 \times 3 = 12$

最小公倍数を求める

すべての素因数について、指数が大きいほうを選びます。

$2$ については、指数 $2$ と $4$ のうち大きいほうの $2^4$
$3$ については、指数 $2$ と $1$ のうち大きいほうの $3^2$

これらを掛け合わせます。

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

検算

$a \times b = G \times L$ の関係を使って確かめます。

$36 \times 48 = 1728$

$12 \times 144 = 1728$

両辺が一致したので、計算は正しいと確認できます。

したがって、最大公約数は $12$、最小公倍数は $144$ です。

例題2(標準)

問題

最大公約数が $6$、最小公倍数が $72$ であるような2つの自然数の組 $(a, b)$($a \leqq b$)をすべて求めなさい。

解答・解説を見る

いきなり $a, b$ を求めようとすると難しいので、最大公約数を使って $a, b$ を表すところから始めます。

$a$ と $b$ の最大公約数が $6$ であるということは、$a$ も $b$ も $6$ で割り切れるということです。そこで、

$a = 6a', \quad b = 6b'$

とおきます。ここで $a'$ と $b'$ は自然数で、しかも「$a$ と $b$ の公約数はちょうど $6$ しかない」ようにするためには、$a'$ と $b'$ は互いに素(最大公約数が $1$)である必要があります。

次に、最大公約数と最小公倍数の関係の式を使います。

$a \times b = G \times L$

$G=6$、$L=72$ を代入すると、

$a \times b = 6 \times 72 = 432$

一方、$a=6a'$、$b=6b'$ を代入すると、

$a \times b = 6a' \times 6b' = 36 \, a'b'$

この2つの式は同じ $a \times b$ を表しているので、

$36 \, a'b' = 432$

両辺を $36$ で割ります。

$a'b' = 12$

つまり、「積が $12$ になり、かつ互いに素である自然数の組 $(a', b')$」を探せばよいことになります。

$12$ を2つの自然数の積で表す組を、$a' \leqq b'$ となるように書き出すと、次の3通りです。

$a'=1, b'=12$
$a'=2, b'=6$
$a'=3, b'=4$

それぞれについて、互いに素かどうかを確認します。

$1$ と $12$ ……最大公約数は $1$ なので、互いに素です。
$2$ と $6$ ……どちらも $2$ で割り切れるので、最大公約数は $2$ です。互いに素ではありません。
$3$ と $4$ ……最大公約数は $1$ なので、互いに素です。

したがって、条件を満たすのは $(a', b')=(1,12)$ と $(a', b')=(3,4)$ の2通りです。

最後に、$a=6a'$、$b=6b'$ に戻します。

$(a', b')=(1,12)$ のとき、$(a,b)=(6 \times 1,\ 6 \times 12)=(6, 72)$

$(a', b')=(3,4)$ のとき、$(a,b)=(6 \times 3,\ 6 \times 4)=(18, 24)$

検算

$(6,72)$ について、$6=2\times3$、$72=2^3\times3^2$ なので最大公約数は $2\times3=6$、最小公倍数は $2^3\times3^2=72$ となり、条件に合います。

$(18,24)$ について、$18=2\times3^2$、$24=2^3\times3$ なので最大公約数は $2\times3=6$、最小公倍数は $2^3\times3^2=72$ となり、こちらも条件に合います。

以上より、求める組は $(a,b)=(6,72),\ (18,24)$ です。

例題3(応用)

問題

縦 $48\,\text{cm}$、横 $60\,\text{cm}$ の長方形の紙があります。これを、あまりが出ないように、同じ大きさの正方形にすべて切り分けます。正方形の枚数をできるだけ少なくするには、正方形の1辺を何cmにすればよいですか。また、そのときの枚数を求めなさい。

解答・解説を見る

正方形の1辺の長さを $x\,\text{cm}$ とします。この正方形で長方形をあまりなく敷き詰めるためには、縦の長さ $48$ も横の長さ $60$ も、どちらも $x$ でちょうど割り切れる必要があります。

つまり、$x$ は $48$ と $60$ の「公約数」でなければなりません。

さらに、正方形の枚数をできるだけ少なくしたいので、1枚あたりの正方形をできるだけ大きくしたいということになります。公約数の中で一番大きいものは「最大公約数」ですから、$x$ は $48$ と $60$ の最大公約数にすればよいとわかります。

そこで、$48$ と $60$ を素因数分解します。

$48 = 2^4 \times 3$

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

最大公約数は、共通する素因数について指数の小さいほうを選んで掛け合わせたものです。

$2$ については、指数 $4$ と $2$ のうち小さいほうの $2^2$
$3$ については、指数 $1$ と $1$ のうち小さいほうの $3^1$
$5$ については、$48$ には含まれていないので、共通の素因数にはなりません

これらを掛け合わせます。

$\text{GCD} = 2^2 \times 3 = 4 \times 3 = 12$

したがって、正方形の1辺は $12\,\text{cm}$ にすればよいとわかります。

次に、そのときの枚数を求めます。縦方向には $48 \div 12 = 4$ 枚、横方向には $60 \div 12 = 5$ 枚並ぶことになります。

長方形全体では、縦方向の枚数と横方向の枚数を掛け合わせたものが全体の枚数になるので、

$4 \times 5 = 20$

より、正方形は全部で $20$ 枚になります。

以上より、正方形の1辺は $12\,\text{cm}$、そのときの枚数は $20$ 枚です。

練習問題

問題

$90$ と $105$ の最大公約数と最小公倍数を、それぞれ求めなさい。

答え

$90 = 2 \times 3^2 \times 5$、$105 = 3 \times 5 \times 7$ と素因数分解できます。

最大公約数は、共通する素因数 $3$ と $5$ の指数が小さいほうを掛け合わせて、

$\text{GCD} = 3 \times 5 = 15$

最小公倍数は、すべての素因数の指数が大きいほうを掛け合わせて、

$\text{LCM} = 2 \times 3^2 \times 5 \times 7 = 2 \times 9 \times 5 \times 7 = 630$

(検算: $90 \times 105 = 9450$、$15 \times 630 = 9450$ で一致します。)

よって、最大公約数は $15$、最小公倍数は $630$ です。