1次不定方程式 $ax+by=1$ の整数解を求める方法を紹介します．
$x, y$ に関する $2$ 元 $1$ 次不定方程式 $ax+by=1$ の整数解を求めます．ここで，$a,b$ はともに整数であるとします．たとえば， $$3x+2y=1$$ の整数解を考えてみると，$(x,y)=(1,-1),(-1,2)$ などが見つかります．しかし，解はこれだけではありません．この方程式の一般解 (すべての解) は，$(x,y)=(2t+1,-3t-1)$ となります．ただし，$t$ は任意の整数です．一般に，$1$ 次不定方程式 $ax+by=1$ の整数解は存在するならば無数にあります．存在するならば，と断ったのは解がない場合があるからです．たとえば， $$2x+4y=1$$ は整数解をもちません．これは左辺がつねに $2$ の倍数となり，右辺の $1$ は $2$ の倍数でないことからわかります．一般につぎの事実が成り立ちます．
$1$ 次不定方程式の解の存在条件： $a,b$ を整数とするとき，つぎが成り立つ．
$x, y$ の方程式 $ax+by=1$ が整数解をもつ ⇔ $a, b$ は互いに素
$a$ と $b$ が互いに素のときに，一般解を求める方法を紹介します．
$2$ 元 $1$ 次不定方程式 $ax+by=1$ のすべての解を求めるために，まずひとつなんでもよいので解を見つけます．実はひとつでも解がみつかれば，その解を用いて芋づる式に他のすべての解をみつけることができます．不定方程式 $5x+7y=1$ を例として説明します．まず，この方程式の整数解をがんばって探します．たとえば，$(x,y)=(3,-2)$ が見つかります． $$5x+7y=1 \cdots (1)$$ $$5・3+7(-2)=1 \cdots (2)$$ ($1$) 式から ($2$) 式を辺々引いて， $$5(x-3)+7(y+2)=0$$ を得ます．これより，$5(x-3)=-7(y+2)$ となり，$5$ と $7$ は互いに素なので，$x-3$ は $7$ の倍数, $y+2$ は $5$ の倍数であることがわかります．整数 $t$ を用いて，$x-3=7t$ とすると，$y+2=-5t$ とかけます．したがって，$(x,y)=(7t+3,-5t-2)$ が一般解となります．
このように，ひとつの解をみつけることができれば，それを用いて一般解を求めることができます．
直感で解を見つけることが難しい場合は，ユークリッドの互除法を用いて解くことができます． $$162x+125y=1$$ を解いてみましょう．この方程式を眺めてひとつの解を暗算で見つけるのはなかなか難しいでしょう．そこで，$x, y$ の係数 $162$ と $125$ に注目します．まず，$162$ を $125$ で割ります． $$162=125\cdot1+37$$ 次に，$125$ を余りである $37$ で割ります． $$125=37\cdot3+14$$ 同様に，$37$ を余りである $14$ で割ります． $$37=14\cdot2+9$$ この操作を余りが $1$ になるまで繰り返します．(最初の $2$ つの係数 $162$ と $125$ は互いに素なので，この操作を繰り返すといずれは余りが必ず $1$ になります．) $$14=9\cdot1+5$$ $$9=5\cdot1+4$$ $$5=4\cdot1+1$$ 余りが $1$ になったところで，今度は先ほどの計算を逆にたどります． $1=5-4\cdot1$ に $4=9-5\cdot1$ を代入して，$1=5\cdot2-9$ です． $1=5\cdot2-9$ に $5=14-9\cdot1$ を代入して，$1=14\cdot2-9\cdot3$ です． $1=14\cdot2-9\cdot3$ に $9=37-14\cdot2$ を代入して，$1=14\cdot 8-37 \cdot 3$ です． $1=14 \cdot 8-37 \cdot 3$ に $14=125-37 \cdot 3$ を代入して，$1=125 \cdot 8-37 \cdot 27$ です． $1=125 \cdot 8-37 \cdot 27$ に $37=162-125 \cdot 1$ を代入して，$1=125 \cdot 35-162 \cdot 27$ です． つまり，つぎつぎに割り算をしていって，最終的に余りが $1$ になったところで，今度は逆にたどって，つぎつぎに式を代入していくことで，$162$ と $125$ の線形和で $1$ を表現できます． よって，$162x+125y=1$ のひとつの解は $(x，y)=(-27，35)$ であることがわかります．あとは先ほどと同じ方法で，一般解を求めることができます．
逆にたどって代入していく操作が少々面倒ですが，この方法はどのような $2$ 元 $1$ 次不定方程式が与えられても原理的には一般解を求めることができるので，強力です．
ユークリッドの互除法は単純な繰り返し作業なので，人間よりもコンピューターの方が得意ですね．
