Polynomial Rings, the Division Algorithm and Roots

Choose $M,N\in \mathbb{N}$ such that $a_i=0$ for $i>M$ and $b_j=0$ for $j>N$.

If $k>\max \{M,N\}$ then $(a+b{)}_k=0$, and if $k>M+N$ then every pair $i+j=k$ has $i>M$ or $j>N$, so every summand $a_i{b}_j$ in $(ab{)}_k$ is zero; hence both sequences have finite support.

Closure follows from [L2]; the additive group laws, including the zero sequence and coefficientwise negatives, follow coefficient by coefficient from the additive group laws in $R$.

Distributivity follows by splitting each finite convolution sum, commutativity follows by reindexing $(i,j)$ as $(j,i)$ and using commutativity in $R$, and associativity follows by [L3] from the equality of the two finite sums ${\sum }_{i+j+k=n}{a}_i{b}_j{c}_k$; the sequence $1$ is a multiplicative identity because only the index-$0$ coefficient contributes. Finally $c(r+s)=c(r)+c(s)$, $c(rs)=c(r)c(s)$, and $c(1_R)=1$, so [L4] makes $c$ a unital ring homomorphism, while equality of constant sequences forces equality of their index-$0$ coefficients and makes $c$ injective.

Send a nonzero sequence $a$ to $(a_0,\dots ,a_{\mathrm{deg}a})$, send the zero sequence to $(0)$, and send a trimmed list $(c_0,\dots ,c_n)$ to the sequence equal to $c_i$ for $i\le n$ and zero for $i>n$; [L2] shows that each construction lands in the stated class and that the two maps are inverse.

Padding a trimmed list by zeros does not change any coefficient, so the inverse maps preserve coefficientwise sums and every convolution coefficient; [L2] then gives preservation of degree and leading coefficient, and the displayed constant and indeterminate sequences correspond to their usual one-term and two-term lists.

For every $k>\max \{\mathrm{deg}f,\mathrm{deg}g\}$ both $a_k$ and $b_k$ vanish, so the coefficient of $x^k$ in $f+g$ vanishes; if the sum is nonzero, [L1] gives the stated inequality.

Put $m=\mathrm{deg}f$ and $n=\mathrm{deg}g$. For $k>m+n$, every pair $i+j=k$ has $i>m$ or $j>n$, while for $k=m+n$ the only possibly nonzero summand is $a_m{b}_n$; hence the top displayed coefficient is $\mathrm{lc}(f)\mathrm{lc}(g)$ and any nonzero product has degree at most $m+n$.

The leading coefficients of $f$ and $g$ are nonzero, so [L2] makes their product nonzero.

Fact [L1] identifies that product as the coefficient at degree $\mathrm{deg}f+\mathrm{deg}g$ and makes every higher coefficient zero, so $fg\mathrm{\ne }0$, its degree is the sum of the degrees, and its leading coefficient is the product of the leading coefficients.

By [L1], $R[x]$ is a commutative ring and its zero and one are distinct because the constant embedding is injective.

By [L2], two nonzero polynomials have nonzero product, so [L3] applied with step 1.1 makes $R[x]$ an integral domain.

If $f$ is a unit, choose $g$ with $fg=1$; neither factor is zero and [L1] gives $0=\mathrm{deg}1=\mathrm{deg}f+\mathrm{deg}g$, so both degrees are $0$, and comparison of constant coefficients shows that the constant value of $f$ is a unit of $R$.

Conversely, if $u\in R$ is a unit with inverse $v$, then [L2] gives $c(u)c(v)=c(uv)=c(1)=1$, so the constant polynomial $u$ is a unit of $R[x]$.

The formula in [L1] preserves sums term by term, sends $1$ to $1$, and sends a convolution product to ${\sum }_{i,j}\phi (a_i)\phi (b_j)s^{i+j}=({\sum }_i\phi (a_i)s^i)({\sum }_j\phi (b_j)s^j)$ by [L5]; thus [L4] makes it a unital ring homomorphism, and [L2] shows that it extends $\phi$ and sends $x$ to $s$.

If $\psi \text{\hspace{0.17em}⁣}:R[x]\to S$ is another such homomorphism, [L3] writes every polynomial as a finite sum ${\sum }_{i}c(a_i)x^i$, so [L4] forces $\psi (f)={\sum }_i\phi (a_i)s^i$; hence $\psi ={\mathrm{ev}}_{\phi ,s}$ and uniqueness holds.

The ring $P_0=R$ is a domain, giving the zero-indeterminate case.

Fix $n\in \mathbb{N}$ and assume that $P_n$ is a domain.

Under that hypothesis, [L1] and [L2] make $P_{n+1}=P_n[x_{n+1}]$ a domain; together with the base case, [L3] proves the claim for every $n$.

