gcdとlcmについての証明

質問

最大公約数gcdと最小公倍数lcmについての質問です。
正の整数n1,n2,......,nlについて
gcd(n1,n2,n3,....,nl)=gcd(gcd(gcd(n1,n2),n3),...,nl)
を示せ。
という問題なのですが、これはどのように証明すればよいのでしょうか？nが3つまでのは証明できたのですが、l個での証明の仕方が分かりません。
lcmについてもgcdの証明と同様にすれば示せるのでしょうか？

回答No.2

proto · ベストアンサー

公倍数の方について、整数の個数が何個でも証明は本質的に同じなので、正の整数(a,b,c,d)で証明しますね。
いま(a,b)の最小公倍数をmとして、(a,b,c,d)の最小公倍数eと、a,bをmで置き換えた(m,c,d)の最小公倍数e'について考えます。

eはa,bの公倍数だから、mの倍数でもある。また仮定よりc,dの公倍数でもある。
結局eはm,c,dの公倍数であり、したがってeはe'の倍数である。

またe'はmの倍数であるからa,bの倍数であり、先ほどと同様にa,b,c,dの公倍数でもあり、eの倍数である。

このようにeはe'の倍数、e'はeの倍数であるからe=e'となる。
すなわち整数(a,b,c,d)のうち二数をその最小公倍数で置き換えても、置き換えの前後で全体の最小公倍数は変わらない。

約数の方も同様に証明できるかな？
互除法とgcd(0,a,b,c,d)=gcd(a,b,c,d)
あたりからも云える気がするけど。

お礼

ありがとうございました。３つで成り立つことを使って解いているということで合っているでしょうか？もしそうなら帰納法を使えば良いということでしょうか？また質問ですいません。

回答No.3

Tacosan

gcd も #2 の lcm と同様に証明できます.
つまり, l 個の整数のうち 2個を「それらの gcd」で置き換えても全体の gcd が変化しないことを示しておけば,
gcd(n1, n2, n3, ..., nl) = gcd(gcd(n1, n2), n3, ..., nl)
となります. 右辺は帰納法の仮定で
gcd(x, n3, ..., nl) = gcd(gcd(...gcd(x, n3), ...), nl)
なので
gcd(n1, n2, n3, ..., nl)
= gcd(gcd(n1, n2), n3, ..., nl)
= gcd(gcd(...gcd(gcd(n1, n2), n3), ...), nl)
とできます.

お礼

ありがとうございました。これでなんとかできそうです。

回答No.1

Tacosan

l に関する帰納法, かなぁ?

お礼

ありがとうございました。質問をする前に帰納法が使えるかなと思い、３つを使って４つを示そうとしたのですが３つの使い方が分かりませんでした。よろしければ帰納法での解き方を教えていただきたいです。