- ベストアンサー
原始根
pを奇素数、rをmod pの原始根で 1≦r≦p-1 をみたすものとすると、 pと(r^(p-1)-1)/pは互いに素ですか？
- Marico_MAP
- お礼率100% (77/77)
- 数学・算数
- 回答数4
- ありがとう数4
- みんなの回答 （4）
- 専門家の回答
質問者が選んだベストアンサー
その他の回答 (3)
- tmppassenger
- ベストアンサー率76% (285/372)
計算機で解かせたら、 p=29の時、r=14はmod pの原始根だが、問題の2つは互いに素にならない、と出ましたね... https://wandbox.org/permlink/U0jdF8RhoADreWb2
お礼
確認できました(wolframで、ですが…)。 ありがとうございました。
- ATZ1229tkt
- ベストアンサー率33% (2/6)
失礼しました。原始根じゃないですね。 2^(2･3･7･13)が-1なのでOKだろうと思っていました。 2^(4･7･13)が1でした。 申し訳ありません。
お礼
確認していただきありがとうございました。
- ATZ1229tkt
- ベストアンサー率33% (2/6)
互いに素であるとは限りません。 r^(p-1)-1がp^2で割り切れるかどうかということですが めったにないらしいですがないわけではありません。 有名なのはp=1093,r=2のときで2^1092-1が1093^2で 割り切れることが知られています。 他にp=3511,r=2でも同様になるようですが、この場合は 2は原始根ではないようです。
お礼
p=1093のとき2って原始根になりますか？
関連するQ&A
- 中国の剰余定理と原始根
アドバイスよろしくおねがいします。 p,ｑを素数としたときに mod p と mod q において 原始根になる値gが存在する。それは中国剰余定理からいえる。 という記述があったのですが、原始根と中国剰余定理が結びつきません。 mod p,mod q において原始根ということは gを法pにおいてp-１乗してはじめて１になり、かつ法qにおいてもq-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はフェルマー素数の原始根となるということの 証明もいまいちよくわかりません。 この回答あってますか？ もっとわかりやすい回答があったら教えてください。 お願いします。
- ベストアンサー
- 数学・算数
- 原始ｎ乗根
FMTの話しの中に、ｎを偶数として、 整数ω＞＝２とすると、P=1+ω^(n/2)上でωは原始ｎ乗根となる。 と書いてある。 たしかに、ωはｎ乗して初めて１とPを法として合同になる。 これは、Pが素数でなくても成立します。 しかし、 原始ｎ乗根の性質として ω^0 + ω^j + ・・ + ω^((n-1)j) = 0 (j=1,2,...,n-1) が成立すると書いてある。 ω＝２、ｎ＝6とすると、 ｊ＝１のときは 1+２+４+８+16+32＝63＝9*7≡0 mod(9) 9=2^(6/2)+1 j=2のときは、 １+４+16+64+256+1024＝1365＝151*9+6 アルゴリズムの設計と解析II （エイホ 他）の28ページには 原始ｎ乗根の定義の中の条件として、原始ｎ乗根は条件 ω^0 + ω^j + ・・ + ω^((n-1)j) = 0 (j=1,2,...,n-1) を満たさなくてはならない。 と書いてある。 さて、原始ｎ乗根の定義は何でしょうか？ 最初の２は原始ｎ乗根なのでしょうか？ Pには他に条件が付くのでしょうか？ ｊ に条件をつけるのでしょうか？ 計算間違いなのか、誤解なのかよく分かりません。 混乱しています。よろしくお願いします。
- ベストアンサー
- 数学・算数
- 原始根をつかって合同式を解く計算過程について
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が５、７、８、９、１０、１２、１５、２７、３０の時にそれぞれの原始根を求めたいのですがどうやればいいのでしょうか？
- ベストアンサー
- 数学・算数
- 原始根についても質問
23の原始根を全て求めよ つまりは２３＝（Ｚ／２３Ｚ）＊＝｛１，２，３、・・・２２｝ φ（２３）＝２２という答えになったような気が済ますが・・・ 自分で解いていながらまったく理解ができていないのでどうかアドバイスはいただけないでしょうか?お願いします。
- 締切済み
- 数学・算数
お礼
あら…こんなに反例あるんですね。 ありがとうございました。