引用:
請教一題
若a>0,b>0,且(a,b)=1,試證方程式
ax+by=n之非負整數解之個數為[n/ab]或[n/ab]+1
其中[a]為最大之整數,且不超過a者
謝謝各位
不吝賜教
因為 (a,b)=1，故必存在整數 h,k ，使得 a h+b k=n
因此 (x,y) 通解為 (h+bt, k-at) ，其中 t 為任意整數
題目要求 (x,y) 為非負整數解，由 h+bt≧0, k-at≧0
可得 t 的範圍為 -h/b ≦ t ≦ k/a
畫在數線上，滿足此條件的 t 的線段長度為 k/a - (-h/b)= (k b+h a)/ab = n/ab
如果 n 不是 ab 的倍數，則在此線段上的整數點至多有 [n/ab]
如果 n 是 ab 的倍數，則在此線段上的整數點至多有 [n/ab] +1
所以在此線段上的整數點(整數 t 的個數)至多有 [n/ab] 或 [n/ab]+1 個
原討論串：
http://www.student.tw/db/showthread.php?t=135207
