[其他] 方程式求整數解

看板Math作者 (抉擇)時間3年前 (2020/09/12 15:28), 3年前編輯推噓2(2推 0噓 14→)
留言16則, 3人參與, 3年前最新討論串1/1
22X + 22Y + 5Z = 1685100 X、Y、Z皆需為整數（且須大於0，不得為負數） （X跟Y可相同或不同） 請問有可能嗎？ 還是不可能三個都整數？ 感謝各位高手解答 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.140.75.107 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1599895736.A.E6C.html
→
09/12 15:59, 3年前 , 1F
可以 直接考慮22x+5y=1685100的整數解即可
09/12 15:59, 1F
→
09/12 16:01, 3年前 , 2F
由輾轉相除法可得22(-2)+5*9=1 所以
09/12 16:01, 2F
→
09/12 16:03, 3年前 , 3F
22*(-3370200)+5*15165900=1685100
09/12 16:03, 3F
→
09/12 16:04, 3年前 , 4F
你再隨便找X,Y使得X+Y=-3370200
09/12 16:04, 4F
→
09/12 16:15, 3年前 , 5F
更進一步 我們可以證明 a_1*x_1+a_2*x_2+...a_n*x_n
09/12 16:15, 5F
→
09/12 16:16, 3年前 , 6F
=N 有整數解 若且唯若 gcd(a_1,...,a_n)|N
09/12 16:16, 6F
→
09/12 16:22, 3年前 , 7F
這是因為gcd(gcd(...gcd(gcd(a_1,a_2),a_3)..),a_n)
09/12 16:22, 7F
→
09/12 16:22, 3年前 , 8F
=gcd(a_1,...,a_n) 然後一直用輾轉相除法就可以了
09/12 16:22, 8F
抱歉忘記說明 我是需要三個都是正數，不能負數 是否有解？ 謝謝！ ※ 編輯: LastLife (223.140.75.107 臺灣), 09/12/2020 16:54:37
→
09/12 17:29, 3年前 , 9F
有 考慮 22x+5y=137 的解就可以了 如22*6+5*1=137
09/12 17:29, 9F
→
09/12 19:53, 3年前 , 10F
更進一步 我們可以證明 "讓a,b,n為正整數 若
09/12 19:53, 10F
→
09/12 19:56, 3年前 , 11F
gcd(a,b)|n 且若ax+by=n的x截距大於等於b(或等價地
09/12 19:56, 11F
→
09/12 19:57, 3年前 , 12F
y截距大於等於a 則ax+by=n必有非負整數解
09/12 19:57, 12F
→
09/12 19:59, 3年前 , 13F
特別地 若是嚴格大於的話 則ax+by=n必有正整數解"
09/12 19:59, 13F
推
09/13 06:56, 3年前 , 14F
22(76595-5k) + 5(2+22k) = 1685100, k=0,...,15318
09/13 06:56, 14F
→
09/13 06:58, 3年前 , 15F
再討論(x+y)=(76595-5k), z=(2+22k)?
09/13 06:58, 15F
推
09/14 15:43, 3年前 , 16F
38295,38295,24
09/14 15:43, 16F
‣ 更多 LastLife 的文章
文章代碼(AID): #1VN7Yuvi (Math)