29x+13y=1の整数解を1組だけ見つけよう。 互除法 の使い方がカギになるよ。

x，yの係数に着目しよう。29と13で、これらの数は 互いに素 だよね。つまり、 29と13の最大公約数は1 になる。最大公約数が1ということは、29と13で互除法を使うと、 必ず最後に「余り1」があらわれる んだ。

29＝13×2+3
13＝3×4 +1
x，yの係数について 「余りが1」 となるまで、互除法を使おう。

なぜ、「余りが1」となるまで互除法を使うかというと、最終的な解答のゴールを次のようにイメージしているからなんだ。
29×□+13×○＝ 1
この式にあてはまる整数が1組見つけたいわけだから、「=1」の式をつくるんだね。

29，13について互除法を使うことで、
13＝3×4 +1
⇔13-3×4= 1
＝1 の部分が共通した式がつくれたね。

でも、「13-3×4=1」ではまだ、ゴールである「29×□+13×○＝1」の式には遠いよね。そこで、
13- 3×4 =1……①
3×4 に着目して式変形をしていこう。互除法の途中式 29＝13×2+3⇔3＝29-13×2 を、上の式①の 3 に代入すると、
13- (29-13×2) ×4=1
⇔29× (-4) +13× 9 ＝1
となるよ。