Polynomial Rings, Irreducibility and Greatest Common Divisors

If R is a commutative ring, then a sequence σ in R is σ = (s0, s1, s2, . . . , si, . . . ); the entries si ∈R, for all i ≥0, are called the coefficients of σ. To determine when two sequences are equal, let us recognize that a sequence σ is really a function σ : N →R, where N is the set of natural numbers, with σ(i) = si for all i ≥0. Thus, if τ = (t0, t1, t2, . . . , ti, . . . ) is a sequence, then σ = τ if and only if σ(i) = τ(i) for all i ≥0; that is, σ = τ if and only if si = ti for all i ≥0.

If σ = (s0, s1, . . . , sn, 0, 0, . . . ) ̸= 0 is a polynomial, then there is sn ̸= 0 with si = 0 for all i > n. We call sn the leading coefficient of σ, we call n the degree of σ, and we denote the degree n by deg(σ). The zero polynomial 0 does not have a degree because it has no nonzero coefficients. Some authors define deg(0) = −∞, and this is sometimes convenient, for −∞< n for every integer n. On the other hand, we choose not to assign a degree to 0 because it is often a genuinely different case that must be dealt with separately. Notation. If R is a commutative ring, then the set of all polynomials with coefficients in R is denoted by R[x].

Let k be a field. The fraction field of k[x], denoted by k(x), is called the field of rational functions over k.

If f (x) ∈k[x], where k is a field, then a root of f (x) in k is an element a ∈k with f (a) = 0. Remark. The polynomial f (x) = x2 −2 has its coefficients in Q, but we usually say that √ 2 is a root of f (x) even though √ 2 is irrational; that is, √ 2 /∈Q. ◀ We will use the following elementary exercise in the proof of the next lemma. If f (x), g(x) ∈R[x], where R is a commutative ring, write a(x) = f (x) + g(x) and m(x) = f (x)g(x); evaluating at u ∈R gives a(u) = f (u) + g(u) and m(u) = f (u)g(u). Greatest Common Divisors

If k is a finite field, a generator of the cyclic group k× is called a primitive element of k. Although the multiplicative groups I× p are cyclic, no explicit formula giving a primitive element of each of them is known. For example, finding a primitive element of F257 essentially involves checking the powers of each [i], where 1 < i < 257, until one is found for which im ̸≡1 mod 257 for all positive integers m < 256. The definition of a greatest common divisor of polynomials is essentially the same as the corresponding definition for integers. Greatest Common Divisors

An element p in a domain R is irreducible if p is neither 0 nor a unit and, in any factorization p = uv in R, either u or v is a unit. Elements a, b ∈R are associates if there is a unit u ∈R with b = ua. For example, a prime p ∈Z is an irreducible element, as is −p. We now describe irreducible polynomials p(x) ∈k[x], when k is a field.

If k is a field, then a rational function f (x)/g(x) ∈k(x) is in lowest terms if f (x) and g(x) are relatively prime.

If A and R are (commutative) rings, a (ring) homomorphism is a function f : A →R such that (i) f (1) = 1; (ii) f (a + a′) = f (a) + f (a′) for all a, a′ ∈A; (iii) f (aa′) = f (a) f (a′) for all a, a′ ∈A. A homomorphism that is also a bijection is called an isomorphism. Commutative rings A and R are called isomorphic, denoted by A ∼= R, if there is an isomorphism f : A →R.

If R is a commutative ring, then R[x] is a commutative ring that contains R as a subring.

(i) If σ = (s0, s1, . . . ), then xσ = (0, s0, s1, . . . ); that is, multiplying by x shifts each coefficient one step to the right. (ii) If n ≥1, then xn is the polynomial having 0 everywhere except for 1 in the nth coordinate. (iii) If r ∈R, then (r, 0, 0, . . . )(s0, s1, . . . , s j, . . . ) = (rs0,rs1, . . . ,rs j, . . . ).

Polynomials f (x) = s0 + s1x + s2x2 + · · · + snxn and g(x) = t0 + t1x + t2x2 + · · · + tmxm of degrees n and m, respectively, are equal if and only if n = m and si = ti for all i.

If p is a prime, then the field of rational functions Ip(x) is an infinite field containing Ip as a subfield.7

Let f (x) ∈k[x], where k is a field, and let u ∈k. Then there is q(x) ∈k[x] with f (x) = q(x)(x −u) + f (u).

Let k be a field and let f (x) ∈k[x]. If f (x) has degree n, then f (x) has at most n roots in k.

Every nth root of unity in C is equal to e2πik/n = cos 2πk n + i sin 2πk n , where k = 0, 1, 2, . . . , n −1.

