Polynomial Congruences

The Mod Operator for Polynomials

Recall from Modular Arithmetic that the whole of integer modular arithmetic grew out of a single result: the Division Theorem, which says that any integer $a$ can be written uniquely as $a=qn+r$ with $0\le r<n$. Everything after that (congruence classes, ${\mathbb{Z}}_n$, linear congruences, the CRT) was really just bookkeeping around remainders.

Now that Polynomial Rings has handed us a Division Theorem for $F[x]$ over any field $F$, we can run the entire story again with polynomials playing the part of integers. This lecture is the polynomial mirror of Topics 3 and 4, and almost every statement in it will look familiar; the only real change is that the size condition "$0\le r<n$" gets replaced by the degree condition "$\mathrm{deg}(r)<\mathrm{deg}(m)$".

Basically, $f(x)\mathrm{mod}g(x)$ is just "do the long division and throw the quotient away". The Division Theorem is what makes this a legitimate operator: it guarantees that the pair $q(x),r(x)$ exists and is unique, so there is exactly one possible answer. Notice that the remainder is allowed to be the zero polynomial, which is exactly the statement $g(x)\mid f(x)$.

The coefficients must live in a field, and every coefficient has to be reduced inside that field before you read off your answer. This is the single most common slip when the field is ${\mathbb{Z}}_p$; a coefficient of $-4$ in ${\mathbb{Z}}_3[x]$ is not a coefficient of $-4$, it is a coefficient of $2$, and writing it the wrong way will make a perfectly correct division look wrong.

Example. In $\mathbb{Q}[x]$, find $(x^2+x+1)\mathrm{mod}(x^2+1)$.
The two polynomials have the same degree, so the quotient is just the constant $1$;

$$\begin{array}{rl}{x}^2+x+1& =1\cdot (x^2+1)+x,\end{array}$$

and $\mathrm{deg}(x)=1<2=\mathrm{deg}(x^2+1)$, so the division has finished. Therefore, $(x^2+x+1)\mathrm{mod}(x^2+1)=x$.

Example. In ${\mathbb{Z}}_3[x]$, find $(x^2-4)\mathrm{mod}(x+1)$.
First reduce the coefficients in ${\mathbb{Z}}_3$: since $-4=-4+6=2$ in ${\mathbb{Z}}_3$, the polynomial being divided is really $x^2+2$. Dividing,

$$\begin{array}{rl}{x}^2+2& =(x-1)(x+1)+3\\ & =(x+2)(x+1)+0\text{ in }{\mathbb{Z}}_3[x],\end{array}$$

since $3=0$ in ${\mathbb{Z}}_3$. Therefore, $(x^2-4)\mathrm{mod}(x+1)=0$; equivalently, $(x+1)\mid (x^2-4)$ in ${\mathbb{Z}}_3[x]$.

The Remainder Theorem from Polynomial Rings gets this instantly and with no long division at all: dividing by $x-a$ leaves remainder $f(a)$, and here $a=-1$, so

$$\begin{array}{rl}f(-1)& =(-1{)}^2-4\\ & =-3\\ & =0\text{ in }{\mathbb{Z}}_3.\end{array}$$

Whenever the divisor is linear, use the Remainder Theorem; long division by $x-a$ is wasted effort. Notice also that this answer is genuinely field-dependent: over $\mathbb{Q}$ the same computation gives $f(-1)=-3\ne 0$, so $(x^2-4)\mathrm{mod}(x+1)=-3$ in $\mathbb{Q}[x]$. The polynomial did not change, the field did.

Example. In ${\mathbb{Z}}_3[x]$, find $(x^4+2x^3+x+1)\mathrm{mod}(x^2+2)$.
Long division, remembering that every coefficient is reduced mod $3$ as we go:

$$\begin{array}{rl}{x}^4+2x^3+x+1-x^2(x^2+2)& =2x^3-2x^2+x+1\\ & =2x^3+x^2+x+1,\\ 2x^3+x^2+x+1-2x(x^2+2)& =x^2+x+1-4x\\ & =x^2+1,\\ x^2+1-1(x^2+2)& =-1\\ & =2.\end{array}$$

Collecting the quotient terms $x^2$, $2x$ and $1$ gives

$$x^4+2x^3+x+1=(x^2+2x+1)(x^2+2)+2,$$

