Polynomial Congruences

    This topic is the study of polynomial congruences and some theorems related to solving them.

Definition (Polynomial Congruence) Given a polynomial with integer coefficients, the congruence equation is called a polynomial congruence.

Example (Polynomial Congruence) (a) Consider the example Any solution of this satisfies Trying and in the latter congruence gives us the complete solution thus we can restrict our search for solutions of to the integers in some complete residues system modulo congruent to 1 modulo and 7 for example. Substitution shows that none of these work; the congruence has no solutions.
    (b) As another example, let us look at We start with a complete solution is Thus the possible solutions of are and Substitution shows that only works. Since all solutions of must be congruent to modulo 4, we try and in this congruence. Since   and only works. We note that is a solution of is the only other possibility. But and so is a complete solution to

Proposition (Polynomial Congruence Reduction) Let be the unique factorization of Then the polynomial congruence has the same set of solutions as the system of simultaneous congruences



    Proof. As consequence of the fundamental theorem of arithmetic, if and only if for each This follows easily since, for some integer
    


for each Hence, if and only if all of the congruences
    


also hold. It follows that



has the same set of solutions as the system of simultaneous congruences

Example (Polynomial Congruence Reduction) Consider trying to solve the polynomial congruence equation



Since by inspection we solve the following congruences, and we have  







Thus there are a total of 18 solutions to ; for example to find one of them we solve



Using the Chinese remainder theorem we obtain the solution The other 17 solutions are also found by using the Chinese remainder theorem.

    In order to solve a polynomial congruence we can reduce to the case of moduli that are powers of primes. Thus solving these polynomial congruences becomes the main focus. In order to solve where is some prime power, we would actually like to reduce even further and just solve, So our first goal will be how to solve polynomial congruences with a prime moduli, and then to see how to lift these solutions to However, the general procedure for solving is non-rival; instead, we set a limit to the number of solutions, which will help in some cases.

Proposition (Factor Theorem for Polynomial Congruences) Let with integers and is a prime such that , then the congruence has at most mutually incongruent solutions modulo

    Solving where is some prime power, our strategy is to solve the case for when (if possible) and then to lift these solutions to the case for and then to the case for eventually we can reach In order to state the main theorem and understand its proof we need some results from calculus; in particular, the derivative of a polynomial. Given recall that the derivative is Assuming and are polynomials with integer coefficients, here are three other properties from calculus that we will use,





and (the Taylor expansion),



These results will lead to a proof of the next theorem which states when a solution to lifts to a unique solution of and when such a solution lifts to incongruent solutions modulo or to none at all.
    Let denote the inverse modulo that is, given a prime and an integer any integer for which We are now reading for the main theorem of this topic.

Proposition (Hensel's Lifting Theorem) If is a polynomial with integers coefficients and is a solution to with and prime , then

(i) if then there is a unique integer such that   given by



(ii) if and then for all integers

(iii) if and then has no solutions with

Furthermore, if and then there is a unique solution modulo for such that   

Example (Solving Polynomial Congruences) Solve the polynomial congruence equations.  

(a) Solve the polynomial congruence equation



    Solution. Since first we consider the equation By inspection, we see that the solutions are and Note that,
    For we find that Thus lifts successively to unique solutions modulo each power of We set Then, since we have and so  
    






So we have lifted to a solution
     For we find that Thus lifts successively to unique solutions modulo each power of We set Then, since we have and so  
    






So we have lifted to a solution
    
(b) Solve the polynomial congruence equation



    Solution.  Since first we consider the equation By inspection, we see that the solutions are and modulo 5. Note that,
    For we find that Thus we check, and so does not lift to a solution modulo .
    For we find that and so has unique lifts modulo We set Then, since we have and so  
    




So we have lifted to a solution ; that is we have solved
      Now we consider the case for By inspection, we see that the solutions are and modulo 7.
      For we find that Thus we check, and so does not lift to a solution modulo .  
     For we find that and so has unique lifts modulo We set Then, since we have and so  
    


So we have lifted to a solution ; that is we have solved
     It remains to solve the system:



This is easy since and we have and so



as desired.

• print this page
• pages linking here
• related pages