Let p be a prime and k a positive integer such that $a^k$mod p = a mod p for all integers a. Prove that p - 1 divides k - 1. 
Let p be a prime and k a positive integer such that $a^k$mod p = a mod
  p for all integers a. Prove that p - 1 divides k - 1.

I think I need to use Fermat's Little Theorem, and I can get  $a^k$mod p =  $a^p$mod p, and I think it follows that  $a^{k-1}$mod p = $a^{p-1}$mod p = 1, but from there I'm stumped. 
I think it follows that $a^{k-1}$ = m$a^{p-1}$, but why couldn't m be a fraction, i.e. k - 1 divides p - 1 but not the other way around?
 A: The OP's solution is incorrect.  This deduction is flawed: 

"Multiplying both sides by $a^{k-1}$
$$a^{k-1}({a^{p-1}})^m=1a^{k-1} \implies a^{(k-1)+m(p-1)}=a^{k-1} \implies (k-1)+m(p-1) = k-1$$
  by the definition $x$ mod $(p-1)$".

Here is a different approach.  Let $k-1=(p-1)q+r$ for some non-negative integers $q$ and $r$ with $r<p-1$.  If $r\neq 0$, then we have by Fermat's little theorem that
$$a^{r+1}\equiv a^{r+(p-1)q+1}= a^{k}\equiv a\pmod{p}.$$
Therefore, the polynomial $x^{r+1}-x$ is of degree $r+1<p$, but it has $p$ roots in the Galois field $\operatorname{GF}(p)$.  This is impossible, so $r=0$ must be the case.
A: Another proof would be to consider the group $U(p)$ of multiplicative units in $\mathbb Z / p \mathbb Z$.  For $p$ prime the order of $U(p)$ is $p-1$.  Since $p$ is prime, $U(p)$ is cyclic (see Keith Conrad's exposition) and so it has elements of all orders $d$ dividing $p-1$.
If $a$ is such an element of order $d$ then our hypothesis is that $a^{k-1} \equiv 1 \mod p$, and so $|a|=d$ divides $k-1$.  So any divisor of $p-1$ is a divisor of $k-1$, hence $p-1$ divides $k-1$.
This avoids Galois theory, unless of course you used Galois theory to prove that $U(p)$ is cyclic.  But that can be avoided because all we really needed was that $U(p)$ has an element of order $q$ for each prime $q$ dividing $p-1$, which is guaranteed by Cauchy's theorem.
A: I figured out my own question. Here is is for anyone else that wants to know (maybe my classmates...)
By FML, $a^p=a$ mod $p$.
$a^p$ mod $p=a$ mod $p$
multiplying both sides by $a^{-1}$ we get:
$a^{-1}a^p=a^{-1}a$ $\implies$ $a^{p-1}=1$.
$a^{p-1}=1$ (mod $p$)
Taking each each side to the m$^{th}$ power:
$({a^{p-1}})^m=1^m \implies ({a^{p-1})}^m=1$  
Multiplying both sides by $a^{k-1}$
$a^{k-1}({a^{p-1}})^m=1a^{k-1} \implies a^{(k-1)+m(p-1)}=a^{k-1} \implies (k-1)+m(p-1) = k-1$
by the definition $x$ mod $(p-1)$ iff $x=q(p-1)+r$, so
$(k-1)+m(p-1) = k-1 \implies (k-1)$ mod $(p-1)=k-1$
By hypothesis we have $a^k$=a mod p. Like in the beginning,
$a^k$=a mod p $\implies$ $a^{-1}a^k$= $a^{-1}$a mod p $\implies$ $a^{k-1}$ = 1 mod p
Substituting $(k-1)$ mod $(p-1)$ for $k-1$ we get:
$a^{(k-1) \textrm{ mod } (p-1)} = 1$ mod $p = a^0$ mod $p= a^{0\textrm{ mod }(p-1)}$mod $p$
so, $(k-1)$ mod $p = 0 $mod $p$
By definition, this means that
$(k-1)=m(p-1)$, i.e. that $p-1$ divides $k-1$. $\square$
