ユークリッドの互除法をわかりやすく解説｜マイナス・証明・不定方程式まで

ユークリッドの互除法で最初に覚えるのは、大きい数＝小さい数×商＋余りと書き、次は「小さい数と余り」の組で同じ操作を続けることです。ただし、手順だけを暗記すると、逆代入でどの式を使うか、負号をどこへ付けるか、整数解が存在するかを判定するときに迷います。そこで本記事は、計算・理由・応用を切り離さず、答案として再現できる形まで解説します。

ユークリッドの互除法とは｜最大公約数を求める3ステップ

ユークリッドの互除法とは、2つの整数の最大公約数を、余りを使って段階的に求める方法です。大きい数を小さい数で割り、余りが0でなければ、今度は「直前の割る数」を「余り」で割ります。余りが0になったとき、その直前に割る数として使った正の整数が、最初の2数の最大公約数です。

例題｜252と198の最大公約数を求める

252を198で割ると、252＝198×1＋54です。次に198を54で割って198＝54×3＋36、さらに54＝36×1＋18、最後に36＝18×2＋0となります。余りが0になった式で割る数は18なので、gcd(252,198)＝18です。素因数分解のように割れる素数を探し続けなくても、割り算だけで機械的に答えへ到達できます。

回	割り算の式	次に使う2数
1	252＝198×1＋54	198と54
2	198＝54×3＋36	54と36
3	54＝36×1＋18	36と18
4	36＝18×2＋0	終了。最大公約数は18

3ステップを答案の型にする

高校数学の整数分野を広く復習したい場合は、既存記事の高校数学「整数の性質」完全ガイドもあわせて使うと、約数・倍数・n進法との位置関係まで整理できます。

なぜ最大公約数が変わらないのか｜互除法の原理と証明

互除法の中心は、a＝bq＋rならgcd(a,b)＝gcd(b,r)という等式です。「最大公約数だけが偶然同じ」なのではありません。aとbの公約数を集めた集合と、bとrの公約数を集めた集合が、そっくり同じになるため、その中の最大の正の数も一致します。

証明の前半｜aとbの公約数はbとrの公約数でもある

aとbの公約数をdとします。dはaもbも割り切るので、整数A、Bを使ってa＝dA、b＝dBと書けます。ここでr＝a－bqですから、r＝dA－dBq＝d(A－Bq)です。A－Bqは整数なので、dはrも割り切ります。もともとdはbを割り切っているため、dはbとrの公約数です。

証明の後半｜bとrの公約数はaとbの公約数でもある

逆向きも示します。bとrの公約数をeとすれば、b＝eB、r＝eRと書けます。a＝bq＋rへ代入すると、a＝eBq＋eR＝e(Bq＋R)となるので、eはaを割り切ります。eはもともとbも割り切るため、eはaとbの公約数です。両方向が示せたので、公約数の集合が一致し、最大公約数も一致します。

なぜ割り算は必ず終わるのか

各段階の余りは、0以上で割る数より小さく取ります。余りが0でない間は、正の整数が198、54、36、18のように必ず小さくなります。正の整数を無限に小さくし続けることはできないため、有限回で余り0に到達します。最後の0でない余りまでgcdの値が保存されるので、その数が最初の2数の最大公約数です。

この原理と証明は、電気通信大学の資料「RSA暗号の数学的基礎」の命題2.9、上越教育大学の公開講座資料の補題2.1・定理2.2、東京大学の教材「電算機応用(2) 第8章」でも同じ形で確認できます。答案では資料の文を暗記するのではなく、r＝a－bqとa＝bq＋rの2本を使って両方向を自分で書けるようにしてください。

マイナスを含むユークリッドの互除法｜余りと符号の扱い方

負の数を含むときも互除法の原理は変わりません。ただし、最大公約数は正の数として扱い、計算の最初に絶対値へ直す方法と、負の整数のまま余りを0以上にそろえる方法を混同しないことが重要です。最大公約数だけを求めるなら、gcd(−252,198)＝gcd(252,198)として、絶対値252と198へ直してから計算するのが最も安全です。

負の数を割るときは商を負の方向へ調整する

例として−19を7で割ります。−19＝7×(−2)−5は等式として正しくても、余り−5が0以上7未満ではないため、除法の原理の余りとしては使いません。商を−3にすると、−19＝7×(−3)＋2となり、余り2が条件を満たします。負の割られる数では、小数の商−2.7…を0へ近づけて−2とするのではなく、より小さい整数−3を選ぶと覚えると整理できます。