and $\mathrm{deg}(2)=0<2$. Therefore, $(x^4+2x^3+x+1)\mathrm{mod}(x^2+2)=2$.

Example. In $\mathbb{Q}[x]$, find $(x^3-2x+5)\mathrm{mod}(x-2)$.
The divisor is linear, so the Remainder Theorem applies with $a=2$;

$$\begin{array}{rl}f(2)& =2^3-2(2)+5\\ & =8-4+5\\ & =9.\end{array}$$

Therefore, $(x^3-2x+5)\mathrm{mod}(x-2)=9$. (As a check, the full division gives $x^3-2x+5=(x^2+2x+2)(x-2)+9$.)

Congruence of Polynomials

With a mod operator in hand, congruence is defined exactly as it was for integers.

Basically, two polynomials are congruent when they leave the same remainder, which is the same as saying their difference is a multiple of the modulus. These are the same two descriptions we had for integers in Modular Arithmetic, and in practice you pick whichever is cheaper: computing two remainders, or subtracting and doing one divisibility check.

There is a third description that we will make official in the next section, and it is the one that gets used most: $f(x)$ and $g(x)$ are congruent mod $m(x)$ exactly when they are equal as elements of the quotient system $F[x]/⟨m(x)⟩$. So there are three equivalent formulations to keep straight:

• $f(x)\mathrm{mod}m(x)=g(x)\mathrm{mod}m(x)$ (equal remainders),
• $m(x)\mid f(x)-g(x)$ (the difference is a multiple of the modulus),
• $f(x)=g(x)$ in $F[x]/⟨m(x)⟩$ (equal in the quotient).

Example. In ${\mathbb{Z}}_3[x]$, verify that $x^3+2x+1\equiv x+1(\mathrm{mod}{x}^2+1)$ using both of the first two formulations.
For the remainder version, divide each side by $x^2+1$. Since $x^2\equiv -1$, we get $x^3=x\cdot x^2\equiv -x=2x$, so

$$\begin{array}{rl}{x}^3+2x+1& \equiv 2x+2x+1\\ & =4x+1\\ & =x+1\text{ in }{\mathbb{Z}}_3[x],\end{array}$$

while $x+1$ already has degree $1<2$ and so is its own remainder. Both sides leave remainder $x+1$.
For the divisibility version, subtract:

$$\begin{array}{rl}(x^3+2x+1)-(x+1)& =x^3+x\\ & =x(x^2+1),\end{array}$$

which is visibly a multiple of $x^2+1$. Therefore, the congruence holds, and the two tests agree as the mod operator promises they must.

The Set of Polynomials Modulo m(x)

For integers, the set of remainders modulo $n$ was packaged into the ring ${\mathbb{Z}}_n$ (see Modular Rings and Units). The polynomial version does exactly the same thing with the set of possible remainders modulo $m(x)$.

Basically, the elements are exactly the possible remainders on division by $m(x)$; every polynomial of degree less than $n$, and nothing else. You add and multiply as normal polynomials and then reduce mod $m(x)$ at the end, in the same way that arithmetic in ${\mathbb{Z}}_n$ is ordinary integer arithmetic followed by taking a remainder.

This matches the habit from earlier topics of writing "$=4$ in ${\mathbb{Z}}_{15}$" rather than "$\equiv 4(\mathrm{mod}15)$"; the $\equiv$ notation emphasises the relation, the $=$ notation emphasises that we are working inside a fixed finite system where the reduced form is the element.

Counting is easy: an element is determined by its $n$ coefficients $a_0,\dots ,a_{n-1}$, each chosen freely from $F$. So if $F$ is finite,

$$\boxed{\left|F[x]/⟨m(x)⟩\right|=|F{|}^n,\text{where }n=\mathrm{deg}(m(x)).}$$

The count depends only on the degree of $m(x)$, not on which polynomial of that degree you chose. Whether $m(x)$ factors or not changes the structure enormously (that is the subject of Irreducible Polynomials), but never the number of elements.

Example. List the elements of ${\mathbb{Z}}_3[x]/⟨x^2+1⟩$.
Here $F={\mathbb{Z}}_3$ and $\mathrm{deg}(x^2+1)=2$, so the elements are all $a_0+a_{1}x$ with $a_0,a_1\in \{0,1,2\}$, and there are $|F{|}^n=3^2=9$ of them:

$$\begin{array}{rl}{\mathbb{Z}}_3[x]/⟨x^2+1⟩& =\{0,1,2,x,x+1,x+2,2x,2x+1,2x+2\}.\end{array}$$

Therefore, there are exactly $9$ elements. Notice that this is not ${\mathbb{Z}}_9$; it has nine elements, but the arithmetic is completely different, as the next example shows.

Example. In ${\mathbb{Z}}_3[x]/⟨x^2+1⟩$, compute $(x+2)+(2x+2)$ and $(2x+1)(x+2)$.
Addition never needs reducing, since the sum of two polynomials of degree $<2$ still has degree $<2$:

$$\begin{array}{rl}(x+2)+(2x+2)& =3x+4\\ & =0x+1\\ & =1.\end{array}$$

Multiplication does need reducing. The key relation is $x^2+1=0$, i.e.

$$x^2=-1=2\text{ in }{\mathbb{Z}}_3[x]/⟨x^2+1⟩,$$

so every $x^2$ that appears can be swapped for $-1$ on sight:

$$\begin{array}{rl}(2x+1)(x+2)& =2x^2+4x+x+2\\ & =2x^2+5x+2\\ & =2x^2+2x+2\\ & =2(-1)+2x+2\\ & =2x.\end{array}$$

Therefore, $(x+2)+(2x+2)=1$ and $(2x+1)(x+2)=2x$ in ${\mathbb{Z}}_3[x]/⟨x^2+1⟩$. Substituting $x^2=-1$ is the same operation as dividing by $x^2+1$ and keeping the remainder; it is just far faster, and you should always reach for it once the modulus is fixed.

Example. List the elements of ${\mathbb{Z}}_2[x]/⟨x^2+x+1⟩$ and write down its multiplication table.
Here $|F{|}^n=2^2=4$, so the elements are $0,1,x,x+1$. The relation $x^2+x+1=0$ gives

$$\begin{array}{rl}{x}^2& =-x-1\\ & =x+1\text{ in }{\mathbb{Z}}_2[x]/⟨x^2+x+1⟩,\end{array}$$

using $-1=1$. Reducing every product with this,

$$\begin{array}{rl}x\cdot x& =x^2=x+1,\\ x(x+1)& =x^2+x=(x+1)+x=1,\\ (x+1)(x+1)& =x^2+2x+1=x^2+1=(x+1)+1=x,\end{array}$$

which fills in the table:

Therefore, ${\mathbb{Z}}_2[x]/⟨x^2+x+1⟩$ has four elements and the multiplication table above. Notice that every nonzero row contains a $1$, so every nonzero element has a multiplicative inverse; by the definition in Rings and Fields this system is a field with four elements, which is something ${\mathbb{Z}}_n$ can never give us (there is no ${\mathbb{Z}}_4$ that is a field). This is exactly why polynomial quotients matter, and it happens here because $x^2+x+1$ has no roots in ${\mathbb{Z}}_2$; more on that in Irreducible Polynomials.

Reducing Powers in the Quotient

Computing a high power of $x$ inside $F[x]/⟨m(x)⟩$ is the polynomial version of computing $a^k$ in ${\mathbb{Z}}_n$, and there are the same two ways to do it: grind out the division, or find a small power of $x$ that collapses to something trivial and exploit it. The second way is almost always faster, and it is the direct analogue of reducing an exponent modulo the order in Order and Primitive Elements.

Example. Find $x^5+1$ in ${\mathbb{Z}}_3[x]/⟨x^2+1⟩$.
By long division, taking one quotient term at a time:

$$\begin{array}{rl}{x}^5+1-x^3(x^2+1)& =-x^3+1,\\ -x^3+1+x(x^2+1)& =x+1,\end{array}$$

and $\mathrm{deg}(x+1)=1<2$, so we stop. Collecting the quotient terms,

$$x^5+1=(x^3-x)(x^2+1)+(x+1),$$

so the remainder is $x+1$.
Alternatively, and much faster, use the relation $x^2=-1$ directly:

$$\begin{array}{rl}{x}^4& =(x^2{)}^2\\ & =(-1{)}^2\\ & =1,\\ x^5& =x^4\cdot x\\ & =x,\\ x^5+1& =x+1.\end{array}$$

