    # Polynomial Rings. Division Algorithm.

“I hope you rot in the deepest, darkest, and filthiest pit of hell where you really belong, being tormented day and night watching CNN, MSNBC, and woke movies and series forever,” Apocalypse, Anawim, #justtothepoint.

Recall. A commutative ring is a ring in which the multiplication operation is commutative,i.e., ∀a, b ∈ R, a·b = b·a.

Definition. Let R be a commutative ring. A polynomial ring is a ring formed from the set of polynomials in one or more indeterminates or variables with coefficients in R. R[x] = {anxn + an-1xn-1+ ··· + a1x + a0 | ai ∈ R, n ∈ ℤ+}, e.g. 2x3+ 7x2 +4∈ ℤ[x], 23x2 + 4x -7 ∈ ℚ[x].

The degree of f(x) = anxn + an-1xn-1+ ··· + a1x + a0, expressed or written as deg(f(x)), is the largest k such that the coefficient of ak is not zero. If an ≠ 0, we say that f(x) has degree n and its leading coefficient is an. A constant polynomial is either the zero polynomial or a polynomial of degree zero.

Two polynomials anxn + an-1xn-1+ ··· + a1x + a0 and bmxm + bm-1xm-1+ ··· + b1x + b0 are equal when the corresponding coefficients of xk are equal, ai = bi ∀i ∈ ℤ+, ai = 0 when m < i ≤ n, bj = 0 when n < j ≤ m

Let R be a commutative ring, and let f(x) = anxn + an-1xn-1+ ··· + a1x + a0 and g(x) = bmxm + bm-1xm-1+ ··· + b1x + b0 ∈ R[x]. The polynomial ring R[x] is equipped with addition and multiplication,

1. f(x) + g(x) = $\sum_{i=0}^{max(m,n)} (a_i+b_i)x^i$ = (as + bs)xs + (as-1 + bs-1)xs-1+ ··· + (a1 + b1)x + a0 + b0, where s = max(m, n), ai = 0 for i > n, bi = 0 for i > m.
2. f(x)g(x) = = $\sum_{k=0}^{m + n} (\sum_{i=0}^k a_ib_{k-i})x^k$ = cm+nxm+n + cm+n-1xm+n-1+ ··· + c1x + c0 where ck = akb0 + ak-1b1 + ··· + a1bk-1 + a0bk, for k = 0,···, m+n

# Examples

• f(x) = x2 − 5x + 6 ∈ ℤ[x] and g(x) = 2x3 − 5 ∈ ℤ[x], f(x) + g(x) = 2x3 + x2 − 5x + 1, and f(x)g(x) = 2x5 − 10x4 + 12x3 − 5x2 + 25x − 30.
• f(x) = 2x3 + x2 + 2x + 2, g(x) = 2x2 + 2x + 1 ∈ ℤ3[x], then f(x) + g(x)=[2x3 + 3x2 + 4x + 3] 2x3 + x because addition and multiplication of the coefficients are done modulo 3. f(x)·g(x) = x5 + 2x3 + 2.

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

• (x2 + 2x + 3)(x3 + 4x) = x5 + 2x4 + x3 + 2x2 in ℤ6[x] (Figure 1.a.) Theorem. Let R be a commutative ring with unity 1. R[x] is a commutative ring under the operations of polynomial addition and multiplication with unity (1, 0, 0, ···).

Proof.

It is left to the reader to verify that (R[x], +, ·) is a commutative ring with unity (1, 0, 0, · · ·). Besides, (0, 0, · · ·) is the zero element of R[x] and the addition inverse of (a0, a1, ···, an) is (-a0, -a1, ···, -an).

Futhermore, the mapping a → (a, 0, 0, ···) is a monomorphism (an injective homomorphism) of the ring R into R[x]. Thus (R ≋ Φ(R[x])), R can be considered as a subring of R[x] and we no longer need to distinguish between a and (a, 0, 0, ···).

Theorem. Let D be a commutative ring with unity 1. Then, D[x] is an integral domain if and only if D is an integral domain.

Proof.

Recall that an integral domain is a commutative ring with unity in which the product of any two nonzero elements is nonzero.

⇒ ) Suppose D[x] is an integral domain. D is a subring of D[x] (D ⊆ D[x]), then it is obvious that D must also be commutative ring with unity(🚀) and has no zero divisors (∀x, y ∈ D with x·y = 0, x, y ∈ D[x] ⇒[D[x] is an integral domain] x = 0 or y = 0).

🚀 Consider the map, Φ:R[x] → R, such that Φ(f(x)) = Φ(a0 + a1x + ··· + anxn) = a0. Φ is an onto homomorphism (it is left as an easy exercise) ⇒ R is a homomorphic image of R[x], a ring with unity and [A homomorphic image of a ring with unity is a ring with unity] Φ(e(x)) will be the unity of R where e(x) is the unity of R[x].

⇐ ) Conversely, suppose D be an integral domain.

