- ベストアンサー
原始根
tmppassengerの回答
ちょっとプログラムを変更して、p<= 2000の場合を調べてみましたが、反例はこれだけあるようです (29, 14) (37, 18) (43, 19) (71, 11) (103, 43) (109, 96) (113, 68) (131, 111) (181, 78) (191, 176) (211, 165) (257, 48) (263, 79) (269, 171) (283, 147) (349, 317) (353, 14) (359, 257) (367, 159) (367, 205) (373, 242) (397, 175) (439, 194) (449, 210) (461, 52) (487, 10) (509, 250) (563, 486) (599, 559) (617, 556) (619, 286) (631, 534) (641, 340) (647, 526) (653, 84) (653, 120) (653, 287) (653, 410) (701, 375) (739, 168) (743, 467) (773, 392) (797, 446) (839, 667) (857, 682) (863, 13) (863, 434) (883, 657) (887, 292) (907, 127) (907, 771) (919, 457) (947, 208) (971, 296) (983, 419) (1019, 705) (1031, 158) (1051, 806) (1061, 508) (1087, 617) (1091, 691) (1097, 776) (1103, 284) (1103, 793) (1103, 1054) (1109, 1082) (1117, 1066) (1123, 1012) (1163, 170) (1187, 184) (1229, 821) (1249, 326) (1283, 45) (1327, 585) (1327, 1149) (1367, 411) (1373, 884) (1381, 653) (1447, 584) (1453, 378) (1483, 1061) (1493, 164) (1499, 1172) (1523, 1032) (1549, 855) (1549, 1069) (1553, 568) (1559, 1454) (1571, 1265) (1579, 906) (1579, 1235) (1597, 453) (1601, 1420) (1607, 874) (1607, 1253) (1619, 371) (1619, 536) (1657, 1481) (1697, 461) (1697, 857) (1787, 631) (1867, 828) (1873, 731) (1933, 963) (1949, 704)
関連するQ&A
- 中国の剰余定理と原始根
アドバイスよろしくおねがいします。 p,qを素数としたときに mod p と mod q において 原始根になる値gが存在する。それは中国剰余定理からいえる。 という記述があったのですが、原始根と中国剰余定理が結びつきません。 mod p,mod q において原始根ということは gを法pにおいてp-1乗してはじめて1になり、かつ法qにおいてもq-1乗してはじめて1になるわけだと思います。(ほかにも条件がありますが…) で、中国剰余定理は 簡単に言うと 複数の法が違い、法の数が互いに素な連立合同式に対して、解が一意に定まるということだと思います。 この二つが結びつきません。 ご教授お願いします
- ベストアンサー
- 数学・算数
- 原始根の問題です。
整数aがpの原始根であるための必要十分条件は(a/p)=-1であることを示せ。という問題です。(ちなみにこの(a/p)=-1のかっこはルシャンドルの記号です。) 回答には p=2^(2n) +1とおく。3がpの原始根ならば、(3/p)=-1 原始根でなければ、p-1の約数は2べきだから(3/p)=1 ところで、相互法則から、(3/p)=(p/3), p≡(-1)^(2n) +1≡2(mod3)より、 (p/3)=(2/3)=-1 よって原始根になる。 と書いてあったのですが、 なんで、p=2^(2n) +1と最初におくのかわかりません。 これってフェルマー素数におくっていうことですよね? ちなみに3はフェルマー素数の原始根となるということの 証明もいまいちよくわかりません。 この回答あってますか? もっとわかりやすい回答があったら教えてください。 お願いします。
- ベストアンサー
- 数学・算数
- 原始n乗根
FMTの話しの中に、nを偶数として、 整数ω>=2とすると、P=1+ω^(n/2)上でωは原始n乗根となる。 と書いてある。 たしかに、ωはn乗して初めて1とPを法として合同になる。 これは、Pが素数でなくても成立します。 しかし、 原始n乗根の性質として ω^0 + ω^j + ・・ + ω^((n-1)j) = 0 (j=1,2,...,n-1) が成立すると書いてある。 ω=2、n=6とすると、 j=1のときは 1+2+4+8+16+32=63=9*7≡0 mod(9) 9=2^(6/2)+1 j=2のときは、 1+4+16+64+256+1024=1365=151*9+6 アルゴリズムの設計と解析II (エイホ 他)の28ページには 原始n乗根の定義の中の条件として、原始n乗根は条件 ω^0 + ω^j + ・・ + ω^((n-1)j) = 0 (j=1,2,...,n-1) を満たさなくてはならない。 と書いてある。 さて、原始n乗根の定義は何でしょうか? 最初の2は原始n乗根なのでしょうか? Pには他に条件が付くのでしょうか? j に条件をつけるのでしょうか? 計算間違いなのか、誤解なのかよく分かりません。 混乱しています。よろしくお願いします。
- ベストアンサー
- 数学・算数
- 原始根をつかって合同式を解く計算過程について
2が11の原始根で有る事をつかって3X^3 ≡ 2(mod 11)を解きたいのですが計算途中でつまずいてしまいます。 φ(11) = 10 2^10 = 1(mod 11) ind_2 (3X^3) ≡ ind_2 2 = 1(mod 11) ind_2 (3X^3) ≡ ind_2 3 + ind_2 X^3 ≡ 8 + 3 * ind_2 X (mod 11) 8+3*ind_2 X ≡ 2(mod 11) ここまでわかったのですがここから先の計算がわかりません。どうやれば X ≡ n1, n2, n3 ,.... (mod 11)の形に持っていけるのでしょうか?
- 締切済み
- 数学・算数
- 原始根の求め方について
gcd(m, x) =1 ord_m(x) = φ(m) mが5、7、8、9、10、12、15、27、30の時にそれぞれの原始根を求めたいのですがどうやればいいのでしょうか?
- ベストアンサー
- 数学・算数
- 原始根についても質問
23の原始根を全て求めよ つまりは23=(Z/23Z)*={1,2,3、・・・22} φ(23)=22という答えになったような気が済ますが・・・ 自分で解いていながらまったく理解ができていないのでどうかアドバイスはいただけないでしょうか?お願いします。
- 締切済み
- 数学・算数
お礼
あら…こんなに反例あるんですね。 ありがとうございました。