基準問題
ユークリッドの互除法を用いて、次の2数の最大公約数を求めなさい。
(1) $84$ と $36$
(2) $377$ と $232$
- 単元：数学A・整数（最大公約数）
- 難易度：★★（基本〜標準）
- ポイント：「大きい数 ÷ 小さい数」の余りを次の除数として使い、余りが $0$ になるまで繰り返す。
- 解答：(1) $12$ (2) $29$
この問題を解くための基礎知識
ユークリッドの互除法とは
「最大公約数（GCD）を求める方法」のひとつです。
素因数分解で求める方法 との違いは、数が大きくなっても機械的に手順を繰り返すだけで必ず答えが出る点です。
手順
2つの自然数 $a$、$b$（$a > b$）の最大公約数を求めます。
- $a$ を $b$ で割って、余り $r$ を求める。
- 余り $r = 0$ ならば → $b$ が最大公約数。終了。
- 余り $r \neq 0$ ならば → 「$b$ と $r$」の組に置き換えて、[1] に戻る。
この操作を繰り返すと、余りは毎回かならず小さくなるので、必ず $0$ に到達します。
なぜこれで最大公約数が求まるのか
$a = bq + r$ のとき、次のことが成り立ちます。
$$ \text{GCD}(a,\ b) = \text{GCD}(b,\ r) $$
理由：$a$ と $b$ の公約数 $d$ は $r = a – bq$ の約数でもあります。逆に $b$ と $r$ の公約数は $a = bq + r$ の約数でもあります。よって「$a$ と $b$ の公約数全体」と「$b$ と $r$ の公約数全体」が一致し、最大公約数も等しくなります。
例題（簡単な確認）
例：$30$ と $18$ の最大公約数を求めよ。
$$ 30 = 18 \times 1 + 12 $$
余り $12 \neq 0$ → 次は「$18$ と $12$」を調べます。
$$ 18 = 12 \times 1 + 6 $$
余り $6 \neq 0$ → 次は「$12$ と $6$」を調べます。
$$ 12 = 6 \times 2 + 0 $$
余りが $0$ になりました。このときの割る数が最大公約数です。
$$ \text{最大公約数} = 6 $$
確認：$30 = 2 \times 3 \times 5$、$18 = 2 \times 3^2$ → GCD $= 2 \times 3 = 6$ ✓
Level A（少し簡単）
数が小さく、2〜3回の操作で余りが $0$ になる問題です。手順の流れを確認するために使いましょう。
問 1
$48$ と $18$ の最大公約数を、ユークリッドの互除法を用いて求めなさい。
問 2
$56$ と $21$ の最大公約数を、ユークリッドの互除法を用いて求めなさい。
問 3
$72$ と $48$ の最大公約数を、ユークリッドの互除法を用いて求めなさい。
問 4
$90$ と $24$ の最大公約数を、ユークリッドの互除法を用いて求めなさい。
Level B（同じレベル）
基準問題と同程度の難易度です。操作回数が3〜4回になる問題で、手順を正確に追う練習をしましょう。
問 5
$156$ と $84$ の最大公約数を、ユークリッドの互除法を用いて求めなさい。
問 6
$221$ と $143$ の最大公約数を、ユークリッドの互除法を用いて求めなさい。
問 7
$273$ と $119$ の最大公約数を、ユークリッドの互除法を用いて求めなさい。
問 8
$299$ と $161$ の最大公約数を、ユークリッドの互除法を用いて求めなさい。
Level C（少し難しい）
操作回数が4〜5回に増える、やや大きな数の問題です。手順を途中で混乱しないよう、縦に書きながら丁寧に進めましょう。
問 9
$391$ と $323$ の最大公約数を、ユークリッドの互除法を用いて求めなさい。
問 10
$437$ と $209$ の最大公約数を、ユークリッドの互除法を用いて求めなさい。
問 11
$899$ と $493$ の最大公約数を、ユークリッドの互除法を用いて求めなさい。
問 12
$1547$ と $595$ の最大公約数を、ユークリッドの互除法を用いて求めなさい。
解くときのポイント
- 大きい数 ÷ 小さい数 の順に割る。どちらで割っても最終的に同じ答えになりますが、小さい数で割ると手順が増えて混乱しやすくなります。
- 余りを次のステップの「割る数」にする。余りが左側（割られる数）になるミスが多いので注意しましょう。
- 余りが $0$ になったとき に終了し、そのときの「割る数」が最大公約数です。「余り」ではありません。
- 縦に書く習慣をつけましょう。式を横に並べると取り違えやすくなります。
- 答えの確認 ：素因数分解が可能な場合は、確認として使うと安心です。
解答解説
問 1 の解説
$48$ と $18$ の最大公約数を求めます。
まず $48$ を $18$ で割って余りを求めます。
$$ 48 = 18 \times 2 + 12 $$
余り $12 \neq 0$ なので、次は「$18$ と $12$」を調べます。
$$ 18 = 12 \times 1 + 6 $$
余り $6 \neq 0$ なので、次は「$12$ と $6$」を調べます。
$$ 12 = 6 \times 2 + 0 $$
余りが $0$ になりました。このときの割る数が最大公約数です。
$$ \boxed{\text{最大公約数} = 6} $$
問 2 の解説
$56$ と $21$ の最大公約数を求めます。
$$ 56 = 21 \times 2 + 14 $$
余り $14 \neq 0$ → 次は「$21$ と $14$」を調べます。
$$ 21 = 14 \times 1 + 7 $$
余り $7 \neq 0$ → 次は「$14$ と $7$」を調べます。
$$ 14 = 7 \times 2 + 0 $$
余りが $0$ になりました。
$$ \boxed{\text{最大公約数} = 7} $$
問 3 の解説
$72$ と $48$ の最大公約数を求めます。
$$ 72 = 48 \times 1 + 24 $$
余り $24 \neq 0$ → 次は「$48$ と $24$」を調べます。
$$ 48 = 24 \times 2 + 0 $$
余りが $0$ になりました。
$$ \boxed{\text{最大公約数} = 24} $$
確認：$72 = 8 \times 9$、$48 = 8 \times 6$、GCD $= 24$ ✓（$72 = 24 \times 3$、$48 = 24 \times 2$）
問 4 の解説
$90$ と $24$ の最大公約数を求めます。
$$ 90 = 24 \times 3 + 18 $$
余り $18 \neq 0$ → 次は「$24$ と $18$」を調べます。
$$ 24 = 18 \times 1 + 6 $$
余り $6 \neq 0$ → 次は「$18$ と $6$」を調べます。
$$ 18 = 6 \times 3 + 0 $$
余りが $0$ になりました。
$$ \boxed{\text{最大公約数} = 6} $$
問 5 の解説
$156$ と $84$ の最大公約数を求めます。
$$ 156 = 84 \times 1 + 72 $$
余り $72 \neq 0$ → 次は「$84$ と $72$」を調べます。
$$ 84 = 72 \times 1 + 12 $$
余り $12 \neq 0$ → 次は「$72$ と $12$」を調べます。
$$ 72 = 12 \times 6 + 0 $$
余りが $0$ になりました。
$$ \boxed{\text{最大公約数} = 12} $$
問 6 の解説
$221$ と $143$ の最大公約数を求めます。
$$ 221 = 143 \times 1 + 78 $$
余り $78 \neq 0$ → 次は「$143$ と $78$」を調べます。
$$ 143 = 78 \times 1 + 65 $$
余り $65 \neq 0$ → 次は「$78$ と $65$」を調べます。
$$ 78 = 65 \times 1 + 13 $$
余り $13 \neq 0$ → 次は「$65$ と $13$」を調べます。
$$ 65 = 13 \times 5 + 0 $$
余りが $0$ になりました。
$$ \boxed{\text{最大公約数} = 13} $$
確認：$221 = 13 \times 17$、$143 = 13 \times 11$ → GCD $= 13$ ✓
問 7 の解説
$273$ と $119$ の最大公約数を求めます。
$$ 273 = 119 \times 2 + 35 $$
余り $35 \neq 0$ → 次は「$119$ と $35$」を調べます。
$$ 119 = 35 \times 3 + 14 $$
余り $14 \neq 0$ → 次は「$35$ と $14$」を調べます。
$$ 35 = 14 \times 2 + 7 $$
余り $7 \neq 0$ → 次は「$14$ と $7$」を調べます。
$$ 14 = 7 \times 2 + 0 $$
余りが $0$ になりました。
$$ \boxed{\text{最大公約数} = 7} $$
問 8 の解説
$299$ と $161$ の最大公約数を求めます。
$$ 299 = 161 \times 1 + 138 $$
余り $138 \neq 0$ → 次は「$161$ と $138$」を調べます。
$$ 161 = 138 \times 1 + 23 $$
余り $23 \neq 0$ → 次は「$138$ と $23$」を調べます。
$$ 138 = 23 \times 6 + 0 $$
余りが $0$ になりました。
$$ \boxed{\text{最大公約数} = 23} $$
問 9 の解説
$391$ と $323$ の最大公約数を求めます。
$$ 391 = 323 \times 1 + 68 $$
余り $68 \neq 0$ → 次は「$323$ と $68$」を調べます。
$$ 323 = 68 \times 4 + 51 $$
余り $51 \neq 0$ → 次は「$68$ と $51$」を調べます。
$$ 68 = 51 \times 1 + 17 $$
余り $17 \neq 0$ → 次は「$51$ と $17$」を調べます。
$$ 51 = 17 \times 3 + 0 $$
余りが $0$ になりました。
$$ \boxed{\text{最大公約数} = 17} $$
確認：$391 = 17 \times 23$、$323 = 17 \times 19$ → GCD $= 17$ ✓
問 10 の解説
$437$ と $209$ の最大公約数を求めます。
$$ 437 = 209 \times 2 + 19 $$
余り $19 \neq 0$ → 次は「$209$ と $19$」を調べます。
$$ 209 = 19 \times 11 + 0 $$
余りが $0$ になりました。今回は2回の操作で終わりました。
$$ \boxed{\text{最大公約数} = 19} $$
確認：$437 = 19 \times 23$、$209 = 19 \times 11$ → GCD $= 19$ ✓
問 11 の解説
$899$ と $493$ の最大公約数を求めます。操作回数が5回になります。焦らず1行ずつ進めましょう。
$$ 899 = 493 \times 1 + 406 $$
$$ 493 = 406 \times 1 + 87 $$
$$ 406 = 87 \times 4 + 58 $$
$$ 87 = 58 \times 1 + 29 $$
$$ 58 = 29 \times 2 + 0 $$
余りが $0$ になりました。
$$ \boxed{\text{最大公約数} = 29} $$
問 12 の解説
$1547$ と $595$ の最大公約数を求めます。$1547$ は大きい数ですが、手順は変わりません。
$$ 1547 = 595 \times 2 + 357 $$
余り $357 \neq 0$ → 次は「$595$ と $357$」を調べます。
$$ 595 = 357 \times 1 + 238 $$
余り $238 \neq 0$ → 次は「$357$ と $238$」を調べます。
$$ 357 = 238 \times 1 + 119 $$
余り $119 \neq 0$ → 次は「$238$ と $119$」を調べます。
$$ 238 = 119 \times 2 + 0 $$
余りが $0$ になりました。
$$ \boxed{\text{最大公約数} = 119} $$
確認：$1547 = 119 \times 13$、$595 = 119 \times 5$ → GCD $= 119$ ✓
一緒に解いてみよう
ここまで12問、お疲れさまでした。全問解き終わったあなたは、どんな大きな数が来ても互除法の手順を迷わず動かせるようになっています。
実は「人に教えること」は、学習の中でいちばん記憶に定着する方法といわれています。同じ単元で詰まっている友達がいたら、ぜひ「余りが $0$ になるまで繰り返すだけだよ」と自分の言葉で教えてみてください。教えられたとき、本物の理解になります。
このページのURLをLINEで送るだけでも、友達の「わからない」を「わかった！」に変えるきっかけになれます。
1ヶ月間「0円」で体験
無料学習相談で、あなたの状況に合わせた学習計画と「最適なプランの使い方」を具体的にご案内します。
お友達紹介・兄弟姉妹割引あり。口コミで広がっています。
【期間限定】
- 無料学習相談（プロが学習計画をご提案）
- 全教科 LINE質問し放題
- オンライン自習室 利用し放題
- 学習コーチング（希望者）
▼ 友だち追加後、すぐに「無料学習相談」を予約できます ▼
