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 &amp; 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 &amp;= 1 + {m \choose 1}p + {m \choose 2}p^2 + \cdots + {m \choose m-1}p^{m-1}
+ p^m\\
&amp;= 1 + mp + a_2mp^2 + a_3mp^3 + \cdots + a_{m-1}mp^{m-1}+ p^m\\
&amp; = 1 + p^n + a_2p^{n+1} + a_3p^{n+2} + \cdots + p^m\\
&amp;= 1 + p^n(1+ a_2p + a_3p^2+ \cdots + p^{m-n})\\
&amp;\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.
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$".)
$(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}--&gt;(1),$ but $ord_{p^{r+2}} (1+p)\not\mid p^r--&gt;(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&gt;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---&gt;(1)$ 

if $ord_{(p^s)}(a)=d$ and $ord_{p^{(s+1)}}(a)=pd,$ then $ord_{p^{(s+2)}}(a)=p^2d---&gt;(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$