- #1

Albert01

- 14

- 0

I have a question about the FFT and would like to share my thoughts with you. The background is a problem 30.2-6 from the legendary algorithms book by Cormen.

It says that instead of doing an n element FFT over the field of complex numbers, we can use ##\mathbb{Z}_m##, where ##m = 2^{t \cdot n/2}## and t is a positive integer. So we can use ##\omega = 2^t## instead of ##\omega_n## as the nth unit root modulo m.

First, we can note that all ##2^t,2^{2t},...,2^{t \cdot n/2}## are all distinct, so far clear. But how can we determine that all powers of ##\omega## are different? I found the following approach to this, which I first state and then ask my question about it: for ##1 \leq k < n/2## (why ##<## and not ##\leq## ?), ##2^{kt}2^{nt/2}## is equivalent to ##-2^{kt}## which is respectively ##2^{nt/2}+1-2^{kt}## and this is odd (why is this important?) and one conclude that all powers of ##\omega## are different (why?).

Now why does it just follow that if this is odd that the powers are different? would like to understand what this "odd" means in this context.

Thanks!