ユークリッド互除法と一次不定方程式：余りからすべての整数解へ

最大公約数が変わらない理由を確かめ、割り算を逆にたどって整数解を一つ発見する。解の存在条件、一般解、個数の制約までをつなぐ。

この単元の目標

余りに置き換えても公約数が変わらないことを説明できる
ユークリッド互除法と逆代入で最大公約数を整数の一次結合として表せる
一次不定方程式の整数解の存在条件を判定し、すべての解を表せる
整数解と非負整数解を区別し、条件を満たす解を絞り込める

📑 目次

1．大きな数を、余りの問題に置き換える
2．割り算を逆にたどると何が分かるか
3．整数解が存在する条件
4．一つの解から「すべての解」へ
5．個数を表すなら非負条件を追加する
練習：解の存在・全解・制約を分けよう

1．大きな数を、余りの問題に置き換える

二つの正の整数の最大公約数を、素因数分解せずに求める方法がユークリッド互除法です。以下、最大公約数は正の値をとり、gcd(a,b) と書きます。まず a ≥ b > 0 とします。割り算の商を q、余りを r とすると、次の式が成り立ちます。

a=bq+r,\qquad q,r\in\mathbb Z,\quad 0\le r<b

🔍 公約数の集合が同じになる理由

a と b の公約数は r も割り切る
$r=a-bq$
d が a と b を割り切るなら、その整数倍の差 r も割り切ります。
b と r の公約数は a も割り切る
$a=bq+r$
逆に d が b と r を割り切るなら、その和 a も割り切ります。
公約数が一致するので最大のものも一致
$\gcd(a,b)=\gcd(b,r)$
r=0 の場合は gcd(b,0)=b とします。正の b は 0 を割り切ります。

余りが0でなければ、今の割る数と余りで次の割り算をします。正の余りは毎回小さくなるので、いつか必ず余り0で止まります。答えは0ではなく、最後に現れた0でない余り（最後の割り算の割る数）です。最初から割り切れる場合は最初の割る数が答えです。

例題1：252と198の最大公約数

252と198の最大公約数を互除法で求めよう。

解答・解説

252=198×1+54、198=54×3+36、54=36×1+18、36=18×2+0。よって最大公約数は18です。実際に252=18×14、198=18×11。単に18が公約数と確認するだけでなく、互除法の各段階で最大公約数が保存されたことが「最大」の根拠です。

2．割り算を逆にたどると何が分かるか

例題1の余りを、元の252と198の整数倍の和に書き直してみます。最後の0の式は使わず、18が現れた式から始めます。途中で出てきた36、54を順に消していくのが逆代入です。

🔍 最大公約数を元の二数で表す

18の式から出発
$18=54-36$
36を置き換える
$18=54-(198-3\cdot54)=4\cdot54-198$
54を置き換える
$18=4(252-198)-198=4\cdot252-5\cdot198$
検算すると1008−990=18です。

つまり252x+198y=18には整数解 (x,y)=(4,−5) があります。負の整数も許している点に注意しましょう。このように、二つの整数にそれぞれ整数を掛けて足したものを「整数の一次結合」といいます。互除法の各余りは直前の二数の整数の一次結合なので、逆代入すれば最大公約数も元の二数の整数の一次結合で表せます。

3．整数解が存在する条件

一次不定方程式 ax+by=c では、未知数 x、y の値を整数に限定します。ここでは a、b は正の整数、c は任意の整数とします。実数解なら直線上に無数にあっても、整数の組が存在するとは限りません。「不定」は解がないという意味ではありません。

d=\gcd(a,b)\quad\Longrightarrow\quad ax+by=c\text{ が整数解をもつ}\ \Longleftrightarrow\ d\mid c

記号 d | c は「d が c を割り切る」という意味です。必要性：a と b がともに d の倍数なら、整数 x、y に対して左辺も必ず d の倍数です。十分性：逆代入で au+bv=d を満たす整数 u、v を求め、c=dk と書けば、両辺を k 倍して x=ku、y=kv を得られます。c=0 も含まれ、この場合は (0,0) が一つの解です。

小例：計算前に解の有無を判定する

252x+198y=30と252x+198y=54は整数解をもつか。

解答・解説

最大公約数は18です。30は18の倍数ではないので前者は整数解なし。54=18×3なので後者は整数解をもち、前節の等式を3倍すれば (x,y)=(12,−15) が得られます。252×12−198×15=3024−2970=54です。

4．一つの解から「すべての解」へ

整数解が一つ見つかっても、それだけでは全解を求めたことになりません。d=gcd(a,b) とし、A=a/d、B=b/d と置くと A と B は互いに素です。一つの解を (x₀,y₀)、任意の別の解を (x,y) として引き算します。

🔍 一般解に漏れがないことを示す

