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