Therefore, $x^5+1=x+1$ in ${\mathbb{Z}}_3[x]/⟨x^2+1⟩$. Notice how $x^4=1$ means the powers of $x$ cycle with period $4$; this is precisely an order calculation, with $x$ playing the role of a unit.

Example. Find $x^5+1$ in ${\mathbb{Z}}_2[x]/⟨x^2+x+1⟩$.
By long division, remembering that in ${\mathbb{Z}}_2$ subtracting is the same as adding:

$$\begin{array}{rl}{x}^5+1+x^3(x^2+x+1)& =x^4+x^3+1,\\ x^4+x^3+1+x^2(x^2+x+1)& =x^2+1,\\ x^2+1+1(x^2+x+1)& =x,\end{array}$$

so the quotient is $x^3+x^2+1$ and

$$x^5+1=(x^3+x^2+1)(x^2+x+1)+x.$$

Alternatively, use $x^2=x+1$ from the previous section, which gives

$$\begin{array}{rl}{x}^3& =x\cdot x^2\\ & =x(x+1)\\ & =x^2+x\\ & =(x+1)+x\\ & =1,\end{array}$$

so the powers of $x$ cycle with period $3$ and

$$\begin{array}{rl}{x}^5& =x^3\cdot x^2\\ & =1\cdot (x+1)\\ & =x+1,\\ x^5+1& =x+1+1\\ & =x.\end{array}$$

Therefore, $x^5+1=x$ in ${\mathbb{Z}}_2[x]/⟨x^2+x+1⟩$; both routes agree, and the second one took three lines.

Example. Find $x^{100}$ in ${\mathbb{Z}}_2[x]/⟨x^2+x+1⟩$, and find $x^{10}+x^7$ in ${\mathbb{Z}}_3[x]/⟨x^2+1⟩$.
Nobody is doing these by long division. From the previous examples, $x^3=1$ in the first system and $x^4=1$ in the second, so in each case we reduce the exponent modulo that period:

$$\begin{array}{rl}100& =3\times 33+1,\\ x^{100}& =(x^3{)}^{33}\cdot x\\ & =x\text{ in }{\mathbb{Z}}_2[x]/⟨x^2+x+1⟩.\end{array}$$

For the second, $10=4\times 2+2$ and $7=4\times 1+3$, so

$$\begin{array}{rl}{x}^{10}& =(x^4{)}^2\cdot x^2\\ & =x^2=-1=2,\\ x^7& =(x^4)\cdot x^3\\ & =x\cdot x^2=-x=2x,\\ x^{10}+x^7& =2x+2\text{ in }{\mathbb{Z}}_3[x]/⟨x^2+1⟩.\end{array}$$

Therefore, $x^{100}=x$ and $x^{10}+x^7=2x+2$. Reduce the exponent modulo the period of $x$, never modulo the degree of $m(x)$; the degree tells you how big the remainders are allowed to be, not how the powers repeat.

Solving Linear Congruences with Polynomial Moduli

Now for the polynomial version of Linear Congruences and Diophantine Equations. Given $f(x),g(x),m(x)\in F[x]$, we want to solve the general linear congruence

$$f(x)a(x)\equiv g(x)(\mathrm{mod}m(x))$$

for the unknown polynomial $a(x)$. Compare this with $ax\equiv c(\mathrm{mod}n)$: the method is word-for-word the same, with $\gcd$ of polynomials (from the polynomial Euclidean algorithm in Polynomial Rings) replacing $\gcd$ of integers.

• Find $d(x)=\gcd (f(x),m(x))$. If $d(x)\nmid g(x)$, there is no solution; stop.
• Find polynomials $p(x),q(x)\in F[x]$ such that $d(x)=f(x)p(x)+m(x)q(x)$, e.g. via the Euclidean algorithm and working backwards.
• The general solution is then

$$\boxed{a(x)\equiv \frac{g(x)}{d(x)}p(x)(\mathrm{mod}\frac{m(x)}{d(x)}).}$$

