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$.