• ベストアンサー
  • すぐに回答を!

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

こんばんは。 研究で次のような問題で戸惑っています。次のものが半群となるかどうか調べたいのですが、なかなか証明できません・・。アドバイス等をいただきたく質問させていただきました。ご回答お願いいたします。 S=N、 a○b=G⊂D(a、b) (a、bの最大公約数) S:空でない集合 N:自然数全体の集合 ※「○」はマルのことです。

noname#146701
noname#146701

共感・応援の気持ちを伝えよう!

質問者が選んだベストアンサー

  • ベストアンサー
  • 回答No.4

多分問題文は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)が成り立つことがいえた。

共感・感謝の気持ちを伝えよう!

質問者からのお礼

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

その他の回答 (3)

  • 回答No.3

最大公約数の最大公約数は、皆、最大公約数だ。 世界に広げよう、最大公約数の… 古いし、公約数なら「和!」は上手くない。 恐縮。 参考: 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

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

共感・感謝の気持ちを伝えよう!

質問者からのお礼

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

  • 回答No.1

>S:空でない集合 Nじゃないの??

共感・感謝の気持ちを伝えよう!

質問者からのお礼

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

質問者からの補足

補足です。ご回答ありがとうございます。 すみません。書き間違いです(><)「S:空でない集合」というのは無視してください。