Basically, $p(x)$ is playing the role of an inverse: the Bézout identity says $f(x)p(x)\equiv d(x)(\mathrm{mod}m(x))$, so multiplying the congruence through by $p(x)$ converts the left-hand side from $f(x)a(x)$ into $d(x)a(x)$, and then everything divides by $d(x)$. The divisibility condition $d(x)\mid g(x)$ appears for exactly the same reason as $d\mid c$ did for integers; the reachable values of $f(x)a(x)+m(x)b(x)$ are precisely the multiples of the gcd.

The modulus shrinks from $m(x)$ to $\frac{m(x)}{d(x)}$, and forgetting this is the classic mistake. In the integer case a single class mod $\frac{n}{d}$ split into $d$ separate classes mod $n$; here a single class mod $\frac{m(x)}{d(x)}$ splits into $|F{|}^{\mathrm{deg}d}$ separate classes mod $m(x)$, by the count of elements in the quotient when $F$ is finite. If a question asks for the answer modulo the original $m(x)$, you have to list all of them by repeatedly adding $\frac{m(x)}{d(x)}$.

In ${\mathbb{Z}}_2[x]$, subtraction is identical to addition, because $-1=1$; so signs never matter and you may freely replace every minus with a plus. This is a genuine convenience when back-substituting through the Euclidean algorithm (no sign bookkeeping at all), but it is also the single most common source of confusion in this topic, because the same manipulation in ${\mathbb{Z}}_3[x]$ or $\mathbb{Q}[x]$ absolutely does need its signs. Always know which field you are in before you start cancelling.

Example. Solve $(x^3+x^2+1)a(x)\equiv x^2(\mathrm{mod}{x}^4+1)$ in ${\mathbb{Z}}_2[x]$.
First run the Euclidean algorithm on $m(x)=x^4+1$ and $f(x)=x^3+x^2+1$. Dividing,

$$\begin{array}{rl}{x}^4+1& =(x+1)(x^3+x^2+1)+(x^2+x),\\ x^3+x^2+1& =x(x^2+x)+1,\\ x^2+x& =(x^2+x)(1)+0,\end{array}$$

so the last nonzero remainder is $d(x)=1$. (It is worth checking the first line: $(x+1)(x^3+x^2+1)=x^4+x^3+x+x^3+x^2+1=x^4+x^2+x+1$, and adding $x^2+x$ gives $x^4+1$ as required.) Since $1$ divides everything, a solution exists.

Now work backwards from the second line to build the Bézout identity:

$$\begin{array}{rl}1& =(x^3+x^2+1)+x(x^2+x)\\ & =(x^3+x^2+1)+x[(x^4+1)+(x+1)(x^3+x^2+1)]\\ & =(x^3+x^2+1)[1+x(x+1)]+x(x^4+1)\\ & =(x^3+x^2+1)(x^2+x+1)+x(x^4+1),\end{array}$$

so $p(x)=x^2+x+1$ and $q(x)=x$. As a check,

$$\begin{array}{rl}(x^3+x^2+1)(x^2+x+1)& =x^5+x^4+x^3+x^4+x^3+x^2+x^2+x+1\\ & =x^5+x+1,\end{array}$$

and adding $x(x^4+1)=x^5+x$ leaves exactly $1$. $✓$

Since $d(x)=1$, neither the right-hand side nor the modulus shrinks, and the general solution is

$$\begin{array}{rl}a(x)& \equiv x^2(x^2+x+1)(\mathrm{mod}{x}^4+1)\\ & \equiv x^4+x^3+x^2(\mathrm{mod}{x}^4+1)\\ & \equiv 1+x^3+x^2(\mathrm{mod}{x}^4+1),\end{array}$$

using $x^4=-1=1$ in ${\mathbb{Z}}_2[x]/⟨x^4+1⟩$. Checking the answer by multiplying out, and using the fact that squaring in ${\mathbb{Z}}_2[x]$ kills all the cross terms,

$$\begin{array}{rl}(x^3+x^2+1)(x^3+x^2+1)& =x^6+x^4+1\\ & =x^2(x^4)+x^4+1\\ & =x^2+1+1\\ & =x^2\text{ in }{\mathbb{Z}}_2[x]/⟨x^4+1⟩.✓\end{array}$$

Therefore, the solution is $a(x)\equiv x^3+x^2+1(\mathrm{mod}{x}^4+1)$. Amusingly the answer is $f(x)$ itself, i.e. $f(x)$ happens to be its own "square root of $x^2$" here; that is a coincidence of this example, not a general phenomenon.

