最大公約数・最小公倍数・互除法

解説＋ドリル全18問・自動採点つき

問題プリントPDF 解答つきPDF
STEP 1

最大公約数・最小公倍数 ― 素因数分解から求める

2つ以上の整数に共通な約数のうち、いちばん大きいものを最大公約数（\(\gcd\)）という。共通な倍数のうち、いちばん小さいものを最小公倍数（\(\operatorname{lcm}\)）という。素因数分解を使うと、この2つを機械的に求められる。

重なる部分（共通部分）が「公約数」の集合。その中でいちばん大きいものが最大公約数。

例えば \(60\) と \(84\) の最大公約数・最小公倍数を求めてみよう。まず素因数分解する。

\(60 = 2^2 \times 3 \times 5\)　　\(84 = 2^2 \times 3 \times 7\)

最大公約数：共通する素因数を、指数が小さい方だけ取ってかける。
\(\gcd(60,84) = 2^2 \times 3 = 12\)

最小公倍数：現れるすべての素因数を、指数が大きい方だけ取ってかける（一方にしかない素因数も忘れずに含める）。
\(\operatorname{lcm}(60,84) = 2^2 \times 3 \times 5 \times 7 = 420\)

例題1　\(96\) と \(60\) の最大公約数・最小公倍数を求めよ。

解答を見る
\(96 = 2^5 \times 3\)　　\(60 = 2^2 \times 3 \times 5\) 共通する素因数は \(2\) と \(3\)。指数の小さい方を取って \(\gcd = 2^2 \times 3 = 12\)。 現れる素因数すべてを指数の大きい方で取って \(\operatorname{lcm} = 2^5 \times 3 \times 5 = 480\)。 最大公約数 \(12\)、最小公倍数 \(480\)

ここで、2つの整数 \(a, b\) について、次の関係がいつでも成り立つ。

\[a \times b = \gcd(a,b) \times \operatorname{lcm}(a,b)\] \(a = G \times p\)、\(b = G \times q\)（\(G=\gcd(a,b)\)、\(p,q\) は互いに素）とおくと \(\operatorname{lcm}(a,b) = G \times p \times q\) となるので、\(G \times \operatorname{lcm}(a,b) = G^2 \times pq = (Gp)\times(Gq) = a\times b\)。（例：\(60\times84=5040\)、\(\gcd\times\operatorname{lcm}=12\times420=5040\)。一致する。）

例題2　\(a\) と \(b\) の最大公約数が \(7\)、積 \(a\times b\) が \(1260\) であるとき、最小公倍数を求めよ。

解答を見る
\(a\times b = \gcd(a,b)\times\operatorname{lcm}(a,b)\) より \(\operatorname{lcm}(a,b) = \dfrac{a\times b}{\gcd(a,b)} = \dfrac{1260}{7} = 180\) 最小公倍数 \(180\)
STEP 2

ユークリッドの互除法 ― 原理を証明する

桁数が大きい数どうしでは、素因数分解でGCDを求めるのは大変になる。もっと機械的で、どんな整数にも通用する方法が「ユークリッドの互除法」だ。

互除法の原理　整数 \(a, b\)（\(a \ge b \gt 0\)）について、\(a\) を \(b\) で割ったときの商を \(q\)、余りを \(r\) とする（\(a = bq + r\)、\(0 \le r \lt b\)）。このとき \[\gcd(a,b) = \gcd(b,r)\] が成り立つ。つまり「大きい方を小さい方で割った余り」に置き換えても、最大公約数は変わらない。

証明　\(d = \gcd(a,b)\) とする。\(d\) は \(a\) と \(b\) をともに割り切る。\(r = a - bq\) であり、\(bq\) は \(b\) の倍数（つまり \(d\) の倍数）だから、\(d\) の倍数どうしの差である \(r\) も \(d\) で割り切れる。よって \(d\) は \(b\) と \(r\) の公約数の1つである。

