最大公約数と最小公倍数

重要度 難易度

こんにちは、リンス(@Lins016)です。
今回は最大公約数と最小公倍数について学習していこう。

スポンサーリンク

最大公約数と最小公倍数

最大公約数と最小公倍数って実は小学校のときに初めて教わるんだけど、みんなどんな数か覚えてるよね。

すごく昔に教わった\(\small{ \ 2 \ }\)つの数だけど、高校では文字式を利用した問題まで発展させて勉強するんだ。
そんなに難しいことないから、きちんと理解しながら進めていこう。

最大公約数と最小公倍数

最大公約数
\(\small{ \ 2 \ }\)つ以上の整数の共通の約数のうち最大の数のこと
最小公倍数
\(\small{ \ 2 \ }\)つ以上の整数の共通の倍数のうち最小の数のこと
互いに素
\(\small{ \ 2 \ }\)つ整数の最大公約数が\(\small{ \ 1 \ }\)であること

\(\small{ \ a=a'g, \ b=b'g \ }\)のとき
(だだし\(\small{ \ a' \ }\)と\(\small{ \ b' \ }\)は互いに素)
最大公約数\(\small{ \ g \ }\)
最小公倍数\(\small{ \ a'b'g \ }\)

最大公約数

最大公約数とは、\(\small{ \ 2 \ }\)つ以上の整数の共通の約数のうち最大の数のこと
英語表記の「Greatest Common Divisor」の頭文字をとって「G.C.D.」って書くこともあるよね。

だから文字を使って表すときは「\(\small{ \ a \ }\)と\(\small{ \ b \ }\)の最大公約数を\(\small{ \ g \ }\)とする」っていうように英語表記の頭文字\(\small{ \ g \ }\)が使われていることが多いんだ。

ちなみに少し前までは「Greatest Common Measure」の頭文字から「G.C.M.」って書くことが多かったけど、今は「G.C.D.」の方がよく使われているかな。

最大公約数の求め方は小学生のときもやっていた連除法で求めるのが一般的だよね。はしご算とも呼ばれている方法ね。
数を並べて書いて、共通の数で割っていくやり方。共通の数といっても合成数じゃなくて素数だから注意してね。

例えば\(\small{ \ 24 \ }\)と\(\small{ \ 108 \ }\)なら
\(\small{\begin{array} \ 2&)&24& \ \ &108\\
\hline
2&)&12& \ \ &54\\
\hline
3&)&6& \ \ &27\\
\hline
&&2& \ \ &9 \ \end{array}}\)

\(\small{ \ 24 \ }\)と\(\small{ \ 108 \ }\)と\(\small{ \ 180 \ }\)なら
\(\small{\begin{array} \ 2&)&24& \ \ &108& \ \ &180\\
\hline
2&)&12& \ \ &54& \ \ &90\\
\hline
3&)&6& \ \ &27& \ \ &45\\
\hline
&&2& \ \ &9& \ \ &15 \ \end{array}}\)

共通の素数で割ることが出来なくなるまで割るんだったよね。
このとき左側の割った数(素因数)をかけた数が最大公約数になるんだったよね。
つまり\(\small{ \ 24 \ }\)と\(\small{ \ 108 \ }\)の最大公約数は\(\small{ \ 2\times2\times3=12 \ }\)だし、\(\small{ \ 24 \ }\)と\(\small{ \ 108 \ }\)と\(\small{ \ 180 \ }\)の最大公約数も\(\small{ \ 2\times2\times3=12 \ }\)ってこと。

実はこれって素因数分解を同時にやっているのと同じことだよね。
\(\small{\begin{eqnarray} \ 24&=&2^2\times3\times2\\
&=&2^3\times3\\
\ 108&=&2^2\times3\times9\\
&=&2^2\times3^3 \\
\ 324&=&2^2\times3\times15\\
&=&2^2\times3^2\times5 \ \end{eqnarray}}\)
つまり素因数分解したこの形の場合、共通の素因数のうち指数が小さいものをかけた値が最大公約数になるんだ。
ちなみに公約数ってなると最大公約数の約数になるからね。

ただ最大公約数を見つけるとき、元の数が大きくて、すぐに割れる共通の素数が見つからない場合もある。
その場合はユークリッドの互除法を使って最大公約数を見つけるんだけど、これについては下の記事で確認しておこう。

▼あわせてCHECK▼(別ウィンドウで開きます)

最小公倍数

最小公倍数とは、\(\small{ \ 2 \ }\)つ以上の整数の共通の倍数のうち最小の数のこと
英語表記の「Least Common Multiple」の頭文字をとって「L.C.M.」って書くこともあるよね。

