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

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}$.

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 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 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.