Primitive Roots of Unity and GCD

Quote:

Originally Posted by meggnog

We say a complex number z is a primitive nth root of unity if $z^n=1$ but $z^m\neq1$ for 0<m<n. Show that $\omega^k$ is a primitive nth root of unity if and only if gcd(k,n)=1.

$(\Longrightarrow)$ Assume $g=(a,b)>1 \implies \frac ng < n$ and suppose $k=gd$ . $\left(\omega^k\right)^{n/g} = \omega^{dgn/g} = \left(\omega^n\right)^d = 1$ . Thus $\omega^k$ is not primitive.

$(\Longleftarrow)$ If $(k,n)=1$ and $i<n$ , then $ki=dn+r$ where $0\leq r<n$ . Thus $\omega^{ki} = \omega^{dn}\omega^r = \omega^r\neq1$ . So we see $\omega^k$ is primitive.