【問題】數論入門題

[maxravel 10]

請教一題

若a>0,b>0,且(a,b)=1,試證方程式

ax+by=n之非負整數解之個數為[n/ab]或[n/ab]+1

其中[a]為最大之整數,且不超過a者

謝謝各位

不吝賜教

[weiye 10]

請教一題

若a>0,b>0,且(a,b)=1,試證方程式

ax+by=1之非負整數解之個數為[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 個

[maxravel 10]

感恩謝謝