※ 引述《karfeon (卡非)》之銘言：
: 標題: [代數] 2題數論證明
: 時間: Tue Sep 11 11:39:27 2012
:
:
: 2.
:
: 任2個大於1且互質的正整數a,b ，證明
:
: (1) ab-a-b 不能寫成ax+by的形式，其中x,y為非負整數
:
: (2)任意比ax-a-b大的整數都可以寫成ax+by的形式，其中x,y為非負整數
:
: //如：a=3 b=5 則 7 無法寫成 ax+by ，但8=3+5 9=3x3 10=5x2 ...
:
http://en.wikipedia.org/wiki/Coin_problem
簡單地說就是如果我們手頭上有幾種互質面額的硬幣，
我們想問一個問題：可以用這些硬幣湊不出來的金額的最大值是多少？
這個最大值顯然是存在的，所以這個問題是有意義的。
以這題為例，就是考慮只有兩種面額的情況。
(1)應該隨便寫一寫就解決了，一般都不會有什麼問題。
(2)的話，我們從一個比較直觀的路線來做看看，把事情弄得比較簡單一點。
令n是一個比 ab-a-b 大的數。
我們的想法很簡單，就是先拿出一個 a元硬幣出來，檢驗 n- a*1是不是 b的倍數。
不是的話，再多拿一個 a 元硬幣出來，看 n-a*2 是不是b的倍數。
以此類推。
另一方面還要考慮到：我們不能拿太多 a 元硬幣出來，
要是拿太多，導致 n-a * k變負的，就掛了。
把上面這個檢驗的動作，用同餘的符號表示，
我們即是在考慮下面這個等價的事情：
_
find x such that ax = n (mod b)
白話點的說法就是我們希望找到一個 x ，使得 ax 跟 n 是同餘 ( mod b)。
同時在這樣的系統下來看，x一個很自然的上限就浮現出來了： b-1。
這件事一定辦的到的原因是因為 a跟b互質，
所以 0,a,2a,...,(b-1)a 一定兩兩不同餘 mod b 。
到目前為止，我們已經保證可以找到一個 x，
滿足 0 小於等於 x 小於等於 b-1，使得 b 是 n-ax 的因數；
因此 n-ax=by for some integer y。
接下來只剩下一個問題：y是不是非負，如果我們可以說明y非負，就解決了。
此時 n 的條件（以及x的上限）就派上用場了。
by=n-ax > ab-a-b+1-a(b-1)= -b + 1
=
所以 y 是非負的。
用同樣的思維，可以類推搞定：
假設a,b,c為三個兩兩互質的數，那麼
任意比2abc-ab-bc-ac 大的整數都可以寫成abx+bcy+acz的形式，其中x,y,z為非負整數。
就按照同樣的思路，途中運用一次降個數的步驟，順順地寫下去就可以出來了。
可參考http://tinyurl.com/99rcwa2
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.70.174.246
※ 編輯: Eeon 來自: 219.70.174.114 (03/22 04:17)