2-1337:原始根...その2...^^;

画像:http://kishuji-minabe.jp/?p=2957 より 引用 Orz〜
94b49ad0e232653c08a95e923ecc16f52.jpg

問題 2-1337・・・http://aozoragakuen.sakura.ne.jp/suuron/node37.html より 引用 Orz〜

$p=41$法とする原始根を一つ求めよ.



































解答

・わたしの...

2で...
2^1...2
2^2...4
2^3...8
2^4...16
2^5=32≡-9
2^6...-18
2^7...5
2^8...10
2^9...20
2^10...-1
2^11...-2
2^12...-4
2^13...-8
2^14...-16
2^15...9
2^16...18
2^17...-5
2^18...-10
2^19...-20
2^20...1
2^21...2 でダメ...

こりゃ、も少し基本がわかってないと無理ですばい...^^;

・鍵コメT様からのもの Orz〜

2^10で「-1」が出てきた時点で,2^20で「1」となることは明らかであり,
それ以上計算を進める必要はありません.・・・でしたわ ^^;
また,ここまでで得られた数
(および,2^11~2^19で出てくる,2^1~2^9での数の-1倍)
±1,±2,±4,±8,±16,±9,±18,±5,±10,±20
はどれも原始根にはなり得ません.
(「-」がついた数は,21以上の数だと思えばよいことになります.)

見えやすいのは「7」でしょうか.
7^2=49は,41を法として2^3と合同であり,
7^nは順に,
7,2^3,(2^3)*7,2^6,(2^6)*7,2^9,(2^9)*7,…
と合同です.
・2^(3n)の形式ではじめて41を法として1と合同になるのは2^60であること,
・2^(3n)の形式で7をかけたものが41を法として1と合同になるはずはないこと
[理由:2^(3n)*7≡1 (mod 41)と仮定すると,
2^(39*3n)*7^39≡1 (mod 41)より,2^(39*3n)*7^40≡7 (mod 41),
つまり2^(39*3n)≡7 (mod 41)となり,「2^n」の列に,「7」が登場するはず]
から,7が原始根の1つであることが確定します.

*これ以下の内容が理解できません...^^;
できれば...もちっと飲み込みやすいヒントプリーズ Orz〜

> ・2^(3n)の形式ではじめて41を法として1と合同になるのは2^60であること,
> ・2^(3n)の形式で7をかけたものが41を法として1と合同になるはずはないこと
> [理由:2^(3n)*7≡1 (mod 41)と仮定すると,
> 2^(39*3n)*7^39≡1 (mod 41)より,2^(39*3n)*7^40≡7 (mod 41),
> つまり2^(39*3n)≡7 (mod 41)となり,「2^n」の列に,「7」が登場するはず]
> から,7が原始根の1つであることが確定します.

7^40≡1 (mod 41)が成り立つのは当然です.
「7^1,7^2,…,7^39がどれも41を法に1と合同でない」ことが示せれば,
7が原始根であることが確定します.

すでに,7^2,…,7^39は41を法に
2^3,(2^3)*7,2^6,(2^6)*7,…,2^57,(2^57)*7と合同であることが示されているので,
示すべきは
「2^3,2^6,2^9,…,2^57およびその7倍のうちには,41を法に1と合同なものはない」
ことです.

「2^n≡1(mod 41)は,n=1,2,…,19で不成立,n=20で成立」より,
「2^n≡1(mod 41)となる条件は,nが20の倍数であること」とわかるので,
2^3,2^6,2^9,…,2^57のうちには41を法に1と合同なものはありません.

また,例えば(2^33)*7≡1 (mod 41)であったと仮定すると,両辺に7をかけて
2^36≡7 (mod 41)となるはずですが,2^nは,41を法に
±1,±2,±4,±8,±16,±9,±18,±5,±10,±20
のいずれかと合同であり,7と合同にはなり得ないはずで,矛盾です.


*熟読玩味ぃ...^^;v
関連記事
スポンサーサイト



コメント

>鍵コメT様へ ^^

スモークマン
なるほど...^^;
って、すぐに頭に染み込んでるわけではないですけど...^^;;
2^10≡-1 (mod 41) から、2^20≡1とわかるわけですね?
2^40≡1だから...2^2,2^5,2^8,2^10を調べればいいですのね...

紹介させていただきまっす〜m(_ _)m〜v

管理人のみ閲覧できます

-
このコメントは管理人のみ閲覧できます

>鍵コメT様へ ^^

スモークマン
> 2^10で「-1」が出てきた時点で,2^20で「1」となることは明らかであり,
> それ以上計算を進める必要はありません.
> また,ここまでで得られた数
> (および,2^11~2^19で出てくる,2^1~2^9での数の-1倍)
> ±1,±2,±4,±8,±16,±9,±18,±5,±10,±20
> はどれも原始根にはなり得ません.
> (「-」がついた数は,21以上の数だと思えばよいことになります.)
>
> 見えやすいのは「7」でしょうか.
> 7^2=49は,41を法として2^3と合同であり,
> 7^nは順に,
> 7,2^3,(2^3)*7,2^6,(2^6)*7,2^9,(2^9)*7,…
> と合同です.

これ以下の内容が理解できません...^^;
できれば...もちっと飲み込みやすいヒントプリーズ Orz〜

> ・2^(3n)の形式ではじめて41を法として1と合同になるのは2^60であること,
> ・2^(3n)の形式で7をかけたものが41を法として1と合同になるはずはないこと
> [理由:2^(3n)*7≡1 (mod 41)と仮定すると,
> 2^(39*3n)*7^39≡1 (mod 41)より,2^(39*3n)*7^40≡7 (mod 41),
> つまり2^(39*3n)≡7 (mod 41)となり,「2^n」の列に,「7」が登場するはず]
> から,7が原始根の1つであることが確定します.

管理人のみ閲覧できます

-
このコメントは管理人のみ閲覧できます
非公開コメント