表し方	等式	互除法の余りとして
不適切	−19＝7×(−2)−5	余りが負なので使わない
適切	−19＝7×(−3)＋2	0≦2＜7なので使える
絶対値で処理	gcd(−19,7)＝gcd(19,7)	最大公約数だけなら簡単

負の係数を含む不定方程式では未知数側の符号を戻す

たとえば−41x＋26y＝1を考えます。まず41と26について互除法を行うと、後で示す逆代入から41×7＋26×(−11)＝1が得られます。元の係数は−41なので、41の前の符号を戻し、−41×(−7)＋26×(−11)＝1とします。したがって特殊解はx＝−7、y＝−11です。係数を絶対値に直したときは、最後にどの係数の符号を変えたかを確認してください。

東海大学の「代数学序論のノート」では、a＜0、b＞0の場合に−aを用いた方程式を解き、最後にxの符号を反転して元の方程式の解を得る方法が示されています。負の係数が2つある場合も、絶対値で特殊解を求めてから元の係数へ戻す、という同じ方針で処理できます。

拡張ユークリッドの互除法｜逆代入で特殊解を1組求める

通常の互除法は最大公約数を求めて終わります。拡張ユークリッドの互除法は、その割り算の式を下から逆に代入し、最大公約数を元の2数の整数係数の和として表します。つまり、ax＋by＝gcd(a,b)を満たす整数x,yを1組作る方法です。この1組を、一次不定方程式の特殊解と呼びます。

例題｜41x＋26y＝1の特殊解を求める

まず41と26に互除法を使います。41＝26×1＋15、26＝15×1＋11、15＝11×1＋4、11＝4×2＋3、4＝3×1＋1、3＝1×3＋0です。最後の0でない余りが1なので、41と26は互いに素です。

逆代入は「余り＝」へ直して下から戻る

逆代入では、1を含む最後の式から始めます。1＝4−3、3＝11−4×2なので、1＝4−(11−4×2)＝3×4−11です。さらに4＝15−11を入れて1＝3×15−4×11、11＝26−15を入れて1＝7×15−4×26、最後に15＝41−26を入れると、1＝7×41−11×26です。したがって、41x＋26y＝1の特殊解は(x,y)＝(7,−11)です。

逆代入の段階	1の表し方
開始	1＝4−3
3を消す	1＝3×4−11
4を消す	1＝3×15−4×11
11を消す	1＝7×15−4×26
15を消す	1＝7×41−11×26

逆代入で計算ミスを減らす書き方

電気通信大学の資料では、この逆代入を係数の数列として計算する拡張アルゴリズムも示されています。高校数学の答案では、割り算の式を残して下から代入する形が追いやすいでしょう。途中式を省くと、符号を落としたときに戻れないため、1回の代入につき1行を使うのが安全です。

一次不定方程式ax＋by＝c｜整数解の条件と一般解

一次不定方程式ax＋by＝cに整数解があるための必要十分条件は、d＝gcd(a,b)がcを割り切ることです。aとbがともにdの倍数なら、左辺ax＋byも必ずdの倍数です。したがってcがdの倍数でなければ整数解はありません。逆にdがcを割り切れば、互除法でax＋by＝dの特殊解を作り、両辺をc/d倍すればax＋by＝cの特殊解が得られます。

解の存在判定｜まず最大公約数を見る

例として18x＋30y＝12では、gcd(18,30)＝6で、6は12を割り切るため整数解があります。一方、18x＋30y＝7では、左辺がどの整数x,yを入れても6の倍数になるのに、右辺7は6の倍数ではありません。したがって整数解はありません。互除法を長く続ける前に、右辺が最大公約数で割り切れるかを確認すると、解けない方程式を早く判定できます。

特殊解を1組作る｜18x＋30y＝12

18x＋30y＝12を最大公約数6で割ると、3x＋5y＝2です。ここでは3×4＋5×(−2)＝2なので、(x,y)＝(4,−2)が特殊解です。互除法で求めるなら、5＝3×1＋2から2＝5−3と戻し、3x＋5y＝2の特殊解(x,y)＝(−1,1)を得ても構いません。特殊解は1組に限られないため、どちらも正解です。

一般解へ広げる｜特殊解との差を取る

18x＋30y＝12の特殊解を(x0,y0)＝(4,−2)とします。元の式から特殊解の式18×4＋30×(−2)＝12を引くと、18(x−4)＋30(y＋2)＝0です。6で割って3(x−4)＝−5(y＋2)とすると、3と5は互いに素なので、x−4は5の倍数です。整数kを使ってx−4＝5kと置けば、y＋2＝−3kとなります。

