Polynomial Congruences with Hensel’s Lifting Theorem

Direct Knowlege Contributor David A. Smith
  • By David A. Smith, Founder & CEO, Direct Knowledge
  • David Smith has a B.S. and M.S. in Mathematics and has enjoyed teaching calculus, linear algebra, and number theory at both Tarrant County College and the University of Texas at Arlington. David is the Founder and current CEO of Direct Knowledge.

The idea behind solving polynomial congruence equations is that we can reduce a congruence equation to an equivalent system of congruence equations using prime factorization. We then 1) solve each equation modulo a prime number (by brute force), 2) use Hensel’s Lifting theorem, and then 3) piece together the solutions using the Chinese Remainder Theorem. We provide several nontrivial examples many of which are workable by hand.

Congruence Reduction

Congruence reduction is used to a congruence equation modulo a composite integer by converting the congruence equation into a system of congruence equations each of which has a prime power modulus. We will state the general theorem and demonstrate is use through examples.

Theorem. (Congruence Reduction) Let $n = p_1^{e_1}p_2^{e_2} \cdots p_s^{e_s}$ be the unique factorization of $n.$ Then the linear congruence $a x\equiv b \pmod{n}$ has the same set of solutions as the system of simultaneous congruences \begin{equation}\begin{cases} a x\equiv b \pmod{p_1{}^{e_1}} \\ a x\equiv b \pmod{p_2^{e_2}} \\ \quad \vdots \\ a x\equiv b \pmod{p_s^{e_s}}. \end{cases}\end{equation}

Proof. As consequence of the Fundamental Theorem of Arithmetic, $n|m$ if and only if $\left.p_i^{e_i}\right|m$ for each $i.$ This follows easily since, for some integer $k,$ $$ n|m \Longleftrightarrow m=\left.n k \Longleftrightarrow m=k p_1^{e_1}p_2^{e_2} \cdots p_s^{e_s} \Longleftrightarrow p_i^{e_i}\right| m$$ for each $i.$ Hence, $A\equiv B \pmod{n}$ if and only if all of the congruences $A\equiv B \pmod{p_1^{e_1}}$, $A\equiv B \pmod{p_2^{e_2}}$, $\cdots$, $A\equiv B \pmod{p_s^{e_s}}$ also hold.

Example of Congruence Reduction

Example. Solve the linear congruence equation $17x\equiv 9 \pmod{276}$ by reducing to a linear system of congruence equations. 

Solution. Since $276=\left(2^2\right)(3)(23)$ the given congruence may be replaced by the system $17x\equiv 9 \pmod{4}$, $17x\equiv 9 \pmod{3}$, $17x\equiv 9 \pmod{23}$. We find $N=(4)(3)(23)=276$ and we use a table to construct the solution. $$\begin{array}{c|c|c|c|c|c|c} i & n_i & a_i & b_i & a_i x_i \equiv b_i \pmod{n_i} & \bar{n}_i & \bar{n}_iu_i \equiv 1 \pmod{n_i} \\ \hline 1 & 4 & 17 & 9 & x_1=1 & 69 & u_1=1 \\ 2 & 3 & 17 & 9 & x_2=0 & 92 & u_2=2 \\  3 & 23 & 17 & 9 & x_3=10 & 12 & u_3=2 \end{array} $$ The solution is $$x_0=(1)(69)(1)+(0)(92)(2)+(10)(12)(2)=309\equiv 33 \pmod{276}$$ and so the solution to $17x\equiv 9 \pmod{276}$ is $x\equiv 33 \pmod{276}$.

Example. Solve the linear congruence equation $3 x\equiv 11 \pmod{2275}$ by reducing to a linear system of congruence equations. 

Solution. Since $2275=\left(5^2\right)(7)(13)$ the given congruence may be replaced by the system $$\begin{cases} 3 x\equiv 11 \pmod{25}  \\ 3 x\equiv 11 \pmod{7}  \\ 3 x\equiv 11 \pmod{13}. \end{cases} $$ We find $N=(25)(7)(13)=2275$ and we use a table to construct the solution.  $$\begin{array}{c|c|c|c|c|c|c}   i & n_i & a_i & b_i &  a_i x_i \equiv b_i \pmod{n_i} & \bar{n}_i & \bar{n}_iu_i  \equiv 1 \pmod{n_i} \\   \hline 1 & 25 & 3 & 11 & x_1=12 & 91 & u_1=11  \\ 2 & 7 & 3 & 11 & x_2=6 & 325 & u_2=5  \\ 3 & 13 & 3 & 11 & x_3=8 & 175 & u_3=11 \end{array} $$ The solution is $$x_0=(12)(91)(11) +(6)(325)(5) +(8)(175)(11) = 37162 \equiv 762 \pmod{2275}$$ and so the solution to $2275=\left(5^2\right)(7)(13)$ is $x\equiv 762 \pmod{2275}$.

Simple Examples of Polynomial Congruence

Given a polynomial $f$ with integer coefficients, the congruence equation $f(x)\equiv 0 \pmod{n}$ is called a polynomial congruence.

Example. Solve the polynomial congruence, $$x^3+2\equiv 0 \pmod{9}.$$

Solution. Any solution also satisfies $ x^3+2\equiv 0 \pmod{3}.$ Trying $x=0, 1$ and $2$ in the latter congruence gives us $x=1.$ Thus we can restrict our search for solutions  to the integers in some complete residue system modulo $9$ congruent to 1 modulo $3$; namely, $1,4,$ and 7. Substitution shows that none of these work, and therefore there are no solutions.

