polynomials – Precisely

The theorem

If $n > 0$ and $a, b_1, \ldots b_n \in \Z$ are such that $a$ is separately coprime with each $b_i$ , then $a$ is coprime with their product $b_1 b_2 \ldots b_n$ .

The proof

Proof: Through Bézout. $a$ being coprime with each $b_i$ , we can write, for each $i = 1, \ldots n$ :

$p_i a + q_i b_i = 1$

If we take the product of each of these expressions, we get:

$\prod_{i = 1}^n (p_i a + q_i b_i) = 1$

Among the $2^n$ terms of this product, all but one contain $a$ as a factor. The one that doesn’t have $a$ as a factor is $q_1 b_1 q_2 b_2 \ldots q_n b_n$ . Hence we obtain an expression of the form:

$(\ldots) a + (q_1 \ldots q_n) (b_1 \ldots b_n) = 1$

Hence $a$ and $b_1 b_2 \ldots b_n$ are coprime. $\blacksquare$

In the case of polynomials

The same result holds with polynomials: if $P$ and $Q_1, \ldots Q_n$ are polynomials over a field $\K$ , such that $P$ is coprime with each $Q_i$ , then $P$ is coprime with their product $Q_1 Q_2 \ldots Q_n$ .

The proof is identical.

Definition

Let $\K$ be a commutative field. The polynomials $\K[X]$ form a commutative unital algebra over $\K$ containing an element $X$ such that the following universal property holds:

For any unital algebra $A$ (commutative or otherwise) and any element $a \in A$ , there exists exactly one unital algebra morphism $\phi: \K[X] \to A$ such that $\phi(X) = a$ .

If $P$ and $Q$ are elements of $\K[X]$ , let $\gamma_Q: \K[X] \to \K[X]$ be the unique morphism such that $\gamma_Q(X) = Q$ . Then the composition $P(Q)$ of $P$ and $Q$ is defined by $P(Q) = \gamma_Q(P)$ .

Effect of composition of polynomials on the corresponding functions

In terms of polynomial functions, the composition of polynomials is the equivalent to the composition (via “ $\circ$ ”) of the associated functions.

Let us first define the function that is associated with a polynomial.

The set $\K^\K$ of functions $\K \to \K$ is made into a commutative and unital associative algebra by the usual operations of summing ( $(f + g)(x) = f(x) + g(x)$ , multiplication by a scalar ( $(af)(x) = a(f(x))$ and internal multiplication ( $(fg)(x) = f(x) g(x)$ ).

Hence, following the universal property of the algebra of polynomials, there exists a unique morphism $\phi: \K[X] \to \K$ such that $\phi(X) = \Id_\K$ .

By definition, the function $p$ associated with a polynomial $P$ is simply $p = \phi(P)$ .

We wish to show that if $P$ and $Q$ are polynomials and $p$ and $q$ the respective associated functions, the function associated with $P(Q)$ is $p \circ q$ .

Let $Q$ be a polynomial and $q = \phi(Q)$ . Let us consider the mapping $\alpha: \K[X] \to \K^\K, P \mapsto \phi(P) \circ q$ .

It is easy to check that $\alpha$ is a morphism.

Furthermore, $\alpha(X) = \phi(X) \circ q = \Id_\K \circ q = q$ .

On the other hand, $\phi \circ \gamma_Q$ is also a morphism from $\K[X]$ to $\K^\K$ , and $(\phi \circ \gamma_Q)(X) = \phi(\gamma_Q(X)) = \phi(Q) = q$ .

Thus both $\alpha$ and $\phi \circ \gamma_Q$ are morphisms $\K[X] \to \K^\K$ and they agree on the value $X$ . The universal property of polynomials entails that they are equal.

Hence for any $P \in \K[X]$ , $(\phi \circ \gamma_Q)(P) = \alpha(P)$ .

That is, $\phi(P(Q)) = \phi(P) \circ \phi(Q)$ .

Effect on the evaluation of a polynomial

If $P \in \K[X]$ and $a \in \K$ , the evaluation of $P$ at $a$ is, by definition, the value at $P$ of the unique morphism $\epsilon_a: \K[X] \to \K$ such that $\epsilon_a(X) = a$ .

Given polynomials $P$ and $Q$ and $a \in \K$ , we wish to evaluate $P(Q)$ at $a$ , and, specifically, show that $\epsilon_a(P(Q)) = \epsilon_{\epsilon_a(Q)}(P)$ .

Since $P(Q) = \gamma_Q(P)$ , we have $\epsilon_a(P(Q)) = (\epsilon_a \circ \gamma_Q)(P)$ .

Both $\epsilon_a \circ \gamma_Q$ and $\epsilon_{\epsilon_a(Q)}$ are morphisms $\K[X] \to \K$ . Both evaluate at $X$ to $\epsilon_a(Q)$ . Hence they are equal:

$\epsilon_a \circ \gamma_Q = \epsilon_{\epsilon_a(Q)}$

which entails $(\epsilon_a \circ \gamma_Q)(P) = \epsilon_{\epsilon_a(Q)}(P)$

hence: $\epsilon_a(P(Q)) = \epsilon_{\epsilon_a(Q)}(P)$ , as announced.

In particular: if $P \in \K[X]$ and $a, b \in \K$ , then $\epsilon_a(P(X + b)) = \epsilon_{\epsilon_a(X + b)}(P) = \epsilon_{\epsilon_a(X) + \epsilon_a(b)}(P) = \epsilon_{a + b}(P)$ .

Associativity

If $P$ , $Q$ and $R$ are polynomials in $\K[X]$ , we wish to show that:

$P(Q(R)) = (P(Q))(R)$

Using the definition of composition, this translates into:

$\gamma_{\gamma_R(Q)}(P) = \gamma_R(\gamma_Q(P))$

That is:

$\gamma_{\gamma_R(Q)}(P) = (\gamma_R \circ \gamma_Q)(P)$

We need to show that for any $Q$ and $R$ in $\K[X]$ , the two $\K[X] \to \K[X]$ mappings $\gamma_{\gamma_R(Q)}$ and $\gamma_R \circ \gamma_Q$ are identical.

Both are endomorphisms of $\K[X]$ .

We have:

$\gamma_{\gamma_R(Q)}(X) = \gamma_R(Q)$ by definition of $\gamma_{\gamma_R(Q)}$ .
$(\gamma_R \circ \gamma_Q)(X) = \gamma_R(\gamma_Q)(X)) = \gamma_R(Q)$ by definition of $\gamma_Q)$ .

Hence both morphisms agree on the image of $X$ . By virtue of the universal property of polynomials, they are equal.

Hence for any $P \in \K[X]$ , we indeed have $\gamma_{\gamma_R(Q)}(P) = (\gamma_R \circ \gamma_Q)(P)$ , that is, $P(Q(R)) = (P(Q))(R)$ .

Effect of composition on the evaluation of polynomials

todo

Derivation of the composition of polynomials