Example. In ${\mathbb{Z}}_2[x]$, solve (a) $(x^2+1)a(x)\equiv x(\mathrm{mod}{x}^3+1)$, and (b) $(x^2+1)a(x)\equiv x^2+x(\mathrm{mod}{x}^3+1)$.
Both parts need the same gcd, so compute it once. In ${\mathbb{Z}}_2[x]$,

$$\begin{array}{rl}{x}^3+1& =x(x^2+1)+(x+1),\\ x^2+1& =(x+1)(x+1)+0,\end{array}$$

so $d(x)=x+1$. (Both lines are just the factorisations $x^3+1=(x+1)(x^2+x+1)$ and $x^2+1=(x+1{)}^2$ in disguise.)
(a) Does $x+1$ divide $g(x)=x$? By the Remainder Theorem the remainder is the value at $x=1$, namely $1\ne 0$; so no. Therefore, part (a) has no solutions.
(b) Here $g(x)=x^2+x=x(x+1)$, which is divisible by $x+1$, so solutions exist. From the first division line,

$$x+1=(x^3+1)+x(x^2+1),$$

giving $p(x)=x$. Dividing the pieces by $d(x)=x+1$,

$$\begin{array}{rl}\frac{g(x)}{d(x)}& =\frac{x^2+x}{x+1}=x,\\ \frac{m(x)}{d(x)}& =\frac{x^3+1}{x+1}=x^2+x+1,\end{array}$$

so the general solution is

$$\begin{array}{rl}a(x)& \equiv x\cdot x(\mathrm{mod}{x}^2+x+1)\\ & \equiv x^2(\mathrm{mod}{x}^2+x+1)\\ & \equiv x+1(\mathrm{mod}{x}^2+x+1),\end{array}$$

using $x^2=x+1$ in ${\mathbb{Z}}_2[x]/⟨x^2+x+1⟩$ as before. Checking with $a(x)=x+1$,

$$\begin{array}{rl}(x^2+1)(x+1)& =x^3+x^2+x+1\\ & =1+x^2+x+1\\ & =x^2+x\text{ in }{\mathbb{Z}}_2[x]/⟨x^3+1⟩,✓\end{array}$$

since $x^3=-1=1$. Therefore, the solution to (b) is $a(x)\equiv x+1(\mathrm{mod}{x}^2+x+1)$. Notice the modulus really did shrink, from degree $3$ down to degree $2$; modulo the original $x^3+1$ there are $|F{|}^{\mathrm{deg}d}=2^1=2$ solutions, namely $a(x)=x+1$ and $a(x)=(x+1)+(x^2+x+1)=x^2$, and indeed $(x^2+1)x^2=x^4+x^2=x+x^2$ in ${\mathbb{Z}}_2[x]/⟨x^3+1⟩$ as well.

Example. Solve $(x^2+1)a(x)\equiv x+2(\mathrm{mod}{x}^3+2x+1)$ in ${\mathbb{Z}}_3[x]$.
This one is over ${\mathbb{Z}}_3$, so signs matter again; recall $-1=2$ and $-2=1$ in ${\mathbb{Z}}_3$. Running the Euclidean algorithm,

$$\begin{array}{rl}{x}^3+2x+1& =x(x^2+1)+(x+1),\\ x^2+1& =(x+2)(x+1)+2,\\ x+1& =(2x+2)(2)+0,\end{array}$$

where the middle line uses $(x+2)(x+1)=x^2+3x+2=x^2+2$, so the remainder is $(x^2+1)-(x^2+2)=-1=2$. The last nonzero remainder is the constant $2$, whose monic form is $1$; so $d(x)=1$ and a solution exists.

Working backwards,

$$\begin{array}{rl}2& =(x^2+1)-(x+2)(x+1)\\ & =(x^2+1)-(x+2)[(x^3+2x+1)-x(x^2+1)]\\ & =(x^2+1)[1+x(x+2)]-(x+2)(x^3+2x+1)\\ & =(x^2+1)(x^2+2x+1)-(x+2)(x^3+2x+1).\end{array}$$

Multiplying through by $2^{-1}=2$ in ${\mathbb{Z}}_3$ to make the gcd monic,

