# Showing $1+p$ is an element of order $p^{n-1}$ in $(\mathbb{Z}/p^n\mathbb{Z})^\times$

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.

-
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. –  André Nicolas Nov 16 '12 at 3:24
@Carl When $m=3^2$, $a_3 = 28/3$. –  Erick Wong Nov 16 '12 at 3:28
@Carl Thanks, but perhaps you misread how I defined the $a_i$'s. –  sourisse Nov 16 '12 at 3:38
@sourisse Oh snap. I feel foolish now. Sorry! I'll delete comments to as not confuse anyone in the future –  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$".)

-
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... –  sourisse Nov 16 '12 at 4:55
@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. –  Erick Wong Nov 16 '12 at 9:02
What a great answer! +1 –  Eric Auld Mar 14 at 5:49

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

-