ユークリッドの互除法｜gcd(a,b)=gcd(b,r) の証明・長方形の図と最大公約数・不定方程式の例題【大学受験 数学A】

ユークリッドの互除法｜gcd(a,b)=gcd(b,r) の証明・長方形の図と最大公約数・不定方程式の例題【大学受験 数学A】

合格大作戦 算数・数学公式辞典 › 数と式

大学受験

a=bq+r ⇒ gcd⁡(a, b)=gcd⁡(b, r)a=bq+r\ \Rightarrow\ \gcd(a,\ b)=\gcd(b,\ r)

余りが0になったときの割る数が最大公約数

この公式のポイント

  • aa を bb で割った余り rr について gcd⁡(a, b)=gcd⁡(b, r)\gcd(a,\ b)=\gcd(b,\ r)
  • 理由：aa と bb の公約数と、bb と rr の公約数はまったく同じ
  • 割り算をくり返し、余りが0のときの割る数が答え
  • 逆にたどると ax+by=gcd⁡(a,b)ax+by=\gcd(a,b) の整数解が見つかる
うかるくん

うかるくん

割り算をくり返すだけで、どうして最大公約数が出てくるの？

合格先生

合格先生

a=bq+ra=bq+r なら、aa と bb の公約数と、bb と rr の公約数がまったく同じだからだ。

ユークリッドの互除法

2つの自然数の最大公約数を、割り算をくり返すだけで求める方法です。大きな数でも、素因数分解をせずにすばやく求められます。

互除法の原理

aa を bb で割った余りを rr とすると（a=bq+ra=bq+r）、

gcd⁡(a, b)=gcd⁡(b, r)\gcd(a,\ b)=\gcd(b,\ r)

これをくり返し、余りが0になったときの割る数が最大公約数。

割り算式
1071÷4621071\div4621071=462×2+1471071=462\times2+147
462÷147462\div147462=147×3+21462=147\times3+21
147÷21147\div21147=21×7+0147=21\times7+0
結論gcd⁡(1071, 462)=21\gcd(1071,\ 462)=21

なぜ gcd(a, b)=gcd(b, r) なのか（証明）

a=bq+ra=bq+r のとき、aa と bb の公約数全体と、bb と rr の公約数全体が同じであることを示します。

  • dd が aa と bb の公約数なら、r=a−bqr=a-bq も dd で割り切れる。よって dd は bb と rr の公約数。
  • dd が bb と rr の公約数なら、a=bq+ra=bq+r も dd で割り切れる。よって dd は aa と bb の公約数。

公約数の集まりがまったく同じなので、その中でいちばん大きいもの（最大公約数）も同じです。割り算のたびに数は小さくなるので、必ず有限回で余りが0になって終わります。

10510545a＝255＝15×17b＝105＝15×7r＝45＝15×3白い線＝15ごとの目もりr＝a−2b なので目もりがそろう
255=105×2+45255=105\times2+45。公約数15の目もりは a=255a=255 にも b=105b=105 にも合うので、r=a−2b=45r=a-2b=45 にもぴったり合う

図で見る：長方形を正方形で切り取る

105の正方形×245×2、15×3
255×105 の長方形から、できるだけ大きい正方形を切り取っていくと、最後は 15×15 の正方形でぴったり分けられる

たて bb、横 aa の長方形から1辺 bb の正方形を qq 個切り取ると、残りは b×rb\times r の長方形。これをくり返して最後に残る正方形の1辺が、最大公約数です（255と105なら15）。互除法は「余りの長方形でも同じことができる」という考え方です。

発展：ax＋by＝1 の整数解

互除法を逆にたどると、gcd⁡(a, b)=d\gcd(a,\ b)=d のとき ax+by=dax+by=d をみたす整数 x, yx,\ y が見つかります。たとえば gcd⁡(17, 5)=1\gcd(17,\ 5)=1 で、17=5×3+217=5\times3+2、5=2×2+15=2\times2+1 から 1=5−2×2=5−(17−5×3)×2=5×7−17×21=5-2\times2=5-(17-5\times3)\times2=5\times7-17\times2。よって 17×(−2)+5×7=117\times(-2)+5\times7=1。

大学受験（数学A）での使い方

大学受験

例題1（最大公約数）

gcd⁡(391, 299)\gcd(391,\ 299) を求めなさい。

解き方

391=299×1+92391=299\times1+92、299=92×3+23299=92\times3+23、92=23×4+092=23\times4+0。

答え　2323

大学受験

例題2（不定方程式）

13x+5y=113x+5y=1 をみたす整数 x, yx,\ y の組を1つ求め、すべての整数解を求めなさい。

解き方

13=5×2+313=5\times2+3、5=3×1+25=3\times1+2、3=2×1+13=2\times1+1 を逆にたどると 1=3−2=3−(5−3)=2×3−5=2(13−5×2)−5=13×2−5×51=3-2=3-(5-3)=2\times3-5=2(13-5\times2)-5=13\times2-5\times5。

(x, y)=(2, −5)(x,\ y)=(2,\ -5) が1つの解。すべての解は x=2+5tx=2+5t、y=−5−13ty=-5-13t（tt は整数）。

答え　x=2+5t, y=−5−13tx=2+5t,\ y=-5-13t

よくある間違い

腕でバツを作る合格先生

合格先生

次は「割った数」を「余り」で割る。割る数と余りを取りちがえて進むな。

  • 割る数と余りを取りちがえて次に進む：次は「割った数」を「余り」で割る。
  • 最後の余り（0）の1つ前を答える：答えは余りが0になったときの割る数。

練習問題

「ここが大事！」と説明する合格先生

合格先生

答えは、余りが0になったときの割る数だ。

  1. 大学受験 gcd⁡(252, 198)\gcd(252,\ 198) を互除法で求めなさい。
    答えと解説を見る252=198+54252=198+54、198=54×3+36198=54\times3+36、54=36+1854=36+18、36=18×236=18\times2。答え 1818
  2. 大学受験 gcd⁡(1001, 143)\gcd(1001,\ 143) を求めなさい。
    答えと解説を見る1001=143×7+01001=143\times7+0。答え 143143

関連する公式

この公式が出てくる合格大作戦の記事

よくある質問

ユークリッドの互除法とは？

2つの自然数の最大公約数を、割り算をくり返して求める方法です。a を b で割った余りを r とすると gcd(a, b)=gcd(b, r) が成り立つことを使います。

なぜ gcd(a, b)=gcd(b, r) なのですか？

a=bq+r なので、a と b の公約数は r=a−bq も割り切り、b と r の公約数は a=bq+r も割り切ります。公約数の集まりが同じなので、最大公約数も同じです。

互除法で不定方程式を解くには？

互除法の式を逆にたどって ax+by=1 の形を作ると、整数解が1組見つかります。そこから一般解を求めます。

ユークリッドの互除法は何年生で習いますか？

高校の数学A「数学と人間の活動」などで習います。

あわせて読みたい

出典・参考

  • 文部科学省「高等学校学習指導要領（平成30年告示）」数学A（数学と人間の活動）

最終更新：2026年10月11日／作成：大学受験合格大作戦