$$\begin{array}{rl}1& =(x^2+1)(2x^2+4x+2)-(2x+4)(x^3+2x+1)\\ & =(x^2+1)(2x^2+x+2)+(x+2)(x^3+2x+1),\end{array}$$

so $p(x)=2x^2+x+2$. Since $d(x)=1$, the general solution is $a(x)\equiv g(x)p(x)$ modulo $m(x)$:

$$\begin{array}{rl}a(x)& \equiv (x+2)(2x^2+x+2)(\mathrm{mod}{x}^3+2x+1)\\ & \equiv 2x^3+x^2+2x+4x^2+2x+4(\mathrm{mod}{x}^3+2x+1)\\ & \equiv 2x^3+2x^2+x+1(\mathrm{mod}{x}^3+2x+1).\end{array}$$

Now $x^3\equiv -2x-1=x+2$, so $2x^3\equiv 2x+4=2x+1$, giving

$$\begin{array}{rl}a(x)& \equiv (2x+1)+2x^2+x+1\\ & \equiv 2x^2+3x+2\\ & \equiv 2x^2+2(\mathrm{mod}{x}^3+2x+1).\end{array}$$

Checking: with $x^3\equiv x+2$ we get $x^4\equiv x^2+2x$, so

$$\begin{array}{rl}(x^2+1)(2x^2+2)& =2x^4+4x^2+2\\ & =2x^4+x^2+2\\ & \equiv 2(x^2+2x)+x^2+2\\ & =3x^2+4x+2\\ & =x+2.✓\end{array}$$

Therefore, the solution is $a(x)\equiv 2x^2+2(\mathrm{mod}{x}^3+2x+1)$.

The Chinese Remainder Theorem for Polynomials

Everything from Simultaneous Congruences and the CRT carries over as well, with the same pairwise-coprime hypothesis and the same uniqueness statement.

The proof is analogous to the integer case from Simultaneous Congruences and the CRT, so the lecture only sketches it; the substitution argument below is constructive anyway, which is really all we need in practice.

Pairwise coprime means coprime in pairs, not "no factor common to all of them". Exactly as with integers, $\gcd (m_1,m_2,m_3)=1$ is not enough; you must check every pair separately. Notice also that "coprime" here means the gcd is the constant polynomial $1$, i.e. the two moduli share no common factor of degree $\ge 1$.

To solve a system, we use the same substitution method as in the integer case:

• Solve the first congruence and write $f(x)$ in terms of some polynomial $k_1(x)\in F[x]$.
• Substitute this into the second congruence and solve for $k_1(x)$ in terms of some new polynomial $k_2(x)\in F[x]$.
• Rewrite $f(x)$ in terms of $k_2(x)$, substitute into the third congruence, and so on.
• The final expression for $f(x)$, with $k_t(x)$ ranging over all of $F[x]$, describes every solution.

Basically, each congruence narrows the family of possible $f(x)$ down further, and the parameter $k_i(x)$ keeps track of whatever freedom is left. Since the final answer is unique modulo the product of the moduli, the degree of the product is a free sanity check: the reduced answer must have degree less than $\mathrm{deg}(m_1)+\cdots +\mathrm{deg}(m_t)$.

Example. Solve the following system of polynomial congruences in ${\mathbb{Z}}_2[x]$:

$$\begin{array}{rl}f(x)& \equiv x+1(\mathrm{mod}{x}^2+x+1),\\ f(x)& \equiv x(\mathrm{mod}{x}^3).\end{array}$$

First check the hypothesis: $x^2+x+1$ has constant term $1$, so it is not divisible by $x$, and the only factor of $x^3$ of positive degree is $x$; hence $\gcd (x^2+x+1,x^3)=1$ and the CRT applies. The answer will be unique modulo

$$x^3(x^2+x+1)=x^5+x^4+x^3.$$

From the first congruence,

$$f(x)=x+1+(x^2+x+1)k(x),k(x)\in {\mathbb{Z}}_2[x].$$

Substituting this into the second congruence,

$$\begin{array}{rl}x+1+(x^2+x+1)k(x)& \equiv x(\mathrm{mod}{x}^3)\\ (x^2+x+1)k(x)& \equiv x-x-1(\mathrm{mod}{x}^3)\\ (x^2+x+1)k(x)& \equiv 1(\mathrm{mod}{x}^3),\end{array}$$

