# Thread: 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 $\displaystyle z^n=1$ but $\displaystyle z^m\neq1$ for 0<m<n. Show that $\displaystyle \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 $\displaystyle z^n=1$ but $\displaystyle z^m\neq1$ for 0<m<n. Show that $\displaystyle \omega^k$ is a primitive nth root of unity if and only if gcd(k,n)=1.
$\displaystyle (\Longrightarrow)$ Assume $\displaystyle g=(a,b)>1 \implies \frac ng < n$ and suppose $\displaystyle k=gd$. $\displaystyle \left(\omega^k\right)^{n/g} = \omega^{dgn/g} = \left(\omega^n\right)^d = 1$. Thus $\displaystyle \omega^k$ is not primitive.

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