Example. Solve the polynomial congruence, \begin{equation} \label{pc2} f(x)=x^3+3\equiv 0 \pmod{16}.\end{equation}

Solution. We start with $x^3+3\equiv 0 \pmod{2};$ and find $x=1$ is a solution. Thus the only possible solutions of $x^3+3\equiv 0 \pmod{4}$ are $x=1$ and $x=3.$ Substitution shows that only $x=1$ works. Since all solutions of $x^3+3\equiv 0 \pmod{8}$ must be congruent to $1$ modulo 4, we try $x=1$ and $x=5$. Since $f(1)=4$ and $f(5)=128,$ only $x=5$ works. We note that $x=5$ is a solution of \eqref{pc2} and $x=13$ is the  only other possibility. But $f(13) \equiv 0 \pmod{16}$ is not true and so $x=5$ is a complete solution.

The Importance of Congruence Reduction

Theorem. Let $n=p_1^{e_1}p_2^{e_2}\cdots p_s^{e_s}$ be the unique factorization of $n.$  Then the polynomial congruence $f(x)\equiv 0 \pmod{n}$ has the same set of solutions as the system of simultaneous congruences  $$\begin{array}{cccc} f(x)\equiv 0 \pmod{p_1^{e_1}},  & f(x)\equiv 0 \pmod{p_2^{e_2}},  &  \ldots,  &    f(x)\equiv 0 \pmod{p_s^{e_s}}  \\ \end{array}.$$

Proof. As consequence of the Fundamental Theorem of Arithmetic, $n|m$ if and only if  $\left.p_i^{e_i}\right|m$ for each $i.$ This follows easily since, for some integer $k,$ $$n|m \Longleftrightarrow  m=\left.n k \Longleftrightarrow k p_1^{e_1}p_2^{e_2}\cdots p_s^{e_s} \Longleftrightarrow   p_i^{e_i}\right|m$$ for each $i.$ Hence, $A\equiv B \pmod{n} $  if and only if all of the congruences $A\equiv B \pmod{p_1^{e_1}}$, $A\equiv B \pmod{p_2^{e_2}}$, $\cdots$, $A\equiv B \pmod{p_s^{e_s}}$ are satisfied.

About Hensel’s Lifting Theorem

In general, in order to solve a polynomial congruence $f(x)\equiv 0 \pmod{n}$ 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 $f(x)\equiv 0 \pmod{p^i}$ where $p^i$ is  some prime power, we would actually like to reduce even further and just solve, $f(x)\equiv 0 \pmod{p}.$ 

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 $f(x)\equiv 0 \pmod{p^i}.$ However,  the general procedure for solving $f(x)\equiv 0 \pmod{p}$ is non-trivial; instead, we set a limit to the number of solutions, which will help in some cases.

Let $f(x)=\sum _{k=1}^n a_kx^k$ with integers $a_k$ and $p$ is a prime such that $p\nmid   a_n$, then the congruence $f(x)\equiv 0 \pmod{p}$ has at most $n$ mutually incongruent solutions modulo $p.$ 

Solving $f(x)\equiv 0 \pmod{p^i}$ where $p^i$ is some prime power, our strategy is to solve the case for when $f(x)\equiv  0 \pmod{p}$ (if possible) and then to lift these solutions to the case for $f(x)\equiv 0 \pmod{p^2},$ and then to the case  for $f(x)\equiv 0 \pmod{p^3},$ eventually we can reach $f(x)\equiv 0 \pmod{p^i}.$ 

Let $\bar{a}$ denote the inverse $a$ modulo $p;$ that is, given a prime $p$ and an integer $a$ any integer $\bar{a}$ for which  $a \bar{a}\equiv 1 \pmod{p}.$ 

Hensel’s Lifting Theorem

Hensel’s lemma, also known as Hensel’s lifting lemma, named after Kurt Hensel, is a result in modular arithmetic, stating that if a polynomial equation has a simple root modulo a prime number $p$, then this root corresponds to a unique root of the same equation modulo any higher power of $p$, which can be found by iteratively “lifting” the solution modulo successive powers of $p$.

Theorem. (Hensel’s Lifting) If $f$ is a polynomial with integers coefficients and $r$ is a solution to $f(x)\equiv 0\pmod{p^{k-1}}$ with $k\geq 2$ and prime $p$, then

(1) if $\neg(f'(r)\equiv 0) \pmod{p},$ then there is a unique integer $t,$ $0\leq t<p,$ such that $f\left(r+t p^{k-1}\right)\equiv 0 \pmod{p^k}$ given by $t\equiv -\overline{f'(r)} \frac{f(r)}{p^{k-1}}\pmod{p}$

(2) if $f'(r)\equiv 0 \pmod{p}$ and $f(r)\equiv 0 \pmod{p^k},$ then $f\left(r+t p^{k-1}\right)\equiv 0\pmod{p^k}$ for all integers $t;$

(3) if $f'(r)\equiv 0\pmod{p}$ and $\neg(f(r)\equiv 0)\pmod{p^k},$ then $f(x)=0 \pmod{p^k}$  has no solutions with $x\equiv r\pmod{p^{k-1}}.$

Furthermore, if $f(r)\equiv 0\pmod{p}$ and $\neg(f'(r)\equiv 0) \pmod{p},$ then there is a unique solution $r_k$ modulo  $p^k$ for $k=2,3, \ldots $ such that $r_k=r_{k-1}-f\left(r_{k-1}\right)\overline{f'(r)}.$