逆に \(e = \gcd(b,r)\) とする。\(e\) は \(b\) と \(r\) をともに割り切る。\(a = bq + r\) は「\(e\) の倍数」と「\(e\) の倍数」の和なので、\(e\) は \(a\) も割り切る。よって \(e\) は \(a\) と \(b\) の公約数の1つである。

したがって「\(a,b\) の公約数の集合」と「\(b,r\) の公約数の集合」はまったく同じ集合になる。同じ集合の中の最大値どうしは等しいから、\(\gcd(a,b) = \gcd(b,r)\) が成り立つ。

この性質を繰り返し使うと、割る数と余りの組がどんどん小さくなり、やがて余りが \(0\) になる。そのときの「割る数」が最大公約数である（余り \(0\) は「割り切れた」ということなので、\(\gcd(b,0)=b\) は明らか）。

例題　\(84\) と \(36\) の最大公約数を互除法で求めよ。

解答を見る
\(84 = 36 \times 2 + 12\) \(36 = 12 \times 3 + 0\)　→　余りが \(0\) になった。 最大公約数は \(12\)

例題　\(272\) と \(119\) の最大公約数を互除法で求めよ。

解答を見る
\(272 = 119 \times 2 + 34\) \(119 = 34 \times 3 + 17\) \(34 = 17 \times 2 + 0\)　→　余りが \(0\) になった。 最大公約数は \(17\)
STEP 3

互除法で計算練習 ― 大きい数にこそ威力を発揮

桁数が大きくなると素因数分解は骨が折れるが、互除法なら「割って余りを出す」という同じ手順をただ繰り返すだけでよい。実際にやってみよう。

例題　\(2310\) と \(1785\) の最大公約数を互除法で求めよ。

解答を見る
\(2310 = 1785 \times 1 + 525\) \(1785 = 525 \times 3 + 210\) \(525 = 210 \times 2 + 105\) \(210 = 105 \times 2 + 0\)　→　余りが \(0\) になった。 （検算：\(2310 = 2\times3\times5\times7\times11\)、\(1785=3\times5\times7\times17\) なので \(\gcd=3\times5\times7=105\)。素因数分解でも一致する。） 最大公約数は \(105\)
威力を実感しよう　\(1073\) と \(851\) を素因数分解しようとすると、\(30\) 前後までの素数で次々に割り算を試す必要があり大変（実は \(1073=29\times37\)、\(851=23\times37\)）。ところが互除法なら、次の割り算を機械的に繰り返すだけで求まる。
\(1073 = 851 \times 1 + 222\) \(851 = 222 \times 3 + 185\) \(222 = 185 \times 1 + 37\) \(185 = 37 \times 5 + 0\)　→　余りが \(0\) になった。 最大公約数は \(37\)

互除法の手順まとめ：大きい方を小さい方で割り、余りを出す → 「割る数」と「余り」の組で同じことを繰り返す → 余りが \(0\) になったときの割る数が最大公約数。どちらが大きくてもよい（もし \(a \lt b\) なら先に入れ替えて割ればよい）。

STEP 4

互いに素 ― 最大公約数が1になるとき

2つの整数の最大公約数が \(1\) であるとき、その2数は互いに素であるという。整数の性質を調べるうえで、とても大切な考え方。

性質1　連続する2つの整数は必ず互いに素
\(n\) と \(n+1\) の最大公約数は、\(n\) がどんな自然数でも \(1\) である。
証明：\(d\) を \(n\) と \(n+1\) の公約数とする。\(d\) は差 \((n+1)-n=1\) も割り切る。\(1\) を割り切る自然数は \(1\) しかないので \(d=1\)。よって \(n\) と \(n+1\) の公約数は \(1\) しかなく、\(\gcd(n,n+1)=1\)。

連続する2つの整数の約数の集合は、\(1\) 以外に共通部分を持たない→互いに素。

