ログイン 新規登録

お使いのブラウザ(Internet Explorer)では閲覧、ログイン、質問の作成や回答などに不具合が生じることがございます。
誠に恐れ入りますが、下記の推奨ブラウザをご利用くださいませ。

推奨ブラウザ:Google Chrome(グーグル・クローム)

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の形に持ち込める。

回答(1件)

ベストアンサーに選ばれました
tamu先生
先生
先生 の回答 9か月前
その考え方であっています。

>a、bが互いに素なら必ず余りが1になる式ができるのか自信がありません
ユークリッドの互除法はもともと最大公約数を求めるアルゴリズムで
a÷b=q余りrの時
「aとbの最大公約数」は「bとrの最大公約数」
を利用しています。
最終的に2つの数が公約数nを持つと、元々のaとbも公約数nを持つことになるので、n≠1だと矛盾します。
  • ご回答いただきありがとうございます!
    理解できました。

    9か月前
回答へコメントする
あなたがベストアンサーに選んだ
tamu
さんは先生をしています

詳しくはこちら

同じ問題集の質問(149件)

問題集・参考書の情報

新興出版社啓林館; 4th Edit版

他の質問・回答も見る