一次不定方程式の整数解のうちの一組を求める際に、ユークリッドの互除法を利用するのはなぜか？

色々検索してみましたが、やはりさっぱり理解できなかったため、お聞きしたいです。

タイトルの通りなのですが、例えば「11x+19y=1という等式を満たす整数x,yの組を一つ求めよ」という問題があったとき、その解説を見てもなぜそうするのかを理解できませんでした。そもそも何をやっているのか本当に理解していないからなのかもしれませんが……。どうかご教授願います。

質問者からの補足コメント

• ご指摘を受け、どこが分からないか具体的に自分自身が理解できておらず、質問の説明不足を痛感したため補足いたします。
  
  （模範解答）
  19=11・1+8 移項すると8=19-11・1
  11=8・1+3 移項すると3=11-8・1
  8=3・2+2 移項すると2=8-3・2
  3=2・1+1 移項すると1=3-2・1
  よって 1=3-2・1=3-(8-3・2)・1
  =8・(-1)+3・3=8・(-1)+(11-8・1)・3
  =11・3+8・(-4)=11・3+(19-11・1)・(-4)
  =11・7+19・(-4)
  すなわち11・7+19・(-4)=1……①
  ゆえに、求める整数x,yの組の一つはx=7,y=-4
  
  計算作業としては何をしているのか分かっているのでしょうが、なぜこのやり方で答えの一つが出てくるのかがよく分かっていないのだと思います。

    補足日時：2017/03/17 23:17

• 認識できていません。なぜこの問題でそれを使ったのか理解した上で使えていないのだと思います。無理矢理よく分からない道具を使わされている感じです。
  模範解答以外のやり方で、係数を減らす為に互除法を利用して、模範解答で導き出したもの（移項していない方）を利用して
  11x+19y=1
  ⇔11x+(11+8)y=1
  ⇔11(x+y)+8y=1
  ここでx+y=p……①とおいて
  11p+8y=1
  ⇔(8・1+3)p+8y=1
  ⇔3p+8(y+p)=1
  ここでy+p=q……②とおいて
  3p+8q=1
  これを満たす整数解の一組はp=-5,q=2
  よってその時のy,xは
  y=q-p=2-(-5)=7(∵②）
  x=p-y=-5-7=-12(∵①)
  よって求める整数解のうち一組は(x,y)=(-12,7)
  という風にもできるようですが、模範解答と違う値が出る理由もよく分かりません……。

  No.1の回答に寄せられた補足コメントです。 補足日時：2017/03/17 23:18

• 係数が比較的少ないときなら、工夫をせずとも少し調べれば簡単に出せますね。互いに素だから、互除法を使えば必ず1は出てくる。1=の形にしたいから、余り１になるまで互除法の計算をして、それを元の係数の形に戻していっているのですね。
  ax+by=d は左辺が(a,b)の最大公約数の倍数になってるから、dも(a,b)の最大公約数の倍数である。というのは理解できましたし、ユークリッドの互除法が最大公約数を見つけやすくするためのものだということも分かるのですが……その二つをつながりが理解できていないです。

  No.2の回答に寄せられた補足コメントです。 補足日時：2017/03/17 23:27

No.3 ベストアンサー 回答者： syotao 回答日時： 2017/03/18 22:20

う～ん、整数問題むずかしいよね。

互除法で最大公約数を求めるのを知っているのならば、こう考えたらどうですか？
互除法で計算してると、最後はどこかで割り切れますね。そしてその割り切れる式の
１つ前の式の計算で出る余りが最大公約数になるということだから、２数が互いに素ならば
最大公約数はもともと1なので、この割り切れる式の前の式の余りはかならず1でなくちゃいけない。
ということは、互いに素な２数の互除法の計算ではかならず余りが1になる式が出てくるということです。
だからこの式を1＝・・・と書きなおして逆算すれば、1＝２数の整数倍の和として表わせるので、
整数解の1つが互除法によって求められるということです。

それと、11x+19y=1は一般の整数解としてｘ＝7＋19ｔ、ｙ＝－4－11ｔ（ｔは任意の整数）となるのです。
つまり、解は無数にあります。
ここでｔ＝0とすれば互除法で求めた整数解ｘ＝7、ｙ＝－4が、またｔ＝－1とおけば
主さんが出したｘ＝－12、ｙ＝7　が出てきます。

この回答へのお礼

先の問題を解いていて、具体的な整数解をとにかく一組出せれば必ず一般式を求められるのだな、つまり一次不定方程式を解くことができるのだなとようやく理解できました。
互除法を用いるやり方はsyotaoさんの説明してくださったように捉えておこうと思います。この度は回答をありがとうございました。

お礼日時：2017/03/19 04:02

No.2 回答者： t_fumiaki 回答日時： 2017/03/17 06:04

互除法を使わなくてはイケナイ訳じゃあ無い。

11を何倍かした物を19で割って1余る数を求めれば良いわけで、x=7,y=4の場合にそうなる事は少し試すと解る。だから特殊解はx=7,y=-4。

これを機械的にする。
余りが1をなるまで繰り返す。理由は1=の形にしたいから・・。

19=11×1 + 8
11=8×1 + 3
8=3×2 + 2
3=2×1 + 1・・・・+1が出てきたから、ここまで

上の式を余り= ○　に変形しながら、下から上に辿る

①1=3 - 2×1
②2=8 - 3×2
③3=11 - 8×1
④8=19 - 11×1 この最後の式が11×○ + 19×□の形になる。

①の2に②を代入
1=3 - (8-3×2)×1 = 3-8+3×2 = 3×3 - 8

この右辺の3に③を代入
1=(11 - 8×1)×3 - 8 =11×3 -8×4

この右辺の8に④を代入
1=11×3 -(19 - 11×1)×4 = 11×7 + 19×(-4)

1=11×○ + 19×□　の形になった。

ユークリッドの互除法は最大公約数を求める時に便利。
ax+by=d を解くというのは、左辺が(a,b)の最大公約数の倍数になってるから、dも(a,b)の最大公約数の倍数。

最大公約数をmとすれば
a(mx)+b(my)=d と書ける。

No.1 回答者： Tacosan 回答日時： 2017/03/17 03:15

どのような解説のどこが理解できなかったのかまったくわからんのだけど....

「互除法を使わなければならない」などということはない, ということは認識できていますか?