Proving that if $a^n \equiv 1 \pmod m$ then $d\mid n$ I'm having some trouble proving the following:

Let $d$ be the smallest positive integer such that $a^d \equiv 1 \pmod m$, for $a \in \mathbb Z$ and $m \in \mathbb N$ and with $\gcd(a,m) = 1$. Prove that, if $a^n \equiv 1 \pmod m$ then $d\mid n$.

The first thing that came to my mind was Euler's theorem but I couldn't conclude anything because I'm not very skilled when it comes to using Euler's totient function. Can someone give me any tips or show me how to solve this?
 A: Hint:
Prove the contrapositive assertion: if $d$ does not divide $n$, $d$ is not the smallest positive integer such the $a^d\equiv 1 \bmod n$.
Note: actually, it is a particular case of a more general assertion: for an element $g$ of finite order  in a group , the set $\bigl\{n\in\mathbf Z\::\: a^n=1\bigr\}$ is an ideal of $\mathbf Z$, and as $\mathbf Z$ is a P.I.D.…
A: Let $n = dq + r$ with $0 \le r < d$, then
$$
a^r \equiv a^{dq+r} \equiv a^n \equiv 1 \pmod m
$$
which means that $r = 0$ since otherwise we have a contradiction with the fact that $d$ is the $smallest$ positive integer such that $a^d \equiv 1 \pmod m$.
A: Let us try a constructive proof (also):
Firstly, an edge case: If $d=1$, we know that $a\equiv 1$ and $a^n \equiv 1 \bmod m$ for any $n$, and also that $1\mid n$ always, so the assertion is true in this case.
So otherwise we know that $a^0 \equiv 1, a^1\equiv a \bmod m$ and that $d$ is defined such that not only $a^d\equiv 1 \bmod m$ but also that $a^k \not\equiv 1 \bmod m$ for $1\leq k<d$.
Now consider the value of $a^n \bmod m$, where $n>d$, since the assertion is true by definition for smaller $n$. Find the closest multiple of $d$ no greater than $a$ and the residue so that $n=bd+c$, with $c<d$. Now $a^n \equiv a^{bd+c} \equiv a^{bd}\cdot a^c \equiv  (a^d)^b\cdot a^c \equiv 1^b\cdot a^c \equiv a^c\bmod m$. Now since $c<d$, the only value for which $a^c\equiv 1 \bmod m$ is $c=0$, in which case $n=bd$; that is, $a^n\equiv 1 \bmod m \implies d\mid n$ as required.
A: It easy to to see the if $a^d\equiv 1 \pmod m$ then for any multiple of $kd$ of $d$ we have $a^{kd}\equiv (a^d)^k\equiv 1^k \equiv 1 \pmod m$.
So we have to prove that if $n$ is not a multiple of $d$ and $a^n\equiv 1$ is impossible.
If $d\not \mid n$ then $kd < n < (k+1)d$ for some $k$.
So we need a way to either prove directly that $a^n\not \equiv 1 \pmod n$ or athat if $a^n\equiv 1\pmod m$ we can contradict that $d$ is the least such positive integer.
Hint:

And if we consider that if $kd < n < (k+1)d$ then $n = kd + r$ for some $r:  0 < r < d$

And with that hint:

 And $a^n \equiv a^{kd+r} \equiv a^{kd}a^r\equiv a^r\pmod m$.
 And $0< r < d$ so $a^n \equiv a^r \not \equiv 1$.

And that's that.
