# 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 . Lift those (if possible) to solutions mod . And so on.

I'll begin with two preliminary results.

Lemma. If , then the product of k consecutive integers is divisible by .

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

Next, if all of the consecutive integers are negative, their product is equal to 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 .

Write the k consecutive positive integers in descending order as

Then the product is

Therefore,

Proposition. Let , let , and let p be prime. For all ,

Proof. Let . Consider the Taylor expansion of f:

I need to show that

Since and ,

Hence, . This shows that the result is true, provided that is an integer.

Write . Then

Each coefficient has a a factor the product of j consecutive integers, which is divisible by . Therefore, is an integer, and the argument above is complete.

Theorem. Let , let , let p be prime, and let c be a solution to .

(a) If , then has a unique solution congruent to c mod . It is given by , where

(b) If , then:

(i) If , then has p solutions congruent to c mod . They're given by for .

(ii) If , then has no solutions congruent to c mod .

Proof. Since , I have , and is an integer.

Suppose first that . Then is invertible mod p. Let

By the previous result

This shows that is a solution to , and clearly .

Reversing these steps shows that t is unique mod p.

Now suppose that . Then , so the previous result yields

If , the equation says

Since t was arbitrary, this equation is satisfied for all of the p distinct values of t mod p, namely .

Finally, if , the equation says

This means that for no t is a solution to .

Example. Solve the congruence

Step 1. Find solutions mod 7.

The solutions are and .

Step 2. For each solution c to the congruence mod , determine whether p does or does not divide and consider cases.

Since , I have .

I have and . I have and .

I'll do first. Note that . Applying the first case of the theorem, I solve:

Hence, a solution mod 49 is given by .

Next, I'll do . Note that . Applying the first case of the theorem, I solve:

Hence, a solution mod 49 is given by .

Contact information