Exercise involving DFT

Solution 1:

Hint:

You need to use the fact that $\ n\ $ is a power of $\ 2\ $. I believe a key observation is that because $\ c\ $ is odd, it is a unit in the ring of integers mod $\ n=2^r\ $ (for some positive integer $\ r\ $), and so, as $\ k\ $ ranges from $\ 0\ $ to $\ 2^r-1\ $ in the sum $$ \hat{\omega}_{cf}=\sum_{k=0}^{2^r-1}e^\frac{2\pi i kcf}{2^r}v_{ck+d\pmod{2^r}}\ ,\\ $$ the residues of $\ ck\ $ mod $\ 2^r\ $ will range over the same set of values, but in a different order. For each $\ k\in\big\{0,1,\dots,$$2^r-1\big\}\ $ there is a (unique) integer $\ u_k\ $ with $\ 0\le$$ u_k\le $$2^r-1\ $ such that $\ ck=u_k + z_k2^r\ $ for some integer $\ z_k\ $, and $\ u\ $ will be a permutation on the set of integers $\ \big\{0,1,\dots,2^r-1\big\}\ $. We then have \begin{align} \sum_{k=0}^{2^r-1}e^\frac{2\pi i kcf}{2^r}v_{ck+d\pmod{2^r}}&=\sum_{k=0}^{2^r-1}e^\frac{2\pi i \left(u_k+z_k2^r\right)f}{2^r}v_{u_k+z_k2^r+d\pmod{2^r}}\ ,\\ &=\sum_{k=0}^{2^r-1}e^\frac{2\pi iu_kf}{2^r}v_{u_k+d\pmod{2^r}}\ ,\\ &=\sum_{t=0}^{2^r-1}e^\frac{2\pi itf}{2^r}v_{t+d\pmod{2^r}}\ , \end{align} the last expression being obtained by rearranging the order of summation.