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 .
Copyright 2019 by Bruce Ikenaga