性質2　既約分数の判定
\(a\) と \(b\) が互いに素であるとき、分数 \(\dfrac{a}{b}\) はこれ以上約分できない（既約分数）。逆に、約分できる分数は分子と分母が互いに素でない（共通な約数を持つ）ということ。
性質3　互いに素なら最小公倍数は積そのもの
\(a\times b = \gcd(a,b)\times\operatorname{lcm}(a,b)\) で \(\gcd(a,b)=1\) のときは \(\operatorname{lcm}(a,b) = a\times b\) となる。共通な素因数が1つもないので、最小公倍数は単純に2数をかけ合わせたものになる。

例題1　\(50\) と \(51\) は互いに素であることを確かめよ。

解答を見る
\(50\) と \(51\) は連続する整数なので、性質1よりただちに互いに素である。 （確かめに素因数分解すると \(50=2\times5^2\)、\(51=3\times17\) で共通の素因数がなく、\(\gcd=1\) と一致する。） \(\gcd(50,51)=1\)（互いに素）

例題2　分数 \(\dfrac{108}{144}\) は既約分数か。既約分数でなければ約分せよ。

解答を見る
\(108 = 2^2\times3^3\)、\(144=2^4\times3^2\) より \(\gcd(108,144)=2^2\times3^2=36\)。 \(\gcd\) が \(1\) でないので既約分数ではない。分子・分母を \(36\) で割ると \(\dfrac{108}{144} = \dfrac{108\div36}{144\div36} = \dfrac{3}{4}\) 既約分数ではない。約分すると \(\dfrac{3}{4}\)
STEP 5

解き方の流れ（まとめ）

手順1　2数を素因数分解できそうなら分解し、GCD＝共通素因数の小さい方の指数の積、LCM＝現れる素因数の大きい方の指数の積で求める
↓
手順2　桁数が大きく素因数分解が大変なら、互除法を使う（大きい方を小さい方で割り、余りで置き換えることを繰り返す）
↓
手順3　余りが \(0\) になったときの割る数が最大公約数
↓
手順4　最小公倍数が必要なら \(a\times b = \gcd(a,b)\times\operatorname{lcm}(a,b)\) の関係を使って \(\operatorname{lcm}(a,b)=\dfrac{a\times b}{\gcd(a,b)}\) で求める
注意　最大公約数が \(1\)（互いに素）のときは、最小公倍数は単純に2数の積になる。この特別な場合は覚えておくと計算が速い。
練習問題（全18問）

答えを入力して「採点」を押すと○×が出るぞ。
わからないときは「解説を見る」で解き方を確認しよう。

基本（1〜7）
1
素因数分解から

\(18\) と \(24\) の最大公約数・最小公倍数を求めよ。

最大公約数 　最小公倍数
解説を見る
\(18 = 2\times3^2\)　　\(24 = 2^3\times3\) \(\gcd = 2\times3 = 6\)　　\(\operatorname{lcm} = 2^3\times3^2 = 72\) 最大公約数 \(6\)、最小公倍数 \(72\)
2
素因数分解から

\(36\) と \(84\) の最大公約数・最小公倍数を求めよ。

最大公約数 　最小公倍数
解説を見る
\(36 = 2^2\times3^2\)　　\(84 = 2^2\times3\times7\) \(\gcd = 2^2\times3 = 12\)　　\(\operatorname{lcm} = 2^2\times3^2\times7 = 252\) 最大公約数 \(12\)、最小公倍数 \(252\)
3
素因数分解から

\(45\) と \(150\) の最大公約数・最小公倍数を求めよ。

最大公約数 　最小公倍数
解説を見る
\(45 = 3^2\times5\)　　\(150 = 2\times3\times5^2\) \(\gcd = 3\times5 = 15\)　　\(\operatorname{lcm} = 2\times3^2\times5^2 = 450\) 最大公約数 \(15\)、最小公倍数 \(450\)
4
素因数分解から

\(63\) と \(90\) の最大公約数・最小公倍数を求めよ。

最大公約数 　最小公倍数
解説を見る
\(63 = 3^2\times7\)　　\(90 = 2\times3^2\times5\) \(\gcd = 3^2 = 9\)　　\(\operatorname{lcm} = 2\times3^2\times5\times7 = 630\) 最大公約数 \(9\)、最小公倍数 \(630\)
5
素因数分解から（数が少し大きい）

