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

Question

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

Answer 1

若方程组无解，那么N<ab。命题得证(因为若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<=k<=y0/a。这个区间内的k共有[y0/a+x0/b]或者[y0/a+x0/b]+1个。也就是[N/ab]或[N/ab]+1个。所以相应的，方程组的解也有[N/ab]或[N/ab]+1组本回答被提问者采纳