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!