\(112\) と \(84\) の最大公約数・最小公倍数を求めよ。

最大公約数 　最小公倍数
解説を見る
\(112 = 2^4\times7\)　　\(84 = 2^2\times3\times7\) \(\gcd = 2^2\times7 = 28\)　　\(\operatorname{lcm} = 2^4\times3\times7 = 336\) 最大公約数 \(28\)、最小公倍数 \(336\)
6
\(a\times b=\gcd\times\operatorname{lcm}\) の関係を利用

\(72\) と \(90\) の最大公約数は \(18\) である。このとき、最小公倍数を求めよ。

最小公倍数
解説を見る
\(\operatorname{lcm}(72,90) = \dfrac{72\times90}{18} = \dfrac{6480}{18} = 360\) （検算：\(72=2^3\times3^2\)、\(90=2\times3^2\times5\) より \(\gcd=2\times3^2=18\) で一致、\(\operatorname{lcm}=2^3\times3^2\times5=360\) で一致。） 最小公倍数 \(360\)
7
\(a\times b=\gcd\times\operatorname{lcm}\) の関係を利用

\(36\) と \(48\) の最小公倍数は \(144\) である。このとき、最大公約数を求めよ。

最大公約数
解説を見る
\(\gcd(36,48) = \dfrac{36\times48}{144} = \dfrac{1728}{144} = 12\) （検算：\(36=2^2\times3^2\)、\(48=2^4\times3\) より \(\operatorname{lcm}=2^4\times3^2=144\) で一致、\(\gcd=2^2\times3=12\) で一致。） 最大公約数 \(12\)
標準（8〜14）
8
互除法：余りを追う

\(84\) を \(36\) で割ると商 \(2\)、余り \(r_1\)。次に \(36\) を \(r_1\) で割ると割り切れた（余り \(0\)）。\(84\) と \(36\) の最大公約数を互除法で求めよ。

\(r_1=\) 　最大公約数
解説を見る
\(84 = 36\times2+12\)（\(r_1=12\)） \(36 = 12\times3+0\)　→　余りが \(0\) になった。 \(r_1=12\)、最大公約数は \(12\)
9
互除法：余りを追う（3回繰り返す）

\(154\) を \(98\) で割ると商 \(1\)、余り \(r_1\)。次に \(98\) を \(r_1\) で割ると商 \(1\)、余り \(r_2\)。次に \(r_1\) を \(r_2\) で割ると商 \(1\)、余り \(14\)。最後に \(r_2\) を \(14\) で割ると割り切れた。\(154\) と \(98\) の最大公約数を求めよ。

\(r_1=\) 　\(r_2=\) 　最大公約数
解説を見る
\(154 = 98\times1+56\)（\(r_1=56\)） \(98 = 56\times1+42\)（\(r_2=42\)） \(56 = 42\times1+14\) \(42 = 14\times3+0\)　→　余りが \(0\) になった。 \(r_1=56\)、\(r_2=42\)、最大公約数は \(14\)
10
互除法：大きい数でも手順は同じ

\(1271\) を \(779\) で割ると商 \(1\)、余り \(r_1\)。以下同様に割り算を繰り返していくと、最終的に割り切れる。\(1271\) と \(779\) の最大公約数を求めよ。

\(r_1=\) 　最大公約数
解説を見る
\(1271 = 779\times1+492\)（\(r_1=492\)） \(779 = 492\times1+287\) \(492 = 287\times1+205\) \(287 = 205\times1+82\) \(205 = 82\times2+41\) \(82 = 41\times2+0\)　→　余りが \(0\) になった。 （実は \(1271=31\times41\)、\(779=19\times41\)。素因数分解では見つけにくいが、互除法なら機械的に求まる。） \(r_1=492\)、最大公約数は \(41\)
11
約分（既約分数にする）

\(\gcd\) の考え方を使って、分数 \(\dfrac{126}{210}\) を既約分数にせよ。

