整数問題

質問

次の整数問題はどのようにときますか。連続除法とそうでない場合とで考えたいのでご教授してください。いくら考えてもよい答えができません。
「a,bは整数とする。(a,b）=1のときax+by=1を満たす整数x,yが存在することを示せ」

よろしくお願いします。

回答No.3

arrysthmia · ベストアンサー

a と b の最大公約数 (a,b) を、互除法で求めてみましょう。
r[1] = a,
r[2] = b と置いて、以後、
r[k] を r[k+1] で割った余りを r[k+2] としてゆきます。
各段の商を q[k] と置けば、
r[k] = q[k]・r[k+1] + r[k+2] と書けますね。
これを続けて、r[m] = 0 となったときの
r[m-1] の値が、最大公約数です。
ですから、a,b が素であるとき、
r[m-3] = q[m-3]・r[m-2] + 1 となります。
この式に、先の割り算の式を順次代入して、
式に登場する r[k] の k を小さくしてゆけば、
最後には、a・(係数) + b・(係数) = 1
という式が得られます。
この式の (係数) は、どちらも、
q[k] から掛け算と足し算引き算だけで算出できますから、
値は整数です。
こうして、ax + by = 1 が構成できました。

回答No.4

zk43

ax+byの形で表わされる最小の自然数をkとする。
（そのような自然数は存在する。a(-x)+b(-y)を考えれば
良いから。）
ax+by=kより、(a,b)|k
次に、aをkで割って、a=kq+r（0≦r<k）となったとする。
すると、
r=a-kq=a-(ax+by)q=a-aqx-bqy=a(1-qx)+b(-qy)
となり、rはa,bの整数係数の線形結合で表わされるので、
kの最小性より、r=0でなくてはならない。
よって、a=kqで、k|aとなる。
同様に、bをkで割ることを考えて、k|bとなる。
よって、kはa,bの公約数なので、k|(a,b)となる。
よって、(a,b)とkは互いに割り切り合うので、k=(a,b)
よって、ax+byで表わされる最小の自然数は(a,b)である。
よって、(a,b)=1のときは、ax+by=1と表すことができる。
これは、単に存在を示す証明で、具体的に解を求めるには、
ユークリッドの互除法による方が良いです。
また、これは、イデアルの考えに基づく証明でもあります。

お礼

ありがとうございます。
参考にしてみます

回答No.2

nag0720

同様の質問があります。
http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1129118476

回答No.1

nattocurry

(a,b）=1
これはどういう意味なのでしょうか？

補足

(a,b)=1は互いに素ということです。