最大公約数の証明

gcd(n,a)=1かつgcd(n,b)=1ならばgcd(n,ab)=1をベズーの等式を用いて証明するっていう問題なのですが、

nx+ay=1 nu+bw=1 と書いて、最初の式にｂを掛けたりしたんですが、どうやって証明すればいいのか全くわかりません。

わかる方、どうかお願いします。

No.2 ベストアンサー 回答者： zk43 回答日時： 2007/01/31 18:46

ベズーの等式って初耳なんですが、

一般にaX+bY=cが整数解を持つための必要十分条件がgcd(a,b)がcを
割り切ること、と考えてよいですか？
とすると、nx+ay=1 nu+bw=1を辺々かけて、
(nx+ay)(nu+bw)=1
n^2xu+nxbu+aynu+aybw=1
n(nxu+xbu+ayu)+ab(yw)=1
これは、nX+abY=1が整数解X=nxu+xbu+ayu、Y=ywを持つことを意味する
ので、
gcd(n,ab)が1を割り切る、すなわち、gcd(n,ab)=1
こんなんで良いのかな？

直感的に明らかな事実ですがね・・・素因数を考えれば。

この回答へのお礼

ありがとうございます！
理解することができました。
わかりやすく説明してくれてありがとうございます。両辺同士をかけるというのもやってみましたが、nとabでまとめるというのを思いつきませんでした。

お礼日時：2007/01/31 19:32

No.3 回答者： koko_u 回答日時： 2007/01/31 22:30

>直感的に明らかな事実ですがね・・・素因数を考えれば。

素因数分解の一意性を証明するのに質問の命題が必要になります。
数学的には素数 p が ab を割り切るときに p が a または b を割り切るとは即答できません。

No.1 回答者： guuman 回答日時： 2007/01/31 18:35

n・x+a・y=1

n・u+b・w=y
とできるから
n・x+a・n・u+a・b・w=1
すなわち
(x+a・u)・n+w・(a・b)=1
よってgcd(n,ab)=1

この回答へのお礼

ありがとうございます。
もしよろしければ
>n・u+b・w=y
の説明をお願いしてもいいでしょうか？
お手数かけます、すみません。

お礼日時：2007/01/31 18:49