Skip to main content
Logo image

Section 7.2 From Linear to General

In this section, we will take two ideas we already used with linear congruences, and see how they can be modified to apply in any polynomial situation. (Note that, as in Fact 6.1.4, we only consider polynomials with integer coefficients.)

Subsection 7.2.1 Combining solutions

One of the most important things we can do is study congruences with prime (power) modulus, because we can combine their solutions to get solutions for any congruences when we combine the Chinese Remainder Theorem and Fundamental Theorem of Arithmetic (recall Proposition 6.5.1). Even more interestingly, we can combine the numbers of solutions.
Informally, if you want to get the total number of solutions of a polynomial congruence, just write the modulus as a product of prime powers \(n=\prod_{i=1}^k p_i^{e_i}\text{,}\) find out how many solutions the congruence has with each prime power modulus, then multiply those numbers for the total number of solutions.

Example 7.2.1.

For instance, if \(f(x)\equiv 0\) has 2 solutions modulo 3, 1 solution modulo 5, and 3 solutions modulo 7, it would have \(2\cdot 1\cdot 3=6\) solutions modulo \(105=3\cdot 5\cdot 7\text{.}\)
We will state this for the general case of a coprime factorization of \(n\text{,}\) though again the prime power factorization is usually the most useful.
For all \(i\text{,}\) among the \(N_i\) solutions to the \(i\)th congruence choose a solution \(a_i\text{,}\) so that
\begin{equation*} f(a_i)\equiv 0\text{ (mod }n_i)\text{.} \end{equation*}
Since the moduli \(n_i\) for these congruences are coprime, we can use the Chinese Remainder Theorem to obtain one number \(a\) such that \(a\equiv a_i\) (mod \(n_i\)) for all \(i\text{.}\)
Since (integer) polynomials are exclusively made up of addition and multiplication on integers, and addition and multiplication are well-defined, we also have \(f(a)\equiv f(a_i)\equiv 0\) (mod \(n_i\)), so as promised we have a solution
\begin{equation*} f(a)\equiv 0\left(\text{mod }\prod_{i=1}^k n_i\right)\text{.} \end{equation*}
Each such set of \(a_i\) will yield a solution, and if \(\{a_i\}_{i=1}^k\neq \{b_i\}_{i=1}^k\) then if \(a_j\not\equiv b_j\) (mod \(n_j\)) they certainly are not equivalent modulo \(\prod_{i=1}^k n_i\) either.
Now multiply how many solutions there are for each \(n_i\) to get the total number of combinations of solutions. If there are \(N_i\) solutions modulo \(n_i\text{,}\) we would get \(\prod_{i=1}^k N_i\text{.}\) There aren’t any additional answers, because any answer to the ‘big’ congruence automatically also satisfies the ‘little’ ones; if \(\prod_{i=1}^k n_i\mid f(a)\text{,}\) then certainly \(n_i\mid f(a)\) as well.

Subsection 7.2.2 Prime power congruences