Let k be any field, perhaps finite. If f (x), g(x) ∈k[x], if deg( f ) ≤ deg(g) ≤n, and if f (a) = g(a) for n + 1 elements a ∈k, then f (x) = g(x).

If k is a field and f (x), g(x) ∈k[x], then their gcd d(x) is a linear combination of f (x) and g(x); that is, there are s(x), t(x) ∈k[x] with d(x) = s(x) f (x) + t(x)g(x).

If k is a field, then a polynomial p(x) ∈k[x] is irreducible if and only if deg(p) = n ≥1 and there is no factorization in k[x] of the form p(x) = g(x)h(x) in which both factors have degree smaller than n.

Let k be a field and let f (x), g(x) ∈k[x]. If p(x) is an irreducible polynomial in k[x], and p(x) | f (x)g(x), then either p(x) | f (x) or p(x) | g(x). More generally, if p(x) | f1(x) · · · fn(x), then p(x) | fi(x) for some i.

If k is a field and f (x), g(x) ∈k[x], then there are algorithms for computing the gcd ( f, g), as well as for finding a pair of polynomials s(x) and t(x) with ( f, g) = s(x) f (x) + t(x)g(x).

If k is a field, then every polynomial f (x) ∈ k[x] of degree ≥1 is a product of a nonzero constant and monic irreducibles. Moreover, if f (x) has two such factorizations f (x) = ap1(x) · · · pm(x) and f (x) = bq1(x) · · · qn(x), that is, a and b are nonzero constants and the p’s and q’s are monic irreducibles, then a = b, m = n, and the q’s may be reindexed so that qi = pi for all i.

A rational number z that is an algebraic integer must lie in Z. More precisely, if f (x) ∈Z[x] ⊆Q[x] is a monic polynomial, then every rational root of f (x) is an integer that divides the constant term.

(i) We determine the irreducible polynomials in I2[x] of small degree. As always, the linear polynomials x and x + 1 are irreducible. There are four quadratics: x2; x2 + x; x2 + 1; x2 + x + 1 (more generally, there are pn monic polynomials of degree n in Ip[x], for there are p choices for each of the n coefficients a0, . . . , an−1). Since each of the first three has a root in I2, there is only one irreducible quadratic. There are eight cubics, of which four are reducible because their constant term is 0. The remaining polynomials are x3 + 1; x3 + x + 1; x3 + x2 + 1; x3 + x2 + x + 1. Since 1 is a root of the first and fourth, the middle two are the only irreducible cubics. There are 16 quartics, of which eight are reducible because their constant term is 0. Of the eight with nonzero constant term, those having an even number of nonzero coefficients have 1 as a root. There are now only four surviving polynomials f (x), and each of them has no roots in I2; i.e., they have no linear factors. If f (x) = g(x)h(x), then both g(x) and h(x) must be irreducible quadratics. But there is only one irreducible quadratic, namely, x2 + x + 1, and so (x2 + x + 1)2 = x4 + x2 + 1 is reducible while the other three quartics are irreducible. The following list summarizes these observations. Irreducible Polynomials of Low Degree over I2 degree 2: x2 + x + 1. degree 3: x3 + x + 1; x3 + x2 + 1. degree 4: x4 + x3 + 1; x4 + x + 1; x4 + x3 + x2 + x + 1. Greatest Common Divisors (ii) Here is a list of the monic irreducible quadratics and cubics in I3[x]. The reader can verify that the list is correct by first enumerating all such polynomials; there are 6 monic quadratics having nonzero constant term, and there are 18 monic cubics having nonzero constant term. It must then be checked which of these have 1 or −1 as a root (it is more convenient to write −1 instead of 2). Monic Irreducible Quadratics and Cubics over I3 degree 2: x2 + 1; x2 + x −1; x2 −x −1. degree 3: x3 −x + 1; x3 + x2 −x + 1; x3 −x2 + 1; x3 −x2 + x + 1; x3 −x −1; x3 + x2 −1; x3 + x2 + x −1; x3 −x2 −x −1. If, in addition, both p(x) and q(x) are monic, then p(x) | q(x) implies p(x) = q(x).

(i) Let R be a domain and let F = Frac(R) denote its fraction field. In Theorem 3.13 we said that R is a subring of F, but that is not the truth; R is not even a subset of F. We did find a subring R′ of F, however, that has a very strong resemblance to R, namely, R′ = {[a, 1] : a ∈R} ⊆F. The function f : R →R′, given by f (a) = [a, 1], is easily seen to be an isomorphism. (ii) When an element in a commutative ring R was “identified” with a constant polynomial [in the proof of Lemma 3.16(iii)], that is, r was identified with (r, 0, 0, . . . ), we implied that R is a subring of R[x]. The subset R′ = {(r, 0, 0, . . . ) : r ∈R} is a subring of R[x],