# Question regarding a step in the computation of $QFT_{16} \frac{1}{2} ( \mid 1 \rangle + \mid 5 \rangle + \mid 9 \rangle + \mid 13 \rangle )$

In clas we computed the Quantum Fourier Transformation $$QFT_{16} \frac{1}{2} ( \mid 1 \rangle + \mid 5 \rangle + \mid 9 \rangle + \mid 13 \rangle )$$. We started with the following computation:

\begin{align} \text{QFT}&_{16}{\frac{1}{2} \left( \mid 1 \rangle + \mid 5 \rangle + \mid 9 \rangle + \mid 13 \rangle \right)} \\ &= \frac{1}{8} \sum_{k=0}^{15} \omega_{16}^{k} \left( 1 + \omega_{16}^{4k} + \omega_{16}^{8k} +\omega_{16}^{12k} \right) \mid k \rangle \\ &= \frac{1}{8} \sum_{k=0}^{15} \omega_{4}^{k} \left( 1 + \omega_{4}^{k} + \omega_{4}^{2k} +\omega_{4}^{3k} \right) \mid k \rangle \end{align}

However, I do not understand the second equation. I know that $$\omega_{n}^{2k} = \omega_{n/2}^k$$, but I do not understand why $$\omega_{16}^{k}$$ becomes $$\omega_{4}^{k}$$. Could you please explain this to me?

Remark: $$\omega_n$$ denotes the $$n$$-th root of unity.

We have: $$\omega_n^k=\mathrm{e}^{\frac{2\mathrm{i}\pi k}{n}}$$ As such, for any $$p\in\mathbb{N}^*$$: $$\omega_n^{pk}=\mathrm{e}^{\frac{2\mathrm{i}\pi pk}{n}}=\mathrm{e}^{\frac{2\mathrm{i}\pi k}{\frac{n}{p}}}=\omega_{\frac{n}{p}}^k$$ Thus, we have: $$\omega_{16}^{4k}=\omega_{\frac{16}{4}}^{k}=\omega_{4}^{k}$$ The same formula can be applied to the two other terms to find the correct result.