Using Hensel’s Lifting Theorem

Example. Solve the polynomial congruence equation \begin{equation}\label{pce1}f(x)=x^2+x+47\equiv 0\pmod{2401}.\end{equation}

Solution. Since $2401=7^4,$ first we consider the equation $f(x)\equiv 0 \pmod{7}.$ By inspection, we see that the solutions  are $x=1$ and $x=5.$ Note that, $f'(x)=2x+1.$ For $x=1$ we find that $f'(1)\equiv 3  \pmod{7}.$ Thus $x=1$ lifts successively to unique solutions modulo each power of $7.$  We set $x_1=1$. Then, since $(3)(5)\equiv 1 \pmod{7}$ we have $\overline{f'(1)}=5,$ and so \begin{align*} x_2& =x_1-f\left(x_1\right)\overline{f'(1)}=1-f(1)(5)=1-(49)(5)=-244\equiv 1  \pmod{49} \\ x_3& =x_2-f\left(x_2\right)\overline{f'(1)}=1-f(1)(5)=1-(49)(5)=-244\equiv 99  \pmod{343} \\ x_4& =x_3-f \left( x_3 \right) \overline{f'(1)}=99-f(99)(5)=99-(9947)(5)\equiv 785 \pmod{2401}\end{align*} So we have lifted $x\equiv 1  \pmod{7}$ to a solution $x=785  \pmod{2401}.$ For $x=5$ we find that $f'(5)\equiv 4  \pmod{7}.$ Thus $x=5$ lifts successively to unique solutions modulo each power of $7.$

We set $x_1=5.$ Then, since $(4)(2)\equiv 1  \pmod{7}$ we have $\overline{f'(5)}=2,$ and so \begin{align*}x_2 & =5-f(5)(2)=5-(77)(2)\equiv 47 \pmod{49} \\ x_3 & =47-f(47)(2)=47-(2303)(2)=243\equiv 243  \pmod{343} \\ x_4 & =243-f(243)(2)=243-(59339)(2)\equiv 1615  \pmod{2401} \end{align*} So we have lifted $x\equiv 5  \pmod{7}$ to a solution $x=1615 \pmod{2401}.$ Therefore the solutions to \eqref{pce1} are $x\equiv 785 \pmod{2401}$ and $x\equiv 1615 \pmod{2401}$.

$$ \begin{array}{|c|c|c|c|c|}   \hline x  &  f(x)  & f'(x) & \overline{f'(x)} &  \pmod{7} \\ \hline   0 & 5 & – & – & –  \\  \hline 1 & 0 & 3 & 5 & \begin{array}{c|c} k & x_k=x_{k-1}-f\left(x_{k-1}\right)\overline{f'(x)}  \\   \hline k=1 & x_1\equiv 1 \pmod{7^1}  \\ k=2 & x_2=1-f(1)*5\equiv 1 \pmod{7^2} \\ k=3 & x_2=1-f(1)*5\equiv 99 \pmod{7^3} \\ k=4 & x_2=99-f(99)*5\equiv 785 \pmod{7^4} \\ \end{array} \\ \hline 2 & 4 & – & – & –  \\ \hline 3 & 3 & – & – & – \\   \hline 4 & 4 & – & – & – \\   \hline 5 & 0 & 4 & 2 & \begin{array}{c|c}   k & x_k=x_{k-1}-f\left(x_{k-1}\right)\overline{f'(x)}  \\  \hline k=1 & x_1\equiv 5 \pmod{7^1}  \\   k=2 & x_2=5-f(5)*2\equiv 47 \pmod{7^2}  \\ k=3 & x_2=47-f(47)*2\equiv 243 \pmod{7^3} \\ k=4 & x_2=243-f(243)*2\equiv 1615 \pmod{7^4} \\ \end{array} \\ \hline 6 & 5 & – & – & –  \\ \hline \end{array}$$

Solving a Polynomial Congruence

Example.  Consider trying to solve the polynomial congruence equation  \begin{equation} \label{pce4} f(x)=x^5-3x^4+7x^3-2x^2-9x+6\equiv 0 \pmod{165}. \end{equation}

Solution. Since $165=(3)(5)(11),$ by inspection we solve the following congruences, and we have  $$f(x)\equiv 0\pmod{3}\Longrightarrow x\equiv 0,1\pmod{3} $$ $$ f(x)\equiv 0 \pmod{5} \Longrightarrow x\equiv 1, 2, 3\pmod{5}$$ $$f(x)\equiv 0\pmod{11} \Longrightarrow x\equiv 1, 6, 8\pmod{11}$$

$$\begin{array}{l|l} x & f(x) \pmod{25} \\ \hline 0 & \neg(15\equiv 0) \\ 5 & \neg(15 \equiv 0) \\ 10 & \neg(15 \equiv 0) \\ 15 & \neg(15 \equiv 0) \\ 20 & \neg(15 \equiv 0) \end{array} \qquad \begin{array}{l|l} x & f(x) \pmod{25} \\  \hline 0 & \neg(14\equiv 0) \\ 7 &  \neg(14 \equiv 0) \\ 14 & \neg(14 \equiv 0) \\ 21 & \neg(14 \equiv 0) \\ 28 & \neg(14 \equiv 0) \\ 35 & \neg(14 \equiv 0) \\ 42 & \neg(14 \equiv 0) \\ \end{array}$$

Thus there are a total of $(2)(3)(3)=18$ solutions to \eqref{pce4}; for example to find one of them we solve the system $x\equiv 0 \pmod{3}$, $x\equiv 1 \pmod{5}$, $x\equiv 1 \pmod{11}$.  Using the Chinese Remainder Theorem we obtain the solution $x\equiv 111 \pmod{165}.$

