Quantum Fourier Transform and roots of unity. I need to find $QFT_{6}$ for the state quantum state $\frac{1}{\sqrt2}(|0\rangle + |3\rangle)$. I received a very sufficient answer recently on simplifying nth roots of unity, but I am having a lot of trouble applying it to this problem. I have obtained the $QFT_6$ matrix below, and multiplied it by the shown state:
$$
\begin{pmatrix} 
  \frac{1}{\sqrt6} & \frac{1}{\sqrt6} & \frac{1}{\sqrt6} & \frac{1}{\sqrt6} & \frac{1}{\sqrt6} & \frac{1}{\sqrt6}\\
  \frac{1}{\sqrt6} & \frac{1}{\sqrt6}\omega & \frac{1}{\sqrt6}\omega^2 & \frac{1}{\sqrt6}\omega^3 & \frac{1}{\sqrt6}\omega^4 & \frac{1}{\sqrt6}\omega^5\\
  \frac{1}{\sqrt6}  & \frac{1}{\sqrt6}\omega^2 & \frac{1}{\sqrt6}\omega^4 & \frac{1}{\sqrt6}\omega^6 & \frac{1}{\sqrt6}\omega^8 & \frac{1}{\sqrt6}\omega^{10}\\
  \frac{1}{\sqrt6}  & \frac{1}{\sqrt6}\omega^3 & \frac{1}{\sqrt6}\omega^6 & \frac{1}{\sqrt6}\omega^9 & \frac{1}{\sqrt6}\omega^{12} & \frac{1}{\sqrt6}\omega^{15}\\
  \frac{1}{\sqrt6}  & \frac{1}{\sqrt6}\omega^4 & \frac{1}{\sqrt6}\omega^8 & \frac{1}{\sqrt6}\omega^{12} & \frac{1}{\sqrt6}\omega^{16} & \frac{1}{\sqrt6}\omega^{20}\\
  \frac{1}{\sqrt6}  & \frac{1}{\sqrt6}\omega^5 & \frac{1}{\sqrt6}\omega^{10} & \frac{1}{\sqrt6}\omega^{15} & \frac{1}{\sqrt6}\omega^{20} & \frac{1}{\sqrt6}\omega^{25}\\
\end{pmatrix}
\begin{pmatrix}
  \frac{1}{\sqrt2}\\
  0 \\
  0 \\
  \frac{1}{\sqrt2}\\
  0 \\
  0 
\end{pmatrix}
$$
Right, well now I don't understand how to just express all of the omegas in terms of $\omega$ and $\omega^2$. Help would be much appreciated.
 A: Position a regular hexagon on the unit circle with vertices at $\pm1$. Let $\zeta$ be the first complex root of unity counterclockwise from $1$. Then $\zeta^2$ is a third full rotation away from $1$, in other words it is a third root of unity. And $\zeta^3=-1$ since it sweeps out exactly half a rotation. Algebraically speaking we know $(\zeta^3)^2=1$ and $\zeta^3\ne1$ (since $\zeta$ is a primitive $6$th root) so $\zeta^3=-1$.
This tells us that $\zeta^4=-\zeta$ and $\zeta^5=-\zeta^2$. We already know $\zeta^6=1$. Can $\zeta^2$ be reduced?
Indeed it can. The theory of cyclotomic polynomials tells us that
$$\Phi_6(x)=\frac{(x^6-1)(x-1)}{(x^3-1)(x^2-1)}=\frac{x^3+1}{x+1}=x^2-x+1.$$
So $\zeta^2=\zeta-1$. Thus all of $\zeta^2,\zeta^3,\zeta^4,\zeta^5,\zeta^6$ can be written in the form $a+b\zeta$ with these relations.
One can also argue $\zeta^2=\zeta-1$ with a more geometric toolkit. Looking at the hexagon it is clear that $\zeta^2$ bisects the vectors representing $-1$ and $\zeta$, so $\zeta^2=r(\zeta-1)$ already; at this stage one shows $\zeta-1$ has modulus $1$ so $r=1$ hence $\zeta^2=\zeta-1$.
Finally with the cycling $1=\zeta^6=\zeta^{12}=\zeta^{18}=\cdots$ you should have all you need.