公式の符号は丸暗記せず、代入して確認します。18(4＋5k)＋30(−2−3k)＝72＋90k−60−90k＝12で、kの項が打ち消されます。x側をプラスにしたらy側はマイナスになること、増分がb/dとa/dに対応することを、検算から確かめてください。

整数解の存在条件d｜cは、東海大学「代数学序論のノート」の命題4.4で必要十分条件として証明されています。一般解は電気通信大学の資料でも、特殊解との差を取り、互いに素な係数の倍数関係から導いています。入試答案でも「公式より」とだけ書くより、特殊解との差を1行示すと、符号の根拠が明確になります。

ユークリッドの互除法の応用｜証明・合同式・よくあるミス

互除法は、最大公約数を求める計算だけではありません。公約数を保存する原理と、最大公約数をax＋byの形へ戻す逆代入を組み合わせることで、互いに素の証明、合同式の逆元、一次不定方程式、複数整数の最大公約数へ応用できます。問題文が何を要求しているかを読み、余り0までで止めるのか、逆代入まで進むのかを判断してください。

応用1｜互いに素であることを証明する

2数の最大公約数が1だと示したいときは、互除法で最後の余り1を出す方法が直接的です。文字式なら、共通の約数dが差や整数倍の差も割り切ることを使います。たとえば連続する整数nとn＋1の公約数dは、差(n＋1)−n＝1も割り切ります。1の正の約数は1だけなので、gcd(n,n＋1)＝1です。これは互除法の「片方から他方の整数倍を引いても公約数は変わらない」という考え方そのものです。

応用2｜合同式の逆元を求める

合同式7x≡1 (mod 26)は、7x−1が26の倍数という意味なので、7x＋26y＝1と同じ形です。互除法を逆代入すると、1＝26×3−7×11です。したがってx＝−11が1つの解で、26を法として−11≡15ですから、x≡15 (mod 26)となります。実際、7×15＝105は26で割ると1余ります。

応用3｜3つ以上の整数の最大公約数を求める

3数84、126、198の最大公約数は、まずgcd(84,126)＝42を求め、次にgcd(42,198)を求めます。198＝42×4＋30、42＝30×1＋12、30＝12×2＋6、12＝6×2＋0なので、答えは6です。つまりgcd(84,126,198)＝gcd(gcd(84,126),198)として、2数ずつ互除法を適用できます。

よくあるミス｜商・余り・一般解の符号

ミス	起こる理由	直し方
余り0を最大公約数にする	最後の式だけを見る	0を出した割る数を読む
余りが割る数以上になる	商が小さい	0≦r＜bを毎行確認する
逆代入で符号を落とす	括弧を省く	代入前の式を括弧ごと入れる
整数解なしを見落とす	すぐ逆代入する	最初にgcd(a,b)｜cを確認する
一般解の符号が同じ	公式だけを暗記する	元の式へ代入してkを消す

練習するときは1問を4段階で解き直す

互除法は、答えを眺めるより途中式を再現する練習が有効です。①最大公約数だけを求める、②各式を余り＝の形へ直す、③逆代入で特殊解を1組作る、④一般解へ広げて代入検算する、という4段階で同じ係数を使うと、各技能のつながりが見えます。間違えたときは「割り算」「逆代入」「存在判定」「一般解」のどこで止まったかを記録してください。

数学Aの整数分野をまとまった流れで進めたい人は、1Day鬼管理数学合宿とはで全体像を確認できます。数学のコースや参加方法の説明は、1Day鬼管理数学合宿の公式ページで確認してください。

ユークリッドの互除法は「普通の対策」では身につかない

結論から言うと、解説を読んで割り算の手順を覚えるだけの「普通の対策」では、ユークリッドの互除法を入試答案で使える状態にするのは厳しいです。この記事だけでも、余りの更新、原理の証明、負号の処理、逆代入、整数解の存在判定、一般解、検算という複数の操作がありました。知識を得た後に、手を動かして途中式を再現する行動まで進めなければ、別の係数になった瞬間に止まります。

鬼管理専門塾が示す従来塾の3つの限界は、①授業で情報を得ても行動は変わらない、②全員同じ指導は偏差値50に収束する、③週1指導では変化が遅い、というものです。ユークリッドの互除法でも、分かった回数ではなく、どの段階を自力で再現し、誤りを直したかが重要です。代表的な選択肢を1つずつ検討します。

独学・参考書のみでは演習の完了を自分で管理する

参考書は原理と例題を整理するのに役立ちますが、読んだ後に何問を解き、逆代入や一般解まで終えたかは自分で管理しなければなりません。説明を読んで理解した感覚だけで止まれば、限界①の「情報を得ても行動は変わらない」に当たります。

