原始ｎ乗根

質問

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には他に条件が付くのでしょうか？
　ｊ　に条件をつけるのでしょうか？

計算間違いなのか、誤解なのかよく分かりません。
混乱しています。よろしくお願いします。

回答No.2

Tacosan · ベストアンサー

そ～いうことです.

実のところ,
ω^0 + ω^j + ・・　+ ω^((n-1)j) = 0 (j=1,2,...,n-1) なら ω は 1 の原始 n乗根
は成り立ちます. ところがそれを実際に示すとその過程で
逆は必ずしも成り立たない
こともわかります. あなたの書いた ω=2, n=6 が「逆は成り立たない」例になります.

9 を法とする剰余系は体にはならないですよね.

お礼

ありがとうございました。

アルゴリズムの設計と解析II　（エイホ　他）の28ページ

の記述は、議論を簡単にするために仮定した

と理解します。
Pが素数だと結構楽になります。

回答No.1

Tacosan

「n乗すれば 1 になる」のが 1 の n乗根.
そのうち「n乗しなければ 1 にならない」のが 1 の原始 n乗根.

お礼

ありがとうございます。
すっきりしましたが、
条件
原始ｎ乗根の定義の中の条件として、原始ｎ乗根は条件
ω^0 + ω^j + ・・　+ ω^((n-1)j) = 0 (j=1,2,...,n-1)
を満たさなくてはならない。
は、
要求しないことになりますね。
これが成立するか否かは定義には関係ないが、それを利用する場合には
成立するか否かを検証しなくてはならない。
ということでしょうか。