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

  • $\begingroup$ Can one use Fermat's Theorem? The Chinese Remainder Theorem will not be useful, it requires relatively prime moduli. $\endgroup$ – André Nicolas Feb 26 '15 at 20:10
  • 2
    $\begingroup$ in fact this is equivalent to the Euler's theorem and every proof of this theorem give a proof of Euler theorem $\endgroup$ – ali Feb 26 '15 at 20:11
  • $\begingroup$ 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. $\endgroup$ – Erick Wong Jun 21 '16 at 7:51

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


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.

  • $\begingroup$ 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? $\endgroup$ – Dane Bouchie Feb 26 '15 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.