最大公約数・最小公倍数・互除法｜数A 数学と人間の活動（整数）

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〜9）

素因数分解から

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

最大公約数　最小公倍数

解説を見る

\(18 = 2\times3^2\)　　\(24 = 2^3\times3\) \(\gcd = 2\times3 = 6\)　　\(\operatorname{lcm} = 2^3\times3^2 = 72\) 最大公約数 \(6\)、最小公倍数 \(72\)

素因数分解から

\(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\)

素因数分解から

\(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\)

素因数分解から

\(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\)

素因数分解から（数が少し大きい）

\(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\)

\(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\)

\(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\)

合同式の定義

整数 \(a\), \(b\) と正の整数 \(m\) について、\(a-b\) が \(m\) の倍数であるとき \(a\equiv b\pmod{m}\) と表す。この定義が「\(a\) を \(m\) で割った余りと \(b\) を \(m\) で割った余りが等しい」ことと同じ意味であることを、\(a=23\)、\(b=8\)、\(m=5\) の場合で確かめよ。

解説を見る

\(23\) を \(5\) で割ると商 \(4\) 余り \(3\)。\(8\) を \(5\) で割ると商 \(1\) 余り \(3\)。どちらも余りが \(3\) で等しい。一方、\(23-8=15\) であり、\(15=5\times3\) だから \(23-8\) は \(5\) の倍数になっている。つまり「余りが等しい」ことと「差が \(m\) の倍数になる」ことは、同じ状況を指している。実際、\(a=mk_1+r\)、\(b=mk_2+r\)（\(r\) は共通の余り）と表せるとき、\(a-b=m(k_1-k_2)\) となり必ず \(m\) の倍数になる。逆に \(a-b\) が \(m\) の倍数ならば、\(a\) と \(b\) を \(m\) で割った余りは一致する。 \(23\equiv8\pmod5\) であり、これは両者を \(5\) で割った余りがともに \(3\) で等しいことと同じ意味である

合同式の性質（加法・乗法の保存）の証明

\(m\) を正の整数とする。\(a\equiv b\pmod{m}\)、\(c\equiv d\pmod{m}\) のとき、\(a+c\equiv b+d\pmod{m}\) および \(ac\equiv bd\pmod{m}\) が成り立つことを証明せよ。空欄を埋めて証明を完成させよ。

\(a\equiv b\pmod m\) の定義より \(a-b=\) （\(k\) は整数）。
\(c\equiv d\pmod m\) の定義より \(c-d=\) （\(l\) は整数）。
よって \((a+c)-(b+d)=\) となり、これは \(m\) の倍数だから \(a+c\equiv b+d\pmod m\)。
また \(ac-bd=c(a-b)+b(c-d)=\) となり、これも \(m\) の倍数だから \(ac\equiv bd\pmod m\)。

解説を見る

合同式 \(a\equiv b\pmod m\) の定義は「\(a-b\) が \(m\) の倍数である」ことである。この定義を使って、和 \(a+c\) と積 \(ac\) それぞれについて差を計算し、\(m\) の倍数の形に持ち込めばよい。まず加法について。 \(a\equiv b\pmod m\) だから、ある整数 \(k\) を用いて \(a-b=mk\) と書ける。 \(c\equiv d\pmod m\) だから、ある整数 \(l\) を用いて \(c-d=ml\) と書ける。このとき \((a+c)-(b+d)=(a-b)+(c-d)=mk+ml=m(k+l)\) \(k+l\) は整数だから、\((a+c)-(b+d)\) は \(m\) の倍数である。よって \(a+c\equiv b+d\pmod m\)。次に乗法について。差 \(ac-bd\) は \(a-b\) と \(c-d\) だけでは直接表せないので、間に \(bc\) を挟んで変形する。 \(ac-bd=ac-bc+bc-bd=c(a-b)+b(c-d)\) ここに \(a-b=mk\)、\(c-d=ml\) を代入すると \(c(a-b)+b(c-d)=c\cdot mk+b\cdot ml=m(ck+bl)\) \(ck+bl\) は整数だから、\(ac-bd\) は \(m\) の倍数である。よって \(ac\equiv bd\pmod m\)。 \(a+c\equiv b+d\pmod m\)、\(ac\equiv bd\pmod m\) がともに示された