映像授業・学習アプリだけでは視聴と答案作成が分かれる

映像授業やアプリは、割り算の流れを短時間で確認できます。一方、映像を見終えたことと、余りの式を下から戻して特殊解を書けることは別です。視聴後の計算と検算が利用者任せなら、ここでも限界①が残ります。

集団授業の大手予備校ではつまずきの段階を個別に追いにくい

同じ互除法の問題でも、ある人は商の計算で、別の人は逆代入の符号で、さらに別の人は一般解の作り方で止まります。集団授業は同じ説明を同じ進度で届けるため、個別の誤答段階に合わせた反復量を確保しにくく、限界②の「全員同じ指導」に当たりやすい方法です。

一般的な個別指導塾では授業外の反復が途切れやすい

個別に質問できても、授業がない日に割り算から検算までを通して解かなければ、手順は定着しません。次の指導日まで演習が止まり、誤った符号の付け方を直すのが遅れる形では、限界③の「週1指導では変化が遅い」が残ります。

そこで、ユークリッドの互除法を含む整数の性質の単元を1日でやり切りたい人には、鬼管理専門塾が開く1Day鬼管理数学合宿をおすすめします。

1Day鬼管理数学合宿の特徴

1Day鬼管理数学合宿は、鬼管理専門塾が開くオンラインの合宿です。数学の1つの単元や志望校の範囲を、1日でやり切ります。授業を聞く日ではなく、紙に解いて答えを確かめる日です。塾生でなくても参加できます。合宿の全体像は、1Day鬼管理数学合宿とはで確かめられます。

塾に入るなら｜鬼管理専門塾の特徴

合宿の日だけでなく、毎日の勉強まで見てもらうなら、塾は鬼管理専門塾です。

鬼管理専門塾は、日々の学習を1日単位で管理するオンライン塾です。ここでは、公式サイトで確認できる6つの特徴を、ユークリッドの互除法を含む受験数学の学習へどう活用できるかとあわせて整理します。

❶ 1日単位の数値化した学習指示

鬼管理専門塾では、毎朝「今日やるべきこと」を数値で指示します。時間・場所・教材・目的まで具体化し、何をすべきかで迷う時間を減らします。

互除法では、最大公約数を求める、逆代入する、一般解を作る、代入検算するという作業を日ごとの課題へ落とし込む必要があります。数値化した指示なら、解説を読んだだけで終わらず演習量を確保できます。

❷ 生徒ごとの個別行動プラン

全員に同じ課題を出すのではなく、現在の得点、得意・不得意、志望校の配点に合わせて、生徒ごとの行動プランを設計します。

商の計算で止まる人、負号で迷う人、存在条件を忘れる人では必要な課題が異なります。誤答段階から個別行動プランを作れば、分かっている計算の反復を減らし、弱点へ時間を使えます。

❸ 毎日・毎週の徹底管理と確認テスト

日々の進捗確認に加えて毎週の確認テストを行い、基準に届かなければ追加課題と計画修正を行って、遅れをその週のうちに戻します。

互除法は一度解けても、係数や右辺が変わると再び迷いやすい分野です。毎日の進捗と毎週の確認テストで別の数でも逆代入と一般解を再現できるかを確かめれば、理解と実行のずれを早めに修正できます。

❹ 採用率0.6%の専属講師陣

講師は難関大学合格実績と独自審査を満たした人材から採用し、採用率は0.6%です。指導の質は講師満足度アンケート回答1,524件でも継続的に検証しています。

不定方程式で誤答したとき、答えだけでなく除法の原理、逆代入、一般解のどこへ戻るべきかを説明できる講師がいれば、誤った符号処理を長く続けずに済みます。講師体制は学習の修正精度に関わります。

❺ 大学受験〜英語資格まで専門コース展開

大学・学部特化の大学受験、総合型選抜・推薦、英検・TOEIC・TOEFL・IELTS・TEAPなどの英語資格、高校受験まで専門コースを展開しています。

整数分野は大学受験や高校受験の目標によって、必要な証明の深さや演習範囲が変わります。目標に対応する専門コースの中で、基礎計算から志望校の出題形式へ必要な学習をつなげられます。

❻ LINE質問対応+無料説明会・資料請求

授業がない日もLINEで質問でき、入会前にはZoomの無料説明会や資料請求を利用できます。生徒と保護者が指導内容を確認してから判断できます。

互除法の途中式について質問が生じた日にLINEで確認できれば、誤った余りや負号のまま次の問題へ進むのを防げます。入会前の案内窓口も含め、指導内容を確認する連絡手段が用意されています。

