求整數解的方法?

Question

想要請教各位關於解整數解的"尤拉法"例如求 125x+2164y=826 的整數解請用這一個說明(當然用其他的也可以)重點是讓我了解這一個解法 謝謝

Answer 1

Euler法說穿了就是用輾轉相除法不斷地把係數變小，而變得好解。125x=826-2164y，這就是說826-2164y是125的倍數125 | 826-2164y → 125 | (826-6*125)-(2164-17*125)y → 125 | 76-39y令76-39y=125a同理，39 | 125a-76 → 39 |  8a-37，令8a-37=39b8 | 39b+37 → 8 |  7b+5取b=5，則a=(39b+37)/8=29，y=(76-125a)/39=-91，x=(826-2164y)/125=1582那麼x=1582，y=-91就是一組特解，通解是x=1582+2164t，y=-91-125t，t為整數通解t的係數就是把當初x,y的係數顛倒過來，並且若當初x,y係數同號，則通解的t需異號；若當初x,y係數異號，則通解的t需同號；也就是代入後，t會完全消掉就是了。

Answer 2

解整數解的"尤拉法"例如求 125x+2164y=826 的整數解因為125x+2164y=826 所以 x = (826-2164y)/125 = 6-18y + (86y+76)/125令 z = (86y+76)/125  所以 y = (125z-76)/86 = z-1+(39z+10)/86 令 u = (39z+10)/86所以 z = (86u-10)/39 = 2u +(8u-10)/39因為z是整數,所以取 u = 11所以 z = 22+2 = 24所以 y = z-1+u = 23+11 = 34所以 x = 6-18y+(86y+76)/125 = 6-18y+z = -582所以 x = -582 , y = 34