Prime Power Congruences

In this section, I'll discuss how you solve polynomial congruences mod a power of a prime. The basic idea is to "lift" solutions one power at a time: Start with solutions mod p. Lift them (if possible) to solutions mod $p^2$ . Lift those (if possible) to solutions mod $p^3$ . And so on.

I'll begin with two preliminary results.

Lemma. If $k \ge 1$ , then the product of k consecutive integers is divisible by $k!$ .

Proof. First, if any of the consecutive integers is 0, the product is 0, and it is divisible by $k!$ .

Next, if all of the consecutive integers are negative, their product is equal to $(-1)^k$ times the product of k consecutive positive integers.

Hence, it suffices to prove the result for positive integers: The product of k consecutive integers is divisible by $k!$ .

Write the k consecutive positive integers in descending order as

$$n,\ n - 1,\ \ldots n - k + 1.$$

Then the product is

$$n \cdot (n - 1) \cdots (n - k + 1) = \dfrac{[n \cdot (n - 1) \cdots (n - k + 1)] (n - k) (n - k - 1) \cdots 1}{(n - k) (n - k - 1) \cdots 1} = \dfrac{n!}{(n - k)!} = k! {n \choose k}.$$

Therefore,

$$k! \mid n \cdot (n - 1) \cdots (n - k + 1).\quad\halmos$$

Proposition. Let $f(x) \in \integer[x]$ , let $n \ge 1$ , and let p be prime. For all $x, t \in \integer$ ,

$$f(x + p^n t) = f(x) + f'(x) p^n t \mod{p^{n + 1}}.$$

Proof. Let $k = \deg(f)$ . Consider the Taylor expansion of f:

$$f(x + p^n t) = f(x) + f'(x) \cdot p^n t + \dfrac{f''(x)}{2!} p^{2 n} t^2 + \dfrac{f^{(3)}(x)}{3!} p^{3 n} t^3 + \cdots + \dfrac{f^{(k)}(x)}{k!} p^{k n} t^k.$$

I need to show that

$$p^{n + 1} \mid \dfrac{f^{(j)}(x)}{j!} p^{j n} t^j \quad\hbox{for}\quad j \ge 2.$$

Since $j \ge 2$ and $n \ge 1$ ,

$$j n \ge 2 n = n + n \ge n + 1.$$

Hence, $p^{n + 1} \mid
   p^{j n}$ . This shows that the result is true, provided that $\dfrac{f^{(j)}(x)}{j!}$ is an integer.

Write $\displaystyle
   f(x) = \sum_i c_i x^i$ . Then

$$f^{(j)}(x) = \sum_i c_i (i)(i - 1) \cdots (i - j + 1) x^{i - j}.$$

Each coefficient $c_i
   (i)(i - 1) \cdots (i - j + 1)$ has a a factor the product of j consecutive integers, which is divisible by $j!$ . Therefore, $\dfrac{f^{(j)}(x)}{j!}$ is an integer, and the argument above is complete.

Theorem. Let $f(x) \in \integer[x]$ , let $n \ge 1$ , let p be prime, and let c be a solution to $f(x) = 0
   \mod{p^n}$ .

(a) If $p \notdiv
   f'(c)$ , then $f(x) = 0 \mod{p^{n + 1}}$ has a unique solution congruent to c mod $p^n$ . It is given by $c + p^n t$ , where

$$t = -f'(c)^{-1} \cdot \dfrac{f(c)}{p^n} \mod{p}.$$

(b) If $p \mid f'(c)$ , then:

(i) If $p^{n + 1} \mid
   f(c)$ , then $f(x) = 0 \mod{p^{n + 1}}$ has p solutions congruent to c mod $p^n$ . They're given by $c + p^n t$ for $t = 0, 1, \ldots, p - 1$ .

(ii) If $p^{n + 1}
   \notdiv f(c)$ , then $f(x) = 0 \mod{p^{n + 1}}$ has no solutions congruent to c mod $p^n$ .

