# 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$.

• Can one use Fermat's Theorem? The Chinese Remainder Theorem will not be useful, it requires relatively prime moduli. – André Nicolas Feb 26 '15 at 20:10
• in fact this is equivalent to the Euler's theorem and every proof of this theorem give a proof of Euler theorem – ali Feb 26 '15 at 20:11
• You can use binomial theorem to show that if $x \equiv 1 \pmod{p^r}$ for some $r\ge 1$, then $x^p \equiv 1 \pmod{p^{r+1}}$. Induction then gives exactly what you want, assuming you can start from Fermat's theorem. – Erick Wong Jun 21 '16 at 7:51

$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$.
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.
• Great, but is this not the same as using the proof of Euler's totient function for $p^k$? and then proving Euler's Theorem? – Dane Bouchie Feb 26 '15 at 21:11