原始根

質問

pを奇素数、rをmod pの原始根で
1≦r≦p-1 をみたすものとすると、
pと(r^(p-1)-1)/pは互いに素ですか？

回答No.4

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)

お礼

あら…こんなに反例あるんですね。
ありがとうございました。

回答No.3

tmppassenger

計算機で解かせたら、 p=29の時、r=14はmod pの原始根だが、問題の2つは互いに素にならない、と出ましたね...

https://wandbox.org/permlink/U0jdF8RhoADreWb2

お礼

確認できました(wolframで、ですが…)。
ありがとうございました。

回答No.2

ATZ1229tkt

失礼しました。原始根じゃないですね。
2^(2･3･7･13)が-1なのでOKだろうと思っていました。
2^(4･7･13)が1でした。
申し訳ありません。

お礼

確認していただきありがとうございました。

回答No.1

ATZ1229tkt

互いに素であるとは限りません。
r^(p-1)-1がp^2で割り切れるかどうかということですが
めったにないらしいですがないわけではありません。

有名なのはp=1093,r=2のときで2^1092-1が1093^2で
割り切れることが知られています。
他にp=3511,r=2でも同様になるようですが、この場合は
2は原始根ではないようです。

お礼

p=1093のとき2って原始根になりますか？