The other 17 solutions are also found using the Chinese Remainder Theorem.

Solving Another Polynomial Congruence

Example.  Solve the polynomial congruence equation \begin{equation*} f(x)=x^6-2x^5-35\equiv 0 \pmod{6125}. \end{equation*}

Solution.  Since $6125=5^37^2,$ first we consider the equation $f(x)\equiv 0 \pmod{5}.$ By inspection, we see that the  solutions are $x=0$ and $x=2$ modulo 5. Note that, $f'(x)=6x^5-10x^4$.  For $x=0$ we find that $f'(0)\equiv 0 \pmod{5}.$ Thus we check, $f(0)=-35\equiv 15 \pmod{25}$ and so $x=0$ does not lift  to a solution modulo $5^k$. For $x=2$ we find that $f'(2)=32\equiv 2 \pmod{5}$ and so $x=2$ has unique lifts modulo $5^k.$ We set $x_1=2.$  Then, since  $(2)(3)\equiv 1\pmod{5}$ we have $\overline{f'(2)}=3,$ and so \begin{align*} x_2 & =2-f(2)(3)=2-(-35)(3)\equiv 7\pmod{25} \\ x_3 & =7-f(7)(3)=7-(76832)(3)\equiv 7 \pmod{125}.\end{align*}

So we have lifted $x\equiv 5 \pmod{5}$ to a solution $x\equiv 7 \pmod{125}$; that is we have  solved $f(x)\equiv  0 \pmod{125}.$  Now we consider the case for $f(x)\equiv 0 \pmod{7}.$  By inspection, we see that the solutions are $x=0$ and  $x=2 \pm{7}$. For $x=0$ we find that $f'(0)\equiv 0 \pmod{7}.$  Thus we check, $f(0)=-35\equiv 7 \pmod{49}$ and so $x=0$  does not lift to a solution modulo $7^k$. For $x=2$ we find that $f'(2)=32\equiv 4 \pmod{7}$ and so $x=2$ has unique lifts modulo $7^k.$  We set $x_1=2.$ Then, since  $(4)(2)\equiv 1 \pmod{7}$ we have $\overline{f'(2)}=2,$ and so $$ x_2=2-f(2)(2)=2-(-35)(2)\equiv 23 \pmod{49}. $$  So we have lifted $x\equiv 2 \pmod{7}$ to a solution $x\equiv 23 \pmod{49}$; that is we have solved $f(x)\equiv  0 \pmod{49}.$ 

It remains to solve the system $x\equiv 7 \pmod{125}$, $x\equiv 23 \pmod{49}$. This is easy since $(125,49)=1$ and we have $125(-29)+49(74)=1$ and so $$x=125(-29)(23)+49(74)(7)=-57993\equiv 3257\pmod{6125}$$ as desired.

Outline Another Polynomial Congruence

Example. Outline how to solve the polynomial congruence equation. \begin{equation*} -82+12 x-10 x^2+x^3\equiv 0 \pmod{33075} \end{equation*}

Solution. The unique factorization of $33075,$ is $3^35^27^2$ and the derivative is $f'(x)=3 x^2-20 x+12.$

$$\begin{array}{|c|c|c|c|c|c|}   \hline x  &  f(x)  & f'(x) & \overline{f'(x)} &  \pmod{3} \\ \hline  0 & 2 & – & – & –  \\ \hline 1 & 2 & – & – & –  \\ \hline 2 & 0 & 2 & 2 &  \begin{array}{c|c}  k & x_k=x_{k-1}-f\left(x_{k-1}\right)\overline{f'(x)}  \\  \hline 1 & x_1\equiv 2 \pmod{3^1}  \\  2 & x_2=2-f(2)*2\equiv 2 \pmod{3^2}  \\  3 & x_3=2-f(2)*2\equiv 20 \pmod{3^3} \end{array}  \\  \hline \end{array}$$

$$ \begin{array}{|c|c|c|c|c|}   \hline x  &  f(x)  & f'(x) & \overline{f'(x)} &  \pmod{5} \\ \hline 0 & 3 & – & – & –  \\  \hline 1 & 1 & – & – & –  \\  \hline 2 & 0 & 4 & 4 &  \begin{array}{c|c}    k & x_k=x_{k-1}-f\left(x_{k-1}\right)\overline{f'(x)}  \\   \hline k=1 & x_1\equiv 2 \pmod{5^1}  \\   k=2 & x_2=2-f(2)*4\equiv 12 \pmod{5^2}  \end{array}   \\   \hline 3 & 1 & – & – & –  \\   \hline 4 & 0 & 0 & – & \begin{array}{c} \neg(f(x)\equiv 0) \pmod{25} \\ \therefore  x \text{ does not lift where $x=4,9,14,19,24$} \end{array} \\ \hline \end{array}$$

$$ \begin{array}{|c|c|c|c|c|}   \hline x  &  f(x)  & f'(x) & \overline{f'(x)} &  \pmod{7} \\ \hline 0 & 2 & – & – & –  \\   \hline 1 & 5 & – & – & –  \\   \hline  2 & 1 & – & – & –  \\   \hline 3 & 3 & – & – & –  \\    \hline 4 & 3 & – & – & –  \\    \hline 5 & 0 & 1 & 1 & \begin{array}{c|c}   k & x_k=x_{k-1}-f\left(x_{k-1}\right)\overline{f'(x)}  \\  \hline k=1 & x_1=5 \pmod{7^1} \\     k=2 & x_2=5-f(5)*1\equiv 5 \pmod{7^2}  \end{array}    \\   \hline 6 & 0 & 0 & – & \begin{array}{c} \fneg((x)\equiv 0) \pmod{49} \\ \therefore  x \text{ does not lift where $x=6,13,20,27,34,41,48$} \end{array} \\ \hline \end{array} $$

After applying Hensel’s Lifting theorem, we now must solve the system $x\equiv 20 \pmod{27}$,  $x\equiv 12 \pmod{25}$,  $x\equiv 5 \pmod{49}$. The Chinese remainder theorem yields $$ x\equiv 20\left(\frac{33075}{27}\right)y_1+12\left(\frac{33075}{25}\right)y_2+5\left(\frac{33075}{49}\right)y_3  \pmod{ 33075} $$where $y_1, y_2,$ and $y_3$ are solutions to $$ \frac{33075}{27}y_1\equiv 1 \pmod{27} \Longrightarrow y_1=19$$ $$ \frac{33075}{25}y_2\equiv 1 \pmod{25} \Longrightarrow y_2=12$$ $$ \frac{33075}{49}y_3\equiv 1 \pmod{49} \Longrightarrow y_3=40$$ Therefore, $$x \equiv 20 \left( \frac{33075}{27} \right) 19+12 \left(\frac{33075}{25} \right)12 + 5\left( \frac{33075}{49}\right ) 40 \equiv 30287 \pmod{33075}$$ is the solution.

Full Example of Another Polynomial Congruence

Example. Solve the polynomial congruence equation \begin{equation*} 2308-567 x-6 x^2+35x^3\equiv 0 \pmod{148225}. \end{equation*}

Solution.  The unique factorization of $148225,$ is $5^27^211^2$ and the derivative is  $f'(x)=105 x^2-12 x-567.$  We apply Hensel’s Lifting theorem and display the computations in the following tables. 

First we find that $$ \begin{array}{|c|c|c|c|c|}  \hline x  &  f(x)  & f'(x) & \overline{f'(x)} &  \pmod{5} \\ \hline 0 & 3 & – & – & – \\    \hline 1 & 0 & 1 & 1 & \begin{array}{c|c}   k & x_k=x_{k-1}-f\left(x_{k-1}\right)\overline{f'(x)} \\   \hline k=1 & x_1\equiv 1 \pmod{5^1} \\   k=2 & x_2=1-f(1)*1\equiv 6 \pmod{5^2}  \end{array}   \\   \hline 2 & 0 & 4 & 4 & \begin{array}{c|c}   k & x_k=x_{k-1}-f\left(x_{k-1}\right)\overline{f'(x)}  \\   \hline k=1 & x_1\equiv 2\pmod{5^1}  \\   k=2 & x_2=2-f(2)*4\equiv 7\pmod{5^2}  \end{array}    \\   \hline 3 & 3 & – & – & –  \\   \hline 4 & 4 & – & – & –  \\ \hline \end{array} $$

