Subsection 7.2.1 Combining 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.
Fact 7.2.2.
Let \(n_1,n_2,\cdots ,n_k\) be a set of \(k\) mutually coprime moduli. Suppose that for some polynomial \(f(x)\) you know that there are \(N_i\) (congruence classes of) solutions to
\begin{equation*}
f(x)\equiv 0 \text{ (mod }n_i)\text{.}
\end{equation*}
Then the congruence
\begin{equation*}
f(x)\equiv 0 \text{ }\left(\text{mod }\prod_{i=1}^k n_i\right)\text{ has }\prod_{i=1}^k N_i\text{ total solutions.}
\end{equation*}
Proof.
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.
Theorem 7.2.3. Hensel’s Lemma.
For \(p\) prime and \(e\geq 2\text{,}\) suppose you already know a solution equivalence class \(x_{e-1}\text{ (mod }p^{e-1})\) of the (polynomial) congruence
\begin{equation*}
f(x)\equiv 0\text{ (mod }p^{e-1})
\end{equation*}
Assume the technical condition that \(\gcd(p,f'(x_{e-1}))=1\text{.}\) Then there is also a solution to
\begin{equation*}
f(x)\equiv 0\text{ (mod }p^e)
\end{equation*}
of the form (and unique of this form)
\begin{equation*}
x_{e}=x_{e-1}+kp^{e-1}
\end{equation*}
where \(k\) satisfies
\begin{equation*}
\frac{f(x_{e-1})}{p^{e-1}}+k\cdot f'(x_{e-1})\equiv 0\text{ (mod }p\text{)}\text{.}
\end{equation*}
Proof.
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.
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.
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.
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.