NTIC From Linear to General

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.

🔗

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.

🔗

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 polynomials are exclusively made up of addition and multiplication, 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\text{ (mod }\prod_{i=1}^k n_i\text{)}\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¹Given these conditions, it will be the only one of this form. to

$\begin{equation*} f(x)\equiv 0\text{ (mod }p^e) \end{equation*}$

of the 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} \end{equation*}

Since $e\geq 2$ in this context, the extra terms (from Taylor or binomial series)²One way or another one of these series will have to enter in, unfortunately; [C.2.1, Section 4.3] has more of a binomial theorem-esque treatment, while [C.2.13, Theorem 4.7] and [C.5.1, Theorem 6.2] more explicitly invoke Taylor series. involving $p^{(e-1)/2}$ will be divisible by at least $p^e$ and hence be irrelevant in that modulus, so 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*}

We're nearly done with the individual terms. Recall Proposition 5.2.6 where we are allowed to cancel a nonzero divisor from “all three sides” of a congruence. That motivates dividing each term and the modulus by $p^{e-1}$ to get

\begin{equation*} \frac{c_i x_{e-1}^i}{p^{e-1}}+c_i \cdot i x_{e-1}^{i-1}\cdot k\text{ (mod }p)\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 $x_{e-1}^i$ will give us $f(x_{e-1})\text{,}$ and summing up $i x_{e-1}^{i-1}$ is adding terms that look like the derivative of polynomials, so modulo $p$ we have

\begin{equation*} \frac{f(x_{e-1})}{p^{e-1}}+f'(x_{e-1})\cdot k\text{,} \end{equation*}

which is divisible by $p$ by hypothesis.

Now we have that

\begin{equation*} f(x_e)/p^{e-1}=f(\text{the sum})/p^{e-1}\equiv 0\text{ (mod }p)\text{,} \end{equation*}

so we multiply everything by $p^{e-1}$ (this time actually using Proposition 5.2.6) and get $f(x_{e})\equiv 0\text{ (mod }p^e)$ 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{.}$

🔗

Example 7.2.4.

First we solve $x^2+1\equiv 0\text{ (mod }25)\text{.}$ By inspection, the solutions modulo $5$ are $[2],[3]$ (or $[\pm 2]$ ). So 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 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.5.

We can try the same process with $e=3\text{.}$ Taking (from the previous example) $x_2\equiv 7$ yields, as a condition for $k\text{,}$

$\begin{equation*} \frac{7^2+1}{25}+14k\equiv 0\text{ (mod }5) \end{equation*}$

This gives $k=2\text{,}$ and indeed

$\begin{equation*} x_3 = x_2+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. (Unlike in the Newton case, it is also possible for there to be solutions here if

$\gcd(p,f'(x_{e-1}))\neq 1\text{,}$ but only if

$\frac{f(x_{e-1})}{p^{e-1}}$ itself is also divisible by

$p\text{.}$ We omit details of this case, which then yields additional solutions for each successive

$e\text{.}$ )

🔗

If you didn't notice this, 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.