Proof. Since $f(c) = 0 \mod{p^n}$ , I have $p^n \mid f(c)$ , and $\dfrac{f(c)}{p^n}$ is an integer.

Suppose first that $p
   \notdiv f'(c)$ . Then $f'(c)$ is invertible mod p. Let

$$t = -f'(c)^{-1} \cdot \dfrac{f(c)}{p^n}.$$

By the previous result

$$\eqalign{ f(c + p^n t) & = f(c) + f'(c) p^n t \mod{p^{n + 1}} \cr \noalign{\vskip2pt} f(c + p^n t) & = f(c) + f'(c) p^n \cdot \left(-f'(c)^{-1} \cdot \dfrac{f(c)}{p^n}\right) \mod{p^{n + 1}} \cr \noalign{\vskip2pt} f(c + p^n t) & = f(c) - f(c) = 0 \mod{p^{n + 1}} \cr}$$

This shows that $c +
   p^n t$ is a solution to $f(x) = 0 \mod{p^{n + 1}}$ , and clearly $c + p^n t = c \mod{p^n}$ .

Reversing these steps shows that t is unique mod p.

Now suppose that $p
   \mid f'(c)$ . Then $p^{n + 1} \mid f'(c) p^n$ , so the previous result yields

$$f(c + p^n t) = f(c) + f'(c) p^n t = f(c) + 0 = f(c) \mod{p^{n + 1}}.$$

If $p^{n + 1} \mid
   f(c)$ , the equation says

$$f(c + p^n t) = f(c) = 0 \mod{p^{n + 1}}.$$

Since t was arbitrary, this equation is satisfied for all of the p distinct values of t mod p, namely $t = 0, 1, \ldots p - 1$ .

Finally, if $p^{n + 1}
   \notdiv f(c)$ , the equation says

$$f(c + p^n t) = f(c) \ne 0 \mod{p^{n + 1}}.$$

This means that for no t is $c + p^n t$ a solution to $f(x) = 0 \mod{p^{n +
   1}}$ .

Example. Solve the congruence

$$x^2 + 5 x + 18 = 0 \mod{49}.$$

Step 1. Find solutions mod 7.

$$\vbox{\offinterlineskip \halign{& \vrule # & \strut \hfil \quad # \quad \hfil \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr & x & & 0 & & 1 & & 2 & & 3 & & 4 & & 5 & & 6 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr & $x^2 + 5 x + 18 \mod{7}$ & & 4 & & 3 & & 4 & & 0 & & 5 & & 5 & & 0 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} }} $$

The solutions are $x =
   3$ and $x = 6$ .

Step 2. For each solution c to the congruence mod $p^n$ , determine whether p does or does not divide $f'(c)$ and consider cases.

Since $f(x) = x^2 + 5 x
   + 18$ , I have $f'(x) = 2 x + 5$ .

I have $f'(3) = 11$ and $7 \notdiv 11$ . I have $f'(6) = 17$ and $7 \notdiv 17$ .

I'll do $x = 3$ first. Note that $f(3) = 42$ . Applying the first case of the theorem, I solve:

$$\eqalign{ 11 t & = -\dfrac{42}{7} \mod{7} \cr \noalign{\vskip2pt} 4 t & = -6 \mod{7} \cr 2 \cdot 4 t & = 2 \cdot (-6) \mod{7} \cr t & = -12 = 2 \mod{7} \cr}$$

Hence, a solution mod 49 is given by $3 + 7 \cdot 2 = 17$ .

Next, I'll do $x = 6$ . Note that $f(6) = 84$ . Applying the first case of the theorem, I solve:

$$\eqalign{ 17 t & = -\dfrac{84}{7} \mod{7} \cr \noalign{\vskip2pt} 3 t & = -12 = 2 \mod{7} \cr 5 \cdot 3 t & = 5 \cdot 2 \mod{7} \cr t & = 10 = 3 \mod{7} \cr}$$

Hence, a solution mod 49 is given by $6 + 7 \cdot 3 = 27$ .



Contact information

Bruce Ikenaga's Home Page

Copyright 2017 by Bruce Ikenaga