using $-1=1$ in ${\mathbb{Z}}_2$. So $k(x)$ must be the inverse of $x^2+x+1$ modulo $x^3$; and the gcd is $1$, so an inverse exists. Rather than run the full Euclidean algorithm, notice that

$$\begin{array}{rl}(x^2+x+1)(x+1)& =x^3+x^2+x+x^2+x+1\\ & =x^3+1\\ & \equiv 1(\mathrm{mod}{x}^3),\end{array}$$

so the inverse is $x+1$ and

$$k(x)=x+1+x^{3}t(x),t(x)\in {\mathbb{Z}}_2[x].$$

Substituting back,

$$\begin{array}{rl}f(x)& =x+1+(x^2+x+1)[x+1+x^{3}t(x)]\\ & =x+1+(x^3+1)+x^3(x^2+x+1)t(x)\\ & =x^3+x+(x^5+x^4+x^3)t(x).\end{array}$$

Checking both congruences with $f(x)=x^3+x$: modulo $x^3$ we have $x^3\equiv 0$, so $f(x)\equiv x$; and modulo $x^2+x+1$ we showed earlier that $x^3=1$, so $f(x)\equiv 1+x=x+1$. Both hold. $✓$ Therefore, the general solution is

$$f(x)\equiv x^3+x(\mathrm{mod}{x}^5+x^4+x^3),$$

and its degree $3$ is comfortably below $5$, as the uniqueness statement requires.

Example. Solve $f(x)\equiv 1(\mathrm{mod}x+1)$ and $f(x)\equiv x(\mathrm{mod}{x}^2+1)$ in ${\mathbb{Z}}_3[x]$.
Coprimality first: by the Remainder Theorem, $x+1$ divides $x^2+1$ only if $(-1{)}^2+1=2$ were $0$ in ${\mathbb{Z}}_3$, which it is not; so the moduli are coprime and the answer is unique modulo

$$(x+1)(x^2+1)=x^3+x^2+x+1.$$

From the first congruence, $f(x)=1+(x+1)k(x)$. Substituting into the second,

$$\begin{array}{rl}1+(x+1)k(x)& \equiv x(\mathrm{mod}{x}^2+1)\\ (x+1)k(x)& \equiv x-1(\mathrm{mod}{x}^2+1).\end{array}$$

We need the inverse of $x+1$ modulo $x^2+1$. Using $x^2\equiv -1$,

$$\begin{array}{rl}(x+1)(x-1)& =x^2-1\\ & \equiv -1-1\\ & =-2\\ & =1\text{ in }{\mathbb{Z}}_3,\end{array}$$

so $(x+1{)}^{-1}=x-1=x+2$. Multiplying through,

$$\begin{array}{rl}k(x)& \equiv (x-1)(x-1)(\mathrm{mod}{x}^2+1)\\ & \equiv x^2-2x+1(\mathrm{mod}{x}^2+1)\\ & \equiv -1-2x+1(\mathrm{mod}{x}^2+1)\\ & \equiv x(\mathrm{mod}{x}^2+1),\end{array}$$

since $-2=1$ in ${\mathbb{Z}}_3$. Hence $k(x)=x+(x^2+1)t(x)$, and

$$\begin{array}{rl}f(x)& =1+(x+1)[x+(x^2+1)t(x)]\\ & =x^2+x+1+(x+1)(x^2+1)t(x).\end{array}$$

Checking: at $x=-1$ we get $f(-1)=1-1+1=1$, so $f(x)\equiv 1(\mathrm{mod}x+1)$; and modulo $x^2+1$ we have $x^2\equiv -1$, so $f(x)\equiv -1+x+1=x$. Both hold. $✓$ Therefore,

$$f(x)\equiv x^2+x+1(\mathrm{mod}{x}^3+x^2+x+1).$$

So the whole of Topics 3 and 4 transfers across intact: remainders, congruence classes, a finite quotient system, linear congruences solved by Bézout, and simultaneous congruences solved by substitution. The only things you have to keep watch over are which field the coefficients live in (because $-1=1$ in ${\mathbb{Z}}_2$ but not in ${\mathbb{Z}}_3$), and the fact that "size" now means degree; once those two habits are in place, every method here is one you have already used on integers.