原始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 に条件をつけるのでしょうか?
計算間違いなのか、誤解なのかよく分かりません。
混乱しています。よろしくお願いします。