一次不定方程式の整数解
名前がないけど重要な定理
$ ^{\forall a,b\in\Z}\left[^{\exist(x,y)\in\Z\times\Z}[a\,x+b\,y=c]\Leftrightarrow\,^{\exist k\in\Z}[c=k\gcd(a,b)]\right]
一次不定方程式が整数解を持つ$ \Leftrightarrow$ cが$ \gcd(a,b)の倍数
証明
補題
$ ^{\forall a,b\in\Z}\left[^{\exist(x,y)\in\Z\times\Z}[a\,x+b\,y=1]\Leftrightarrow\,1=\gcd(a,b)\right]
一次不定方程式$ a\,x+b\,y=1が整数解を持つ$ \Leftrightarrow$ a,bが互いに素
証明
$ \Rightarrowの証明
$ \gcd(a,b)=gとすると$ a\,x+b\,y\overset g\equiv 0
$ a\overset g\equiv0,\ b\overset g\equiv0なので
$ \Leftarrowの証明
$ a\,x+b\,y=1
$ a\,x=-b\,y+1
$ \gcd(a,b)=1より$ a,2a,3a,\cdots,(b-1)aの中に$ bで割った余りが$ 1のものが存在するため
$ a,2a,3a,\cdots,(b-1)aで割った余りはすべて異なるため
全体の証明
$ \gcd(a,b)=gとすると$ \begin{cases}a=k_a\,g\\b=k_b\,g\end{cases}\quad(\gcd(k_a,k_b)=1)と置ける
補題より
$ k_a\,x+k_b\,y=1
$ a\,x+b\,y=k_a\,g\,x+k_b\,g\,y=g
$ a\,k\,x+b\,k\,y=k\,g
$ \therefore a\,x'+b\,y'=c\Leftrightarrow c=kg