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$.
$(1+p)^n$ is not $1 \pmod {p^r}$ when n < p^{r-1}
-
1Ah, no problem. Deleting comment. – 2012-01-03
2 Answers
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
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.$
-
0Why 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. – 2012-01-12
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.