If $d=0$, monicity gives $g=1$, so $q=f,r=0$ works for every $f$. Hence suppose $d>0$; for the zero dividend, $q=r=0$ works.

Let $f\mathrm{\ne }0$ have degree $n$ and assume, as the strong induction hypothesis, that division exists for every zero polynomial or nonzero polynomial of degree below $n$. If $n<d$, take $q=0,r=f$.

If instead $n\ge d$, put $a=\mathrm{lc}(f)$; the polynomial $f_1=f-a{x}^{n-d}g$ has its degree-$n$ coefficient cancelled and is zero or has degree below $n$. The induction hypothesis gives $f_1=q_{1}g+r$ with $r=0$ or $\mathrm{deg}r<d$, whence $f=(q_1+a{x}^{n-d})g+r$.

Steps 1.1–2.1 and strong induction [L3] prove existence for every dividend.

If $f=qg+r=q^{\mathrm{\prime }}g+r^{\mathrm{\prime }}$ are two such expressions, then $(q-q^{\mathrm{\prime }})g=r^{\mathrm{\prime }}-r$; if $q-q^{\mathrm{\prime }}\mathrm{\ne }0$, the leading coefficient of $(q-q^{\mathrm{\prime }})g$ equals the nonzero leading coefficient of $q-q^{\mathrm{\prime }}$ because $g$ is monic, so [L1] gives degree at least $d$, whereas $r^{\mathrm{\prime }}-r$ is zero or has degree below $d$, a contradiction. Thus $q=q^{\mathrm{\prime }}$ and then $r=r^{\mathrm{\prime }}$, proving uniqueness and completing the induction proof.

If $R$ is the zero ring then $R[x]$ has one element, $f=0=0\cdot (x-a)+f(a)$, and the conclusion holds with $q=0$; this case is separated because $x-a=0$ there, which has no leading coefficient and so is not monic, leaving [L1] inapplicable. Otherwise $1\mathrm{\ne }0$, so $x-a$ is monic of degree one. Apply [L1]; the remainder $r$ is zero or constant, and applying [L3] to $f=q(x-a)+r$ gives $f(a)=q(a)(a-a)+r=r$, so $f=q(x-a)+f(a)$.

If $f(a)=0$, step 1.1 gives $f=q(x-a)$; conversely, if $f=q(x-a)$, applying [L3] gives $f(a)=q(a)(a-a)=0$, proving the biconditional.

By [L3] the coefficient $c$ has an inverse, and $h=c^{-1}g$ is monic with the same degree as $g$; [L1] gives unique $Q,r$ with $f=Qh+r$ and $r=0$ or $\mathrm{deg}r<\mathrm{deg}g$, so $q=c^{-1}Q$ gives $f=qg+r$.

If $f=qg+r=q^{\mathrm{\prime }}g+r^{\mathrm{\prime }}$, then $(q-q^{\mathrm{\prime }})g=r^{\mathrm{\prime }}-r$; unless $q=q^{\mathrm{\prime }}$, [L2] makes the left side have degree at least $\mathrm{deg}g$, while the right side is zero or has degree below $\mathrm{deg}g$, so $q=q^{\mathrm{\prime }}$ and then $r=r^{\mathrm{\prime }}$.

By [L4] and [L1], $F[x]$ is an integral domain.

Degree is natural-valued on nonzero polynomials, and [L2] supplies the division condition of [L3], so $F[x]$ is Euclidean with $\delta =\mathrm{deg}$.

By [L1] and [L2], $F[x]$ is a principal ideal domain.

Unfolding [L3], every ideal of $F[x]$ therefore has the form $(d)$ for some polynomial $d$.

If necessary interchange $f$ and $g$ so the second input is nonzero. Repeatedly apply [L2]; this also covers a zero first input, when the first remainder is already zero. Each nonzero remainder has strictly smaller natural degree than its divisor, so the process terminates. Every remainder is a polynomial linear combination of the original $f,g$ by back-substitution, and the last nonzero remainder $r$ divides the preceding remainder and hence, successively, both inputs.

Every common divisor of $f,g$ divides each remainder and therefore divides $r$; after multiplying $r$ and its back-substituted coefficients by $\mathrm{lc}(r{)}^{-1}$, the resulting monic polynomial $d=Af+Bg$ has the divisibility property and generates $(f,g)$, so [L1] identifies it with $\gcd (f,g)$.

If $p\mid f$ there is nothing to prove. Otherwise, if a common divisor $d$ of $p$ and $f$ were a nonunit, a factorization $p=de$ and irreducibility would make $e$ a unit, so $d$ would be associate to $p$ and $d\mid f$ would imply $p\mid f$, a contradiction. Thus every common divisor is a unit, and [L1] gives $A,B\in F[x]$ with $Ap+Bf=1$.

