Gauss' Primitive Polynomial Lemma

# Gauss' Primitive Polynomial Lemma

Recall from the Primitive Polynomial over Z page that a polynomial $f \in \mathbb{Z}[x]$ with $f(x) = a_0 + a_1x + ... + a_nx^n$ is a primitive polynomial over $\mathbb{Z}$ if $\gcd (a_0, a_1, ..., a_n) = 1$.

We will now prove a very important result which states that the product of two primitive polynomials is a primitive polynomial. This result is known as Gauss' primitive polynomial lemma. We need to prove a preliminary result first.

Lemma 1: Let $f, g, h \in \mathbb{Z}[x]$ with $f = gh$ and let $f(x) = a_0 + a_1x + ... a_mx^m$, $g(x) = b_0 + b_1x + ... + b_nx^n$, and $h(x) = c_0 + c_1x + ... + c_kx^k$. Let $p$ be a prime number. If $s$ and $t$ are the smallest indices such that the coefficients $b_s$ and $c_t$ are not divisible by $p$ then $s + t$ is the smallest index such that the coefficient $a_{s+t}$ is not divisible by $p$. |

**Proof:**Since $f = gh$ we see that the coefficients of $f$, $g$, and $h$ are related by:

\begin{align} \quad a_{s+t} = b_0c_{s+t} + b_1c_{s+t-1} + ... + b_{s-1}c_{t+1} + b_sc_t + b_{s+1}c_{t-1} + ... + b_{s+t}c_0 \end{align}

- Since $p | b_0, b_1, ..., b_{s-1}$ and $p|c_0, c_1, ..., c_{t-1}$, and since $p$ does not divide $b_sc_t$ we have that $p$ does not divide $a_{s+t}$.

- For $j < s +t$ consider the coefficient:

\begin{align} \quad a_j = \sum_{i=0}^{j} b_ic_{j-1} \end{align}

- Then $p | a_j$ since each term in the sum is divisible by $p$. So $s + t$ is the smallest index such that the coefficient $a_{s+t}$ is not divisible by $p$. $\blacksquare$

Lemma 2 (Gauss' Primitive Polynomial Lemma): Let $g, h \in \mathbb{Z}[x]$ be primitive polynomials. Then $gh$ is a primitive polynomial. |

**Proof:**Let $g$ and $h$ be primitive polynomials. Let $f = gh$ and let:

\begin{align} \quad f(x) &= a_0 + a_1x + ... + a_mx^m \\ \quad g(x) &= b_0 + b_1x + ... + b_nx^n \\ \quad h(x) &= c_0 + c_1x + ... + c_kx^k \end{align}

- Now let $p$ be a prime number. Since $g$ and $h$ are primitive polynomials there exists least indices $s$ and $t$ such that $p$ does not divide $b_s$ and $p$ does not divide $c_t$. Then $p$ does not divide $a_{s+t}$ from the previous Lemma. Since $p$ is an arbitrary prime we have that no prime divides all of the coefficients of $f$. So $\gcd (a_0, ..., a_m) = 1$ and $f = gh$ is a primitive polynomial. $\blacksquare$