# $(1+p)^n$ is not $1 \pmod {p^r}$ when $n < p^{r-1}$

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

-
Ah, no problem. Deleting comment. –  Cam McLeman Jan 3 '12 at 14:08

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

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

-