Our goal is to prove that $\operatorname{order}(\overline a)=\frac{n}{k}$, where $k=\gcd(a,n)$, and where $1\leq a\leq n$.

We've shown that for any $t$ that divides $n$, it holds that $\operatorname{order}\overline t=n/t$. Now I have to show that $\operatorname{order}(\overline{mk})=\operatorname{order}(\overline k)$, for any $m\in\mathbb Z$. The harder part is in showing that it can't be true that $\operatorname{order}(\overline{mk})<\operatorname{order}(\overline k)$. Assume the inequality holds, and that $\operatorname{order}(\overline{mk})=l$ and $\operatorname{order}(\overline k)=r$. …