質問＜１８８７＞２００４／８／２３
from=オレンジ
「１次不定方程式」

2176x+629y=cを満たす整数x,yが存在するための整数cの条件を求めよ。
ついで、整数cがその条件を満たすとき、整数x,yを決定せよ。
です。お願いします。

★希望★完全解答★

お便り２００４／８／２６
from=下野哲史

2176 と 629 の最大公約数は
ユークリッド互除法を用いて求めると
17 となる。(途中式省略)

よって、c は 17 の倍数である。
ここで c=17k とおく。
与式は 2176x+629y=17k 
両辺を 17 で割って 128x+37y=k

k=1 のときを考える。
128÷37=3…17 → 128=37×3+17 → 17=128-37×3
37÷17=2…3 → 37=2×17+3 → 3=37-17×2
17÷3=5…2 → 17=5×3+2 →2=17-5×3
3÷2=1…1 → 3=2×1+1 → 37-17×2=(17-5×3)×1+1
→37- 17×3 + 5×3=1 →37- 17×3 + 5(37-17×2)=1
→37×6 - 17×13=1 → 37×6 - (128-37×3)×13=1
→ 128×(-13) + 37×45=1
よって、(x,y)=(-13,45) が解の１つ。
128x+37y=1 は直線であるから、傾きを考えれば
(x,y)=(-13+37n , 45-128n) である。

128x+37y=1 の整数解が
(x,y)=(-13+37n , 45-128n) であるということは、
両辺を K 倍して 128×kx + 37×ky = k より、
128x+37y=k の整数解は
(x,y)=( (-13+37n)k , (45-128n)k )