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. (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}},

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 .$

🔗

We will state this for the general case of a coprime factorization of

n,

though again the prime power factorization is usually the most useful.

🔗

Fact 7.2.2.

Let $n_{1}, n_{2}, \dots, 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

f (x) \equiv 0 (mod n_{i}) .

Then the congruence

f (x) \equiv 0 (mod \prod_{i = 1}^{k} n_{i}) has \prod_{i = 1}^{k} N_{i} total solutions.

🔗

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

4 x \equiv 1 (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

4 x - 1 \equiv 0,

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 ∣ 1 - 4 \cdot 2

and then cancelling out

7

from the entire congruence to get that

\frac{1 - 4 \cdot 2}{7} \equiv 4 k (mod 7) .

🔗

We were able to solve the resulting congruence

- 1 \equiv 4 k

(mod

7

), which had solution

k \equiv 5

(mod

7

). Finally, we plugged that back in to get a solution to

4 x \equiv 1

(mod

7^{2}

), which was

2 + 7 k = 2 + 7 \cdot 5 = 37 (mod 7^{2})

🔗

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,$ suppose you already know a solution equivalence class $x_{e - 1} (mod p^{e - 1})$ of the (polynomial) congruence

f (x) \equiv 0 (mod p^{e - 1})

Assume the technical condition that $gcd (p, f^{'} (x_{e - 1})) = 1 .$ Then there is also a solution¹ to

f (x) \equiv 0 (mod p^{e})

of the form

x_{e} = x_{e - 1} + k p^{e - 1}

where $k$ satisfies

\frac{f (x_{e - 1})}{p^{e - 1}} + k \cdot f^{'} (x_{e - 1}) \equiv 0 (mod p) .

Given these conditions, it will be the only one of this form.

🔗

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²) 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*}

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.

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 (mod 5)

and turn them into solutions modulo

25

and

125 .

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 (mod 25) .$ By the preceding remark and the lemma, solutions modulo 25 will look like $3 + k \cdot 5$ or $2 + k \cdot 5 .$ Further, $f^{'} (x) = 2 x,$ so for either solution modulo 5 the technical derivative condition is met.

Let $x_{1} = 3 .$ Then the condition for $k$ is

\frac{f (x_{1})}{5} + k \cdot (2 x_{1}) \equiv 0 (mod 5)

which simplifies to $2 + 6 k \equiv 0,$ which solves to $k \equiv - 2 \equiv 3 .$ Then our solution to the congruence modulo $25$ would be

x_{2} = x_{1} + 3 \cdot 5 \equiv 3 + 3 \cdot 5 \equiv 18 (mod 25)

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 .$ Taking (from the previous example, or the affiliated exercise) $x_{2} \equiv 7$ yields, as a condition for $k,$

\frac{7^{2} + 1}{25} + 2 \cdot 7 k \equiv 0 (mod 5) .

This reduces to $14 k \equiv - 2 (mod 5),$ which gives $k = 2 .$ Indeed,

x_{3} = x_{2} + 2 \cdot 5^{2} \equiv 7 + 2 \cdot 5^{2} = 57

yields

57^{2} + 1 = 3250 \equiv 0 (mod 125) .

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

x_{e} = x_{e - 1} - \frac{f (x_{e - 1})}{f^{'} (x_{e - 1})}

🔗

since

p^{e - 1} ∣ 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,

but only if

\frac{f (x_{e - 1})}{p^{e - 1}}

itself is also divisible by

p .

We omit details of this case, which then yields additional solutions for each successive

e .

)

🔗

If you didn't notice this, don't feel bad! When we had the linear congruence

f (x) = 4 x - 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.