I'm trying to work through Dummit & Foote, but I've gotten stuck on the following question:

Let $p$ be an odd prime and let $n$ be a positive integer. Use the binomial theorem to show that $(1+p)^{p^{n-1}} \equiv 1\bmod{p^n}$ but $(1+p)^{p^{n-2}} \not \equiv 1\bmod{p^n}$. Deduce that $1+p$ is an element of order $p^{n-1}$ in the multiplicative group $(\mathbb{Z}/p^n\mathbb{Z})^\times$.

The trouble I'm having is mostly with respect to the first implication, since I'm not completely confident with what I've done so far. I started by letting $m = p^{n-1}$ and $a_i = {m\choose i}/m$. I then ended up with \begin{align*} (1+p)^m = \sum_{k=0}^{m} {m\choose k}p^k &= 1 + {m \choose 1}p + {m \choose 2}p^2 + \cdots + {m \choose m-1}p^{m-1} + p^m\\ &= 1 + mp + a_2mp^2 + a_3mp^3 + \cdots + a_{m-1}mp^{m-1}+ p^m\\ & = 1 + p^n + a_2p^{n+1} + a_3p^{n+2} + \cdots + p^m\\ &= 1 + p^n(1+ a_2p + a_3p^2+ \cdots + p^{m-n})\\ &\equiv 1 \bmod{p^n} \end{align*}

...but based on some numerical tests I did, the $a_i$'s aren't necessarily integers, so this doesn't work. Would someone please point out what I'm missing here?

For the second implication, I can see a clean application of Euler's theorem starts things off. To finish, I'd like to show that no power of $(1+p)$ less than $(1+p)^{p^{n-1}}$ is congruent to $1\bmod{p^n}$, but I'm not sure how knowing the first part plays into this.

Any pointers would be appreciated.

  • 3
    $\begingroup$ If you want to use the Binomial Theorem, you will need to show that the binomial coefficients have "enough" $p$'s, at least until $k= n-1$. (After that, the $p^k$ term does the job.) The fact that we cannot get the order lower is due to the second term of the expansion. $\endgroup$ – André Nicolas Nov 16 '12 at 3:24
  • $\begingroup$ @Carl When $m=3^2$, $a_3 = 28/3$. $\endgroup$ – Erick Wong Nov 16 '12 at 3:28
  • $\begingroup$ @Carl Thanks, but perhaps you misread how I defined the $a_i$'s. $\endgroup$ – sourisse Nov 16 '12 at 3:38
  • $\begingroup$ @sourisse Oh snap. I feel foolish now. Sorry! I'll delete comments to as not confuse anyone in the future $\endgroup$ – user45793 Nov 16 '12 at 3:38

It's easier to think of this as the result of repeated raising to the power $p$. Start with a general number of the form $1+kp^r$ with $r\ge 1$ and $p \nmid k$ and see what you can deduce about $(1+kp^r)^p$.

For the second part, if an element $x \in (\mathbb Z/p^n \mathbb Z)^\times$ satisfies $x^m = 1$, what can you say about the order of $x$? (You can say something quite a bit stronger than "it could be anywhere from $1$ to $m$".)

  • $\begingroup$ I can show that $(1+kp^r)^p \equiv 1 \bmod{p^r}$, but I don't see exactly where it's applicable at the moment. For your second hint, I know that we must have $|x|$ divides $m$, so that narrows the choices down... $\endgroup$ – sourisse Nov 16 '12 at 4:55
  • $\begingroup$ @sourisse I'd suggest you look at $(1+kp^r)^p$ modulo $p^{r+1}$ rather than just $p^r$, so that you can perform an induction. $\endgroup$ – Erick Wong Nov 16 '12 at 9:02
  • 2
    $\begingroup$ What a great answer! +1 $\endgroup$ – Eric Auld Mar 14 '15 at 5:49
  • $\begingroup$ Mind over matter. $\endgroup$ – caffeinemachine Jul 22 '16 at 10:17
  • $\begingroup$ Thought I am not sure why do you use "$p$ does not divide $k$." $\endgroup$ – caffeinemachine Jul 22 '16 at 10:24

$(1+p)^{p^r}=1+\binom {p^r}1 p+\binom {p^r}2 p^2+\cdots+p^{p^r}$ $=1+p^{r+1}+p^{r+2}(\cdots)\equiv1+p^{r+1}\pmod{p^{r+2}}$ as $p^r\ge r+2$ for $p\ge3,r\ge 1$

$\implies (1+p)^{p^r}\not\equiv1\pmod{p^{r+2}}$

and $(1+p)^{p^r}\equiv1\pmod{p^{r+1}}\implies (1+p)^{p^{r+1}}\equiv1\pmod{p^{r+2}}$

So, $ord_{p^{r+2}} (1+p)\mid p^{r+1}-->(1),$ but $ord_{p^{r+2}} (1+p)\not\mid p^r-->(2)$

$(1)\implies ord_{p^{r+2}} (1+p)$ must be $p^s$ where $s\le r+1$

$(2)\implies s\not\le r$ or $s>r$

So, $(1),(2)$ together $\implies s=r+1,$ i.r., $ ord_{p^{r+2}} (1+p)=p^{r+1}$

More generally, we can prove using Binomial Theorem,

if $ord_{p^s}a=d$ then $ord_{p^{s+1}}a=d, \space or \space pd--->(1)$

if $ord_{(p^s)}(a)=d$ and $ord_{p^{(s+1)}}(a)=pd,$ then $ord_{p^{(s+2)}}(a)=p^2d--->(2)$

Here, $1+p\equiv 1\pmod p,$ more generally $1+k\cdot p^r \equiv 1\pmod {p^r}$ if $p\not\mid k$

and $1+p\not\equiv 1\pmod{p^2},$ more generally $1+k\cdot p^r \not\equiv 1\pmod {p^{r+1}}$ if $p\not\mid k$

So, using $(1), ord_{p^{r+1}}(1+k\cdot p^r)=p\cdot 1=p$

So, using $(2), ord_{p^{r+2}}(1+k\cdot p^r)=p\cdot p=p^2$

Using $(2)$ repeatedly we can derive $ ord_{p^{r+s}}(1+k\cdot p^r)=p^s$

  • $\begingroup$ I disagree with your proof. You are implicitly claiming that $\binom{p^r}{k}$ is divisible by $p^{r-k}$, but that is not trivial. For instance, if $k=8$, then $8!$ contains $7$ factors of two. This is not a counterexample (because as it happens it is true), but an indication of why it's not trivial. $\endgroup$ – Eric Auld Sep 14 '16 at 23:13

A method of proof I like much, much more: this question shows the following lemma:

Let $p$ be a prime, and let $\nu(n)$ denote the largest integer $k$ such that $p^k \mid n$.

Claim: $\nu\left( \binom{p^k}{\ell} \right) = k - \nu(\ell) $. $\qquad \blacksquare$

Now we can just use the binomial theorem and things work out very nicely.


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.