→ inwa :thx a lot 03/21 20:59
※ 引述《inwa (話太多)》之銘言：
: 請問若a、b為互質正整數
: 如何證明ab-a-b不可能寫成ax+by(其中x、y為非負整數)
: 且ab-a-b+k(k為任意正整數)可以寫成ax+by(其中x、y為非負整數)
: 感激不盡
第一部分：a,b 互質→ab-a-b≠ax+by for some x>=0, y>=0
proof:
假設在a,b 互質的前提下，ab-a-b＝ax+by for some x>=0, y>=0
也就是ab = a(x+1) + b(y+1)
那麼 a(b-x-1) = b(y+1)
因為a,b互質，所以
(1) a|(y+1)
(2) b|(b-x-1) → b|[b-(x+1)] → b|(x+1)
把y+1表示成am，x+1表示成bn
則ab = a(x+1) + b(y+1) = abn + abm = ab(m + n)
→←，因為 m>=1，n>=1，ab≠2ab <= ab(m + n)
故得證~
第二部分我還沒想到0x0
有想到的話會再補上0w0
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.160.235.78
※ 編輯: vod800403 來自: 118.160.235.78 (03/21 02:16)