既約分数
解説を見る
\(126 = 2\times3^2\times7\)、\(210 = 2\times3\times5\times7\) より \(\gcd(126,210) = 2\times3\times7 = 42\)。 分子・分母を \(42\) で割ると \(\dfrac{126\div42}{210\div42} = \dfrac{3}{5}\) \(\dfrac{3}{5}\)
12
文章題：最小公倍数の利用

2つのランプ A, B がある。A は \(20\) 秒おきに、B は \(30\) 秒おきに点滅する。いま同時に点滅したとすると、次に同時に点滅するのは何秒後か。

次に同時に点滅するのは 秒後
解説を見る
Aが点滅するのは \(20\) の倍数の秒、Bが点滅するのは \(30\) の倍数の秒。同時に点滅するのは共通の倍数、つまり最小公倍数の秒数ごと。 \(20 = 2^2\times5\)、\(30=2\times3\times5\) より \(\operatorname{lcm}(20,30) = 2^2\times3\times5 = 60\) \(60\) 秒後
13
3つの数の最大公約数・最小公倍数

\(24\)、\(36\)、\(60\) の最大公約数・最小公倍数を求めよ。

最大公約数 　最小公倍数
解説を見る
\(24 = 2^3\times3\)　　\(36 = 2^2\times3^2\)　　\(60 = 2^2\times3\times5\) 最大公約数は3つに共通する素因数を、指数がいちばん小さいものだけ取る：\(\gcd = 2^2\times3 = 12\) 最小公倍数は現れるすべての素因数を、指数がいちばん大きいものだけ取る：\(\operatorname{lcm} = 2^3\times3^2\times5 = 360\) 最大公約数 \(12\)、最小公倍数 \(360\)
14
文章題：タイルを敷き詰める

たて \(168\)cm、よこ \(120\)cm の長方形の床に、すき間なく同じ大きさの正方形のタイルを敷き詰めたい。タイルをできるだけ大きくするには、一辺を何cmにすればよいか。また、そのときタイルは何枚必要か。

一辺 cm　タイルの枚数 枚
解説を見る
すき間なく敷き詰められる正方形の一辺の長さは、\(168\) と \(120\) の両方を割り切れる数、つまり公約数でなければならない。できるだけ大きくしたいので最大公約数を使う。 \(168 = 2^3\times3\times7\)、\(120=2^3\times3\times5\) より \(\gcd(168,120) = 2^3\times3 = 24\) 一辺 \(24\)cm のとき、たて方向に \(168\div24=7\)枚、よこ方向に \(120\div24=5\)枚並ぶので、合計 \(7\times5=35\)枚。 一辺 \(24\)cm、タイル \(35\)枚
挑戦（15〜18）
15
文章題：池のまわりの木（最大公約数）

長方形の池のまわりの遊歩道（たて \(84\)m、よこ \(126\)m）に沿って木を植える。四すみには必ず木を植え、残りも等間隔になるようにしたい。間隔をできるだけ広くとるには何mおきにすればよいか。また、木は全部で何本必要か。

間隔 m　木の本数 本
解説を見る
四すみに木を植えたうえで等間隔にするには、間隔は「たて」と「よこ」の両方をちょうど割り切る数でなければならない。できるだけ広い間隔にしたいので最大公約数を使う。 \(84 = 2^2\times3\times7\)、\(126 = 2\times3^2\times7\) より \(\gcd(84,126) = 2\times3\times7 = 42\) 周囲の長さは \(2\times(84+126) = 420\)m。間隔 \(42\)m ごとに木を植えるので、本数は周囲を1周する木の数＝間隔の個数と同じ \(420\div42 = 10\)本（1周してもとの木に戻るので、周の長さ÷間隔がそのまま本数になる）。 間隔 \(42\)m、木 \(10\)本
16
文章題：等しく配る（最大公約数）

