Let $p$ be a prime and $a$ be an integer such that $p$ does not divide $a$. Suppose $d$ is the smallest positive integer such that $a^d ≡ 1 \ ($mod$ \ p)$. Prove that $d|(p−1)$.
So far I've written the hypothesis out by using the definition of congruences, but I don't know how to show that $d|(p−1)$.
Any help on how to start would be appreciated.
Hint: There are integers $q$ and $r$, with $0\le r\lt d$, such that $p-1=qd+r$.
Use Fermat's Theorem and the minimality of $d$ to conclude that $r=0$.
Added: From $p-1=qd+r$, we conclude that $$a^{p-1}=a^{qd}a^r=(a^d)^q a^r\tag{1}.$$ By Fermat's Theorem, we have $a^{p-1}\equiv 1\pmod{p}$. By assumption, we have $a^d\equiv 1\pmod{p}$, and therefore $(a^d)^q\equiv 1\pmod{p}$. Thus it follows from (1) that $$a^r\equiv 1\pmod{p}.\tag{2}$$ Recall that by definition $d$ was the smallest positive integer $t$ such that $a^t\equiv 1\pmod{p}$. Since $r\lt d$, and by (2) we have $a^r\equiv 1\pmod{p}$, we conclude that $r=0$. Thus $p-1=qd$, and therefore $d$ divides $p-1$.