# Math Help - Primitive Roots of Unity and GCD

1. ## Primitive Roots of Unity and GCD

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.

2. 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, then $ki=dn+r$ where $0\leq r. Thus $\omega^{ki} = \omega^{dn}\omega^r = \omega^r\neq1$. So we see $\omega^k$ is primitive.