標準（10〜18）

互除法：余りを追う

\(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\)

互除法：余りを追う（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\)

互除法：大きい数でも手順は同じ

\(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\)

約分（既約分数にする）

\(\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}\)

文章題：最小公倍数の利用

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\) 秒後

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\)

文章題：タイルを敷き詰める

たて \(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\)枚

和とGCDから2数を求める

2つの正の整数 \(a\), \(b\) の最大公約数が \(6\)、和が \(54\) であるという。考えられる \(a\), \(b\) の組をすべて求めたい。\(a=6p\)、\(b=6q\)（\(p\), \(q\) は互いに素で \(p\lt q\)）とおくとき、以下の問いに答えよ。

\(p+q=\) 　条件を満たす組の数は　組　差が最も小さい組は \(a=\) 、\(b=\)

解説を見る

\(a=6p\)、\(b=6q\) とおくと、\(a+b=6(p+q)=54\) より \(p+q=9\)。 \(p\), \(q\) は互いに素で \(p\lt q\) だから、和が \(9\) になる組を小さい順に調べる。 \(p=1,q=8\)：\(\gcd(1,8)=1\) で条件を満たす。 \(p=2,q=7\)：\(\gcd(2,7)=1\) で条件を満たす。 \(p=3,q=6\)：\(\gcd(3,6)=3\) なので互いに素ではなく不適。 \(p=4,q=5\)：\(\gcd(4,5)=1\) で条件を満たす。これより \((p,q)=(1,8),(2,7),(4,5)\) の \(3\) 組が見つかり、\(6\) 倍すると \((a,b)=(6,48),(12,42),(24,30)\)。組の数は \(3\)、差が最も小さい組は \(a=24\)、\(b=30\)

積と最小公倍数から2数を求める

2つの正の整数 \(a\), \(b\) の積が \(720\)、最小公倍数が \(120\) であるという。考えられる \(a\), \(b\) の組をすべて求めたい。\(ab=\gcd(a,b)\times\operatorname{lcm}(a,b)\) の関係を使って、まず最大公約数を求め、\(a=Gp\)、\(b=Gq\)（\(p\), \(q\) は互いに素で \(p\lt q\)、\(G\) は最大公約数）とおいて考えよ。

最大公約数 \(G=\) 　\(p\times q=\) 　条件を満たす組の数は

解説を見る

\(ab=\gcd(a,b)\times\operatorname{lcm}(a,b)\) より \(\gcd(a,b)=\dfrac{ab}{\operatorname{lcm}(a,b)}=\dfrac{720}{120}=6\)。 \(a=6p\)、\(b=6q\)（\(p\), \(q\) は互いに素）とおくと、\(ab=36pq=720\) より \(pq=20\)。 \(pq=20\) で \(p\lt q\) となる組を調べる。 \(p=1,q=20\)：\(\gcd(1,20)=1\) で条件を満たす。 \(p=2,q=10\)：\(\gcd(2,10)=2\) なので互いに素ではなく不適。 \(p=4,q=5\)：\(\gcd(4,5)=1\) で条件を満たす。これより \((p,q)=(1,20),(4,5)\) の \(2\) 組が見つかり、\(6\) 倍すると \((a,b)=(6,120),(24,30)\)。最大公約数は \(6\)、\(p\times q=20\)、条件を満たす組の数は \(2\)

挑戦（19〜23）

文章題：池のまわりの木（最大公約数）

長方形の池のまわりの遊歩道（たて \(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\)本

文章題：等しく配る（最大公約数）

えんぴつ \(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\)冊ずつ

互除法で大きい分数を約分する

互除法を使って \(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}\)

一般の証明

\(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\)

√2が無理数であることの証明

\(\sqrt2\) が無理数であることを、互いに素な正の整数 \(p\), \(q\) を用いた背理法で証明せよ。

解説を見る

