Primitive $2^k$-th roots of unity in $GF(p)$

While debugging an NTT implementation I've noticed something. Looks like if I have a primitive $(n = 2^k)$-th root of unity $\omega$ in a $GF(p)$, then

$\omega ^0 = -\omega ^{n/2} + p,$

$\omega ^1 = -\omega ^{n/2 + 1} + p,$

$...$

$\omega ^{n/2 - 1} = -\omega ^{n-1} + p.$

Or, maybe, I could rewrite it as

$\omega ^i \equiv \omega ^ {n/2 + i} \mod p \quad \forall i=1..n/2-1$.

Does it always hold? Why? Does it hold under stronger conditions (e.g. for all even $n$, not just $n = 2^k$)?

Thank you very much in advance!

-

In $GF(p)$ we have characteristic $p$ so the $+p$ appended at the end of each equation is superfluous.

Otherwise notice that each of the subsequent equations follow by multiplying the first equation by a power of $\omega$. It suffices therefore to demonstrate the first equation.

Since $\omega^n=1$ and $n$ is even, factoring yields $(\omega^{n/2}+1)(\omega^{n/2}-1)=0$. Because this is a field and so has no zero divisors, we find that $\omega^{n/2}=\pm1$, but $\omega^{n/2}=+1$ would contradict the hypothesis that $\omega$ is a primitive root of unity, so we must have $\omega^{n/2}=-1$. Note this works for any even $n$.

-
A brilliant clarification. Thanks a lot! – wh1t3cat1k Apr 22 '12 at 9:33