题目

数论：证明：二元一次不定方程ax+by=N,的非负整数解为[N/ab]或[N/ab]+1,其中a>0,b>0,(a,b)=1.

提问时间：2021-03-16

答案

若方程组无解,那么N=ab,则N-a,N-2a,……,N-ab都是非负整数且模b两两不同余,所以其中必有一个能被b整除,方程就有解).所以下面假定方程组至少存在一组解(x0,y0)的情况.
于是原方程化成ax+by=N=ax0+by0.这就是a(x-x0)=b(y0-y)
所以a|b(y0-y).又a b互质,所以必有a|(y0-y).所以存在整数k使得y0-y=ak.进而x-x0=bk.于是得x=x0+bk,y=y0-ak.这也是方程的通解形式
现在要求x0+bk>=0,y0-ak>=0.即-x0/b