For which values of $k$, $0\leq k \leq n-1$, is $e^{i2πk/n}$ a primitive nth root of unity? I know that the $n$-th root of unity is a primitive nth root of unity if, and only if, $k$ is relatively prime to $n$, but how do you prove it?
 A: Note that the group $\mathbb G_n$ of the $n$ roots of unity is a group with respect to complex multiplication. In particular, it is cyclic of order $n$. In any group $G$ and for any $a\in G$,$|a|<\infty$, and $r$ we have that $$|a^r|=\frac{|a|}{(r,|a|)}$$
It follows that $|a^r|=|a|\iff (r,|a|)=1$, that is $\langle a^r\rangle=\langle a\rangle\iff (|a|,r)=1$. Note then that $\mathbb G_n=\langle e^{\frac{2\pi i}n}\rangle$, and $\langle \zeta\rangle =\Bbb G_n\iff \zeta$ is a primitive $n$ root of unity. 
NOTE If $a\in G$; $|a|$ denotes the order of $a$, that is, the smallest positive integer $n$ such that $a^n=e$. It might also be noted as $o(a)$.
A: Hint: The proof consists of two parts: (i) If $k$ and $n$ are not relatively prime, then $\exp(2\pi k/n)$ is not a primitive $n$-th root of unity and (ii) if $k$ and $n$ are relatively prime, then $\exp (2\pi i k/n)$ is a primitive $n$-th root of unity. 
For (i), suppose that $d\gt 1$ divides both $k$ and $n$. Let $k=dk'$ and $n=dn'$. Show that $\left(\exp(2\pi i k/n)\right)^{n'}=1$. 
For (ii), the easiest way is to use Bezout's Theorem, which says that if $a$ and $b$ are relatively prime, then there exist integers $x$ and $y$ such that $ax+by=1$.
So there are integers $x$ and $y$ such that $kx+ny=1$. 
It follows that 
$$\left(\exp(2\pi i k/n)\right)^x \left(\exp(2\pi i k/n)\right)^{ny}=\exp(2\pi i /n)  .$$
So a power of $\exp(2\pi i k/n)$ is equal to the primitive root $\exp(2\pi i/n)$, and therefore all $n$-th roots of unity can be expressed as powers of $\exp(2\pi i k/n)$. 
A: Recall that $\omega$ is a primitive $n$th root of unity iff $\omega^n=1$ and $\omega^j \neq 1$ for $j \in I = \{1,...,n-1\}$.
Let $\omega_k = e^{i 2 \pi \frac{k}{n}}$. We note that $\omega_k = 1$ iff $k = 0 \mod n$. Furthermore, $\omega_k^j = \omega_{jk}$.
Then $\omega_k$ is a primitive $n$th root of unity iff $\omega_k^j \neq 1$, for $j \in I$ iff $\omega_{jk} \neq 1$ for all $j \in I$ iff $jk \neq 0 \mod n$ for all $j \in I$.
Let $d=\gcd(k,n)$.
I claim that $d = 1$ iff $jk \neq 0 \mod n$ for all $j \in I$. 
($\Rightarrow$) Suppose $d=1$ and for some $J \in I$ that $jk = 0 \mod n$. Then $jk = ln$ for some $l$. Since $n \mid ln$, we have $n \mid jk$ and since $d=1$, we have $n \mid j$, which contradicts $j \in I$.
($\Leftarrow$) Suppose $d>1$ and $jk \neq 0 \mod n$ for all $j \in I$, then $\frac{n}{d} \in I$, and $\frac{n}{d}k = \frac{k}{d} n$, hence $\frac{n}{d}k = 0 \mod n$, again a contradiction.
Hence the above chain of equivalences gives $\omega_k$ is a primitive $n$th root of unity iff $d=1$.
