uncertain orthogonality of discrete Fourier transform on the ring of integers modulo some number

Update: I corresponded with one of the authors of CLRS, and he confirmed that the problem indeed should say "$n$ is a power of two", not "$n$ is even".

Original question:

CLRS Exercise 30.2-6 claims that for any positive even $n$ and positive integer $t$, a discrete Fourier transform can be defined on the ring of integers modulo $m = 2^{tn/2} + 1$, using $w = 2^t$ as the principle $n$th root of unity.

Wikipedia seems to say that if $w$ is a principal $n$th root of unity, then for $1 \leq k < n$, we must have

$$ T_k = \sum_{j=0}^{n-1} w^{jk} = 0 \mod m $$

However, choosing $n = 6$ and $t = 3$, we have $m = 513$ and $w = 8$, and it's easy to see that $T_2 = 114 \mod m$. Isn't this supposed to be zero? If yes, where have I gone wrong above?

Solution 1:

Given any $m$ and $w\in \Bbb{Z/mZ}^\times$ of order $n$, the necessary and sufficient condition for $T_0 \in \Bbb{Z/mZ}^\times$ and $T_1=\ldots=T_{n-1}=0$ is that $\gcd(n,m)=1$ and for each $k\ne 0\bmod n, w^k-1$ is a unit ie. for each prime $p| m$, $w\bmod p$ has order $n$.

If $\gcd(n,m)\ne 1$ then $T_0$ is not a unit.
If each $w^k-1$ is a unit then $w^{nk}-1=0$ implies $T_k=\frac{w^{kn}-1}{w^k-1}=0$.
If $w^k-1$ is not a unit then $w^k=1\bmod p$ for some $p|m$ thus $T_k = n\ne 0 \bmod p$
If for each prime $p| m$, $w\bmod p$ has order $n$ then each $w^k-1$ is a unit.
If for some prime $p| m$, $w\bmod p$ has order $k<n$ then $w^k-1$ is not a unit.