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

Post a comment or leave a trackback: Trackback URL.


  • ai  On July 25, 2011 at 12:25 am

    I think that the seventh line of the Lemma 2 paragraph is incorrect…

    • nbloomf  On August 5, 2011 at 9:44 am

      You’re right. I’ll mark this ‘Incomplete’ until I have time to fix it.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: