【基本】最大公約数と最小公倍数

🕒 2018/07/22 🔄 2023/05/01

ここでは、最大公約数と最小公倍数について見ていきます。小学生のときにも学んだ内容ですが、ここでは、素因数分解を利用して考えなおしてみます。

📘 目次

最大公約数と最小公倍数

【基本】約数と倍数で見た通り、2つの整数 $a,b$ に対して、 $a=bk$ を満たす整数 $k$ があるとき、 $b$ は $a$ の約数といい、 $a$ は $b$ の倍数というのでしたね。

例えば、 $6$ の約数というのは、 $\pm1,\pm2,\pm3,\pm6$ となります。負の整数も対象であることに注意しましょう。また、 $8$ の約数は、 $\pm1,\pm2,\pm4,\pm8$ となります。

これらの中には、 $1$ や $2$ のように、かぶっているものもあります。このように、共通している約数を、公約数(common divisor) といいます。また、公約数の中で、一番大きいものを最大公約数(greatest common divisor、略して、GCD とも書く) といいます。先ほどの例であれば、 $6$ と $8$ の公約数は $\pm1,\pm2$ で、最大公約数は $2$ となります。

倍数についても、「共通する倍数」を考えることができます。共通している倍数を、公倍数(common multiple) といいます。また、こうした公倍数のうち、正の整数の中で一番小さいものを、最小公倍数(least common multiple、略して、LCM とも書く) といいます。 $2$ と $3$ の公倍数は、 $0,\pm6,\pm12,\pm18,\cdots$ と無数にあり、最小公倍数は $6$ となります。

ここに挙げた内容は、小学生のときに扱っていた内容と大きくかぶっています。公倍数や公約数に負の数が含まれている点が異なりますが、他は同じ内容です。

小学生の時は、最大公約数や最小公倍数を求めるために、具体的に約数や倍数を書き出して考えていたかもしれませんが、以下では、素因数分解を用いて考える方法を見ていきます。

最大公約数と素因数分解

【基本】素因数分解と約数の個数では、素因数分解することによって、各素因数の指数に注目すれば、約数そのものや約数の個数を考えやすくなることを見ました。この素因数分解を用いる考え方は、最大公約数・最小公倍数を考えるうえでも有効です。

例えば、 $48$ と $216$ について考えてみましょう。これらの最大公約数・最小公倍数を考えるには、今まではそれぞれの約数や倍数を書き出して考えていたかもしれません。ここでは、これらを素因数分解して、\[ 2^4\times 3,\quad 2^3\times 3^3 \]として考えてみましょう。以下では、正の約数について考えていきます。

$2^4\times 3$ の約数は、 $2^a\times 3^b$ と書けます。ここで、 $a=0,1,2,3,4$, $b=0,1$ です。また、 $2^3\times 3^3$ の約数は、 $2^c\times 3^d$ と書けます。ここで、 $c,d$ は $0$ から $3$ までの整数です。よって、両方に共通する約数は、 $2^x\times 3^y$ と書けることがわかります。

さらに、例えば、 $x=4$ とはできないことがわかります。なぜなら、 $c$ は $3$ までの値しかとれないからです。 $y$ も $2$ になることはできません。 $x$ は $a,c$ がとり得る値の小さい方、つまり、 $3$ までの値しかとれません。 $y$ も同様に考えて、 $1$ までの値しかとれません。よって、最大公約数は\[ 2^3\times 3^1=24 \]だということがわかります。

つまり、最大公約数を考えるには、各整数を素因数分解し、各素因数の指数が小さい方を選んでいけばいい、ということです。\[ 2^4\times 3,\quad 2^3\times 3^3 \]であれば、素因数 $2$ の指数が小さいのは後者の $3$ で、素因数 $3$ の指数が小さいのは前者の $1$ だから、 $2^3\times 3^1$ だとわかるわけですね。

最小公倍数と素因数分解

続いて、最小公倍数について考えてみましょう。ここでも $48$, $216$ について考えますが、素因数分解した形\[ 2^4\times 3,\quad 2^3\times 3^3 \]で考えてみましょう。ここでは、正の倍数についてのみ考えていきます。

$2^4\times 3$ の倍数というのは、素因数 $2$ の指数は $4$ 以上でないといけません。素因数 $3$ の指数は $1$ 以上でないといけません。他には条件はいらないですね。これ以外の素因数が追加されても構いません（例えば $\times 5^2$ などが含まれていてもいい）。

$2^3\times 3^3$ の倍数も同様で、素因数 $2,3$ の指数がどちらも $3$ 以上ならいいですね。

これらの倍数のうち、共通するもので一番小さいものを考える、となれば、余分な素因数を含めないほうがいいでしょう。なので、最小公倍数は、 $2^x\times 3^y$ の形になっているはずです。また、指数の条件を考えると、各指数の大きい方を選べばいいですね。 $2^4\times 3^3$ とすれば、どちらの指数の条件も満たしているし、そうした条件を満たしている中で一番小さいことがわかります。

つまり、最小公倍数を考えるには、各整数を素因数分解し、各素因数の指数が大きい方を選んでいけばいい、ということです。\[ 2^4\times 3,\quad 2^3\times 3^3 \]であれば、素因数 $2$ の指数が大きいのは前者の $4$ で、素因数 $3$ の指数が小さいのは後者の $3$ だから、最小公倍数は、 $2^4\times 3^3=432$ だとわかるわけですね。