だから文字を使って表すときは「\(\small{ \ a \ }\)と\(\small{ \ b \ }\)の最小公倍数を\(\small{ \ l \ }\)とする」っていうように英語表記の頭文字\(\small{ \ l \ }\)が使われていることが多いんだ。

最小公倍数の求め方も連除法で求めるのが一般的。最大公約数を求める場合と同じで、共通の素数で割れなくなるまで割り続けよう。

\(\small{ \ 24 \ }\)と\(\small{ \ 108 \ }\)なら
\(\small{\begin{array} \ 2&)&24& \ \ &108\\
\hline
2&)&12& \ \ &54\\
\hline
3&)&6& \ \ &27\\
\hline
&&2& \ \ &9 \ \end{array}}\)

\(\small{ \ 24 \ }\)と\(\small{ \ 108 \ }\)と\(\small{ \ 180 \ }\)なら
\(\small{\begin{array} \ 2&)&24& \ \ &108& \ \ &180\\
\hline
2&)&12& \ \ &54& \ \ &90\\
\hline
3&)&6& \ \ &27& \ \ &45\\
\hline
3&)&2& \ \ &9& \ \ &15\\
\hline
&&2& \ \ &3& \ \ &5 \ \end{array}}\)

注意しておきたいのは、\(\small{ \ 3 \ }\)つ以上の数の最小公倍数を求めるときは共通の素数で割れなくなるまで割って、残った数のうち\(\small{ \ 2 \ }\)つ以上の数がまだ共通の素数で割れるなら割り続けるってこと。

上の場合、最後の\(\small{ \ 3 \ }\)で割るところね。\(\small{ \ 2, \ 9, \ 15 \ }\)には共通の素数で割れないけど、\(\small{ \ 9, \ 15 \ }\)は\(\small{ \ 3 \ }\)で割れるからね。

つまり\(\small{ \ 24 \ }\)と\(\small{ \ 108 \ }\)の最小公倍数は\(\small{ \ 2\times2\times3\times2\times9=216 \ }\)だし、
\(\small{ \ 24 \ }\)と\(\small{ \ 108 \ }\)と\(\small{ \ 180 \ }\)の最小公倍数も\(\small{ \ 2\times2\times3\times2\times3\times3\times5=1080 \ }\)になるよね。

各数を因数分解をすると、
\(\small{\begin{eqnarray} \ 24&=&2^2\times3\times2\\
&=&2^3\times3\\
\ 108&=&2^2\times3\times9\\
&=&2^2\times3^3 \\
\ 180&=&2^2\times3\times15\\
&=&2^2\times3^2\times5 \ \end{eqnarray}}\)
素因数分解したこの形から最小公倍数を求めるには、素因数は指数が大きいものをかけた値が最小公倍数になるんだ。共通なものだけじゃないってところもポイントね。

つまり\(\small{ \ 24 \ }\)や\(\small{ \ 108 \ }\)には\(\small{ \ 5 \ }\)の因数はないけど\(\small{ \ 5^0 \ }\)があると見なして大きいほう、つまり\(\small{ \ 180 \ }\)の素因数の\(\small{ \ 5^1 \ }\)をかけるってことになるからね。

ちなみに公倍数は最小公倍数の倍数になるからね。

互いに素

最大公約数や最小公倍数を考える問題で\(\small{ \ 1 \ }\)つ覚えておきたいキーワードがあるんだ。
それが「互いに素」って言葉。

\(\small{ \ 2 \ }\)つの数に共通の約数がない場合、つまり最大公約数が\(\small{ \ 1 \ }\)のとき、その\(\small{ \ 2 \ }\)つの数は互いに素ってことになる。

実はこの互いに素っていうのは高校数学ではまあまあ使われる言葉なんだ。
既約分数を表す時も「\(\small{ \ \displaystyle\frac{p}{q} \ }\)ただし\(\small{ \ p, \ q \ }\)は互いに素」って書くからね。
この単元に限らずよく使う言葉だから覚えておこう。

例題を確認
問題解答

次の条件を満たす\(\small{ \ 2 \ }\)つの自然数\(\small{ \ a, \ b \ (a\lt b) \ }\)を求めよ。
(1)最大公約数が\(\small{ \ 3 \ }\)、積が\(\small{ \ 252 \ }\)
(2)和が\(\small{ \ 70 \ }\)、最大公約数が\(\small{ \ 7 \ }\)
(3)積が\(\small{ \ 300 \ }\)、最小公倍数が\(\small{ \ 60 \ }\)