1. We already know that D[x] is a ring.
2. D is a commutative ring ⇒ D[x] is a commutative ring, too.
3. Futhermore, f(x) = 1 is the unity element.
4. Let’s prove that D[x] has no zero-divisors. Suppose that f(x) = anxn + an-1xn-1+ ··· + a1x + a0 and g(x) = bmxm + bm-1xm-1+ ··· + b1x + b0 ∈ D[x] are non-zero polynomials, that is, an ≠ 0, bm ≠ 0 for some n and m positive integers.

f(x)·g(x) = cm+nxm+n + cm+n-1xm+n-1+ ··· + c1x + c0 where ck = akb0 + ak-1b1 + ··· + a1bk-1 + a0bk, for k = 0,···, m+n

Its leading coefficient is cm+n = anbm ≠ 0 because D is an integral domain. Therefore, f(x) ≠ 0 and g(x) ≠ 0 ⇒ f(x)·g(x) ≠ 0, hence D[x] has no zero-divisors.

Theorem. Let R be an integral domain, let f and g be two nonzero polynomials in R[x], then deg(fg) = deg(f) + deg(g).

Proof:

Suppose f(x) = anxn + an-1xn-1+ ··· + a1x + a0 and g(x) = bmxm + bm-1xm-1+ ··· + b1x + b0 are nonzero polynomials of degree n and m respectively, i.e., an, bm ≠ 0R ⇒ the highest possible degree of fg is n + m and the coefficient of xn+m is anbm.

Since R is an integral domain, anbm = 0R if and only if an = 0R or bm = 0R. Therefore, an, bm ≠ 0R ⇒ an·bm ≠ 0R ⇒ deg(fg) = n + m = deg(f) + deg(g).

Counterexample. In ℤ6[x] (it is not an integral domain, e.g., 2x·3x = 0), (3x +3)(2x +5) = 6x2 +21x + 15 = 3x + 3. deg(3x +3) = 1 ≠ 1 + 1.

Theorem. Let R be an integral domain, then the units of R[x] are the units of R.

Proof:

Suppose f(x) = anxn + an-1xn-1+ ··· + a1x + a0 is a unit ⇒ there exist g(x) ∈ R[x], say deg(f(x)) = n, and deg(g(x)) = m, such that f(x)·g(x) = 1 ⇒[deg(fg) = deg(f) + deg(g), f(x)·g(x) = 1] n + m = 0 ⇒ n = m = 0 ⇒ f(x) = u ∈ R, g(x) = v ∈ R, u·v = 1, and therefore u and v are units in R.

Counterexample. In ℤ8[x] (it is not an integral domain), (4x +1)(4x +1) = 16x2 +8x + 1 = 1. 4x +1 is a unit in ℤ8[x].

Theorem. If I is an ideal of a ring R, define I[x] = {i0 +i1x +··· + inxn| ij∈ I}. Then, R[x]/I[x] ≋ (R/I)[x]

Proof.

Consider Φ: R[x] → (R/I)[x] given by Φ(a0 +a1x +··· + anxn) = (a0 + I) +(a1 + I)x +··· + (an + I)xn

Φ is a surjective homomorphism.

∀f(x), g(x) ∈ R[x], f(x) = anxn + an-1xn-1+ ··· + a1x + a0 and g(x) = bmxm + bm-1xm-1+ ··· + b1x + b0

Φ(f(x) + g(x)) = Φ($\sum_{i=0}^{max(m,n)} (a_i+b_i)x^i$) = $\sum_{i=0}^{max(m,n)} (a_i+b_i+I)x^i$ =[By the definion of coset addition] $\sum_{i=0}^{max(m,n)} (a_i+I)x^i+\sum_{i=0}^{max(m,n)} (b_i+I)x^i$ = Φ(f(x)) + Φ(g(x))

Similarly, Φ(f(x) · g(x)) = Φ(f(x))·Φ(g(x)). Futhermore, Φ is onto. Let F[x] ∈ (R/I)[x], then F[x] = $\bar a_0 + \bar a_1x + ··· + \bar a_nx^n,\bar a_0 = a_0 + I, \bar a_1 = a_1 + I, ···, \bar a_n = a_n + I, a_0, a_1, ···, a_n ∈ R$. Set f(x) = a0 + a1x + ··· + anxn ∈ R[x], and obviously Φ(f(x)) = F[x] and F[x] was taken an arbitrary element of (R/I)[x].

f(x) = a0 + a1x + ··· + anxn ∈ Ker(Φ) ↭ ak + I = 0 + I ∀0 ≤ k ≤ n ↭ ak ∈ I ∀0 ≤ k ≤ n ↭ f(x) ∈ I[x], hence ker(Φ) = I[x]. Finally, by the First Isomorphism Theorem for rings, R[x]/I[x] ≋ (R/I)[x]

Theorem. P ⊆ R is a prime ideal if and only if P[x] ⊆ R[x] is a prime ideal.

Proof.

