Proving $a^{(p-1)p^{k-1}} \equiv 1 \pmod {p^k}$ without Euler's Theorem Is there a different way of solving $$a^{(p-1)p^{k-1}} \equiv 1 \pmod {p^k}$$ without the use of Euler's Theorem (or proof of Euler's theorem for $p^k$)? 
I've tried to use the Chinese Remainder Theorem, and so far, I have only got that if $n$ is a solution to $a^n \equiv 1 \pmod {p^k}$, then $n = (p-1)j$.
 A: You can mimic the proof of Fermat's little theorem through binomial coefficients.
$a^{p-1}$ is a number of the form $1+kp$, hence we have:
$$ a^{(p-1)p^{k-1}}=(1+kp)^{p^{k-1}}=\sum_{j=0}^{p^{k-1}}\binom{p^{k-1}}{j}(kp)^j \tag{1}$$
and it is not difficult to check that every term of the sum on the RHS, except $j=0$, is a multiple of $p^k$.
A: An element $\bar x\in\mathbb Z/p^k\mathbb Z$ is invertible (with respect to multiplication) if and only if its representant $x\in\mathbb Z$ is coprime to $p^k$. Since $p$ is a prime, coprimality to $p^k$ is equivalent to coprimality to $p$. Hence the numbers in $\{0,\dots,p^k-1\}$ that are not representants of invertible elements in $\mathbb Z/p^k\mathbb Z$ are exactly those that are multiples of $p$, namely $0,p,2p,\dots,(p^{k-1}-2)p, (p^{k-1}-1)p$ — these are $p^{k-1}$ elements. Therefore, the order of $(\mathbb Z/p^k\mathbb Z)^\ast$ is $p^k-p^{k-1}=(p-1)p^{k-1}$. As a consequence to Lagrange's theorem, a group's exponent must divide its order, which yields the claim.