1日単位の学習管理と従来塾の3つの限界は、「鬼管理」とは？で確認できます。塾全体の進学結果は、鬼管理専門塾の合格実績に掲載されています。

まとめ｜互除法は「割る→戻す→広げる」で理解する

ユークリッドの互除法は、余り0まで割り続けるだけの計算ではありません。a＝bq＋rで公約数の集合が変わらないことを理解すれば、なぜ最大公約数が求まるかを証明できます。さらに式を下から戻せば、最大公約数をax＋byの形へ表し、一次不定方程式の特殊解と一般解へ進めます。

段階	すること	確認すること
割る	a＝bq＋rを繰り返す	0≦r＜bになっている
読む	最後の0でない余りを答える	元の2数を割り切る
証明する	公約数が両方向に一致すると示す	r＝a−bqも使う
戻す	余り＝の式を下から代入する	元の2数だけになった
判定する	gcd(a,b)がcを割るか見る	整数解の有無を先に決める
広げる	特殊解からkで一般解を作る	代入でkの項が消える

まずは252と198の例を何も見ずに解き、次に41x＋26y＝1を逆代入まで再現してください。その後、18x＋30y＝12の存在判定・特殊解・一般解を通して解けば、互除法の主要な使い方を1本の流れで確認できます。負の係数がある場合は絶対値で計算し、最後に符号を戻して元の式へ代入します。

よくある質問

質問のテーマ	最初に見るもの
最大公約数	最後の0でない余り
マイナス	余りの範囲と係数の符号
特殊解	余り＝の逆代入
一般解	最大公約数と特殊解

Q. ユークリッドの互除法とは何ですか？

A. 2つの整数の最大公約数を、割り算の余りを使って求める方法です。大きい数を小さい数で割り、次は小さい数を余りで割る操作を、余りが0になるまで続けます。最後の0でない余りが最大公約数です。

Q. なぜ余りが0になるまで計算するのですか？

A. a＝bq＋rならgcd(a,b)＝gcd(b,r)で、最大公約数を保ったまま余りが小さくなります。正の余りは段階ごとに小さくなるため有限回で0になり、その直前の余りが最大公約数になります。

Q. ユークリッドの互除法でマイナスを含むときはどうしますか？

A. 最大公約数だけを求めるなら2数を絶対値へ直します。負の整数をそのまま割る場合も、余りは0以上で割る数より小さく取ります。不定方程式では、最後に元の係数の符号へ戻して代入検算してください。

Q. ユークリッドの互除法の証明で何を示せばよいですか？

A. a＝bq＋rに対し、aとbの公約数がbとrの公約数でもあり、逆にbとrの公約数がaとbの公約数でもあることを示します。公約数の集合が一致するので、最大公約数も一致します。

Q. 拡張ユークリッドの互除法とは何ですか？

A. 通常の互除法で最大公約数を求めた後、割り算の式を下から逆代入し、ax＋by＝gcd(a,b)を満たす整数x,yを求める方法です。一次不定方程式の特殊解を作るときに使います。

Q. 一次不定方程式ax＋by＝cに整数解がある条件は？

A. d＝gcd(a,b)とすると、dがcを割り切ることが必要十分条件です。dがcを割り切らなければ整数解はなく、割り切ればax＋by＝dの特殊解をc/d倍して、ax＋by＝cの特殊解を作れます。

Q. 特殊解が解答例と違っても正解ですか？

A. 元の方程式を満たす整数の組なら正解です。一次不定方程式には複数の特殊解があり、そこから同じ一般解の集合を別のkの取り方で表せます。必ず元の式へ代入して正しいことを確認してください。

Q. 一般解のプラスとマイナスを覚えるコツは？

A. d＝gcd(a,b)、特殊解を(x0,y0)とすると、x＝x0＋(b/d)k、y＝y0−(a/d)kです。符号を丸暗記せず元の式へ代入し、kの項が互いに打ち消されるかを確認すると間違いを直せます。

Q. 3つの整数にもユークリッドの互除法を使えますか？

A. 使えます。まず2数の最大公約数を求め、その結果と3つ目の整数の最大公約数を求めます。gcd(a,b,c)＝gcd(gcd(a,b),c)として、2数の互除法を順番に適用します。

Q. ユークリッドの互除法を効率よく練習するには？

A. 1つの係数で、最大公約数、余り＝の書き換え、逆代入、特殊解、一般解、代入検算まで通して解きます。誤答は割り算・逆代入・存在判定・一般解のどこで起きたかに分けて解き直してください。