We continue calculating

$$\begin{array}{|c|c|c|c|c|}   \hline x  &  f(x)  & f'(x) & \overline{f'(x)} &  \pmod{7} \\ \hline    0 & 5 & – & – & –  \\     \hline 1 & 6 & – & – & –  \\     \hline 2 & 2 & – & – & –  \\     \hline 3 & 0 & 6 & 6 &  \begin{array}{c|c}    k & x_k=x_{k-1}-f\left(x_{k-1}\right)\overline{f'(x)}  \\   \hline k=1 & x_1\equiv 3 \pmod{7^1}  \\ k=2 & x_2=3-f(3)*6\equiv 31 \pmod{7^2} \\ \end{array}    \\   \hline 4 & 0 & 1 & 1 & \begin{array}{c|c}    k & x_k=x_{k-1}-f\left(x_{k-1}\right)\overline{f'(x)}  \\  \hline k=1 & x_1\equiv 4 \pmod{7^1}  \\   k=2 & x_2=4-f(4)*1\equiv 25 \pmod{7^2}  \\ \end{array}    \\   \hline 5 & 2 & – & – & –  \\   \hline 6 & 6 & – & – & –  \\ \hline \end{array}$$

We continue calculating

$$  \begin{array}{|c|c|c|c|c|}   \hline x  &  f(x)  & f'(x) & \overline{f'(x)} &  \pmod{11} \\ \hline    0 & 9 & – & – & –  \\     \hline 1 & 10 & – & – & –  \\     \hline 2 & 0 & f'(x)\equiv 5 & 9 &    \begin{array}{c|c}   k & x_k=x_{k-1}-f\left(x_{k-1}\right)\overline{f'(x)}  \\     \hline k=1 & x_1\equiv 2 \pmod{11^1} \\    k=2 & x_2=2-f(2)*9\equiv 79 \pmod{11^2}   \end{array}    \\   \hline  3 & 2 & – & – & –  \\ \hline 4 & 6 & – & – & –  \\     \hline 5 & 2 & – & – & –  \\     \hline 6 & 2 & – & – & –  \\ \hline 7 & 7 & – & – & –  \\     \hline 8 & 7 & – & – & –  \\     \hline 9 & 3 & – & – & –  \\ \hline 10 & 7 & – & – & –  \\ \hline \end{array}  $$

We now must solve the four systems 