関連するQ&A

  • 半群の証明

    こんばんは。来週にテストがあるため勉強をしているのですが、問題集に「次は半群となるかどうか調べよ」という以下のような3つの問いがありまして、解いてみたのですが正しいでしょうか?結合法則を満たすかどうか調べました。問1も問2,3と同じような解答ができましたら、そちらもお答えいただけると幸いです。 ご回答お願いいたします。 問1)S=負の数全体の集合、 a○b=ab (通常の積) 解答)a○bはSには属さないため、○はS上の二項演算ではない。    よって半群にはならない。 問2)S=N、 a○b=GCD(a、b) (a、bの最大公約数) 解答)GCD(GCD(a,b),c)=GCD(a,GCD(b,c))    GCD(GCD(a,b),c)   =GCD(GCD(b,c),a)   =GCD(a,GCD(b,c))    (a○b)○c=a○(b○c)    よって半群となる。 問3)S=R, a○b=min{a,b} (a、bのうちの小さい方) 解答)min{min{a,b},c}=min{a,min{c,b}}       min{min{a,b},c}   =min{min{b,c},a}   =min{a,min{c,b}    (a○b)○c=a○(b○c)    よって半群となる。

  • 数学的帰納法の証明

    自然数に関する数学的帰納法の原理が自然数が整列集合であることと同値であるということはわかっていますが 次のように数学的帰納法を証明した場合どこに整列集合の性質が使われているor論法が間違っているのでしょうか。 数学的帰納法 自然数nに関する命題をP(n)とする (ⅰ)P(0)が成り立つ (ⅱ)すべての自然数nに対して、P(n)が成り立つならばP(n+1)も成り立つ この2条件が満たされているときP(n)はすべての自然数nについて成り立つ (論理記号でかくと(ⅱ)は(∀n∈N(P(n)⇒P(n+1))だと思います) [証明] P(n)が成り立たないような集合をSとする Sが空集合である事を示せばP(n)がすべての自然数nについて成り立つ事になる Sが空集合でないと仮定するとm∈Sとなるようなmが存在する このとき条件(ⅱ)を次のように書き換えて (II)すべての自然数nに対して、P(n+1)が成り立たないならばP(n)も成り立たない と考えると P(m)が成り立たないのでP(m-1)も成り立たないことになる このときP(m-1)が成り立たないのでP(m-2)も成り立たない 以下続けると結局 P(1)が成り立たないのでP(0)も成り立たないことになるが これは(ⅰ)に反する よってSが空集合でないという仮定が間違っていたことになる ゆえにSは空集合であり命題P(n)がすべての自然数nに対して成り立つことが示された

  • 半群の証明

    こんばんは。 次は半群となるかどうか? S=R、 a○b=min{a、b} (a、bの内の最小の方) 上記のような問いがあり、半群になるという結果になったのですが合っていますか? ご回答お願いいたします。

  • 証明の仕方を教えてください。

    pを自然数とし、二次方程式x^2-px-1=0の二つの解をα、βとする。 数列{a(n)}をan=α^(n-1)+β^(n-1) (n=1,2,3…)によって定める。 (1)すべての自然数nに対し、a(n+2)=pa(n+1)+a(n)が成り立つことを示せ。 (2)すべての自然数nに対し、a(n)は自然数であることを示せ。 (3)pが奇数であるとき、すべての自然数nに対し、a(n)とa(n+1)の最大公約数は1であることを示せ。 という問題です。 (1)は計算して解けたのですが、(2)(3)をどのように証明したらよいのか分かりません。 教えていただけないでしょうか。よろしくお願いします。

  • 群数列についての証明

    第k群までの項をすべて順に並べた数列を、 c1,c2,c3.......,cn  とする。 この群数列は次の条件を満たしている。  項はすべて自然数  nは第k群までの項の総数  第k群を有限数列と考えたとき、初項はak,末項はbk (特にbk=cn)  第1群の項は自然数aである。(a1=b1=a)  第1群から第k群までに現れない自然数の中で最小のものが第(k+1)群の    初項a k+1  第(k+1)群の第2項以降は    c1+a k+1, c2+a k+1, ....... ,cn+a k+1 (1) a k+1≦bk +1 を証明せよ(k=1,2,3,......) (2) 2ak≦a k+1   を証明せよ(k=1,2,3,......)

  • aとbをa=b=0でない2つの整数とする。a,bの公約数の集合の中の最

    aとbをa=b=0でない2つの整数とする。a,bの公約数の集合の中の最大数dを、aとbの最大公約数といい、 d=(a,b)とかく 例えば(6,4)=2 このときar+bs=(a,b)のような整数rとsが存在するというのを証明する。という問題です、教えてください。

  • 最小公倍数 最大公約数 周辺の定理について

    自然数a=自然数aと自然数bの最大公約数×整数x 自然数b=自然数aと自然数bの最大公約数×整数y ⇒ 自然数aと自然数bの最小公倍数 =整数x × 整数y × 整数aと整数bの最大公約数 =整数x × 自然数b =整数y × 自然数a という定理の証明をおしえてください うんうん唸って考えてみたのですがどうしてもうまく証明できませんでした     

  • ユークリッドの互除法で最大公約数を求める

    <問題> n^2+2n+1とn+3の最大公約数になりうる値をすべて求めよ <解答> 整数a,bに対してa,bの最大公約数をg(a,b)とあらわす。 g(n^2+2n+1,n+3)=g(n+3,4) 4の正の約数は1,2,4であるから、g(n+3,4)として考えうるのも1,2,4である。 例えば、 n+3=5 すなわちn=2のとき、g(5,4)=1 n+3=6 ・・・ g(6,4)=2 n+3=8 ・・・ g(8,4)=4 となり、最大公約数として可能な数は1,2,4の3つの自然数である。 <質問> 「g(n+3,4)として考えうるのも1,2,4である。」 が必要条件であることはわかります。 その後、解答でなにがしたいのかよくわかりません。 なぜ例示しただけで「最大公約数として可能な数は1,2,4の3つの自然数である。」といえるのでしょうか? よろしくお願いします。 <思ったこと> 必要十分条件なら「g(n+3,4)として考えうるのも1,2,4である」場合、「4の正の約数は1,2,4である」であることを示すことになると思います。

  • 証明したいことを証明の途中に使う

    nとaが互いに素 ⇔ nとn-aが互いに素 の証明で2つ疑問がわいたので、質問します。 nとaの最大公約数をdとおくと n=Nd a=Ad (NとAは互いに素 これは背理法の証明 がインターネットでしらべれました。) とおけます。このときn-a=(N-A)dです。 ここからが疑問です。NとAが互いに素より、NとN-Aも互いに素です。 自分はこの文は、nをN、aをAと置き換えてはいるが証明したいことであり、成り立つかわからないので証明の途中には使っていけないと思いました。証明の続きは、 よってdはnとn-aの最大公約数にもなるから、nとaが互いに素 ⇔ nとn-aが互いに素です。で終わっていますが、2つ目の疑問が残りました、自分はd=1を証明しないといけない気がします。 自分の考えに間違いがあったら訂正をお願いします。

  • 群数列です

    1から順に自然数を並べて次のように群にわける。 1/2,3/4,5,6,7/8,9,…/…… ただし第n群が含む数の個数は2のn-1乗個である。 第n群に含まれる数の総和が10000を超えない最大のnを求めよ。 という問題なんですが、わかる方解答お願いします。