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

The general approach (where the modulus is composite) is:

1. Solve the congruence mod p, where p is prime.

2. Solve the congruence mod for , where p is prime.

3. To solve the congruence mod n, let . Use step 2 to solve the congruence mod for , then use the Chinese Remainder Theorem to put together the solutions to get a solution mod n.

First, I'll show how to use a solution to a quadratic congruence for p prime to get a solution to .

Example. Solve the quadratic congruence

has solutions and . (Note that .) I will try to "lift" one of these solutions to a solution mod 169.

Write

I will try to find z so that

In other words, I suppose that a solution mod 169 is congruent mod 13 to the mod 13 solution 5.

Substitute into and solve:

I divide out the common factor of 26, dividing the modulus by :

Note that if , then

Thus, any z which equals 9 mod 13 will give the same solution .

Note that is another solution. You can check that you get it by starting with the solution to .

The general theorem requires 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 as 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 .

Example. Solve the congruence

First, I find solutions to :

I get .

Take . Then . Then , and . Therefore, we're in the second case of the theorem.

Further, , and . Hence, we're in the first subcase of the second case, and has 3 solutions congruent to 1 mod 3. They're obtained by adding multiples of 3 to 1: We get .

Contact information

Copyright 2019 by Bruce Ikenaga