(矛盾?)群Z_8000000で位数が8であるような元を全て求めよ
- [問] 群Z_8000000で位数が8であるような元を全て求めよ。
- 8x≡0 (mod 8000000) and 7x≠0 (mod 8000000), 6x≠0(mod8000000),…, x≠0(mod 8000000)を満たせばいいのでgcd(a,8000000)=1で0≦1000000a<8000000なるaを吟味してみればよい。
- a=1,3,7ならC(1),C(3),C(7)となるが、a=5の場合は5は8000000に互いに素ではないにもかかわらず,C(5000000)は位数8になってしまう。
- ベストアンサー
(矛盾?)群Z_8000000で位数が8であるような元を全て求めよ
[問] 群Z_8000000で位数が8であるような元を全て求めよ。 という問題に下記例題を参考に取り組んでいます。 [例題] 群Z_40で位数が10であるような元を全て求めよ。 [解]10x≡0(mod40)で10より小さいものでは0にならないのだから 4aという形aが40と互いに素． aは40と互いに素で10(4a)≡0(mod40)を満たし,且つ9(4a)≡0(mod40),…,(4a)≡0(mod40)を満たさない。という事は a=1の時,10・4≡0(mod40)つまり,40≡0(mod 40)を満たし,且つ 36≡0(mod40),…,4≡0(mod40)を満たさない。 はOK.よって類はC(4). a=2の時,10・8≡0(mod40)つまり,80≡0(mod 40)を満たし,且つ 72≡0(mod40),…,8≡0(mod40)を満たさない。 は"40≡0(mod 40)を満たさない"が途中に現れてしまいのでNG.(実際,gcd(2,40)=2≠1) a=3の時,10・12≡0(mod40)つまり,120≡0(mod 40)を満たし,且つ 108≡0(mod40),…,12≡0(mod40)を満たさない。はOK.よって類はC(12). a=4の時,10・16≡0(mod40)つまり,160≡0(mod 40)を満たし,且つ 144≡0(mod40),…,16≡0(mod40)を満たさない。 は"80≡0(mod 40)を満たさない"が途中に現れてしまいのでNG.(実際,gcd(4,40)=4≠1) a=5の時,10・20≡0(mod40)つまり,200≡0(mod 40)を満たし,且つ 180≡0(mod40),…,20≡0(mod40)を満たさない。 は"40≡0(mod 40)を満たさない"が途中に現れてしまいのでNG.(実際,gcd(5,40)=5≠1) a=6の時,10・24≡0(mod40)つまり,240≡0(mod 40)を満たし,且つ 216≡0(mod40),…,24≡0(mod40)を満たさない。 は"120≡0(mod 40)を満たさない"が途中に現れてしまいのでNG.(実際,gcd(6,40)=2≠1) a=7の時,10・28≡0(mod40)つまり,280≡0(mod 40)を満たし,且つ252≡0(mod40),…,28≡0(mod40)を満たさない。はOK.よって類はC(28). a=8の時,10・32≡0(mod40)つまり,320≡0(mod 40)を満たし,且つ288≡0(mod40),…,32≡0(mod40)を満たさない。 は"160≡0(mod 40)を満たさない"が途中に現れてしまいのでNG.(実際,gcd(8,40)=4≠1) a=9の時,10・36≡0(mod40)つまり,360≡0(mod 40)を満たし,且つ324≡0(mod40),…,36≡0(mod40)を満たさない。はOK.よって類はC(36). a=10の時,10・40≡0(mod40)つまり,400≡0(mod 40)を満たし,且つ360≡0(mod40),…,40≡0(mod40)を満たさない。 は"40≡0(mod 40)を満たさない"が途中に現れてしまいのでNG.(実際,gcd(10,40)=10≠1) a=11の時,10・44≡0(mod40)つまり,440≡0(mod 40)を満たし,且つ396≡0(mod40),…,44≡0(mod40)を満たさない。 はOK.よって類はC(44).しかし,C(44)=C(4). 即ち,ここでは既に一周しているのでこれ以上は調べる必要は ない。 以下現れる類は上記のC(4),C(12),C(28),C(36)に等しい。 となっています。所でこの「4a」とは何処から来たのでしょう か? [問] 群Z_8000000で位数が8であるような元を全て求めよ。 そして,求めた元が本当に正しいか説明してみせよ。 [解] 8x≡0 (mod 8000000) and 7x≠0 (mod 8000000), 6x≠0(mod8000000),…, x≠0 (mod 8000000)を満たせばいいのでgcd(a,8000000)=1で 0≦1000000a<8000000なるaを吟味してみればよい。.何故なら d=gcd(a,8000000)≠1 なら m(1000000a)=8000000なるm=1,2,…,7がどうしても現れてしまうからである。. 従ってa=1,3,7.即ち C(1),C(3),C(7). 実際,a=1なら,8・1000000≡0(mod8000000) つまり8000000≡0(mod8000000) が成立ち. 7000000≡0(mod8000000),…,1000000≡0(mod8000000)らが成立たない。 従って,a=1はOK. ∴その類はC(1000000). a=2なら,8・2000000≡0(mod8000000)即ち16000000≡0(mod8000000)が成立ち. 14000000≡0(mod8000000),…,2000000≡0(mod8000000)が成立たない. 然し"8000000≡0(mod8000000)は成立たない"が14000000≡0(mod8000000),…,2000000≡0(mod8000000)の中に現れる。.従って,a=2は NG,しかもgcd(2,8000000)=2≠1. ： a=5なら,8・5000000≡0(mod8000000) つまり40000000≡0(mod8000000) が成立ち. 35000000≡0(mod8000000),…,5000000≡0(mod8000000)らが成立たない。 従って,a=5はOK. ∴その類はC(5000000). しかし,gcd(5,8000000)=5≠1 という風に,a=5の場合は5は8000000に互いに素ではないにもかかわらず,C(5000000)は位数8になり,題意を満たしてしまいます。 この矛盾はどうしてなのでしょうか?
- Fumie_0515
- お礼率71% (41/57)
- 数学・算数
- 回答数2
- ありがとう数2
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
例題ではgcd(m,a)=1が成り立つ必要があります 問いではgcd(m,a)=1は成り立つ必要がありません 違う場合ですので、まず区別して下さい 群Z_8000000で位数が8であるような元を求めたい まず位数が8より大きくならないようにその元は1000000の倍数である必要がありますから1000000a(0≦a<8)と書けます・・・(1) 次に位数が8より小さくならないようにaは8と互いに素である必要があります・・・(2) 結局、a=1,3,5,7です 例題では >aが40と互いに素 とありますが、これでも正しいのですが、aと10が互いに素というべきでしょう
その他の回答 (1)
- kobold
- ベストアンサー率62% (20/32)
＞この「4a」とは何処から来たのでしょうか? この説明は最初にあります ＞10x≡0(mod40)で10より小さいものでは0にならないのだから4aという形 ここから来ています もし4の倍数でなければ10倍しても40の倍数にはならないからです ＞aが40と互いに素 aが40と1以外の公約数をもったとします たとえばaが2の倍数だったら、xは8の倍数になり、位数は5以下になります aが5の倍数だったら、xは10の倍数になり、位数は4以下になります これはこの4の素因数である2が位数8の約数でもあるから成り立つことです だから問いの場合には成り立ちません ＞gcd(a,8000000)=1 これが成り立つ必要がないということです
お礼
ありがとうございます。 > ＞この「4a」とは何処から来たのでしょうか? > この説明は最初にあります ： > だから問いの場合には成り立ちません 分かってきました。 一般の場合だと,Z_aで位数bの元を求めと言われたら, bx≡0(mod a)が成立, (b-1)x≡0(mod a),が不成立,(b-2)x≡0(mod a),が不成立,…,x≡0(mod a),が不成立, なるbを探せばいいので,mb=aでgcd(m,a)=1なるmを吟味すればいいのですね。 > ＞gcd(a,8000000)=1 > これが成り立つ必要がないということです すいません。おっしゃってる意味が分かりません。 a=5の場合は5は8000000に互いに素ではないにもかかわらず,C(5000000) は位数8になり,題意を満たしてしまいます。 この矛盾はどうしてなのでしょうか?
関連するQ&A
- 可換群Gの二つの元a,bのそれぞれの位数m,nが
可換群Gの二つの元a,bのそれぞれの位数m,nが 互いに素ならば、abの位数はmnである。 この証明が分からないです。 あと、位数m,nが互いに素なようになる可換群はどのようなものがあるでしょうか？ 例えばmodの世界において考えると、 mod nの時、位数はn-1の約数になるので互いに素にはならないと思うのです。 そもそもが間違えているかもしれません。 優しく教えていただければ幸いです。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 【代数学】位数2の元
代数学の本を読んでいて、練習問題の解説に以下のような記述がありました： pを素数とするとき、Z/pZは体だから、x^2≡1（mod p）なる元はpを法として-1ただ1つ。乗法群(Z/pZ)*において、先にみたように位数2の元はただ1つだから…（以下省略。Zは整数全体のなす環） この解説で「Z/pZは体だから、x^2≡1（mod p）なる元はpを法として-1ただ1つ」（*）という部分が理解できません。ただし、その後の文で「乗法群の位数2の元はただ1つ」とあるので、（*）は1以外でそのようなxは-1だけ（mod p）という意味ではないかと考えています。そこで以下の質問をさせていただきたいです。 １．一般に、体の乗法群には位数2の元は1つだけあるといえるでしょうか。その場合、なぜそういえるのかの説明またはヒントをいただけないでしょうか。 ２．１の答えがnoの場合、反例があれば教えていただきたいです。 よろしくお願いいたします。
- ベストアンサー
- 数学・算数
- 位数を求める問題で、次のように考えたんですが
<a>を位数が100の巡回群とする この部分群<a^162>の位数を求めよ 162×m≡162(mod 1000)を解けばよい 162(m-1)≡0(mod 1000) また、<a^162>の位数をnとおくと、n=m-1なので 162n≡(mod 100) は満たさなければならないため、nは100の倍数 故に、162×100＝16200 162 200=32400 162×300=48600 162×400=64800 162×500=81000 よって、n=500
- 締切済み
- 数学・算数
- 位数を求める問題で、次のように考えたんですが
<a>を位数が1000の巡回群とする この部分群<a^162>の位数を求めよ 162×m≡162(mod 1000)を解けばよい 162(m-1)≡0(mod 1000) また、<a^162>の位数をnとおくと、n=m-1なので 162n≡(mod 100) は満たさなければならないため、nは100の倍数 故に、162×100＝16200 162 200=32400 162×300=48600 162×400=64800 162×500=81000 よって、n=500
- 締切済み
- 数学・算数
- 乗群の位数とラグランジェの定理
(mod p)の剰余類で乗群G*をつくるとき，（pは素数） 0を含む剰余類は除くので，|G*|=p-1かと思います． a ∈ G*で，巡回部分群Hを生成すれば， H=G*であることも確認できます． ただ，ここでどうしてもわからないことがあります． G*の位数も，Hの位数もp-1で，-1されるために一般に素数にはなりません． ラグランジェの定理から位数が素数の有限群が真部分群を持たないことがわかりますが， G*の位数は，p-1で素数にならないため，真部分群を持ってもよさそうな気がします． どこに間違いがあるのでしょうか？
- ベストアンサー
- 数学・算数
- 連立合同式の商の定理について
連立合同式の商の定理について教えてください。 x,yを整数 m,aを自然数とするとき ax≡ay (mod m) ⇔ x≡y ( mod m/GCD(m,a) ) (おかしな表記ですみません。( mod -)は分数式です) が「商の定理」と習いましたが、これは連立合同式 x≡a (mod K) x≡b (mod L) x≡c (mod M) のK L M が「互いに素」ではないときに適用できる定理だと思うのですが、うまく理解できません。 解らない点:(1) 連立合同式 x≡a (mod K) x≡b (mod L) の時、K L のGCDが「1」で「互いに素」と覚えていますが x≡a (mod K) x≡b (mod L) x≡c (mod M) の時も K L MのGCDが「1」で「互いに素」、それ以上ならば「互いに素」ではないと理解してよいのでしょうか？ 解らない点:(2) x≡a (mod K) x≡b (mod L) x≡c (mod M) で K L M が「互いに素」ではない場合、商の定理を適用した解法でx≡y ( mod m/GCD(m,a) )を求める方法。 K L M が「互いに素」ではない時、K L Mの最小公倍数を使えばよいのは解るのですが、GCD(m,a)の「a」が理解できません。「m」はK L Mの最小公倍数だと思うのですが、「a」は何になるのでしょう？ x≡2 (mod 4) x≡4 (mod 12) x≡3 (mod 9) の場合を例として、具体的に解法を教えてください。 よろしくお願いします。もしも上式が連立合同式として成立しないのであれば、その理由も教えてください。 中国式余剰定理では、( mod ○ )が「互いに素」ではない場合にも解を求める事ができると、参考書にはあるのですが、最小公倍数を使う事しか理解できません。 具体的な解法で、よろしくお願いします。
- ベストアンサー
- 数学・算数
- 拡張ユークリッド互除法による乗法逆元の求め方
こんにちは。 タイトルの通りの質問なのですが、過去ログを参考にしても特別分からないところがあったため、質問させて下さい。 11^-1 ≡ x(mod 31) このxを求めたいのですが、11x * 31y = gcd(11, 31)として解いたら、 -14 * 11 + 5 * 31 = 1 となってしまい、うまくいきません。 以下、自分なりの解法です。 ----------------------------------------------------- 11^-1 ≡ x(mod 31)より、11x ≡ 1(mod31) これは、11x + 31y = 1を示す。 gcd(11, 31) 11 = a, 31 = b とする = gcd(31, 11) → b = 2a + 9 → 9 = -2a + b = gcd(11, 9) → a = (-2a + b) + 2 → 2 = 3a - b = gcd(9, 2) → -2a + b = 4(3a - b) + 1 ―(1) = gcd(2, 1) = gcd(1, 0) = 1 (1)の式より、-14a + 5b = 1 先ほどの式と照らし合わせて、(x, y) = (-14, 5) したがって、11^-1 ≡ -14(mod 31) ----------------------------------------------------- おそらく、11x > 31yの条件が取り入れられてないのが原因だと思いますが、どう使えばいいかわからないです。 どなたか正しい解法を教えてください。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 位数１２の群Gの問題なんですが・・・
Gを位数１２の群G＝＜a,b＞,a^^6=e,a^^3=b^^2=(ab)^^2とする。Gの元はG={e,a,a^^2,a^^3,a^^4,a^^5,b,ab,a^^2b,a^^3b,a^^4b,a^^5b}でありまた部分群N、Z、Kを次のようにおく。N=＜a＞,Z<a^^3>,K<b>とした時の （１）剰余群G/N、G/Z、N/Zの乗積表を作れという問題なんですがいまいちわかりません。 （２）またN,Kの標準的準同型写像ｆ：G→G/Z ｘ：→ｘZによる像を求めよという問題なんですがよくわかりません。アドバイス頂ければありがたいです。よろしくお願い致します。（Gの乗積表は省略しました。）
- ベストアンサー
- 数学・算数
- 半群の証明
こんばんは。来週にテストがあるため勉強をしているのですが、問題集に「次は半群となるかどうか調べよ」という以下のような３つの問いがありまして、解いてみたのですが正しいでしょうか？結合法則を満たすかどうか調べました。問１も問２，３と同じような解答ができましたら、そちらもお答えいただけると幸いです。 ご回答お願いいたします。 問１）Ｓ＝負の数全体の集合、 ａ○ｂ＝ａｂ （通常の積） 解答）ａ○ｂはSには属さないため、○はS上の二項演算ではない。 よって半群にはならない。 問２）Ｓ＝Ｎ、 ａ○ｂ＝ＧＣＤ（ａ、ｂ） （ａ、ｂの最大公約数） 解答）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○ｂ＝ｍｉｎ｛ａ，ｂ｝ （ａ、ｂのうちの小さい方） 解答）min｛min｛a,ｂ｝,ｃ｝＝min｛a,min{c,ｂ}｝ min｛min｛a,ｂ｝，c｝ ＝min｛min｛b,ｃ｝,ａ｝ ＝min｛a,min｛c,ｂ｝ （ａ○ｂ）○ｃ＝ａ○（ｂ○ｃ） よって半群となる。
- ベストアンサー
- 数学・算数
お礼
分かりやすいご説明どうもありがとうございました。 納得です。