(矛盾?)群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になり,題意を満たしてしまいます。
この矛盾はどうしてなのでしょうか?
お礼
ご回答ありがとうございます。 わかりました。 体験版をやってみます。