$$\begin{cases}x\equiv 6 & \pmod{25}  \\   x\equiv 31 & \pmod{49}  \\   x\equiv 79 & \pmod{121} \end{cases} \qquad \begin{cases} x\equiv 7 & \pmod{25}  \\   x\equiv 31 & \pmod{49}  \\   x\equiv 79 & \pmod{121}  \end{cases} $$

$$\begin{cases} x\equiv 6 & \pmod{25}  \\   x\equiv 25 & \pmod{49}  \\   x\equiv 79 & \pmod{121}  \end{cases} \qquad \begin{cases} x\equiv 7 & \pmod{25}  \\    x\equiv 25 & \pmod{49}  \\   x\equiv 79 & \pmod{121}  \end{cases} $$

The Chinese remainder theorem yields the four solutions

$$ x\equiv 6\left(\frac{148225}{25}\right)u_1+31\left(\frac{148225}{49}\right)u_2+79\left(\frac{148225}{121}\right)u_3 \pmod{148225}$$ $$x\equiv 7\left(\frac{148225}{25}\right)u_1+31\left(\frac{148225}{49}\right)u_2+79\left(\frac{148225}{121}\right)u_3 \pmod{148225}$$ $$ x\equiv 6\left(\frac{148225}{25}\right)u_1+25\left(\frac{148225}{49}\right)u_2+79\left(\frac{148225}{121}\right)u_3 \pmod{148225}$$ $$x\equiv 7\left(\frac{148225}{25}\right)u_1+25\left(\frac{148225}{49}\right)u_2+79\left(\frac{148225}{121}\right)u_3 \pmod{148225}$$ where $u_1, u_2$ and $u_3$ are found via $$\left(148225/25\right)u_1\equiv 1 \pmod{25} \Longrightarrow u_1=19$$ $$\left(148225/49\right)u_2\equiv 1 \pmod{49} \Longrightarrow u_2=15$$ $$\left(148225/121\right)u_3 \equiv 1 \pmod{121} \Longrightarrow u_3=113$$

Therefore the solutions are

$x \equiv122531 \pmod{148225}$, $x \equiv 86957 \pmod{148225}$, $x \equiv 146731 \pmod{148225}$, and $x\equiv 111157 \pmod{148225}$ as the only solutions.

Exercises on Solving Polynomial Congruences I

Exercise. The following polynomial congruences all have 10 or fewer solutions. Use unique factorization, Hensel’s Lifting theorem and the Chinese remainder theorem to solve them.

$(1) \quad 2+3 x-2 x^2\equiv 0 \pmod{1155} $

$(2) \quad 5+11 x-12 x^2\equiv 0 \pmod{8085}$

$(3) \quad 2+3 x-2 x^2\equiv 0 \pmod{3465}$

$(4) \quad 5+11 x-12 x^2\equiv 0 \pmod{24255}$

$(5) \quad 2+3 x-2 x^2\equiv 0 \pmod{12705}$

$(6) \quad 5+11 x-12 x^2\equiv 0 \pmod{5775}$

$(7) \quad 2+3 x-2 x^2\equiv 0 \pmod{8085}$

$(8) \quad 5+11 x-12 x^2\equiv 0 \pmod{63525}$

$(9) \quad 3+11 x+10 x^2\equiv 0 \pmod{1925}$

$(10) \quad 120-9 x+8 x^2\equiv 0 \pmod{1155}$

$(11) \quad 3+11 x+10 x^2\equiv 0 \pmod{5775}$

$(12) \quad 120-9 x+8 x^2\equiv 0 \pmod{5775}$

$(13) \quad 3+11 x+10 x^2\equiv 0 \pmod{17325}$

$(14) \quad 120-9 x+8 x^2\equiv 0 \pmod{40425}$

$(15) \quad 3+11 x+10 x^2\equiv 0 \pmod{63525}$

$(16) \quad 120-9 x+8 x^2\equiv 0 \pmod{698775}$

$(17) \quad 180-15 x+11 x^2\equiv 0 \pmod{1155}$

$(18) \quad 46-5 x-9 x^2\equiv 0 \pmod{315}$

$(19) \quad 180-15 x+11 x^2\equiv 0 \pmod{56595}$

$(20) \quad 46-5 x-9 x^2\equiv 0 \pmod{10395}$

$(21) \quad 180-15 x+11 x^2\equiv 0 \pmod{24255}$

$(22) \quad 46-5 x-9 x^2\equiv 0 \pmod{51975}$

$(23) \quad 180-15 x+11 x^2\equiv 0 \pmod{17325}$

$(24) \quad 46-5 x-9 x^2\equiv 0 \pmod{121275}$

$(25) \quad 4+6 x+2 x^2\equiv 0 \pmod{312987} $

$(26) \quad 4+6 x+2 x^2\equiv 0 \pmod{521645}$

Exercises on Solving Polynomial Congruences II

Exercise. Solve the polynomial congruence.

$(1) \quad x^2+4x+2\equiv 0 \pmod{7}$

$(2) \quad x^2+4x+2\equiv 0 \pmod{49}$

$(3) \quad x^2+4x+2\equiv 0 \pmod{343}$

$(4) \quad x^3+8x^2-x-1\equiv 0 \pmod{11}$

$(5) \quad x^3+8x^2-x-1\equiv 0 \pmod{121}$

$(6) \quad x^3+8x^2-x-1\equiv 0 \pmod{1331}$

$(7) \quad x^2+x+47\equiv 0 \pmod{2401}$

$(8) \quad x^2+x+34\equiv 0 \pmod{81}$

$(9) \quad 13x^7-42x-649\equiv 0 \pmod{1323}$

