Reducing modulo powers of a prime If p is an odd prime and a is coprime to p, how would one go about reducing $a^{p^{k-1}}\mod p^k$? Using Euler's formula we can get a value for $a^{p^{k-1}(p-1)}\mod p^k$ but I can't really see how this is all that helpful...
For example how would you reduce $3^{625}\mod 5^5$?
 A: Euler's theorem is not really useful in this case because $p^{k-1}\leq \varphi(p^k)$ as your question pointed, because we are dealing with an element of a group so the proprieties of this element depends in his order and not much of the order of the group. Notice that calculating a power $\mod p^k$ is not really difficult in term of computation even for big numbers. for example the order $x$ of an element can be found  in $1+4\sqrt{x}+log(x)$ operations.
Your question can be solved by computing :$3 \mod 5^5$ , $3^5 \mod 5^5$ ,$(3^5)^5 \mod 5^5$ $ \cdots \cdots$ by computing each time the $5$th power of the result.
Mathematically speaking, the order of an element is very hard to find (there is no useful expression which gives the order of an arbitrary element $a$) . If we return to your question finding $a^{p^{k-1}}\mod p^k$ can be done using the following important result:

Theorem (Lifting The Exponent Lemma):
Given an positive integer $p$ (not necessarily a prime),If there exist two integers $n\leq m$ such that $a^{p^{m-n}}\equiv 1 \mod p^m $
then for all $k\geq m$ we have $a^{p^{k-n}}\equiv 1 \mod p^k $

Proof : (by induction on $k$)

*

*Basis step : $k=m$ the result is true according to the hypothesis.

*Induction step : suppose that $ a^{p^{k-n}}\equiv 1 \mod p^k $ or in other words, there exist an integer $q$ such that $a^{p^{k-n}}=1+qp^k$ hence:
$$a^{p^{k+1-n}}=(a^{p^{k-n}})^p=(1+qp^k)^p=1+p.qp^k+\sum_{i=2}^p \binom{p}{i}(qp^k)^i$$
one can notice that $p^{k+1}|p.qp^k$ and $p^{k+1}|(qp^k)^i$ for every $i\geq 2$, thus $a^{p^{k+1-n}}\equiv 1\mod p^{k+1}$ which terminates the induction.

This theorem could not apply to you example because the order of $3$ in $\mathbb{Z_{5^5}}$ is $4.5^4$, but it works in other examples : we know that $5^{2^1}\equiv 1 \mod 2^3$ so for every $n\geq 3$  we have :
$$5^{2^{n-2}}\equiv 1 \mod 2^n $$