(1)最大公約数が\(\small{ \ 3 \ }\)より
\(\small{ \ a=3a', \ b=3b' \ }\)とおける
ただし、\(\small{ \ a' \ }\)と\(\small{ \ b' \ }\)は互いに素
\(\small{ \ ab=252 \ }\)より
\(\small{ \ 9a'b'=252 \ }\)
\(\small{ \ a'b'=28=2^2\times7 \ }\)
ここで\(\small{ \ a' \ }\)と\(\small{ \ b' \ }\)は互いに素より
\(\small{ \ (a', \ b')=(1, \ 28), \ (4, \ 7) \ }\)
\(\small{ \ \therefore(a, \ b)=(3, \ 84), \ (12, \ 21) \ }\)

(2)最大公約数が\(\small{ \ 7 \ }\)より
\(\small{ \ a=7a', \ b=7b' \ }\)とおける
ただし、\(\small{ \ a' \ }\)と\(\small{ \ b' \ }\)は互いに素
\(\small{ \ a+b=7a'+7b'=70 \ }\)
\(\small{ \ a'+b'=10 \ }\)
\(\small{ \ a' \ }\)と\(\small{ \ b' \ }\)は互いに素より
\(\small{ \ (a', \ b')=(1, \ 9), \ (3, \ 7) \ }\)
\(\small{ \ \therefore(a, \ b)=(7, \ 63), \ (21, \ 49) \ }\)

(3)最大公約数を\(\small{ \ g \ }\)とすると
\(\small{ \ a=a'g, \ b=b'g \ }\)とおける
このとき最大公約数を\(\small{ \ l \ }\)とすると
\(\small{ \ l=a'b'g \ }\)となる
\(\small{ \ l=a'b'g=60\cdots① \ }\)
また積が\(\small{ \ 300 \ }\)より
\(\small{ \ ab=a'b'g^2=300\cdots② \ }\)
\(\small{ \ ①② \ }\)より\(\small{ \ g=5 \ }\)
\(\small{ \ a'b'=12=2^2\times3 \ }\)
\(\small{ \ a' \ }\)と\(\small{ \ b' \ }\)は互いに素より
\(\small{ \ (a', \ b')=(1, \ 12), \ (3, \ 4) \ }\)
\(\small{ \ \therefore(a, \ b)=(5, \ 60), \ (15, \ 20) \ }\)

point
\(\small{ \ a+b=10 \ }\)や\(\small{ \ ab=12 \ }\)は\(\small{ \ a, \ b \ }\)の\(\small{ \ 2 \ }\)つの文字が未知数だから式が\(\small{ \ 1 \ }\)つしかないと普通解けないんだけど、「互いに素」っていう条件があると\(\small{ \ a, \ b \ }\)を求める事ができるんだ。

Point 最大公約数と最小公倍数

①最大公約数と最小公倍数は素因数分解(連除法)を利用する
②最大公約数と互いに素をうまく活用する

それじゃあ次は入試レベルの問題にチャレンジしてみよう。
入試レベルにチャレンジ
問題解答

\(\small{ \ X=2^a\cdot3^b \ }\)(\(\small{ \ a, \ b \ }\)は自然数)、\(\small{ \ Y=5400 \ }\)とする。
\(\small{ \ X \ }\)と\(\small{ \ Y \ }\)の最小公倍数が\(\small{ \ 16200 \ }\)で、ある自然数\(\small{ \ n \ }\)に対し\(\small{ \ X^n \ }\)の約数が\(\small{ \ 221 \ }\)個あるとき、\(\small{ \ a, \ b, \ n \ }\)の値を求めよ。

\(\small{ \ X=2^a\cdot3^b \ }\)
\(\small{ \ Y=5400=2^3\cdot3^3\cdot5^2 \ }\)
\(\small{ \ X, \ Y \ }\)の最小公倍数\(\small{ \ 16200=2^3\cdot3^4\cdot5^2 \ }\)
よって\(\small{ \ X^n=2^{an}\cdot3^{4n} \ }\)ただし、\(\small{ \ a=1, \ 2, \ 3 \ }\)
\(\small{ \ X^n \ }\)の約数の個数は\(\small{ \ 221=13\cdot17 \ }\)
\(\small{ \ (an+1)(4n+1)=13\cdot17 \ }\)
\(\small{ \ a\lt4 \ }\)より\(\small{ \ 4n+1=17 \ }\)
\(\small{ \ \therefore n=4, \ a=3, \ b=4 \ }\)

この記事が気に入ったら
いいね ! しよう

Twitter で

  整数の性質

  , , ,