## Use the Binomial Theorem to compute the order of an element in the integers mod a prime power

Let $p$ be an odd prime and $n$ a positive integer. Use the Binomial Theorem to show that $(1+p)^{p^{n-1}} = 1\ \mathsf{mod}\ p^n$ but that $(1+p)^{p^{n-2}} \neq 1\ \mathsf{mod}\ p^n$. Deduce that $1+p$ is an element of order $p^{n-1}$ in $(\mathbb{Z}/(p^n))^\times$.

First we prove some lemmas.

Lemma 1: Let $a$, $b$, and $c$ be integers. If $c$ divides $ab$ and $\mathsf{gcd}(a,c)= 1$, then $c$ divides $b$. Proof: We have integers $k$, $x$, and $y$ such that $ab = kc$ and $ax + cy = 1$. Now $ax = 1-yc$ and $axb= cxk$, so that $b = c(xk+yb)$. $\square$

Lemma 2: Let $n \in \mathbb{Z}^+$, let $p$ be a prime, and let $1 \leq k \leq p^n$. If $p$ divides $k$ $m$ times, then $p$ divides $p^n \choose k$ $n-m$ times. Proof: We proceed by induction on $k$. For the base case $k = 1$, we have ${p^n \choose 1} = p^n = p^{n-0}$. For the inductive step, let $1 \leq k < p^n$. Suppose that $p$ divides $k$ $\ell$ times, divides $k+1$ $m$ times, and divides $p^n \choose k$ $n-\ell$ times. Note that $\ell \leq n$. Now we have $k = p^\ell \cdot Q$, $k+1 = p^m \cdot R$, and ${p^n \choose k} = p^{n-\ell} \cdot S$, where $p$ does not divide $Q$, $R$, and $S$. Note that

 $p^n \choose k$ = ${p^n \choose k} \cdot \frac{p^n - k}{k+1}$ = $\frac{p^{n-\ell}\cdot S \cdot (p^n-p^\ell \cdot Q)}{p^m \cdot R}$ = $p^{n-m} \cdot \frac{S \cdot (p^{n-\ell} - Q)}{R}.\ (1)$

Now (1) is an integer and $\mathsf{gcd}(R,p^{n-m}) = 1$, so by Lemma 1, $R$ divides $S \cdot (p^{n-\ell} - Q)$. Moreover, $p$ does not divide $S$ or $p^{n-\ell} - Q$ (as otherwise $p$ would divide $Q$) so that, since $p$ is prime, $p$ does not divide $\frac{S \cdot (p^{n-\ell} - Q)}{R}$. Thus the highest power of $p$ which divides $p^n \choose k+1$ is $n-m$. Thus the lemma holds for $k+1$, and by induction holds for all $1 \leq k \leq p^n$. $\square$

Lemma 3: Let $p$ be a prime and $k$ a positive integer. If $p$ divides $k$ $m$ times, then $m < k$. Proof: Suppose to the contrary that $m \geq k$; then we have $k = p^m \cdot \alpha$ for some $\alpha$. Moreover, $k < p^k$ $\leq p^m$ $\leq p^m \cdot \alpha = k$, a contradiction. So $m < k$. $\square$.

Lemma 4: Let $a,b \in \mathbb{Z}$ with $a \geq 1$ and $b \geq 3$. Then $a+1 < b^a$. Proof: First we prove the case $b = 3$ by induction. Note that if $a = 1$, we have $1+1 = 2$ $< 3 = 3^1$. Suppose now that the lemma holds for some $a \geq 3$. Then $(a+1)+1 < 3^a + 1$ $< 3 \cdot 3^a$ $= 3^{a+1}$; thus the lemma holds for all $a$ and $b=3$. Now let $b \geq 3$; $a+1 < 3^{a+1} \leq b^{a+1}$. Thus the lemma holds. $\square$

Lemma 5: Let $p$ be an odd prime and $k$ a positive integer. If $p$ divides $k$ $m$ times, then $m+1 < k$. Proof: Suppose $k = p^m \cdot \alpha$. Then by Lemma 4, $m+1 < p^m \leq p^m \cdot \alpha = k$. $\square$

Now to the main result. Recall the Binomial Theorem:

 $(a+b)^n = \displaystyle\sum_{k=0}^n \left( {n \atop k} \right) a^{n-k} b^k.$

In our case, we have

 $(1+p)^{p^{n-1}} = \displaystyle\sum_{k=0}^{p^{n-1}} \left( {p^{n-1} \atop k} \right) p^k.$

By Lemma 2 above, note that ${p^{n-1} \choose k} = p^{n-m_k-1} \cdot \beta_k$, where $m_k$ is the highest power of $p$ dividing $k$ and $p$ does not divide $\beta_k$. Thus

 $(1+p)^{p^{n-1}} = \displaystyle\sum_{k=0}^{p^{n-1}} p^{n-m_k+k-1} \cdot \beta_k.$

Now since $m_k < k$ by Lemma 3, $k-m_k \geq 1$. So $n+k-m_k-1 \geq n$ for all $k \geq 1$. Modulo $p^n$, the only nonzero term is the $k = 0$ term, which is clearly 1. Thus $(1+p)^{p^{n-1}} = 1$ mod $p^n$.

Consider now $(1+p)^{p^{n-2}}$. As before, by Lemma 2, for each $k$ we have ${p^{n-2} \choose k} = p^{m_k} \cdot \beta_k$, where $p$ divides $k$ $m_k$ times and does not divide $\beta_k$. By the Binomial theorem, we have

 $(1+p)^{p^{n-2}}$ = $\displaystyle\sum_{k=0}^{p^{n-2}} {p^{n-2} \choose k} p^k$ = $\displaystyle\sum_{k=0}^{p^{n-2}} p^{n+k-m_k-2} \cdot \beta_k$.

By Lemma 5 above, if $k \geq 2$ then $k \geq m_k - 2$. Thus $n + k - m_k - 2 \geq n$, so that, modulo $p^n$, all terms with $k \geq 2$ are 0. Thus we have

 $(1+p)^{p^{n-2}} = 1 + p^{n-1}.$

Hence $(1+p)^{p^{n-2}} \neq 1$ mod $p^n$.

Finally, recall that for any element $x$ in a group $G$, $x^n = 1$ if and only if $n$ divides $|x|$. Thus we see that in $(\mathbb{Z}/(p^n))^\times$, $|1+p|$ divides $p^{n-1}$ but not $p^{n-2}$; hence $|1+p| = p^{n-1}$. $\blacksquare$