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.
 A: Proposition 1. Let $n$ and $k$ be integers, with $n\geq2$ and $k\geq0$. Then
$$(1+n)^{n^{k}}\equiv1\pmod{n^{k+1}}.$$
Proof. If $k=0$, then the congruence is
$$(1+n)\equiv1\pmod{n},$$
so it is true.
Assume that it is true for some $k\geq0$.
\begin{align*}(1+n)^{n^{k+1}}&=((1+n)^{n^k})^n\\
&=(1+\ell n^{k+1})^n\\
&=1+n\cdot(\ell n^{k+1})+\binom{n}{2}(\ell n^{k+1})^2+\cdots+(\ell n^{k+1})^n
\end{align*}
Since $2k+2\geq k+2$, it follows that
$$(1+n)^{n^{k+1}}\equiv1\pmod{n^{k+2}}.$$
Hence, by induction, the congruence holds for all $k\geq0$.
Proposition 2. If $p$ is an odd prime, then
$$(1+p)^{p^{k}}\equiv1+p^{k+1}\pmod{p^{k+2}}$$
for every positive integer $k$.
Proof. If $k=0$, then the congruence is
$$1+p\equiv1+p\pmod{p^2},$$
so it is true. Assume that it is true for some $k\geq0$.
\begin{align*}(1+p)^{p^{k+1}}&=((1+p)^{p^k})^p\\
&=(1+p^{k+1}+\ell p^{k+2})^p\\
&=(1+p^{k+1}(1+\ell p))^p\\
&=1+p\cdot p^{k+1}(1+\ell p)+\binom{p}{2}(p^{k+1}(1+\ell p))^2+\cdots+(p^{k+1}(1+\ell p))^p\\
&=1+p^{k+2}+\ell p^{k+3}+\binom{p}{2}(p^{k+1}(1+\ell p))^2+\cdots+(p^{k+1}(1+\ell p))^p
\end{align*}
Since $p$ is an odd prime, $\binom{p}{2}=\frac{p(p-1)}{2}$ is divisible by $p$.
Note that
$$1+2(k+1)=2k+3\geq k+3,$$
and
$$3(k+1)=3k+3\geq k+3.$$
It follows that
$$(1+p)^{p^{k+1}}\equiv1+p^{k+2}\pmod{p^{k+3}}.$$
Hence, by induction, the congruence holds for all $k\geq0$.
Corollary 3. If $p$ is an odd prime, then
$$(1+p)^{p^{k}}\not\equiv1\pmod{p^{k+2}}$$
for all $k\geq0$.
Proposition 4. Let $p$ be an odd prime, and $n$ a positive integer. Then the order of $\overline{1+p}\in(\mathbb{Z}/p^n\mathbb{Z})^\times$ is $p^{n-1}$.
Proof. First note that $(1+p,p^n)=1$, so $\overline{1+p}\in(\mathbb{Z}/p^n\mathbb{Z})^\times$.
Let $n\geq2$, and consider $\overline{1+p}\in(\mathbb{Z}/p^n\mathbb{Z})^\times$.
By Proposition 1,
$$(1+p)^{p^{n-1}}\equiv1\pmod{p^n},$$
so $|1+p|\mid p^{n-1}$.

*

*If $n=1$, then $|1+p|\mid1$, so $|1+p|=1=p^{n-1}$.

*Suppose that $n\geq2$. By proposition $2$,
$$(1+p)^{p^{n-2}}\not\equiv1\pmod{p^n},$$
so $|1+p|\nmid p^{n-2}$. It follows that $|1+p|=p^{n-1}$.

A: 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$".)
A: A hint to a confused fellow struggler:
Every member in binomial has $p^{n-1+i}$ in the numerator, and $p^k, k \epsilon \mathbb{Z}^{>=}$ as part of prime factorisation for $i!$ in the denominator. The trick is to show that $i$ grows faster than $k=f(i!)$ for $i>=p$. The proof is straightforward induction.
I feel the main issue with this problem is this: it's supposed to be obvious, being one out of supplementary 26 exercises. And if you miss this, you end up looking at Legendre's formula and whatnot :) 
A: 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.
A: I struggled with this a bit with the details, so here is my take (which piggy backs on the other solutions) just in case it helps others:
This is an answer to Dummit & Foote's "Abstract algebra", 3rd ed, Problem 21 in Section 2.3.
Also, note that ashpool's is the only other answer that explicitly uses the fact that $p$ is odd.
The key result (which Eric Auld notes above and is proved here) is that $\nu_p( \binom{p^l}{k}) = l-\nu_p(k) $ (for $k = 1,....,p^{l}$), where $\nu_p(n)$ is the largest $k$ such that $p^k \mid n$.
Another relevant result is that since $p$ is prime, $\nu_p(ab) = \nu_p(a) + \nu_p(b)$.
However, we need some estimates for $\nu_p(k)$.
We have $p^{\nu_p(k)} \le k$ (by definition) and so $\nu_p(k) \le {\log k \over \log p}$. Also, note that $p \ge 3 > e$ (the latter is used momentarily).
I claim that ${\log k \over \log p} \le k-1$ for $k \ge 1$. Note that this is true for $k=1$ and since (differentiating both sides) ${1 \over k \log p} \le 1$ for $k \ge 1$, we see that this is true for $k \ge 1$. In a similar manner, we can show that ${\log k \over \log p} \le k-2$ for $k \ge 3$.
(Presumably $n \ge 1$ for this part.)
Using the binomial theorem we get
$(1+p)^{p^{n-1}} = 1 + \sum_{k=1}^{p^{n-1}} \binom{p^{n-1}}{k} p^k$, and
$\nu_p(\binom{p^{n-1}}{k} p^k) = n-1 -\nu_p(k)+k$, and using the above, we have $\nu_p(\binom{p^{n-1}}{k} p^k) \ge  n$. Hence
$[(1+p)^{p^{n-1}}]_{p^n} = [1]_{p^n}$.
(Presumably $n \ge 2$ for this part.)
The same approach works for the next part,
$(1+p)^{p^{n-2}} = \sum_{k=0}^{2} \binom{p^{n-2}}{k} p^k + \sum_{k=3}^{p^{n-2}} \binom{p^{n-2}}{k} p^k$, and for the latter sum, note that (since $k \ge 3$) we have
$\nu_p(\binom{p^{n-2}}{k} p^k) = n-2-\nu_p(k)+k \ge n$, and so
$(1+p)^{p^{n-2}} = 1 + p^{n-1} +{p^{n-2} (p^{n-2}-1) \over 2} p^2 = 1 + p^{n-1} +{p^{n-2}-1 \over 2} p^n$. Since $p$ is odd, we see that ${p^{n-2}-1 \over 2} $ is an integer and hence $[(1+p)^{p^{n-2}}]_{p^n} = [1+p^{n-1}]_{p^n}$.
The last part of the question is to show that $1+p$ is an element of order $p^{n-1}$ in $(\mathbb{Z} / p^n \mathbb{Z})^\times$. The result follows from the above noting that $\gcd(1+p,p^n) = 1$, so $[1+p]_{p^n} \in (\mathbb{Z} / p^n \mathbb{Z})^\times$.
A: $(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$
