Prove by contradiction using division algorithm Let $z$ be a primitive $n$-th root of unity. Prove that for any $k\in\mathbb{Z}$, if $z^k=1$, then $n \mid k$.
 A: We start a proof by contradiction by accepting the premise: 

Let $z$ be a primitive n-th root of unity. For $k\in \mathbb Z$, suppose $z^k = 1$.

Then we suppose, for the sake of contradiction, that the desired conclusion is false:

Suppose $n \not \mid k$.

Then we see where those givens and the supposition take us:
By the division algorithm we can express $k$ as such: there exists a unique integer $m$ and $r$ such that $k = nm + r$, where $0 \lt r \lt n$. Then prove that this leads to the fact that $$z^k = 1 \iff = z^{nm+ r} = 1 \iff z^{nm}z^r =1 \iff z^r = 1$$ which contradicts the fact that $n$ must be the smallest positive integer such that $z^n=1$
A: Hint $\rm\ \ z^K = 1 = z^N\:\Rightarrow\: z^{\,K\ mod\ N} = 1\ \ [\ \cdots\, \Rightarrow\: Z^{gcd(K,N)} = 1]$
Remark $\ $ More generally, any nonempty set $\rm\:S\ne \{0\}\:$ of integers closed under subtraction has the form $\rm\: d\,\Bbb Z,\:$ where $\rm\:d\:$ is the least positive element or, equivalently, $\rm\:d = gcd(S).\:$ In the above case where $\rm\:S = \{n\in\Bbb Z\,:\, z^n = 1\},\:$ we call $\rm\:d\:$ the order of $\rm\:z.$ The inductive proof is essentially the Euclidean algorithm, i.e. $\rm\:S\:$ closed under remainder (mod) $\rm\:\Rightarrow\:S\:$ closed under gcd. In fact it suffices for $\rm\:S\:$ to be closed under subtraction, since the remainders arise by iterated subtraction (the Division Algorithm). This essence of the matetr will be clarified when one learns about ideals, e.g order ideals (e.g. as above), and denominator ideals.
