2元1次不定方程式の整数解
\[ ax+by=c \] \(a,b\)は互いに素とする。
解を1つ見つける。
その解を\(\left(x,y\right)=\left(x_{0},y_{0}\right)\)とすると元の不定方程式は\(a\left(x-x_{0}\right)+b\left(y-y_{0}\right)=0\)となる。
\(t\in\mathbb{Z}\)として\(x-x_{0}=bt,y-y_{0}=-at\)が一般解となる。

\(a,b\in\mathbb{Z}\)として、2元1次不定方程式
\[ ax+by=\gcd\left(a,b\right) \] を満たす整数解\(x,y\in\mathbb{Z}\)を1つ求めるには次のようにすればよい。
\(a_{0}=a,b_{0}=b\)として、\(r_{n}\in\left\{ 0,1,\cdots,q_{n}-1\right\} ,a_{n+1}=b_{n},b_{n+1}=r_{n}\)とすると、
\[ a_{0}=q_{0}b_{0}+r_{0} \] \[ a_{1}=q_{1}b_{1}+r_{1} \] \[ a_{2}=q_{2}b_{2}+r_{2} \] \[ \vdots \] \[ a_{N-1}=q_{N-1}b_{N-1}+r_{N-1} \] \[ a_{N}=q_{N}b_{N}+r_{N} \] \begin{align*} a_{N+1} & =q_{N+1}b_{N+1}+r_{N+1}\\ & =q_{N+1}b_{N+1} \end{align*} となり、最後に余り\(r_{N+1}\)が0になる。
このとき、ユークリッドの互除法より、
\begin{align*} \gcd\left(a,b\right) & =\gcd\left(a_{0},b_{0}\right)\\ & =\gcd\left(a_{1},b_{1}\right)\\ & =\cdots\\ & =\gcd\left(a_{N+1},b_{N+1}\right)\\ & =\gcd\left(q_{N+1}b_{N+1},b_{N+1}\right)\cmt{\because a_{N+1}=q_{N+1}b_{N+1}}\\ & =b_{N+1}\\ & =r_{N}\\ & =a_{N}-q_{N}b_{N}\cmt{\because a_{N}=q_{N}b_{N}+r_{N}}\\ & =b_{N-1}-q_{N}r_{N-1}\cmt{\because a_{n+1}=b_{n},b_{n+1}=r_{n}}\\ & =b_{N-1}-q_{N}\left(a_{N-1}-q_{N-1}b_{N-1}\right)\cmt{\because a_{N}=q_{N}b_{N}+r_{N}}\\ & =-q_{N}a_{N-1}+\left(1+q_{N}q_{N-1}\right)b_{N-1}\\ & =-q_{N}b_{N-2}+\left(1+q_{N}q_{N-1}\right)r_{N-2}\cmt{\because a_{n+1}=b_{n},b_{n+1}=r_{n}}\\ & =-q_{N}b_{N-2}+\left(1+q_{N}q_{N-1}\right)\left(a_{N-2}-q_{N-2}b_{N-2}\right)\cmt{\because a_{N}=q_{N}b_{N}+r_{N}}\\ & =\left(1+q_{N}q_{N-1}\right)a_{N-2}-\left(q_{N}+q_{N-2}+q_{N}q_{N-1}q_{N-2}\right)b_{N-2}\\ & =\left(1+q_{N}q_{N-1}\right)b_{N-3}-\left(q_{N}+q_{N-2}+q_{N}q_{N-1}q_{N-2}\right)r_{N-3}\cmt{\because a_{n+1}=b_{n},b_{n+1}=r_{n}}\\ & =\left(1+q_{N}q_{N-1}\right)b_{N-3}-\left(q_{N}+q_{N-2}+q_{N}q_{N-1}q_{N-2}\right)\left(a_{N-3}-q_{N-3}b_{N-3}\right)\cmt{\because a_{N}=q_{N}b_{N}+r_{N}}\\ & =-\left(q_{N}+q_{N-2}+q_{N}q_{N-1}q_{N-2}\right)a_{N-3}+\left(1+q_{N}q_{N-1}+q_{N}q_{N-3}+q_{N-2}q_{N-3}+q_{N}q_{N-1}q_{N-2}q_{N-3}\right)b_{N-3}\\ & =\cdots \end{align*} となり、計算を続けると、
\begin{align*} \gcd\left(a,b\right) & =x\left(q_{1},q_{2},\cdots,q_{N}\right)a_{0}+y\left(q_{0},q_{1},q_{2},\cdots,q_{N}\right)b_{0}\\ & =x\left(q_{1},q_{2},\cdots,q_{N}\right)a+y\left(q_{0},q_{1},q_{2},\cdots,q_{N}\right)b \end{align*} となるので、\(x,y\)を求めることができる。

\(a\)と\(b\)は互いに素な整数とする。
\(ax+by=1\)のタイプの不定方程式は\(a\)と\(b\)に対しユークリッドの互除法を使うと解が1つ求まる。