Number Theoretic Transform (NTT) principal root of unity modulo a prime

Question

I'm not sure why a certain Number Theoretic Transform (NTT) works. Suppose the following:

• Let $n = 2^c$ with integer $c > 0$.
• Let $k$ be the smallest integer such that $p = nk + 1$ is prime.
• Let $g$ be a generator of $Z_p^\star$, the multiplicative group mod $p$.

One example has $n=4$, $k=1$, $p=5$, and $g=2$, since the powers of 3 (mod 5) are $3,4,2,1,3\ldots$.

Consider

$$ S_m = \sum_{j=0}^{n-1} g^{kmj} = \frac{g^{kmn} - 1}{g^{km} - 1} = \prod_{\ell = 0}^{c-1}\left( g^{2^\ell km} + 1\right) $$

It is claimed in the book CLRS that $S_m$ is divisible by $p$ for $m = 1,2 \ldots n-1$, i.e. $g^k$ is a principal root of unity, and thus it can be used to construct a "unitary" DFT matrix for the NTT.

It's unclear to me how to prove this claim.

Answer 1

For any $p$ prime and $k | p-1$

$g$ has order $p-1$ so $g^k$ has order $(p-1)/k$

For $m\not \equiv 0\bmod (p-1)/k$ then $$g^{km} S_m = S_m \implies (g^{km}-1)S_m=0\implies S_m=0$$