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