えんぴつ \(72\)本とノート \(108\)冊を、余りが出ないように、できるだけ多くの子どもに同じ数ずつ配りたい。何人に配れるか。また、そのとき1人あたりのえんぴつとノートはそれぞれ何本・何冊か。

人数 人　えんぴつ 本　ノート 冊
解説を見る
余りなく同じ数ずつ配れる人数は、\(72\) と \(108\) の公約数でなければならない。できるだけ多くの人に配りたいので最大公約数を使う。 \(72 = 2^3\times3^2\)、\(108 = 2^2\times3^3\) より \(\gcd(72,108) = 2^2\times3^2 = 36\) \(36\)人に配るとき、えんぴつは1人あたり \(72\div36=2\)本、ノートは1人あたり \(108\div36=3\)冊。 \(36\)人、えんぴつ \(2\)本、ノート \(3\)冊ずつ
17
互除法で大きい分数を約分する

互除法を使って \(2415\) と \(1035\) の最大公約数を求め、分数 \(\dfrac{2415}{1035}\) を既約分数にせよ。

最大公約数 　既約分数
解説を見る
\(2415 = 1035\times2+345\) \(1035 = 345\times3+0\)　→　余りが \(0\) になった。 最大公約数は \(345\)。分子・分母を \(345\) で割ると \(\dfrac{2415\div345}{1035\div345} = \dfrac{7}{3}\) （検算：\(2415=3\times5\times7\times23\)、\(1035=3^2\times5\times23\) より \(\gcd=3\times5\times23=345\) で一致。） 最大公約数 \(345\)、既約分数 \(\dfrac{7}{3}\)
18
一般の証明

\(n\) を自然数とするとき、\(n\) と \(n+1\) の最大公約数を、互除法の考え方（\(\gcd(a,b)=\gcd(b,r)\)）を使って求めよ。

\(\gcd(n,n+1)=\)
解説を見る
\(n+1\) を \(n\) で割ると、商 \(1\)、余り \(1\)（\(n+1 = n\times1+1\)）。 互除法の性質 \(\gcd(a,b)=\gcd(b,r)\) より \(\gcd(n+1,n) = \gcd(n,1)\) \(n\) を \(1\) で割ると必ず割り切れる（余り \(0\)）ので \(\gcd(n,1)=1\)。 （これはSTEP4の性質1「連続する整数は互いに素」を、互除法の立場から導いたものになっている。） \(\gcd(n,n+1) = 1\)
応用問題（プリント限定）

ここから先はPDF限定の腕試し。最大公約数・最小公倍数の考え方を、もう一段深く使ってみよう。

応1
最大公約数・最小公倍数から2数を復元

2つの自然数 \(a, b\)（\(a \lt b\)）の最大公約数が \(6\)、最小公倍数が \(180\) であり、\(a+b=102\) であるという。\(a\)、\(b\) を求めよ。

\(a=\) 　\(b=\)
解説を見る
\(\gcd(a,b)=6\) より \(a=6p\)、\(b=6q\)（\(p,q\) は互いに素、\(p \lt q\)）とおける。 \(\operatorname{lcm}(a,b)=6pq=180\) より \(pq=30\)。 \(pq=30\) かつ \(\gcd(p,q)=1\) となる組（\(p \lt q\)）は \((1,30)\)、\((2,15)\)、\((3,10)\)、\((5,6)\) の4通り。 それぞれ \(a=6p,\ b=6q\) にすると \((6,180)\)、\((12,90)\)、\((18,60)\)、\((30,36)\) の4通りが候補になる。 条件 \(a+b=102\) を満たすのは \((12,90)\)（\(12+90=102\)）だけ。 （検算：\(12=2^2\times3\)、\(90=2\times3^2\times5\) より \(\gcd=2\times3=6\)、\(\operatorname{lcm}=2^2\times3^2\times5=180\)。どちらも条件と一致。） \(a=12,\ b=90\)
応2
連続する整数は互いに素の利用

\(2024\) と \(2025\) の最大公約数を、素因数分解ではなく「連続する整数は互いに素である」という性質を使って求めよ。またその理由も説明せよ。