Recall: A prime ideal A of a commutative ring R is a proper ideal of R such that if a, b are two elements of R, and whenever their product ab is an element of A, then either a is in A, b is in A or both, i.e., a, b ∈ R, ab ∈ A ⇒ a ∈ A or b ∈ A. Example: ⟨x⟩ ⊆ ℤ[x] is a prime ideal, but ⟨x2⟩ is not, because x2 ∈ ⟨x2⟩ but x ∉ ⟨x2⟩.

P ⊆ R is a prime ideal ↭[Theorem. Let R be a commutative ring with unity, and let A be an ideal of R. Then, A is a prime ideal iff R/A is an integral domain.] R/P is an integral domain ↭[Theorem. Let D be a commutative ring with unity 1. Then, D[x] is an integral domain if and only if D is an integral domain.] (R/P)[x] is an integral domain ↭[Theorem. If I is an ideal of a ring R, define I[x] = {i0 +i1x +··· + inxn| ij∈ I}. Then, R[x]/I[x] ≋ (R/I)[x]] R[x]/P[x] is an integral domain ↭ P[x] is a prime ideal ∎

Division Algorithm. Let F be a field, f(x), g(x) ∈ F[x], g(x) ≠ 0. Then, there exists unique polynomials q(x) and r(x) ∈ F[x] such that

1. f(x) = g(x)q(x) + r(x)
2. Either r(x) = 0 or deg(r(x)) < deg(g(x)).

Proof.

We first prove the existence of the polynomials q and r. There are three possibilities:

1. Suppose f = 0, then the proposition is true with q = r = 0F[x] (q(x) = r(x) = 0).
2. Suppose deg(f) < deg(g), then the proposition is true with q = 0F[x] and r = f.
3. Suppose deg(f) ≥ deg(g), then the proof of existence is obtained by induction on the degree of f.

3.1 If deg(f) = 0 ⇒ deg(g) = 0 ⇒ f = a, g = b, for some nonzero elements a and b, a, b ∈ F ⇒ [F is a field, and by assumption, b = g(x) ≠ 0, and therefore b is a unit, ∃b-1: bb-1 = b-1b = 1] f = a = b(b-1a) = g(b-1a), the theorem holds with q = b-1a, and r = 0F

3.2 Let’s assume that the proposition holds whenever deg(f) < n. We must show that it is true when f(x) has degree n, say f(x) = anxn + an-1xn-1+ ··· + a1x + a0 with an ≠ 0F. The divisor g(x) = bmxm + bm-1xm-1+ ··· + b1x + b0, bm ≠ 0F, and m ≤ n.

bm ≠ 0 (By assumption, g(x) ≠ 0), F is a field ⇒ bm is an unit. Next, we multiply the divisor g by anbm-1xn-m (n -m ≥ 0) to obtain (anbm-1xn-m·g) = anxn + anbm-1bm-1xn-1 + ··· + anbm-1b0xn-m

Since the leading term of this polynomial is identical to that of f, namely an, the difference of f - anbm-1xn-m·g is a polynomial of degree less than n, and we can apply the induction hypothesis with g as the divisor polynomial and f - anbm-1xn-m·g as the dividend ⇒ ∃ polynomials q1 and r:

f - anbm-1xn-m·g = q1g + r, r = 0F or deg(r) < deg(g).

f = (anbm-1xn-m + q1)·g + r, r = 0F or deg(r) < deg(g) ∎

To prove that q and r are unique, suppose that q’ and r’ are polynomials satisfying f = q’g + r’, r’ = 0F and deg(r’) < deg(g).

qg + r = f = q’g + r’ ⇒ g(q - q’) = r’ - r.

If q - q’ ≠ 0F ⇒ the degree of the polynomial on the right hand size of the last equation (r’ - r) is greater than or equal to the degree of g [deg(r’-r) ≥ deg(g) + deg(q -q’) ⇒ deg(r’-r) ≥ deg(g)]. But this is not possible since the polynomials r’ and r are either zero or have degree strictly less that of g ⇒ q’ = q ⇒[By assumption, g(x) ≠ 0] r’ = r ∎

Example: x4 -2x3 -x +1 = (x2 + x -1)(x2 +2x -1) + 2x in ℤ5[x] (Figure 1.b.). x4 -2x3 -x +1 = (x2 - 4x +9)(x2 +2x -1) + (-23x + 10) in ℤ (Figure 1.c.) # Bibliography

This content is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. This post relies heavily on the following resources, specially on NPTEL-NOC IITM, Introduction to Galois Theory, Michael Penn, and Contemporary Abstract Algebra, Joseph, A. Gallian.
1. NPTEL-NOC IITM, Introduction to Galois Theory.
2. Algebra, Second Edition, by Michael Artin.
3. LibreTexts, Abstract and Geometric Algebra, Abstract Algebra: Theory and Applications (Judson).
4. Field and Galois Theory, by Patrick Morandi. Springer.
5. Michael Penn (Abstract Algebra), and MathMajor.
6. Contemporary Abstract Algebra, Joseph, A. Gallian.
7. Andrew Misseldine: College Algebra and Abstract Algebra.
Bitcoin donation 