質問: a x+b y=c(a、bが互いに素)の不定方程式を解く際に... ■考えている内容や答え a x+b y=c(a、bが互いに素)の不定方程式を解く際に、係数a,bが大きい場合、特殊解を求めるためにユークリッド互除法を使用すると思うのですが、なぜユークリッド互除法で考えられるのか疑問に思いました。 そこで、自分なりに考えてみた結果以下のようになったのですが、この認識はは誤りでしょうか。 ■特に不安な点や、確認したいこと 〈自分の考え〉 a、bは互いに素であるから、最大公約数は1である。したがって、ユークリッド互除法を用いて計算を進めていくと余りが1になる式ができる。(←a、bが互いに素なら必ず余りが1になる式ができるのか自信がありません) 代入していくことで a×(特殊解)+b×(特殊解)=1の式ができるので、この式の両辺をc倍した式と与えられた不定方程式からcを消去してa×=b yの形に持ち込める。
回答: その考え方であっています。 >a、bが互いに素なら必ず余りが1になる式ができるのか自信がありません ユークリッドの互除法はもともと最大公約数を求めるアルゴリズムで a÷b=q余りrの時 「aとbの最大公約数」は「bとrの最大公約数」 を利用しています。 最終的に2つの数が公約数nを持つと、元々のaとbも公約数nを持つことになるので、n≠1だと矛盾します。