We have already discussed prime power congruences in Subsection 6.5.2. Recall that in Examples 6.5.3 and 6.5.4 we took the (obvious) solution of \(4x\equiv 1\text{ (mod }7)\) (namely, \(x=[2]\)), and got solutions (mod \(49\)) and even (mod \(343\)) from it relatively easily.
But that is essentially the same as asking for solutions to \(4x-1\equiv 0\text{,}\) a linear congruence. Let’s see if we can generalize this method for more general polynomial congruences.
The key was taking the already known fact \(7\mid 1-4\cdot 2\) and then cancelling out \(7\) from the entire congruence to get that
\begin{equation*} \frac{1-4\cdot 2}{7}\equiv 4k\text{ (mod }7\text{)}\text{.} \end{equation*}
We were able to solve the resulting congruence \(-1\equiv 4k\) (mod \(7\)), which had solution \(k\equiv 5\) (mod \(7\)). Finally, we plugged that back in to get a solution to \(4x\equiv 1\) (mod \(7^2\)), which was
\begin{equation*} 2+7k=2+7\cdot 5=37\text{ (mod }7^2\text{)} \end{equation*}
as the solution.
Can we use this approach to get solutions to more advanced congruences as well, like the simple quadratics we’ve started exploring in this chapter? The answer is yes, with a minor caveat. The preceding discussion was just a basic form of the following.
If \(p\) and \(f'(x_{e-1})\) are relatively prime, then by Proposition 5.1.1 any linear congruence of the form \(f'(x_{e-1})k\equiv b \text{ (mod }p)\) with coefficient \(a=f'(x_{e-1})\text{,}\) unknown \(k\text{,}\) and known \(b\) can be solved (uniquely modulo \(p\text{,}\) given the \(\gcd\) condition). Since \(x_{e-1}\) is a known zero of \(f(x)\) for modulus \(p^{e-1}\text{,}\) we know that as an integer (not modulo anything) \(p^{e-1}\mid f(x_{e-1})\text{.}\)
This means that \(-\frac{f(x_{e-1})}{p^{e-1}}\) exists in \(\mathbb{Z}\text{,}\) so if we set \(b=-\frac{f(x_{e-1})}{p^{e-1}}\) there will indeed be a solution \(k\) to the congruence \(\frac{f(x_{e-1})}{p^{e-1}}+k\cdot f'(x_{e-1})\equiv 0\text{ (mod }p\text{)}\text{.}\) Then the only question becomes why \(x_{e}=x_{e-1}+kp^{e-1}\) is actually a solution to \(f(x)\equiv 0\text{ (mod }p^{e})\text{.}\)
To see this, think of \(f\) as a polynomial with terms of the form \(c_i x^i\text{,}\) e.g. \(f(x)=\sum_{i=0}^n c_i x^i\text{.}\) Then \(f(x_{e-1}+kp^{e-1})\) can be expanded out term-by-term in the following form:
\begin{equation*} f(x_e)=f(x_{e-1}+kp^{e-1})=\sum_{i=0}^n c_i (x_{e-1}+kp^{e-1})^i\text{.} \end{equation*}
Let’s break this down on a term-by-term basis in the sum. Each term will look like
\begin{equation*} c_i(x_{e-1}+kp^{e-1})^i = c_i x_{e-1}^i+c_i (x_{e-1}^{i-1}\cdot kp^{e-1})\cdot i+\text{ terms with at least }p^{(e-1)2}\text{.} \end{equation*}
Since \(e\geq 2\) in this context, the extra terms (from Taylor or binomial series 1 ) involving \(p^{(e-1)2}\) will be divisible by at least \(p^e\) and hence be trivial in that modulus. Thus, each term in the sum will be equivalent to
\begin{equation*} c_i x_{e-1}^i+c_i \cdot i x_{e-1}^{i-1}\cdot kp^{e-1}\text{ (mod }p^e)\text{.} \end{equation*}
Now add up the terms of the sum for all \(i\) to find out something about \(f(x_e)\text{.}\) Summing up the \(c_i x_{e-1}^i\) will give us \(f(x_{e-1})\text{,}\) while summing up \(i x_{e-1}^{i-1}\) is adding terms that look like the derivative of polynomials, so the sum of \(c_i\cdot i x_{e-1}^{i-1}\cdot kp^{e-1}\) yields \(f'(x_{e-1})\cdot kp^{e-1}\text{.}\) Summarizing this paragraph,
\begin{equation*} f(x_e)\equiv f(x_{e-1})+f'(x_{e-1})\cdot kp^{e-1}\text{ (mod }p^e)\text{.} \end{equation*}
By hypothesis \(p^{e-1}\mid f(x_{e-1})\text{,}\) and obviously \(p^{e-1}\mid f'(x_{e-1})\cdot kp^{e-1}\) and \(p^e\text{;}\) so by necessity \(p^{e-1}\mid f(x_e)\) as well. Now recall Proposition 5.2.6, where we are allowed to cancel a nonzero divisor from “all three sides” of a congruence. Then we have that
\begin{equation*} f(x_e)/p^{e-1}\equiv \frac{f(x_{e-1})}{p^{e-1}}+f'(x_{e-1})\cdot k\text{ (mod }p)\text{;} \end{equation*}
but the right-hand expression is divisible by \(p\) by our original hypothesis, so \(f(x_e)/p^{e-1}\equiv 0\text{ (mod }p)\text{.}\) Using Proposition 5.2.6 again we multiply everything by \(p^{e-1}\) and obtain
\begin{equation*} f(x_{e})\equiv 0\text{ (mod }p^e) \end{equation*}
as desired.

Historical remark 7.2.4. Hensel’s Lemma.

The German mathematician Kurt Hensel was a grandson of the famous pianist and composer Fanny Mendelssohn; he was apparently the first one to use the term Fermat’s Little Theorem for the result we will see in Theorem 7.5.3. The lemma as presented here is only the finite case of his use of it to develop the \(p\)-adic numbers, which one may think of power series expansions of modular arithmetic. See [E.2.15] for a good project introducing them.
Let’s use Hensel’s Lemma to take solutions to \(x^2+1\equiv 0\text{ (mod }5)\) and turn them into solutions modulo \(25\) and \(125\text{.}\) By inspection, the solutions to this congruence modulo \(5\) are \([2],[3]\) (or \([\pm 2]\)).

Example 7.2.5.

First let’s tackle \(x^2+1\equiv 0\text{ (mod }25)\text{.}\) By the preceding remark and the lemma, solutions modulo 25 will look like \(3+k\cdot 5\) or \(2+k\cdot 5\text{.}\) Further, \(f'(x)=2x\text{,}\) so for either solution modulo 5 the technical derivative condition is met.
Let \(x_1=3\text{.}\) Then the condition for \(k\) is
\begin{equation*} \frac{f(x_1)}{5}+k\cdot (2x_1)\equiv 0 \text{ (mod }5) \end{equation*}
which simplifies to \(2+6k\equiv 0\text{,}\) which solves to \(k\equiv -2\equiv 3\text{.}\) Then our solution to the congruence modulo \(25\) would be
\begin{equation*} x_2=x_1+3\cdot 5\equiv 3+3\cdot 5\equiv 18\text{ (mod }25) \end{equation*}
And indeed \(18^2+1=325\) is divisible by twenty-five.
Now try the same procedure with \(x_1=2\) to get the solution \(x_2\equiv 7\) in Exercise 7.7.3. (If you get stuck, see Example 16.1.3.)

Example 7.2.6.

We can try the same process with \(e=3\text{.}\) Taking (from the previous example, or the affiliated exercise) \(x_2\equiv 7\) yields, as a condition for \(k\text{,}\)
\begin{equation*} \frac{7^2+1}{25}+2\cdot 7k\equiv 0\text{ (mod }5)\text{.} \end{equation*}
This reduces to \(14k\equiv -2\text{ (mod }5)\text{,}\) which gives \(k=2\text{.}\) Indeed,
\begin{equation*} x_3 = x_2+2\cdot 5^2 \equiv 7+2\cdot 5^2 = 57 \end{equation*}
yields
\begin{equation*} 57^2+1=3250\equiv 0 \text{ (mod }125)\text{.} \end{equation*}
It’s good practice to try the same process with \(x_1=18\) instead in Exercise 7.7.3.
This is a very powerful technique. What is most interesting is that this is even interpretable as Newton’s method in calculus. How? Note that the result above can be rearranged as
\begin{equation*} x_{e}=x_{e-1}-\frac{f(x_{e-1})}{f'(x_{e-1})} \end{equation*}
since \(p^{e-1}\mid f(x_{e-1})\) and the technical condition is tantamount to saying \(f'(x_{e-1})\) has an inverse.

Remark 7.2.7.

In Newton’s method, if the derivative is zero our search for a solution fails. However, given the overall hypotheses of Hensel’s Lemma where instead \(\gcd(p,f'(x_{e-1}))\neq 1\text{,}\) finding some information is possible.
Examining the proof of Theorem 7.2.3, one can see that if \(p\mid f'(x_{e-1})\text{,}\) the congruence \(\frac{f(x_{e-1})}{p^{e-1}}+k\cdot f'(x_{e-1})\equiv 0\text{ (mod }p\text{)}\) can still have a solution if (and only if) \(p\mid \frac{f(x_{e-1})}{p^{e-1}}\) as well (that is, if \(p^e\mid f(x_{e-1})\)). In fact, in this case it doesn’t matter what \(k\) is! So all numbers of the form \(x_{e}=x_{e-1}+kp^{e-1}\) work.
If you didn’t notice this calculus connection, don’t feel bad! When we had the linear congruence \(f(x)=4x-1\) in Examples 6.5.3 and 6.5.4, the derivative was just \(f'(x)=4\) and it was not at all obvious that anything more than a trick was involved. Still, it’s another fascinating place where ideas from calculus can invade the world of number theory.
One way or another one of these series will have to enter in, unfortunately; [E.2.1, Section 4.3] has more of a binomial theorem-esque treatment, while [E.2.13, Theorem 4.7] and [E.5.1, Theorem 6.2] more explicitly invoke Taylor series.