整数の性質｜最大公約数と最小公倍数について
今回は最大公約数と最小公倍数について学習しましょう。こちらも小中学校で学習した内容の続きになるので、忘れていないか確認しながら取り組みましょう。
最大公約数と最小公倍数、互いに素
この単元では、以下のような事柄を学習します。
「最大公約数と最小公倍数について」で学習する事柄
- 最大公約数
- 最小公倍数
- 互いに素
- ２つの整数の積、最大公約数、最小公倍数の関係
初めて聞く用語があるので、定義を文言通り正しく覚えましょう。
最大公約数と最小公倍数
最大公約数
２つ以上の整数について、共通の約数のことを公約数と言います。公約数は、整数を積の形で表したときの共通な因数と考えることもできます。
このような公約数のうち、正で最大のものを最大公約数（Greatest Common Measure , G.C.M.）と言います。
１２と１６の最大公約数
それぞれの約数を調べると
\begin{align*} &\quad 12 \ \cdots \ 1 \ , \ 2 \ , \ 3 \ , \ \underline{4} \ , \ 6 \ , \ 12 \\[ 7pt ] &\quad 16 \ \cdots \ 1 \ , \ 2 \ , \ \underline{4} \ , \ 8 \ , \ 16 \end{align*}よって、$12$ と $16$ の最大公約数は $4$
教科書や参考書では、省略形はG.C.M.と記述されることが多いですが、他にも「G.C.D.（Greatest Common Divisor）」「G.C.F.（Greatest Common Factor）」「H.C.F.（Highest Common Factor）」等と記述されることもあるようです。
最小公倍数
２つ以上の整数について、共通の倍数のことを公倍数と言います。このような公倍数のうち、正で最小のものを最小公倍数（Least Common Multiple , L.C.M.）と言います。
１２と１６の最小公倍数
それぞれの倍数を調べると
\begin{align*} &\quad 12 \ \cdots \ 12 \ , \ 24 \ , \ 36 \ , \ \underline{48} \ ,\cdots \\[ 7pt ] &\quad 16 \ \cdots \ 16 \ , \ 32 \ , \ \underline{48} \ , \ 64 \ ,\cdots \end{align*}よって、$12$ と $16$ の最小公倍数は $48$
教科書や参考書では、省略形はL.C.M.と記述されることが多いですが、小文字にしたlcmと記述されることもあります。
最大公約数や最小公倍数の求め方
中学までの求め方（２つの整数のとき）
整数がそれほど大きくなければ、暗算で最大公約数や最小公倍数を求めることができるでしょう。
たとえば、２４と３６の最大公約数や最小公倍数であれば、頭の中では次のようなことを考えているのではないでしょうか。
２４と３６の最大公約数と最小公倍数
それぞれの約数を大きい方から調べると
\begin{align*} &\quad 36 \ \cdots \ 36 \ , \ 18 \ , \ \underline{12} \ ,\cdots \\[ 7pt ] &\quad 24 \ \cdots \ 24 \ , \ \underline{12} \ ,\cdots \end{align*}よって、$24$ と $36$ の最大公約数は $12$
また、それぞれの倍数を小さい方から調べると
\begin{align*} &\quad 36 \ \cdots \ 36 \ , \ \underline{72} \ , \ 108 \ ,\cdots \\[ 7pt ] &\quad 24 \ \cdots \ 24 \ , \ 48 \ , \ \underline{72} \ ,\cdots \end{align*}よって、$24$ と $36$ の最小公倍数は $72$
最大公約数であれば、大きい方の整数の約数を大きい順に挙げながら、その約数で小さい方の整数を割り切れるか調べましょう。
例のように、３６の約数を大きい方から挙げ、それで２４を割ります。割り切れれば、それは２４の約数でもあります。３６や１８では割り切れませんが、１２なら割り切れます。
また、最小公倍数であれば、大きい方の整数の倍数を小さい順に挙げながら、それが小さい方の整数で割り切れるかを調べましょう。
例のように、３６の倍数を小さい方から挙げ、それを２４で割ります。割り切れれば、それは２４の倍数でもあります。３６は２４で割り切れませんが、７２なら２４で割り切れます。
２つの整数がそれほど大きくなければ、このような調べ方もあります。暗算でできるのが利点ですが、難しく感じるならば、きちんと書き並べる方法が最も確実です。
書き並べる方法よりも手間の少ない方法が筆算です。
筆算では、２つの整数を共通に割り算するのが特徴的です。割り算は下にしていくので、商を２つの整数の下にそれぞれ書きます。これを繰り返し、共通に割れなくなれば筆算を終えます。
共通に割れなくなれば、縦と横に並んだ数を使って、最大公約数や最小公倍数を求めます。求め方は簡単です。
筆算での求め方
- 最大公約数 … 縦に並んだ数の積
- 最小公倍数 … 縦と横に並んだ数の積
この方法では、手順通りに進めていけば機械的に求めることができます。
中学までの求め方（３つの整数のとき）
３つ以上の整数の場合、少し難しくなります。３つの整数を共通に割っていき、商を下にそれぞれ書いていくことを繰り返します。ここまでは同じですが、共通に割れなくなった後が問題です。
３つの整数を共通に割れなくなったら、それまでに縦に並んだ数の積が最大公約数になります。ここから先は最小公倍数を求めるための計算です。
３つの整数のうち、２つを共通に割っていきます。このとき、割れない残りの１つはそのまま下に書きます。２つの整数でも共通に割れなくなれば筆算を終えます。縦と横に並んだ数の積が最小公倍数です。
３つ以上の整数では、最小公倍数の求め方に注意する必要があります。ここまでが小・中学校で学習した方法です。
ここからがこの単元の本題です。ここでは、素因数分解を利用した方法を学習します。
素因数分解を利用した求め方
２つの整数を素因数分解すると、２つの整数の成り立ちが良く分かります。この素因数に注目して、最大公約数や最小公倍数を求めることができます。
まず、２つの整数をそれぞれ素因数分解します。
２４と３６の素因数分解
\begin{align*} 24 &= \underline{2 \times 2} \times 2& &\underline{\times 3}& &= 2^{3} \times 3^{1} \\[ 7pt ] 36 &= \underline{2 \times 2}& &\underline{\times 3} \times 3& &= 2^{2} \times 3^{2} \end{align*}２つの整数をそれぞれ素因数分解すると、素因数には共通のものとそうでないものとがあることが分かります。
２４と３６は、２個の２と１個の３を共通にもっています。ですから、先ほどの筆算で、２で２回、３で１回だけ共通に割ることができたのです。
最大公約数は、２つの整数を共通に割れる数のうち、正で最大のものです。ですから、最大公約数は、共通の素因数をすべてもつ数であれば良いことが分かります。
筆算では共通の数で割りますが、これが共通の素因数となるので、縦に並んだ数の積が最大公約数となるのは明らかです。
２４と３６の最大公約数
\begin{align*} 24 &= \underline{2 \times 2} \times 2& &\underline{\times 3}& &= 2^{3} \times 3^{1} \\[ 7pt ] 36 &= \underline{2 \times 2}& &\underline{\times 3} \times 3& &= 2^{2} \times 3^{2} \end{align*}よって、$24$ と $36$ の最大公約数は
\begin{align*} \quad 2 \times 2 \times 3 &= 2^{2} \times 3^{1} \\[ 7pt ] &= 12 \end{align*}また、整数の倍数は、もとの整数に新たに数を掛け算して得られます。
たとえば、２４の倍数なら２４を△倍したもので、３６の倍数なら３６を□倍したものです（△や□には整数が入ります）。
２４と３６の倍数
$24$ の倍数は
\begin{align*} \quad 24 \times \text{□} = 2 \times 2 \ \underline{\underline{\times 2}} \times 3 \times \text{□} \end{align*}$36$ の倍数は
\begin{align*} \quad 36 \times \text{△} = 2 \times 2 \ \underline{ \times 3} \times 3 \times \text{△} \end{align*}共通の積になるためには、$24$ には $2$ が $1$ つ、$36$ には $3$ が $1$ つだけ余分にある。
公倍数であれば、新たな数を掛けたとしても素因数分解したときの式が全く同じになるはずです。
それでは、公倍数の中でも最小となるにはどうすれば良いでしょうか？
２４と３６に何を掛ければ最小公倍数になるか
$24$ に $3$ を掛けたとき
\begin{align*} \quad 24 \times 3 = 2 \times 2 \ \underline{\underline{\times 2}} \times 3 \times \underline{3} \end{align*}$36$ に $2$ を掛けたとき
\begin{align*} \quad 36 \times 2 = 2 \times 2 \ \underline{\times 3} \times 3 \ \underline{\underline{\times 2}} \end{align*}素因数がすべて同じで最小の公倍数になっている。
最小の公倍数になるのは、一方の整数だけがもつ素因数を、他方の整数に掛けたときの数です。
つまり、最小の公倍数は、２４に３を１個だけ掛けた数、または３６に２を１個だけ掛けた数です。新たに掛けた２や３は、２４と３６の一方だけがもつ素因数で、浮いた素因数と言えます。
このことから、２つの整数が共通にもつ素因数に加えて、浮いた素因数も含めた積が最小公倍数になります。
２４と３６の最小公倍数
$24$ と $36$ の最小公倍数は
\begin{align*} \quad 2 \times 2 \times 3 \ \underline{\underline{\times 2}} \ \underline{\times 3} = 2^{3} \times 3^{2} = 72 \end{align*}ここで
\begin{align*} \quad 2 \times 2 \times 3 \end{align*}は、共通の素因数の積で
\begin{align*} \quad \underline{\underline{2}} \ \times \ \underline{3} \end{align*}は、浮いた素因数の積
実際は、素因数分解すると累乗の形で表します。ですから、累乗の指数を見て判断します。
最大公約数と最小公倍数は指数を参考にする
\begin{align*} &\quad 24 = 2^{3} \times \underline{3^{1}} \\[ 7pt ] &\quad 36 = \underline{2^{2}} \times 3^{2} \end{align*}$24$ と $36$ の最大公約数は
\begin{align*} \quad 2^{2} \times 3^{1} = 12 \end{align*}$24$ と $36$ の最小公倍数は
\begin{align*} \quad 2^{3} \times 3^{2} = 72 \end{align*}最大公約数は、共通の素因数からなります。ですから、共通の素因数があれば、指数の小さい方の累乗を採用します。
また、最小公倍数は、共通の素因数だけでなく、浮いた素因数も含みます。ですから、共通の素因数があれば、指数の大きい方の累乗を採用します。
ただし、下例の２，５のように、完全に浮いた素因数があれば、指数の大小にかかわらずそのまま採用します。
１２と４５の最大公約数と最小公倍数
\begin{align*} \quad 12 &=& 2^{2} \times &3 \\[ 7pt ] \quad 45 &=& &3^{2} \times 5 \end{align*}よって、$12$ と $45$ の最大公約数は $3$
また、$12$ と $45$ の最小公倍数は
\begin{align*} \quad 2^{2} \times 3^{2} \times 5 = 180 \end{align*}素因数分解を利用する方法をまとめると以下のようになります。
素因数と最大公約数・最小公倍数との関係
２つの整数の素因数と、最大公約数・最小公倍数との関係をベン図で表すと良く分かります。２つの整数がもつ素因数を要素とする集合を考えてみましょう。
共通にもつ素因数と浮いた素因数とに分けられます。最大公約数は、共通部分に属する素因数からなり、最小公倍数は、和集合に属する素因数からなることが分かります。
かなり解説が長くなりましたが、素因数と公約数・公倍数との関係がイメージできたのではないでしょうか？
因数に注目できるようになると、数や式の扱いが格段に上達します。めげずに取り組みましょう。
次は、２つの整数の最大公約数が１となるときや、２つの整数の積を考えます。新しい用語や関係式が出てきます。きちんと覚えましょう。
互いに素
２つの整数の最大公約数が１であるとき、２つの整数は互いに素であると言います。
たとえば、２つの整数が３，５のような素数であれば、最大公約数は１となるので、３と５は互いに素であると言えます。
２つの整数が互いに素かどうかの判定は、素因数分解して素因数を調べることで可能です。
互いに素かどうかの判定
\begin{align*} &\quad 15 = 3 \times 5 \\[ 7pt ] &\quad 28 = 2^{2} \times 7 \end{align*}$15$ と $28$ は共通の素因数をもたない。
よって、$15$ と $28$ は互いに素である。
２つの整数が共通の素因数を持たなければ、最大公約数が１となるので互いに素となります。
互いに素かどうかの判定は、暗算で考えるより、素因数分解した方が早く確実。
２つの整数の積、最大公約数、最小公倍数の関係
２つの整数を、最大公約数を用いて表すことができます。また、２つの整数の積を、最大公約数と最小公倍数を用いて表すこともできます。
２４と３６を最大公約数を用いて表す
\begin{align*} \quad 24 &= \underline{2 \times 2} \times 2& &\underline{\times 3} \\[ 7pt ] \quad 36 &= \underline{2 \times 2}& &\underline{\times 3} \times 3 \end{align*}よって、最大公約数は
\begin{align*} \quad 2 \times 2 \times 3=12 \end{align*}であるので
\begin{align*} &\quad 24 = \underline{12} \times 2 \\[ 7pt ] &\quad 36 = \underline{12} \times 3 \end{align*}２４と３６の例で分かるように、２つの整数は、最大公約数１２と浮いた素因数２，３との積でそれぞれ表されます。
ここで、一方の整数だけがもつ、浮いた素因数２，３は、互いに素であることに注意しましょう。もし、互いに素でなければ、共通の素因数がまだ残っているので、最大公約数が間違っていることになります。
一般に、２つの整数の積は、最大公約数と最小公倍数を用いて以下のように表されます。
２つの整数の積
$2$ つの整数 $a \ , \ b$ の積は
\begin{align*} \quad ab = gl \end{align*}と表せる。
ただし
$\quad g$ … 最大公約数
$\quad l$ … 最小公倍数
この式を導出してみましょう。２つの整数や最小公倍数を、最大公約数で表せることがポイントです。
２つの整数の積を導出する
最大公約数を $g$、最小公倍数を $l$ とする。
$2$ つの整数 $a \ , \ b$ は
\begin{align*} &\quad a = a’g \\[ 7pt ] &\quad b = b’g \end{align*}と表せる。
ただし、$a’ \ , \ b’$ は互いに素。
このとき、$2$ つの数の積を求めると
\begin{align*} \quad ab &= a’g \cdot b’g \\[ 7pt ] &= a’b’g \cdot g \end{align*}ここで、$a’b’g=l$ より
\begin{align*} \quad ab = gl \end{align*}が成り立つ。
式だけではよく分からない場合、筆算を思い浮かべると良いでしょう。
次は、最大公約数や最小公倍数を扱った問題を実際に解いてみましょう。