Multiplying the identity by $g$ gives $Apg+Bfg=g$; both terms on the left are divisible by $p$, the second because $p\mid fg$, so $p\mid g$. Thus $p$ satisfies the prime condition in [L2].

Use strong induction on $n=\mathrm{deg}f$; by [L3], a nonzero nonunit has $n\ge 1$.

If $f$ is irreducible, it is already a one-factor product; otherwise [L1] gives $f=gh$ with $g,h$ nonunits, and neither is zero because $f\mathrm{\ne }0$.

By [L2], $\mathrm{deg}g$ and $\mathrm{deg}h$ are positive and strictly below $n$, so the induction hypotheses factor both into irreducibles; concatenating those factorizations gives one for $f$, and [L4] completes the induction.

Fact [L4] makes $F[x]$ a domain, and [L1] supplies existence of irreducible factorizations.

For uniqueness, compare $p_1\cdots p_m=q_1\cdots q_n$; by [L2], $p_1$ divides some $q_j$, and irreducibility makes $p_1$ associate to $q_j$; after reordering and cancelling these nonzero associates in the domain, induction on $m$ pairs all remaining factors and gives $m=n$.

The existence and uniqueness established in steps 1.1 and 2.1 are exactly the conditions of [L3], so $F[x]$ is a UFD.

In a commutative ring the multiples of $p$ form an ideal containing $p$ and lie in every ideal containing $p$, so [L2] identifies $(p)$ with the set of multiples of $p$. Suppose $p$ is irreducible and $f+(p)$ is a nonzero residue class; then $p\nmid f$. If a common divisor $d$ of $p,f$ were a nonunit, a factorization $p=de$ and [L6] would make $e$ a unit, so $d$ would be associate to $p$ and $d\mid f$ would imply $p\mid f$, a contradiction. Thus every common divisor is a unit, and [L1] gives $Ap+Bf=1$, whence [L4] gives $(B+(p))(f+(p))=1+(p)$; every nonzero class is invertible, so the quotient is a field.

Conversely, suppose the quotient is a field and $p=ab$. By [L4], the two residue classes have product zero, so one is zero; say $a\in (p)$. The characterization established in step 1.1 gives $a=pc$, and hence $p=ab=pcb$. A direct leading-coefficient argument shows that $F[x]$ has no zero divisors, because $F$ is a field, so cancellation of the nonzero polynomial $p$ gives $cb=1$ and makes $b$ a unit. The other case similarly makes $a$ a unit, and [L6] makes $p$ irreducible.

Steps 1.1 and 2.1 prove that irreducibility is equivalent to quotient fieldness, and [L5] identifies quotient fieldness with maximality of $(p)$ in the sense of [L3].

If $n=0$, then $f$ is a nonzero constant and has no root, proving the base case.

For $n>0$, if $f$ has no root the claim is immediate; otherwise choose a root $a$, use [L1] to write $f=(x-a)q$, and use [L2] to obtain $\mathrm{deg}q=n-1$.

If $b\mathrm{\ne }a$ is another root, then $0=f(b)=(b-a)q(b)$, and [L3] gives $q(b)=0$ because $b-a\mathrm{\ne }0$; the induction hypothesis bounds the roots other than $a$ by $n-1$, so $f$ has at most $n$ roots, and [L4] completes the induction.

If $G=\{1\}$, then $G=⟨1⟩$ and [L4] makes it cyclic.

Suppose $G$ is nontrivial. Since $D$ is commutative by [L1], [L2] and [L3] make $G$ a finite abelian group; let $e\ge 1$ be its exponent from [L6].

Every $g\in G$ satisfies $g^e=1$, so all $\mathrm{\mid }G\mathrm{\mid }$ distinct elements of $G$ are roots, in the sense of [L10], of the nonzero monic polynomial $T^e-1$, whose degree is $e$ by [L9]; [L11] gives $\mathrm{\mid }G\mathrm{\mid }\le e$.

By [L12], write the invariant-factor list of $G$ as $1<n_1\mid \cdots \mid n_r$. By [L7], $\mathrm{\mid }G\mathrm{\mid }=n_1\cdots n_r$ and $e=n_r$, so $e\le \mathrm{\mid }G\mathrm{\mid }$; step 2.1 gives equality. Hence $n_1\cdots n_r=n_r$, and because every $n_i>1$, this forces $r=1$. Fact [L8] makes $G$ cyclic, while step 1.1 covers the trivial case.

Suppose for contradiction that $h=f-g$ is nonzero, and let $n=\mathrm{deg}h$; the assumed equality of values makes every element of $D$ a root of $h$.

Since $D$ is infinite it contains more than $n$ distinct elements, contradicting [L1]; hence $h=0$ and $f=g$.