發新話題
打印

二元一次不定方程式非負整數解的個數,證明題

二元一次不定方程式非負整數解的個數,證明題

引用:
請教一題
若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

多喝水。

TOP

發新話題