\(\sqrt2\) が無理数でない、つまり有理数であると仮定して矛盾を導く。有理数であれば \(\sqrt2=\dfrac{p}{q}\)（\(p\), \(q\) は互いに素な正の整数）と既約分数の形で表せる。互いに素にとれるのは、共通の約数があれば約分してしまえるからである。両辺を \(2\) 乗すると \(2=\dfrac{p^2}{q^2}\)、すなわち \(p^2=2q^2\)。右辺は \(2\) の倍数だから \(p^2\) は偶数。ここで、もし \(p\) が奇数なら \(p^2\) も奇数になってしまい矛盾するので、\(p\) は偶数でなければならない。そこで \(p=2k\)（\(k\) は正の整数）とおくと、\((2k)^2=2q^2\) より \(4k^2=2q^2\)、整理すると \(q^2=2k^2\)。これは \(q^2\) も偶数であることを示しており、先ほどと同じ理由で \(q\) も偶数でなければならない。すると \(p\) と \(q\) はともに \(2\) を約数に持つことになり、「\(p\), \(q\) は互いに素」という最初の仮定と矛盾する。したがって \(\sqrt2=\dfrac{p}{q}\) と表すことはできず、\(\sqrt2\) は無理数である。 \(p\), \(q\) がともに偶数になり互いに素であることに矛盾するため、\(\sqrt2\) は無理数である

応用問題（プリント限定）

ここから先は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通り

記述チャレンジ

答えだけでなく「なぜそうなるか」を文章と式で書く練習。模範解答と見比べて、書き方の型を身につけよう。

記1

整数 \(a,b\)（\(a\ge b\gt0\)）について、\(a\) を \(b\) で割ったときの商を \(q\)、余りを \(r\)（\(a=bq+r\)、\(0\le r\lt b\)）とするとき、\(\gcd(a,b)=\gcd(b,r)\) が成り立つ理由を説明せよ。

模範解答を見る

\(d=\gcd(a,b)\)、\(e=\gcd(b,r)\) とおいて、\(d=e\) であることを示す。まず\(d\)は\(a\)と\(b\)の公約数なので、\(a\)と\(b\)の両方を割り切る。\(r=a-bq\)であり、\(bq\)は\(b\)の倍数（すなわち\(d\)の倍数）だから、\(d\)の倍数どうしの差である\(r\)も\(d\)で割り切れる。よって\(d\)は\(b\)と\(r\)の公約数の1つでもある。次に\(e\)は\(b\)と\(r\)の公約数なので、\(b\)と\(r\)の両方を割り切る。\(a=bq+r\)は「\(e\)の倍数」と「\(e\)の倍数」の和なので、\(e\)は\(a\)も割り切る。よって\(e\)は\(a\)と\(b\)の公約数の1つでもある。ここで、\(d\)は「\(b\)と\(r\)の公約数」の1つなので、その中の最大値である\(e=\gcd(b,r)\)を超えることはない。すなわち\(d\le e\)。同様に、\(e\)は「\(a\)と\(b\)の公約数」の1つなので、その中の最大値である\(d=\gcd(a,b)\)を超えることはない。すなわち\(e\le d\)。\(d\le e\)と\(e\le d\)が同時に成り立つので\(d=e\)、すなわち\(\gcd(a,b)=\gcd(b,r)\)が成り立つ。 \(d\le e\)かつ\(e\le d\)が同時に成り立つことから\(d=e\)、すなわち\(\gcd(a,b)\)と\(\gcd(b,r)\)は等しくなる。

記2

互除法を用いて \(1029\) と \(693\) の最大公約数を求め、それを使って分数 \(\dfrac{1029}{693}\) を既約分数にせよ。

模範解答を見る

互除法で\(1029\)と\(693\)の最大公約数を求める。 \(1029 = 693\times1+336\) \(693 = 336\times2+21\) \(336 = 21\times16+0\) 余りが\(0\)になったので、最大公約数は\(21\)。分子・分母を\(21\)で割ると \(1029\div21=49\)、\(693\div21=33\) よって \(\dfrac{1029}{693} = \dfrac{49}{33}\) \(49=7^2\)、\(33=3\times11\)であり、共通の素因数を持たないので、\(\dfrac{49}{33}\)はこれ以上約分できない既約分数である。最大公約数は\(21\)、既約分数にすると \(\dfrac{49}{33}\)。