# Primitive Roots of Unity and GCD

• Jul 1st 2010, 03:18 PM
meggnog
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.
• Jul 1st 2010, 05:43 PM
chiph588@
Quote:

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.