最大公約数の証明

質問

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

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

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

回答No.2

zk43 · ベストアンサー

ベズーの等式って初耳なんですが、
一般に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でまとめるというのを思いつきませんでした。

回答No.3

koko_u

>直感的に明らかな事実ですがね・・・素因数を考えれば。
素因数分解の一意性を証明するのに質問の命題が必要になります。
数学的には素数 p が ab を割り切るときに p が a または b を割り切るとは即答できません。

回答No.1

guuman

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
の説明をお願いしてもいいでしょうか？
お手数かけます、すみません。