Coprimality with a product of integers

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.

The composition of polynomials

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

todo