不定方程

变数个数多于方程个数，且变数取整数值的方程（或方程组）称为不定方程（或不定方程组）

1.不定方程$a\times x+b\times y=c,a,b,c$是整数，且不为零
求证：
$\qquad a\times x+b\times y=c$
有整数解的充分必要条件是$gcd(a,b)|c$
证明：
必要性：
有整数解时，满足
$gcd(a,b)\times (a'\times x+b'\times y)=c$,得证
充分性：
$a=gcd(a,b)\times a',b=gcd(a,b)\times b',c=gcd(a,c)\times c'$
$a',b'$互质
等式同除gcd(a,b)
$a'\times x+b'\times y=c'$
由贝祖定理可知，必有整数解满足$a'\times x_0+b'\times y_0=1$
所以有整数解满足
$a'\times (c'\times x_0)+b'\times (c'\times y_0)=c'$
所以有整数解$x=(c'\times x_0),y=(c'\times y_0)$,满足题目条件
充分性得证

2.不定方程$a\times x+b\times y=c$的一组解为$x_0,y_0$
则此不定方程的所有解为
$x=x_0+\frac{b}{gcd(a,b)}\times t$
$y=y_0-\frac{a}{gcd(a,b)}\times t$
$t\in Z$
证明:
易知，上述的给出的x,y对于所有的整数t都满足不定方程
设不定方程的一组普遍解$x_1,y_1$
有：
$a\times x_1+b\times y_1=c=a\times x_0+b\times y_0$
$a\times (x_1-x_0)=-b\times (y_1-y_0)$
同除$gcd(a,b)$
$\frac{a}{gcd(a,b)}\times (x_1-x_0)=-\frac{b}{gcd(a,b)}\times (y_1-y_0)$
因为，$gcd(\frac{a}{gcd(a,b)},\frac{b}{gcd(a,b)})=1$
所以，必然存在整数t使得
$t\times \frac{a}{gcd(a,b)}=-(y_1-y_0)$
$t\times \frac{b}{gcd(a,b)}=(x_1-x_0)$
可知每一个解都满足
$x_1=(x_0+t\times \frac{b}{gcd(a,b)})$
$y_1=(y_0-t\times \frac{a}{gcd(a,b)})$
得证