# When an exponential congruence has solution

I need help proving the following:

Let $a\neq \pm1$ be an integer which is not divisible by an odd prime p. Let $d$ be the order of $a$ modulo $p$ and let $k_0$ be the largest integer such that $a^d=1$ mod $p^{k_0}$. Prove that if $k\geq{k_0}$ is a solution of the exponential congruence $a^k=1$ mod $p^k$ then $$\frac{p^k}{k}\leq \frac{a^d}{d}$$ I don't know how to relate the result with the solution of the equation.

I note in the following $v_p(x)$ for the $p$-adic valuation of $x$, i e $x=x_1 p^{v_p(x)}$ with $p$ not dividing $x_1$
1) Suppose you have $m, q$ such that $v_p(a^m-1)=q\geq 1$. Then for any $n\geq 1$, you have $v_p(a^{mn}-1)=q+v_p(n)$. To see that, first take $n=p$, and putting $a^m=1+up^q$ with $p$ not dividing $u$, write $$a^{mp}=(1+up^q)^p=1+{p \choose 1}up^q+\cdots$$. You have hence the result for $n$ a power of $p$. Now take $n$ prime to $p$, and use the same way.
2) Now you have $d|k$, as $k\geq k_0$, and hence $a^k$ is congruent to $1$ modulo $p^{k_0}$. Put $k=dk_1$, by the above we get $v_p(a^k-1)=k_0+v_p(k_1)$. So $k_0+v_p(k_1)\geq k$, and we get $$p^k \leq p^{k_0}p^{vp(k_1)}$$
As $p^{k_0}\leq a^d-1\leq a^d$ and $p^{vp(k_1)}\leq k_1=\frac{k}{d}$, we are done.