ユークリッドの互除法
着眼点a=bq+r なら \gcd(a,b)=\gcd(b,r)。割り算を余りが0になるまで続け、最後の割る数が最大公約数。
a=bq+r\ \Longrightarrow\ \gcd(a,b)=\gcd(b,r)
計算の過程を逆にたどると、ax+by=\gcd(a,b) の整数解が1組見つかる（不定方程式の特殊解）。
例題
1
391 と 299 の最大公約数を求めよ。
解答
391=299\cdot1+92
299=92\cdot3+23
92=23\cdot4
割り切れたので最大公約数は 23。
（検算：391=23\cdot17,\ 299=23\cdot13）
答 23
299=92\cdot3+23
92=23\cdot4
割り切れたので最大公約数は 23。
（検算：391=23\cdot17,\ 299=23\cdot13）
答 23
2
互除法を用いて、37x+13y=1 を満たす整数の組 (x,y) を1つ求めよ。
解答
37=13\cdot2+11、13=11\cdot1+2、11=2\cdot5+1。
逆にたどる：
1=11-2\cdot5
\ \ =11-(13-11)\cdot5=11\cdot6-13\cdot5
\ \ =(37-13\cdot2)\cdot6-13\cdot5=37\cdot6-13\cdot17。
答 (x,y)=(6,-17)（検算：222-221=1）
逆にたどる：
1=11-2\cdot5
\ \ =11-(13-11)\cdot5=11\cdot6-13\cdot5
\ \ =(37-13\cdot2)\cdot6-13\cdot5=37\cdot6-13\cdot17。
答 (x,y)=(6,-17)（検算：222-221=1）
ポイント係数が小さいときは互除法を使わず、x=1,2,3,\dots と代入して見つける方が速い。