数学 証明問題(初等数学、数と式)

質問

以下の証明は正しいでしょうか?　何か足りない気がするのですが…ご指摘願います。

・問題
以下の1,2が同値であることを証明せよ。
(1).整数a,bは互いに素である。
(2).整数a,bについて、ax+by=1となる整数、x,yが存在する。

・回答
(2)→(1)を示す。
aとbの共通因数をkとおく。この時、a=kp,b=kqとおける。
(2)が成立すると仮定する。上記より、
k(px+qy)=1,(px+qy)=1/k。
しかし、a,bが整数であるためには、px+qyは整数でなければならない。(x,yは整数のため)
よって、kは1のみ妥当。従って、(2)が成立するならば、aとbの共通因数は1でなければならず、従ってaとbは互いに素

(1)→(2)を示す
a>bとしても一般性に差し支えない。ユークリッドの互除法より
a=bs+t
b=ts1+t1
t=t1s2+t2
t1=t2s3+t3
t2=t3s4+t4
...
tn=0となる。(※nは添え字、s,s1,s2,...、t,t1,t2,...は整数)　この時、t(n-1)=1。
従って、この過程を逆にたどると、
t(n-1)=a(1+s1s2+...)+b(-s-s2-ss1s2-...)
となる。s1,s2,...はいずれも整数より、(2)が示せる。

よって、(1),(2)は同値

回答No.2

waseda2003 · ベストアンサー

ユークリッドの互除法について誤解があるようですが，ユークリッドの互除法は
最大公約数を求めるための方法で，ax+byの表現までは言及してはいないので，
「ユークリッドの互除法より」だけでは説明になっていません。

ギャップがあるのは次の３点です。　（(2)⇒(1)はOKです）

１° t_n=0となる自然数nの存在が説明されていない。
　　これは，余りの条件を丁寧に述べれば説明がつくはず。

２° t_n=0だからといって t_(n-1)=1とは限らない。
　　そもそも最大公約数が２以上でもいつかはt_n=0となるのだから，
　　何の説明にもなっていない。
　　t_(n-1)が公約数になることと「互いに素」の仮定から説明できるはず。

３°「この過程を逆にたどると」で済ませているが，この部分が証明の核心部分
　　なのだから，「どのようにたどるか」の説明が必要。

ちなみに，(1)⇒(2)の証明は，除法の原理を用いるより
ディリクレの引き出し論法（鳩ノ巣原理）を用いる方が簡単です。

aとbは互いに素なので，a，2a，3a，…，(b-1)aをbで割った余りは（０以外で）
相異なる（要証明）から，そのうち一つは余りが１となります。それをkaとおき，
bで割ったときの商をqとおくと，
　　　ka=bq+1　したがって　ak+b(-q)=1

回答No.1

nag0720

(2)→(1)はいいですが、(1)→(2)は疑問です。
ユークリッドの互除法を利用してもいいという前提があるんでしょうか？

ユークリッドの互除法を使えば確かに証明できますが、今度はユークリッドの互除法の証明が必要になってきませんか？