What is $(1 + \sqrt{2})^5$, written exactly as a rational number plus a rational multiple of $\sqrt 2$? One way is to expand the binomial and simplify, using $\sqrt{2}^{\,2} = 2$ to replace every power of $\sqrt 2$. The bookkeeping is easier with a letter in place of $\sqrt 2$. Expanding $(1 + x)^5$ gives
$$(1 + x)^5 = x^5 + 5x^4 + 10x^3 + 10x^2 + 5x + 1,$$
and the rule $x^2 \to 2$ turns $x^3$ into $2x$, $x^4$ into $4$ and $x^5$ into $4x$. Collecting terms,
$$1 + 5x + 10 \cdot 2 + 10 \cdot 2x + 5 \cdot 4 + 4x = 41 + 29x,$$
so $(1 + \sqrt 2)^5 = 41 + 29\sqrt 2$. The rule "replace $x^2$ by 2" is the same as "throw away multiples of $x^2 - 2$". Indeed the answer $41 + 29x$ is the remainder on dividing $(1 + x)^5$ by $x^2 - 2$:
$$(1 + x)^5 = (x^2 - 2)(x^3 + 5x^2 + 12x + 20) + (29x + 41).$$
So multiples of $x^2 - 2$ were treated as zero. Why was that allowed, and which rules of arithmetic survive it?
Throwing away multiples of a fixed polynomial is the polynomial version of throwing away multiples of a fixed integer, which is congruence modulo $n$. Polynomials that differ by a multiple of $p(x)$ are congruent modulo $p(x)$. This article follows the integer article in order and proof. First come the definition and the proof that congruence is an equivalence relation. Then we name and count its classes. Next come the rules for sums and products, which answer the opening question. Finally, cancellation survives only in part. Each integer proof needs only the facts about divisibility that polynomial division over a field established for $F[x]$, which is why the translation works.
This is the first article of Congruence in Polynomial Rings and Field Extensions in the MTH 532 notes. It covers §5.1 of the course text (Hungerford, 2014). Throughout, $F$ is a field and $p(x)$ is a nonzero polynomial in $F[x]$.
The definition
Definition. Polynomials $f(x), g(x) \in F[x]$ are congruent modulo $p(x)$, written
$$f(x) \equiv g(x) \pmod{p(x)},$$
if $p(x)$ divides $f(x) - g(x)$ in $F[x]$. The polynomial $p(x)$ is the modulus.
The definition is the integer definition with polynomials in every place. Some examples in $\mathbb{Q}[x]$, each checked by factoring the difference:
- $x^4 \equiv 4 \pmod{x^2 - 2}$, since $x^4 - 4 = (x^2 - 2)(x^2 + 2)$;
- $x^4 - 2x^2 - 3x - 2 \equiv -3x - 2 \pmod{x^2 - 2}$, since the difference is $x^4 - 2x^2 = (x^2 - 2)\,x^2$;
- $x^4 + x^3 - x^2 - 2x - 2 \equiv 0$ modulo $x^2 - 2$ and modulo $x^2 + x + 1$, since it equals $(x^2 - 2)(x^2 + x + 1)$.
The polynomial in the last example is the running example $f(x)$ of Polynomial Arithmetic, and the second is its partner $g(x)$ from the Euclidean algorithm. They are not congruent to each other modulo $x^2 - 2$: their difference $x^3 + x^2 + x$ leaves the remainder $3x + 2$, which is not 0.
Over a finite field the coefficients are reduced as well. In $\mathbb{Z}_2[x]$, with the modulus
$$p(x) = x^3 + x^2 + 1,$$
division gives $x^5 = (x^3 + x^2 + 1)(x^2 + x + 1) + (x + 1)$, so $x^5 \equiv x + 1 \pmod{p(x)}$. This modulus is the article's running example over a finite field. It is irreducible over $\mathbb{Z}_2$, since it is a cubic with no root in $\mathbb{Z}_2$ (its values at 0 and 1 are both 1; see the root test), and in the third article that is what makes its classes a field.
Three ways to say it
For polynomials $f(x)$ and $g(x)$ in $F[x]$, the following statements are equivalent.
- $f(x) \equiv g(x) \pmod{p(x)}$, that is, $p(x) \mid f(x) - g(x)$.
- $f(x) = g(x) + k(x)p(x)$ for some $k(x) \in F[x]$.
- $f(x)$ and $g(x)$ leave the same remainder on division by $p(x)$.
Statements 1 and 2 are the definition of divisibility rewritten. For integers, the equivalence with statement 3 was proved in the division algorithm. The idea: $f - g$ and the difference of the remainders differ by a multiple of $p$, and by uniqueness of the remainder that forces the remainders to agree exactly when $p \mid f - g$.
Proof that 1 and 3 are equivalent. Divide both polynomials by $p$: $f = pq_1 + r_1$ and $g = pq_2 + r_2$, where each remainder is 0 or has degree less than $\deg p$. Then
$$f - g = p\,(q_1 - q_2) + (r_1 - r_2).$$
If $r_1 = r_2$, this says $f - g = p\,(q_1 - q_2)$, so $p \mid f - g$. Conversely, suppose $f - g = pk$ for some $k$. Then
$$f = g + pk = p\,(q_2 + k) + r_2,$$
which is a division of $f$ by $p$ with remainder $r_2$, and $r_2$ is 0 or of degree less than $\deg p$. By the uniqueness part of the division algorithm, $r_2$ is the remainder of $f$, so $r_1 = r_2$. $\blacksquare$
A check on the running pair: modulo $x^2 - 2$, $f$ leaves the remainder 0 and $g$ leaves $-3x - 2$, so $f \not\equiv g$, as the remainder $3x + 2$ of $f - g$ showed. The script also checks the equivalence by brute force over $\mathbb{Z}_2$ with the modulus $x^3 + x^2 + 1$: for all 16,384 pairs of polynomials of degree less than 7, "same remainder" and "difference divisible by $p$" agree. As with integers, statement 2 is the convenient form in proofs and statement 3 in computation.
Corollary. Every polynomial is congruent modulo $p(x)$ to its remainder on division by $p(x)$.
Proof. If $f = pq + r$, then $f - r = pq$. $\blacksquare$
This is what happened in the opening example: $(1 + x)^5 \equiv 41 + 29x \pmod{x^2 - 2}$, and $41 + 29x$ is the remainder.
Congruence is an equivalence relation
Theorem. Congruence modulo $p(x)$ is an equivalence relation on $F[x]$. That is, for all $f(x)$, $g(x)$, $h(x)$ in $F[x]$:
- $f(x) \equiv f(x) \pmod{p(x)}$;
- if $f(x) \equiv g(x) \pmod{p(x)}$, then $g(x) \equiv f(x) \pmod{p(x)}$;
- if $f(x) \equiv g(x)$ and $g(x) \equiv h(x) \pmod{p(x)}$, then $f(x) \equiv h(x) \pmod{p(x)}$.
The idea: each property says that some difference is a multiple of $p$, and the multiples of $p$ contain 0 and are closed under negation and addition.
Proof. (1) $f - f = 0 = p \cdot 0$. (2) If $f - g = pk$, then $g - f = p\,(-k)$. (3) If $f - g = pk$ and $g - h = pl$, then adding,
$$f - h = (f - g) + (g - h) = p\,(k + l). \qquad \blacksquare$$
Line for line, this is the proof for integers. As there, a second proof needs no computation: by the equivalence of statements 1 and 3, congruence modulo $p$ is the relation "same value under the function that sends a polynomial to its remainder", and any such relation is an equivalence relation. The theorem is Hungerford's Theorem 5.1.
Congruence classes
Definition. The congruence class of $f(x)$ modulo $p(x)$ is
$$[f(x)] = \{\, g(x) \in F[x] : g(x) \equiv f(x) \pmod{p(x)} \,\} = \{\, f(x) + k(x)p(x) : k(x) \in F[x] \,\}.$$
The second description is statement 2 above: the class of $f$ is $f$ plus every multiple of $p$. By the general theory of equivalence relations, $[f] = [g]$ exactly when $f \equiv g \pmod p$, and two classes are either equal or disjoint (Hungerford's Theorem 5.3 and Corollary 5.4).
The class of $1$ modulo $x^3 + x^2 + 1$ in $\mathbb{Z}_2[x]$, for instance, contains $1$, $x^3 + x^2$ (that is, $1 + p$), $x^4 + x^3 + x + 1$ (that is, $1 + xp$), $x^5 + x$ (that is, $1 + (x^2 + x + 1)p$), and infinitely many more of higher degree.
How many classes are there, and how can each be named? For integers, the classes modulo $n$ were exactly $[0], [1], \ldots, [n - 1]$, one for each possible remainder. For polynomials the possible remainders are 0 and the polynomials of degree less than $\deg p$, and the same statement holds. The idea: two different remainders differ by a nonzero polynomial too small to be a multiple of $p$.
Theorem. Let $p(x)$ have degree $d$, and let $S$ be the set consisting of the zero polynomial and all polynomials in $F[x]$ of degree less than $d$. Every congruence class modulo $p(x)$ contains exactly one polynomial of $S$. Consequently the classes $[r(x)]$ for $r(x) \in S$ are all the classes, and they are distinct.
Proof. Existence: the class of $f$ contains the remainder of $f$ on division by $p$, by the corollary above, and the remainder lies in $S$.
Uniqueness: suppose $r$ and $s$ are different elements of $S$ in the same class. Then $p \mid r - s$, say $r - s = pk$. Since $r - s \neq 0$, also $k \neq 0$, and as $F$ is a field the degrees add: $\deg(r - s) = \deg p + \deg k \ge d$. But $r$ and $s$ are each 0 or of degree less than $d$, so their difference has degree less than $d$. This contradiction shows $r = s$. $\blacksquare$
This is Hungerford's Corollary 5.5. The polynomials in $S$ are the standard representatives of the classes, as the remainders $0, \ldots, n - 1$ were for integers. When $d = 0$, the modulus is a nonzero constant, $S = \{0\}$, and there is a single class; this is the counterpart of the modulus 1, allowed but uninteresting, and from here on $p(x)$ is assumed nonconstant.
The theorem counts the classes. A polynomial in $S$ is $a_0 + a_1 x + \cdots + a_{d-1}x^{d-1}$ with arbitrary coefficients, the zero polynomial included, so:
- Over an infinite field there are infinitely many classes, one for each list of $d$ coefficients.
- Over a finite field with $q$ elements there are exactly $q^d$ classes, one for each choice of the $d$ coefficients. Modulo $x^3 + x^2 + 1$ in $\mathbb{Z}_2[x]$ there are $2^3 = 8$, drawn with some of their members in the figure below.
The integers modulo $n$ can have any number of classes; polynomials over $\mathbb{Z}_q$ produce class counts that are powers of $q$: $2^8 = 256$ for a modulus of degree 8 over $\mathbb{Z}_2$, $11^2 = 121$ for a quadratic over $\mathbb{Z}_{11}$. The restriction will matter when the classes are made into fields.
Check your understanding. Modulo $x^2 + x + 1$ in $\mathbb{Q}[x]$, the standard representatives are 0 and the polynomials of degree at most 1. Which of them lies in the class of $x^3$? Try it without long division.
$[x^3] = [1]$, since $x^3 - 1 = (x - 1)(x^2 + x + 1)$ (the script confirms the remainder 1). So modulo this factor of the running quartic, $x$ behaves like a cube root of 1. The third article matches its class with the complex number $\omega = -\tfrac{1}{2} + \tfrac{\sqrt 3}{2}i$, and indeed $\omega^3 = 1$.
The partition can be drawn. Every polynomial over $\mathbb{Z}_2$ of degree less than 6 can be written uniquely as $r(x) + k(x)p(x)$ with $r$ and $k$ of degree less than 3, by the division algorithm, and laying these out with $r$ along the columns and $k$ down the rows sorts all 64 of them into their 8 classes.
Arithmetic with congruences
The opening replaced $x^2$ by 2 in the middle of a product. This section shows why that is allowed. The idea: multiplying or adding two expressions of the form "something plus a multiple of $p$" gives the product or sum of the somethings, plus a multiple of $p$.
Theorem. If $f(x) \equiv g(x)$ and $h(x) \equiv j(x) \pmod{p(x)}$, then
- $f(x) + h(x) \equiv g(x) + j(x) \pmod{p(x)}$, and
- $f(x)h(x) \equiv g(x)j(x) \pmod{p(x)}$.
Proof. Write $f = g + kp$ and $h = j + lp$ with $k, l \in F[x]$.
(1) Adding, $f + h = (g + j) + (k + l)p$.
(2) Multiplying out,
$$fh = (g + kp)(j + lp) = gj + (gl + jk + klp)\,p,$$
so $fh - gj$ is a multiple of $p$. $\blacksquare$
This is Hungerford's Theorem 5.2, and its proof is the integer proof with $kp$ in place of $nk$. A check: part 2 applied to $x^2 \equiv 2$ twice gives $x^4 \equiv 4 \pmod{x^2 - 2}$, the first example of the definition. The script checks both parts exhaustively over $\mathbb{Z}_2$ for the modulus $x^3 + x^2 + 1$: for every pair of polynomials of degree less than 5, the sum and product are congruent to the sum and product of their remainders.
Repeating the theorem gives the same consequences as for integers:
- Constant multiples and differences. A constant $c \in F$ is a polynomial, and $c \equiv c$, so $f \equiv g$ gives $cf \equiv cg$; with $c = -1$ and part 1, $f - h \equiv g - j$.
- Powers. If $f \equiv g$, then $f^k \equiv g^k$ for every positive integer $k$, by induction on $k$.
- Substitution. If $f \equiv g \pmod p$ and $H(y) = c_m y^m + \cdots + c_1 y + c_0$ has coefficients in $F$, then $H(f) \equiv H(g) \pmod p$, since each term $c_i f^i$ is congruent to $c_i g^i$ and the terms can be added. Over $\mathbb{Z}_2$ with modulus $x^3 + x^2 + 1$, for example, $x^4 + x \equiv x^2 + 1$, and the script confirms that $H(y) = y^2 + y + 1$ gives $H(x^4 + x) \equiv H(x^2 + 1) \equiv x$.
So a computation modulo $p(x)$ may replace any polynomial by a congruent one at any stage. In particular it may reduce after every step, and no polynomial of degree $2d - 1$ or more ever needs to be written down.
Reducing high powers
The rule in the opening example, "replace $x^2$ by 2", is the general method. If $p(x) = x^d + c_{d-1}x^{d-1} + \cdots + c_0$ is monic, then $p(x) \equiv 0$ gives
$$x^d \equiv -c_{d-1}x^{d-1} - \cdots - c_1 x - c_0 \pmod{p(x)},$$
and multiplying by $x$ and reducing again handles each higher power. (A modulus that is not monic can be replaced by its monic associate, which has the same multiples.) Over $\mathbb{Z}_2$, where $-1 = 1$, the modulus $x^3 + x^2 + 1$ gives $x^3 \equiv x^2 + 1$, and each power of $x$ comes from the previous one by multiplying by $x$ and replacing $x^3$:
| $k$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| $x^k \bmod p$ | $1$ | $x$ | $x^2$ | $x^2 + 1$ | $x^2 + x + 1$ | $x + 1$ | $x^2 + x$ | $1$ |
For instance $x^4 = x \cdot x^3 \equiv x^3 + x \equiv (x^2 + 1) + x$.
Check your understanding. Before reading the last column, explain why none of the powers of $x$ can be 0, and why two of $x^0, \ldots, x^7$ must coincide.
If $x^k \equiv 0$, then $p$ divides $x^k = x \cdot x^{k-1}$, and since $p$ is irreducible, Euclid's lemma applied $k$ times makes $p$ divide $x$, which is impossible for a cubic. So the eight powers lie among the seven nonzero classes, and by the pigeonhole principle two must coincide. The table shows the first repeat as late as it can be, $x^7 \equiv x^0$.
At $k = 7$ the powers return to 1: $x^7 \equiv 1$, which says that $p(x)$ divides $x^7 - 1$, and indeed $x^7 + 1 = (x^3 + x^2 + 1)(x^4 + x^3 + x^2 + 1)$ in $\mathbb{Z}_2[x]$. From then on the powers repeat with period 7, so a large power needs only the remainder of its exponent. Since $100 = 7 \cdot 14 + 2$,
$$x^{100} = (x^7)^{14} \cdot x^2 \equiv x^2 \pmod{x^3 + x^2 + 1},$$
which the script confirms by direct reduction. This is the computation that found the weekday a googol days after a Thursday, with $x$ in place of 10 and $x^3 + x^2 + 1$ in place of 7. The seven powers before the repetition are exactly the seven nonzero classes, each appearing once; why the period is $2^3 - 1$, and why every nonzero class appears, is explained in building fields from irreducible polynomials.
Cancellation
Sums, products and powers all carry over. Does division? For integers, a common factor $c$ can be canceled from a congruence modulo $n$ only at the price of dividing the modulus by $\gcd(c, n)$. Polynomials behave the same way, and the proof is the same. The idea: the factor that $k$ shares with $p$ cancels only together with the same factor of $p$, and the rest of $k$ cancels freely.
Proposition. Let $k(x) \in F[x]$ be nonzero, let $d(x) = \gcd(k(x), p(x))$, and let $p'(x) = p(x)/d(x)$. Then
$$k(x)f(x) \equiv k(x)g(x) \pmod{p(x)} \quad \text{if and only if} \quad f(x) \equiv g(x) \pmod{p'(x)}.$$
In particular, if $k(x)$ and $p(x)$ are relatively prime, then $kf \equiv kg \pmod p$ implies $f \equiv g \pmod p$.
Proof. Write $k = dk'$ and $p = dp'$. The polynomials $k'$ and $p'$ are relatively prime: by Bezout's identity, $d = ku + pv$ for some $u$ and $v$, that is, $d = d\,(k'u + p'v)$, and canceling the nonzero factor $d$ (allowed, since $F[x]$ is an integral domain) gives $1 = k'u + p'v$.
Suppose $kf \equiv kg \pmod p$, so $k(f - g) = pm$ for some $m$. Then $dk'(f - g) = dp'm$, and canceling $d$ gives $k'(f - g) = p'm$. So $p'$ divides $k'(f - g)$, and since $\gcd(p', k') = 1$, the cancellation theorem for polynomials gives $p' \mid f - g$.
Conversely, if $f - g = p'n$, then $k(f - g) = dk'p'n = p\,(k'n)$. $\blacksquare$
With the running example as the modulus: $f(x) = (x^2 - 2)(x^2 + x + 1)$, and the congruence
$$(x^2 - 2)\,x^2 \equiv (x^2 - 2)(-x - 1) \pmod{f(x)}$$
holds because the difference of the two sides is $(x^2 - 2)(x^2 + x + 1) = f(x)$. The common factor $k = x^2 - 2$ has $\gcd(k, f) = x^2 - 2$, so the proposition allows cancellation only down to the modulus $f/(x^2 - 2) = x^2 + x + 1$, giving $x^2 \equiv -x - 1 \pmod{x^2 + x + 1}$, which is true. Canceling naively would claim $x^2 \equiv -x - 1 \pmod{f}$, which is false: the difference $x^2 + x + 1$ is nonzero of degree 2, less than $\deg f = 4$, so $f$ cannot divide it. The script also checks the proposition by brute force over $\mathbb{Z}_3$, for every monic modulus of degree 1 to 3 and every nonzero $k$ and every $f$ and $g$ of degree less than 3, 739,206 cases in all.
Check your understanding. Keep the modulus $f(x)$. The factor $x^2 - 2$ could not be canceled freely. Can the factor $x$?
It can. The irreducible $x$ does not divide $f$, because $f(0) = -2 \neq 0$, so $\gcd(x, f) = 1$ and the proposition cancels $x$ with the modulus unchanged. The next article meets this again: modulo $f$, the class of $x$ has an inverse and that of $x^2 - 2$ does not.
When $p(x)$ is irreducible, its only monic divisors are 1 and its monic associate, so every $k$ not divisible by $p$ is relatively prime to it and can be canceled. That is the polynomial counterpart of cancellation modulo a prime, and it is the first sign that an irreducible modulus will produce a field.
Parallels with the integers
| Modulo $n$ in $\mathbb{Z}$ | Modulo $p(x)$ in $F[x]$ |
|---|---|
| $n \mid a - b$ | $p(x) \mid f(x) - g(x)$ |
| same remainder, $0 \le r < n$ | same remainder, $r = 0$ or $\deg r < \deg p$ |
| $n$ classes $[0], \ldots, [n - 1]$ | one class per remainder; $q^d$ classes over a field with $q$ elements |
| sums, products and powers of congruences | the same, with substitution into any $H(y) \in F[y]$ |
| cancel $c$ down to modulus $n / \gcd(c, n)$ | cancel $k(x)$ down to modulus $p(x)/\gcd(k(x), p(x))$ |
Where it leads
- The classes modulo $p(x)$, with addition and multiplication defined through representatives, form a ring $F[x]/(p(x))$ (Congruence-Class Arithmetic in Polynomial Rings). The theorem on sums and products is what makes those operations well defined, exactly as it was for the integers modulo $n$. The opening computation of $(1 + \sqrt 2)^5$ is arithmetic in that ring for $p(x) = x^2 - 2$.
- When $p(x)$ is irreducible the ring is a field, which contains a root of $p(x)$ (Building Fields from Irreducible Polynomials). Over a field with $q$ elements and with $\deg p = d$, it is a field with $q^d$ elements.
- Congruence modulo $p(x)$ is congruence modulo the set of multiples of $p(x)$, an ideal of $F[x]$. Congruence modulo an ideal in any commutative ring is the subject of Congruence Modulo an Ideal and Quotient Rings.
What we have learned
Congruence modulo a polynomial is congruence modulo an integer with polynomials in every place. It is an equivalence relation, and each class contains exactly one remainder of degree less than $\deg p$, which gives $q^d$ classes over a field with $q$ elements. Congruences can be added, multiplied and raised to powers, which is why the opening could replace $x^2$ by 2. A common factor cancels only down to the modulus $p/\gcd(k, p)$.
Can the classes themselves be added and multiplied as the elements of a ring, as the integers modulo $n$ were? That is the subject of the next article, Congruence-Class Arithmetic in Polynomial Rings.
References
- Hungerford, T. W. (2014). Abstract Algebra: An Introduction (3rd ed.), §5.1. Brooks/Cole, Cengage Learning. The course text: congruence modulo $p(x)$ is an equivalence relation (Theorem 5.1) that respects sums and products (Theorem 5.2); classes are equal exactly when their representatives are congruent and are otherwise disjoint (Theorem 5.3, Corollary 5.4); each class is the class of a unique polynomial of degree less than $\deg p$ or of 0 (Corollary 5.5). record · 44 pages
- Judson, T. W. (2026). Abstract Algebra: Theory and Applications (annual edition, August 2026), §17.2: the division algorithm in $F[x]$ (Theorem 17.2.1), on which the description of the classes rests. Free online at judsonbooks.org. record · 44 pages