半群になるかどうかの証明

質問

こんばんは。
研究で次のような問題で戸惑っています。次のものが半群となるかどうか調べたいのですが、なかなか証明できません・・。アドバイス等をいただきたく質問させていただきました。ご回答お願いいたします。

Ｓ＝Ｎ、　ａ○ｂ＝Ｇ⊂Ｄ（ａ、ｂ）　（ａ、ｂの最大公約数）
Ｓ：空でない集合
Ｎ：自然数全体の集合
※「○」はマルのことです。

回答No.4

yoikagari · ベストアンサー

多分問題文はa○b=gcd(a，b)だったのでしょう。

結論から書きますが、gcd(gcd(a，b)，c)=gcd(a，gcd(b，c))は成り立ちます。
つまり(a○b)○c=a○(b○c)がなりたつので、Nは半群です。
以下、その証明を書きます。

まず以下の性質に注目します。
「m,nがkで割り切れるならばgcd(m,n)がkで割り切れる」…※
あとは
「sがtで割り切れ、tがuで割り切れるならば、sはuで割り切れる」…◎
※と◎の証明は略

それでは回答です。

証明

bはgcd(a，b)で割り切れる、gcd(a，b)はgcd(gcd(a，b)，c)で割り切れる。
したがって、◎よりbはgcd(gcd(a，b)，c)で割り切れる。
cはgcd(gcd(a，b)，c)で割り切れる。
よって、bとcはgcd(gcd(a，b)，c)で割り切れるので、
※より、gcd(b，c)はgcd(gcd(a，b)，c)で割り切れる。
aはgcd(a，b)で割り切れる、gcd(a，b)は(gcd(a，b)，c)で割り切れる。
したがって◎より、aはgcd(gcd(a，b)，c)で割り切れる。
よって、aとgcd(b，c)はgcd(gcd(a，b)，c)で割り切れる。
したがって※より、gcd(a，gcd(b，c))はgcd(gcd(a，b)，c)で割り切れる。…△

bはgcd(b，c)で割り切れる、gcd(b，c)はgcd(a，gcd(b，c))で割り切れる。
したがって◎より、bはgcd(a，gcd(b，c))で割り切れる。
aはgcd(a，gcd(b，c))で割り切れる。
よって、aとbはgcd(a，gcd(b，c))で割り切れるので、
※より、gcd(a，b)は(a，gcd(b，c))で割り切れる。
cはgcd(b，c)で割り切れる、gcd(b，c)はgcd(a，gcd(b，c))で割り切れる。
したがって◎より、cはgcd(a，gcd(b，c))で割り切れる。
よって、gcd(a，b)とcはgcd(a，gcd(b，c))で割り切れる。
したがって※より、gcd(gcd(a，b)，c)はgcd(a，gcd(b，c))で割り切れる。…▲

△と▲よりgcd(gcd(a，b)，c)=gcd(a，gcd(b，c))がいえた。

証明ここまで

よって(a○b)○c=a○(b○c)が成り立つことがいえた。

お礼

ご回答ありがとうございました！参考にさせていただきます＾＾

回答No.3

alice_38

最大公約数の最大公約数は、皆、最大公約数だ。
世界に広げよう、最大公約数の…

古いし、公約数なら「和！」は上手くない。
恐縮。

参考： http://ja.wikibooks.org/wiki/%E5%B0%8F%E5%AD%A6%E6%A0%A1%E7%AE%97%E6%95%B0_6%E5%AD%A6%E5%B9%B4#.E6.9C.80.E5.A4.A7.E5.85.AC.E7.B4.84.E6.95.B0.E3.80.81.E6.9C.80.E5.B0.8F.E5.85.AC.E5.80.8D.E6.95.B0

お礼

ご回答ありがとうございました！参考にさせていただきます＾＾

回答No.2

koko_u_u

結合則が満たされているかを考えるだけです。

お礼

ご回答ありがとうございました！参考にさせていただきます＾＾

回答No.1

koko_u_u

>Ｓ：空でない集合

Ｎじゃないの？？

お礼

ご回答ありがとうございました！

補足

補足です。ご回答ありがとうございます。
すみません。書き間違いです（＞＜）「Ｓ：空でない集合」というのは無視してください。