Just to help your intuition in support of @lhf's and @anon's answers...
Are you aware of the formula (for positive integers $n$) $ n = \sum_{0 where $\phi(n)$ is Euler's totient function? It's basically giving you a breakdown of how many $n$th roots of unity there are which are primitive $d$th roots of unity for each $d$ dividing $n$ (there are $\phi(d)$).
For example, of the six sixth roots of unity, one has order $1$, one order $2$, two have order $3$, and two have order $6$: $\phi(1)=\phi(2)=1$ & $\phi(3)=\phi(6)=2$. Try drawing them on the unit circle.
So with this intuition, we need to show that the order $d$ of $\zeta=e^{2\pi ik/n}$ is $n$ iff $k$ & $n$ are relatively prime, i.e. iff their gcd $g=(k,n)$ is $1$. However, note that for $t=n/g$, $\zeta^t=e^{2\pi ik/g}=1$ since $g|k$, so that $g>1$ implies that the $ord(\zeta)|t, i.e. that $\zeta$ is not a primitive $n$th root but rather a primitive $t$th root of unity, where $t$ is a proper divisor of $n$.