- ベストアンサー
原始根の求め方について
gcd(m, x) =1 ord_m(x) = φ(m) mが５、７、８、９、１０、１２、１５、２７、３０の時にそれぞれの原始根を求めたいのですがどうやればいいのでしょうか？
- みんなの回答 （3）
- 専門家の回答
関連するQ&A
- 原始根の問題です。
整数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には他に条件が付くのでしょうか？ ｊ に条件をつけるのでしょうか？ 計算間違いなのか、誤解なのかよく分かりません。 混乱しています。よろしくお願いします。
- ベストアンサー
- 数学・算数
- 原始ｎ乗根の和をｆ（ｎ）
高木貞治 初等整数論に Ｆn(x）：１の原始ｎ乗根のみを根とする方程式 問題：Ｆn(x）の第2項の係数は-μ(n)に等しい これはほぼ理解できるのですが 解のプロセスの中で、原始ｎ乗根の和をｆ（ｎ）とすれば、、x^n-1=0から d|n Σｆ（ｄ）＝１(n=1のとき） d|n Σｆ（ｄ）＝0(n＞1のとき） ←これがいまひとつよくわかりません。 よろしくお願いします。 ----------------------------------- 原始ｎ乗根；ｎ乗して始めて１になる数
- ベストアンサー
- 数学・算数
- 原始根についても質問
23の原始根を全て求めよ つまりは２３＝（Ｚ／２３Ｚ）＊＝｛１，２，３、・・・２２｝ φ（２３）＝２２という答えになったような気が済ますが・・・ 自分で解いていながらまったく理解ができていないのでどうかアドバイスはいただけないでしょうか?お願いします。
- 締切済み
- 数学・算数
補足
なるほど、例えばm = 27 の時なのですが φ(27) = 18なので 2^18 ≡ 1(mod 27）を先に計算してなりたてつ事を確認してから2^17, 2^16・・・を計算した方が無駄が無くていいですか？