Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $p$ be an odd prime. I know that $(1+p)^{p^{r-1}}\equiv 1 \pmod {p^r}$ but how can I prove that if $n < p^{r-1}$ then $(1+p)^n$ is not $1 \pmod {p^r}$. I tried to prove using the properties of binomial expansion but I cannot show either the sum is less than $p^r$ or not $1 \bmod p^r$.

share|cite|improve this question
Ah, no problem. Deleting comment. – Cam McLeman Jan 3 '12 at 14:08
up vote 7 down vote accepted

Since you know $(1+p)^{p^{r-1}}\equiv 1\pmod{p^r}$, you know that the order of $1+p$ mod $p^r$ divides $p^{r-1}$. So for your problem it suffices to check that $(1+p)^{p^e}\not\equiv1\pmod{p^r}$ for any $e<r-1$, or better, just that $$(1+p)^{p^{r-2}}\not\equiv1\pmod{p^r}.$$

But now the binomial theorem gives $$(1+p)^{p^{r-2}}=\sum_{k=0}^{p^{r-2}}\binom{p^{r-2}}{k}p^k=1+\sum_{k=1}^{p^{r-2}}\binom{p^{r-2}}{k}p^k\equiv 1+p^{r-1}\not\equiv 1\mod p^r.$$

share|cite|improve this answer
Note that this argument generalizes to show any element of the form 1+ap has order $p^{r-1}$ mod $p^r$ for any a $\not\equiv$ 0 mod $p$ – David Marquis Jan 2 '12 at 16:53
There's a nice argument using the logarithm and exponential series, too, but this elementary argument is really more satisfactory. – Lubin Jan 2 '12 at 18:09
Why is it obvious that $\begin{pmatrix} p^{r-2} \\ k \end{pmatrix}p^k \equiv 0 \mod{p^r}$ for $k \ge 2$? I've been able to check a few cases by hand but I have no general proof, it bothers me. – Patrick Da Silva Jan 12 '12 at 1:35

Instead of doing things in one step, using the Binomial Theorem, we can push $r$ upwards one at a time (but again using the Binomial Theorem). We show by induction on $r$ that if $p$ is an odd prime and $r \ge 2$, then
$$(1+p)^{p^{r-2}}\equiv 1+p^{r-1} \pmod{p^r}.$$ The details are similar to those in my answer to an earlier question of yours about the order of $5$ modulo $2^r$, and partly connect the two questions.

The result holds at $r=2$. We show that if it holds at $r=k$ it holds at $r=k+1$. By the induction assumption, we have $$(1+p)^{p^{k-2}}= 1+p^{k-1} +sp^k$$ for some integer $s$. Take the $p$-th power of both sides. We get $$(1+p)^{p^{k-1}}= (1+p^{k-1} +sp^k)^p.$$ Expand the right-hand side, using the Binomial Theorem. We get $$1+p(p^{k-1}+sp^k) + \text{higher order terms}.$$ There is potential trouble only with first term of the higher order part, which is $\binom{p}{2}(p^{k-1}+sp^k)^2$. The $(p^{k-1}+sp^k)^2$ part supplies a factor of $p^{2k-2}$. This is enough if $2k-2 \ge k+1$, but that only happens when $k \ge 3$. When $k=2$, we need the fact that $p \ge 3$, so $\binom{p}{2}$ supplies an additional factor of $p$. (Note that this is exactly where the argument breaks down when $p=2$.)

We conclude that $(1+p)^{p^{k-1}}=1+p^k + \text{terms divisible by } p^{k+1}$, which is what we needed to show.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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