Suppose that $gcd(a,n)= 1$. Prove that $a^m \equiv 1 \pmod n$ iff $ord(a,n) \mid m$ Here is my attempt.
Suppose we have  $a^m \equiv 1 \pmod n$ and assume that $ord(a,n) = k$ (order of $a)$ and so since $k = ord(a,n)$
it follows that $k \leq m$ .
Now if $k = m$ then we are done but now assume that $k < m$ and it also follows that  $a^k \equiv 1 \pmod n$. Hence we do have that  $a^m \equiv a^k \pmod n$ which means that 
$n \mid a^m - a^k$ and so $n | a(a^{m-1} - a^{k-1})$, however since $gcd(a,n) = 1$ then we know that $n \mid a^{m-1} - a^{k-1}$ and eventually since we have $k < m$ we can keep doing that until we have $n \mid a^{m-k} - 1$.
but how do I conclude form here that $k \mid m$  or is there another simpler method ?
For the converse statement (other implication , it's trivial)
Suppose that $ ord(a,n) \mid m$ 
so again let $k = ord(a,n)$ then there exists an integer $t$ such that $kt = m$
then since $a^k\equiv 1 \pmod n$ then $a^{kt} \equiv 1 ^{t} \pmod n$ and so $a^m \equiv 1 \pmod n$ . So I am just stuck in the first implication 
 A: If $k<m$ apply Euclidean division to write $m=qk+r$. Then $a^m\equiv a^r\equiv1$, but $r<k$, and this implies $r=0$.
A: The set $\,\cal O\,$ of integers $\rm\:n >0\:$ such that $\rm\:a^n \equiv 1\:$ is closed under positive subtraction, i.e.
$$\rm \color{#0A0}n>\color{#C00}m\,\in\,{\cal O}\ \Rightarrow\ 1\equiv \color{#0A0}{a^n} \equiv a^{n-m}\, \color{#C00}{a^m} \equiv a^{n-m}\, \Rightarrow\ n\!-\!m\,\in\,{\cal O}$$
Thus, by theorem below, every element of $\rm\,\cal O\,$ is divisible by its least element $\rm\:\ell\ \! $ := order of $\rm\,a.$
Theorem $\ \ $ If a nonempty set of positive integers $\rm\,\cal O\,$ satisfies $\rm\ n > m\, \in\, {\cal O} \ \Rightarrow\  n\!-\!m\, \in\, \cal O$
then every element of $\rm\,\cal O\,$ is a multiple of the least element $\rm\:\ell \in\cal O.$
Proof $\  $ If not there's a least nonmultiple $\rm\:n\in \cal O,\:$ contra  $\rm\:n\!-\!\ell \in \cal O\:$ is a nonmultiple of $\rm\:\ell. \, $ 
See here for elaboration on the Theorem, and for more on the key innate structure  see this post on order ideals and denominator ideals.