\(\gcd(2024,2025)=\)
解説を見る
\(2025 = 2024+1\) なので、\(2024\) と \(2025\) は連続する整数である。 連続する2つの整数の公約数 \(d\) は、その差 \(2025-2024=1\) も割り切らなければならない。\(1\) を割り切る自然数は \(1\) しかないので \(d=1\)。 \(2024\) や \(2025\) をわざわざ素因数分解しなくても（\(2024=2^3\times11\times23\)、\(2025=3^4\times5^2\) と、これはかなり手間がかかる）、連続する整数であることに気づくだけで最大公約数が \(1\) だとわかる。これが「互いに素」の考え方の強み。 \(\gcd(2024,2025) = 1\)
応3
分数が整数になる条件

自然数 \(n\) について、\(\dfrac{n+11}{n+2}\) が整数となるような \(n\) をすべて求めよ。（コンマ区切りで入力）

\(n=\)
解説を見る
\(n+11 = (n+2)+9\) と変形できるので \(\dfrac{n+11}{n+2} = \dfrac{(n+2)+9}{n+2} = 1+\dfrac{9}{n+2}\) これが整数になるためには、\(\dfrac{9}{n+2}\) が整数、すなわち \(n+2\) が \(9\) の約数でなければならない。 \(9\) の約数は \(1,3,9\)。\(n\) は自然数なので \(n+2 \ge 3\)。この条件を満たすのは \(n+2=3\) または \(n+2=9\)。 \(n+2=3\) のとき \(n=1\)（\(\dfrac{12}{3}=4\)） \(n+2=9\) のとき \(n=7\)（\(\dfrac{18}{9}=2\)） \(n=1,\ 7\)
応4
文章題：3本のロープを同じ長さに切る（3つの数の最大公約数）

長さ \(150\)cm、\(210\)cm、\(270\)cm の3本のロープを、余りが出ないようにすべて同じ長さに切り分けたい。1本の長さをできるだけ長くするには何cmにすればよいか。また、ロープは全部で何本できるか。

1本の長さ cm　本数 本
解説を見る
3本すべてを余りなく同じ長さに切れる長さは、\(150,\ 210,\ 270\) すべての公約数でなければならない。できるだけ長くしたいので3つの最大公約数を使う。 \(150=2\times3\times5^2\)、\(210=2\times3\times5\times7\)、\(270=2\times3^3\times5\) より \(\gcd(150,210,270) = 2\times3\times5 = 30\) \(30\)cmずつに切ると、本数は \(150\div30 + 210\div30 + 270\div30 = 5+7+9 = 21\)本。 1本 \(30\)cm、全部で \(21\)本
応5
最大公約数と積から最小公倍数・2数の組を求める

2つの自然数 \(a, b\) の最大公約数は \(15\)、積 \(a\times b\) は \(6750\) であるという。\(a\) と \(b\) の最小公倍数を求めよ。また、\(a \lt b\) として \(a, b\) の組をすべて求めよ。

最小公倍数
解説を見る
\(a\times b = \gcd(a,b)\times\operatorname{lcm}(a,b)\) より \(\operatorname{lcm}(a,b) = \dfrac{6750}{15} = 450\) \(a,b\) の組を求めるには \(a=15p\)、\(b=15q\)（\(p,q\) は互いに素、\(p \lt q\)）とおく。\(pq = \dfrac{\operatorname{lcm}}{\gcd} = \dfrac{450}{15} = 30\)。 \(pq=30\) かつ互いに素な組（\(p \lt q\)）は \((1,30)\)、\((2,15)\)、\((3,10)\)、\((5,6)\) の4通り。 \(15\) 倍すると \((a,b)=(15,450)\)、\((30,225)\)、\((45,150)\)、\((75,90)\) の4組すべてが条件を満たす（それぞれ検算すると \(\gcd=15\)、積 \(=6750\) になっている）。 最小公倍数 \(450\)。組は \((15,450),\ (30,225),\ (45,150),\ (75,90)\) の4通り