$(10) \quad x^8-x^4+1001\equiv 0 \pmod{539}$

$(11) \quad x^4+2x+36\equiv 0 \pmod{4375}$

$(12) \quad x^6-2x^5-35\equiv 0 \pmod{6125}$

Exercise. Let $a$ be an integer and $p$ a prime such that $(a,p)=1.$ Use Hensel’s Lifting theorem to solve the polynomial congruence equation $a x\equiv  1 \pmod{p^k}$ for all positive integer $k.$

Exercise. Solve the polynomial congruence equation $2x^2-3x+12\equiv 0 \pmod{343}.$

Exercises on Solving Polynomial Congruences III

Exercise. Each of the following polynomial congruence equations have fewer than 50 solutions. 

  1. $9 x^5+10 x^4+2 x^3+ x^2+ x+1\equiv 0 \pmod{12960}$ 
  2. $4 x^5+6 x^4+3 x^3+ x^2+ x+1\equiv 0 \pmod{12960}$ 
  3. $6 x^5+6 x^4+ x^3+ x^2+ x+1\equiv 0 \pmod{19440}$
  4. $9 x^5+10 x^4+2 x^3+ x^2+ x+1\equiv 0 \pmod{19440}$
  5. $9 x^5+10 x^4+2 x^3+ x^2+ x+1\equiv 0 \pmod{38880}$ 
  6. $4 x^5+6 x^4+3 x^3+ x^2+ x+1\equiv 0 \pmod{38880}$ 
  7. $6 x^5+6 x^4+ x^3+ x^2+ x+1\equiv 0 \pmod{10800}$
  8. $8 x^5+10 x^4+3 x^3+ x^2+ x+1\equiv 0 \pmod{10800}$
  9. $4 x^5+6 x^4+3 x^3+ x^2+ x+1\equiv 0 \pmod{21600}$
  10. $6 x^5+10 x^4+5 x^3+ x^2+ x+1\equiv 0 \pmod{21600}$
  11. $3 x^5+4 x^4+2 x^3+ x^2+ x+1\equiv 0 \pmod{16200}$
  12. $4 x^5+6 x^4+3 x^3+ x^2+ x+1\equiv 0 \pmod{16200}$
  13. $6 x^5+6 x^4+ x^3+ x^2+ x+1\equiv 0 \pmod{32400}$
  14. $8 x^5+10 x^4+3 x^3+ x^2+ x+1\equiv 0 \pmod{32400}$
  15. $4 x^5+6 x^4+3 x^3+ x^2+ x+1\equiv 0 \pmod{64800}$
  16. $6 x^5+10 x^4+5 x^3+ x^2+ x+1\equiv 0 \pmod{64800}$
  17. $4 x^5+4 x^4+5 x^3+5 x^2+ x+1\equiv 0 \pmod{12150}$
  18. $3 x^5+2 x^4+5 x^3+6 x^2+ x+1\equiv 0 \pmod{12150}$
  19. $3 x^5+4 x^4+2 x^3+ x^2+ x+1\equiv 0 \pmod{24300}$
  20. $4 x^5+3 x^4+ x^3+2 x^2+ x+1\equiv 0 \pmod{24300}$

Exercises on Solving Polynomial Congruences IV

Exercise. Each of the following polynomial congruence equations have fewer than 50 solutions. 

  1. $4 x^5+3 x^4+ x^3+2 x^2+ x+1\equiv 0 \pmod{24300}$
  2. $3 x^5+4 x^4+2 x^3+ x^2+ x+1\equiv 0 \pmod{48600}$
  3. $4 x^5+6 x^4+3 x^3+ x^2+ x+1\equiv 0 \pmod{48600}$
  4. $6 x^5+6 x^4+ x^3+ x^2+ x+1\equiv 0 \pmod{97200}$
  5. $8 x^5+10 x^4+3 x^3+ x^2+ x+1\equiv 0 \pmod{97200}$
  6. $4 x^5+6 x^4+3 x^3+ x^2+ x+1\equiv 0 \pmod{194400}$
  7. $6 x^5+10 x^4+5 x^3+ x^2+ x+1\equiv 0 \pmod{194400}$
  8. $4 x^5+6 x^4+3 x^3+ x^2+ x+1\equiv 0 \pmod{12000}$
  9. $7 x^5+10 x^4+4 x^3+ x^2+ x+1\equiv 0 \pmod{12000}$
  10. $6 x^5+6 x^4+ x^3+ x^2+ x+1\equiv 0 \pmod{18000}$
  11. $8 x^5+10 x^4+3 x^3+ x^2+ x+1\equiv 0 \pmod{18000}$
  12. $4 x^5+6 x^4+3 x^3+ x^2+ x+1\equiv 0 \pmod{36000}$
  13. $6 x^5+10 x^4+5 x^3+ x^2+ x+1\equiv 0 \pmod{36000}$
  14. $3 x^5+4 x^4+2 x^3+ x^2+ x+1\equiv 0 \pmod{13500}$
  15. $4 x^5+3 x^4+ x^3+2 x^2+ x+1\equiv 0 \pmod{13500}$
  16. $3 x^5+4 x^4+2 x^3+ x^2+ x+1\equiv 0 \pmod{27000}$
  17. $4 x^5+6 x^4+3 x^3+ x^2+ x+1\equiv 0 \pmod{27000}$
  18. $6 x^5+6 x^4+ x^3+ x^2+ x+1\equiv 0 \pmod{54000}$
  19. $8 x^5+10 x^4+3 x^3+ x^2+ x+1\equiv 0 \pmod{54000}$
  20. $4 x^5+6 x^4+3 x^3+ x^2+ x+1\equiv 0 \pmod{108000}$
  21. $6 x^5+10 x^4+5 x^3+ x^2+ x+1\equiv 0 \pmod{108000}$

