If p is prime and k is the smallest positive integer such that a^k=1(modp), then prove that k divides p-1 I know you need to use the Division Algorithm but I don't know where to start.
 A: You know that $a^{p-1} = 1 \pmod{p}$. So $k$ is certainly at most $p-1$. 
Now do division with remainder to get $(p-1) = qk + r$ with $0 \le r <k$. You need to show $r=0$.
Then $a^{p-1} = a^{qk +r} = (a^k)^q a^r$.
Now use  $a^{p-1}$ and $a^k$ are $1$ modulo $p$ to get $a^r$ is also $1$ modulo $p$, and continue from there.
A: Let $k$ be the smallest positive integer for which $a^k \equiv 1 \bmod p$.
By Fermat Little Theorem, $k\le p-1$. If $k=p-1$, we are done, otherwise find the largest multiple of $k, jk$ that is less than $p-1$. 
Now let $m=(p-1)-jk \le k$. If $m=k$ then $(j+1)k = p-1$ and we are done. Otherwise if $m<k$ then since we have $a^{p-1} \equiv 1 $ and $a^{jk} \equiv 1^j \equiv 1 \bmod p$, then also $a^m \equiv 1 \bmod p$, which contradicts our definition of $k$.
Therefore $k$ divides $p-1$.
A: A slight amount of abstraction lends further insight to the innate arithmetical structure. 
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}\qquad $$
So, by the 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 $\ {\bf 1}\  $ 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. \, $ 
Proof ${\bf\ 2}\,\rm\ \ \cal O\,$ closed under subtraction $\rm\,\Rightarrow\,\cal O\,$ closed under remainder (mod), when it is $\ne 0,$ since mod may be computed by repeated subtraction: $\rm\, a\ mod\ b\, =\, a - k b\, =\, a-b-b-\cdots -b.\,$ Thus $\rm\,n\in \cal O\,$ $\Rightarrow$ $\rm\, (n\ mod\ \ell) = 0,\,$ else it is $\rm\,\in \cal O\,$ and smaller than $\rm\,\ell,\,$ contra mimimality of $\rm\,\ell.$ 
Remark $\ $ In a nutshell, two applications of induction yield the following inferences
$  \rm\begin{eqnarray} {\cal O}\ closed\ under\ {\bf subtraction}\! &\Rightarrow\:&\rm {\cal O}\ closed\ under\ {\bf mod} = remainder = repeated\ subtraction \\
&\Rightarrow\:&\rm {\cal O}\ closed\ under\ {\bf gcd} = repeated\ mod\ (Euclid's\ algorithm) \end{eqnarray}$
Interpreted constructively, this yields the extended Euclidean algorithm for the gcd. 
For more on the key innate structure  see this post on order ideals and denominator ideals.