二つの等式の差を取り、dで割る
$A(x-x_0)+B(y-y_0)=0$
互いに素であることを使う
$A(x-x_0)=-B(y-y_0)\ \Longrightarrow\ B\mid(x-x_0)$
A と B に共通の素因数がないため、B の各素因数は必要な個数だけ x−x₀ に含まれます。B=1 の場合も成立します。
整数パラメータtで表す
$x=x_0+Bt,\qquad y=y_0-At,\qquad t\in\mathbb Z$
任意の整数解がこの形になります。逆にこの形を元の式に代入すると、t の項が打ち消されるので、どの整数 t も解を与えます。

\boxed{x=x_0+\frac{b}{d}t,\qquad y=y_0-\frac{a}{d}t\quad(t\in\mathbb Z)}

増減の幅は b と a ではなく b/d と a/d です。公約数で割らないと解を取りこぼすことがあります。また x の増分と y の増分は逆符号です。t は実数ではなく整数に限定します。

例題2：35x+22y=1のすべての整数解

互除法、逆代入、一般解の順に解こう。

解答・解説

35=22+13、22=13+9、13=9+4、9=2×4+1 より最大公約数は1。逆代入すると 1=9−2×4=3×9−2×13=3×22−5×13=8×22−5×35。一つの解は (−5,8) です。したがって全解は $x=-5+22t,\,y=8-35t\ (t\in\mathbb Z)$ 。代入すれば $35(-5+22t)+22(8-35t)=1$ となります。

5．個数を表すなら非負条件を追加する

整数解では負数を許しますが、品物の個数には通常 x ≥ 0、y ≥ 0 が必要です。「正の整数」と指定されたら0も除きます。一般解を出したあと、パラメータの範囲を不等式で絞ると数え漏れを防げます。

例題3：6個入りと9個入りの箱で60個を用意する

同じ品物の6個入りの箱を x 箱、9個入りの箱を y 箱選ぶ。合計60個にする非負整数の組をすべて求めよう。箱の在庫に上限はなく、一方を0箱にしてもよい。

解答・解説

$6x+9y=60$ を3で割り $2x+3y=20$ 。一つの解は (10,0) なので一般解は $x=10+3t,\ y=-2t$ 。非負条件から $t\ge-10/3$ かつ $t\le0$ 。整数 t は −3, −2, −1, 0 で、(x,y)=(1,6),(4,4),(7,2),(10,0) の4組です。たとえば (1,6) は6×1+9×6=60個。両方の箱を必ず使うなら (10,0) を除いた3組になります。

このレッスンの一般解の公式は a、b が正の場合に示しました。片方が0なら、たとえば a=0、b≠0 では by=c の整数解を調べ、成立時には x は任意の整数です。両方0なら c=0 のときすべての整数の組が解で、c≠0 のとき解はありません。分母に最大公約数を置く公式を無条件に使わないようにします。

練習：解の存在・全解・制約を分けよう

練習問題

391と299の最大公約数を互除法で求め、それを391と299の整数の一次結合で表そう。
解答・解説
391=299+92、299=3×92+23、92=4×23 より最大公約数は23。逆代入して23=299−3(391−299)=−3×391+4×299。検算は−1173+1196=23です。
18x+30y=7は整数解をもつか。理由も答えよう。
解答・解説
最大公約数は6。左辺は整数 x、y に対して6の倍数ですが、7は6の倍数ではないため整数解をもちません。
14x+21y=35のすべての整数解を求めよう。
解答・解説
7で割って $2x+3y=5$ 。一つの解は (1,1)。2と3は互いに素なので全解は $x=1+3t,\ y=1-2t\ (t\in\mathbb Z)$ 。元の式への代入で $14+42t+21-42t=35$ と確かめられます。
7x+11y=200を満たす非負整数の組 (x,y) をすべて求めよう。
ヒント
一つの解は (5,15)。一般解に非負条件を課します。
解答・解説
7と11は互いに素なので $x=5+11t,\ y=15-7t$ 。非負条件は $-5/11\le t\le15/7$ 。整数 t は0,1,2で、(5,15),(16,8),(27,1) の3組です。それぞれ35+165、112+88、189+11で200になります。

理解の確認

問1. 互除法で余りが0になったとき、最大公約数はどれか。

問2. 24x+36y=c が整数解をもつ c は次のうちどれか。

問3. 6x+9y=3のすべての整数解はどれか。t は任意の整数とする。

問4. 5x+8y=1について正しい記述はどれか。

最大公約数を互除法で求め、右辺を割り切るか判定する。
解が存在すれば逆代入し、必要に応じて定数倍して一つの解を作る。
係数を最大公約数で割った幅を使い、整数パラメータで全解を表す。
個数や正負の制約は最後に不等式として課し、元の式でも検算する。

📝 メモこの端末のみに保存

メモ欄はページ読み込み後に使えるようになります。