Exercises on Solving Polynomial Congruences V

Exercise. Each of the following polynomial congruence equations have fewer than 50 solutions. 

  1. $3 x^5+2 x^4+5 x^3+6 x^2+ x+1\equiv 0 \pmod{20250}$
  2. $6 x^5+6 x^4+ x^3+ x^2+ x+1\equiv 0 \pmod{162000}$
  3. $3 x^5+5 x^4+4 x^3+3 x^2+2 x+1\equiv 0 \pmod{20250}$
  4. $3 x^5+4 x^4+2 x^3+ x^2+ x+1\equiv 0 \pmod{40500}$
  5. $4 x^5+3 x^4+ x^3+2 x^2+ x+1\equiv 0 \pmod{40500}$
  6. $3 x^5+4 x^4+2 x^3+ x^2+ x+1\equiv 0 \pmod{81000}$
  7. $4 x^5+6 x^4+3 x^3+ x^2+ x+1\equiv 0 \pmod{81000}$
  8. $8 x^5+10 x^4+3 x^3+ x^2+ x+1\equiv 0 \pmod{162000}$
  9. $4 x^5+6 x^4+3 x^3+ x^2+ x+1\equiv 0 \pmod{324000}$
  10. $6 x^5+10 x^4+5 x^3+ x^2+ x+1\equiv 0 \pmod{324000}$
  11. $3 x^5+2 x^4+5 x^3+6 x^2+ x+1\equiv 0 \pmod{60750}$
  12. $6 x^5+6 x^4+ x^3+ x^2+ x+1\equiv 0 \pmod{486000}$
  13. $3 x^5+5 x^4+4 x^3+3 x^2+2 x+1\equiv 0 \pmod{60750}$
  14. $3 x^5+4 x^4+2 x^3+ x^2+ x+1\equiv 0 \pmod{121500}$
  15. $4 x^5+3 x^4+ x^3+2 x^2+ x+1\equiv 0 \pmod{121500}$
  16. $3 x^5+4 x^4+2 x^3+ x^2+ x+1\equiv 0 \pmod{243000}$
  17. $4 x^5+6 x^4+3 x^3+ x^2+ x+1\equiv 0 \pmod{243000}$
  18. $8 x^5+10 x^4+3 x^3+ x^2+ x+1\equiv 0 \pmod{486000}$
  19. $4 x^5+6 x^4+3 x^3+ x^2+ x+1\equiv 0 \pmod{972000}$
  20. $6 x^5+10 x^4+5 x^3+ x^2+ x+1\equiv 0 \pmod{972000}$

Exercises on Solving Polynomial Congruences VI

Exercise. Each of the following polynomial congruence equations have fewer than 50 solutions.

  1. $1 x^5+10 x^4+2 x^3+ x^2+ x+1\equiv 0 \pmod{20000}$
  2. $4 x^5+6 x^4+3 x^3+ x^2+ x+1\equiv 0 \pmod{20000}$
  3. $3 x^5+4 x^4+2 x^3+ x^2+ x+1\equiv 0 \pmod{15000}$
  4. $4 x^5+6 x^4+3 x^3+ x^2+ x+1\equiv 0 \pmod{15000}$
  5. $6 x^5+6 x^4+ x^3+ x^2+ x+1\equiv 0 \pmod{30000}$
  6. $8 x^5+10 x^4+3 x^3+ x^2+ x+1\equiv 0 \pmod{30000}$
  7. $4 x^5+6 x^4+3 x^3+ x^2+ x+1\equiv 0 \pmod{60000}$
  8. $7 x^5+10 x^4+4 x^3+ x^2+ x+1\equiv 0 \pmod{60000}$
  9. $5 x^5+3 x^4+3 x^3+5 x^2+ x+1\equiv 0 \pmod{11250}$
  10. $2 x^5+3 x^4+6 x^3+5 x^2+ x+1\equiv 0 \pmod{11250}$
  11. $3 x^5+4 x^4+2 x^3+ x^2+ x+1\equiv 0 \pmod{22500}$
  12. $4 x^5+3 x^4+ x^3+2 x^2+ x+1\equiv 0 \pmod{22500}$
  13. $3 x^5+4 x^4+2 x^3+ x^2+ x+1\equiv 0 \pmod{45000}$
  14. $4 x^5+6 x^4+3 x^3+ x^2+ x+1\equiv 0 \pmod{45000}$
  15. $6 x^5+6 x^4+ x^3+ x^2+ x+1\equiv 0 \pmod{90000}$
  16. $8 x^5+10 x^4+3 x^3+ x^2+ x+1\equiv 0 \pmod{90000}$
  17. $4 x^5+6 x^4+3 x^3+ x^2+ x+1\equiv 0 \pmod{180000}$
  18. $6 x^5+10 x^4+5 x^3+ x^2+ x+1\equiv 0 \pmod{180000}$
  19. $6 x^5+9 x^4+8 x^3+5 x^2+ x+1\equiv 0 \pmod{33750}$
  20. $3 x^5+2 x^4+5 x^3+6 x^2+ x+1\equiv 0 \pmod{33750}$
  21. $3 x^5+4 x^4+2 x^3+ x^2+ x+1\equiv 0 \pmod{67500}$

Leave a Comment