# Don't understand lemma about primitive polynomial product

• I
swampwiz

https://cims.nyu.edu/~kiryl/Algebra/Section_3.10--Polynomials_Over_The_Rational_Field.pdf

Unfortunately, I am stuck on Lemma 3.10.1 that concludes that the product of a pair of primitive polynomials is itself primitive.

I understand about how there is some index in each polynomial at which the polynomial becomes imprimitive, and that the term cj + k is of the form:

cj + k = aj bk + Ta ga + Tb gb

where ga & gb are the Greatest Common Divisor of the terms below aj & bk, respectively (here, I use Ta & Tb to denote general numbers that are multiplied by ga & gb to get the terms for the summation of the products of a & b terms whose index is less than i & j, respectively)

So the proof follows that it presumes that cj + k has a prime divisor. Now, if I presume that this divisor is the same as ga & gb, then I get the contradiction that cj + k has no divisor. Fine. However if I only presume that the divisor is the same as ga, but not gb, I get

(here U is a general number like T)

cj + k = ga U = aj bk + Ta ga + Tb gb

aj bk = ga ( U - Ta ) - gb Tb

Now I don't know what prime factors aj or bk have, and it seems that I have no way of proving that the RHS of this doesn't coincidentally sum up to a number that happens to be a multiple of whatever prime factors aj or bk

What am I missing here?

The point is f(x) and g(x) are primitive, so the assumed prime p which divides f(x)g(x) cannot divide f(x) or g(x). Therefore there exists $a_j,\ b_k$ which are not (and lowest indices having this property). $c_{j+k}$ is the sum of three terms, two if which have p as a divisor. Therefore the third term $a_jb_k$ must also have p as a divisor, but this a contradiction, because p does not divide either factor.

Mentor
2021 Award

https://cims.nyu.edu/~kiryl/Algebra/Section_3.10--Polynomials_Over_The_Rational_Field.pdf

Unfortunately, I am stuck on Lemma 3.10.1 that concludes that the product of a pair of primitive polynomials is itself primitive.

I understand about how there is some index in each polynomial at which the polynomial becomes imprimitive, and that the term cj + k is of the form:

cj + k = aj bk + Ta ga + Tb gb

where ga & gb are the Greatest Common Divisor of the terms below aj & bk, respectively (here, I use Ta & Tb to denote general numbers that are multiplied by ga & gb to get the terms for the summation of the products of a & b terms whose index is less than i & j, respectively)

So the proof follows that it presumes that cj + k has a prime divisor. Now, if I presume that this divisor is the same as ga & gb, then I get the contradiction that cj + k has no divisor. Fine. However if I only presume that the divisor is the same as ga, but not gb, I get

(here U is a general number like T)

cj + k = ga U = aj bk + Ta ga + Tb gb

aj bk = ga ( U - Ta ) - gb Tb

Now I don't know what prime factors aj or bk have, and it seems that I have no way of proving that the RHS of this doesn't coincidentally sum up to a number that happens to be a multiple of whatever prime factors aj or bk

What am I missing here?
Your change of notation makes it tough to argue. You need to have a closer look on what ##g_a## and ##g_b## actually are. The proof assumes that a prime ##p## divides ##c_{j+k}## and in addition that ##p | a_0 , \dots , a_{j-1}## as well as ##p | b_0 , \dots , b_{k-1}.## Therefore both of your ##g_a## and ##g_b## must be divisible by ##p##, hence ##c_{j+k} - g_a T_a - g_b T_b = a_j b_k## is divisible by ##p## which can't be, because neither ##a_j## nor ##b_k## is.

swampwiz
Your change of notation makes it tough to argue. You need to have a closer look on what ##g_a## and ##g_b## actually are. The proof assumes that a prime ##p## divides ##c_{j+k}## and in addition that ##p | a_0 , \dots , a_{j-1}## as well as ##p | b_0 , \dots , b_{k-1}.## Therefore both of your ##g_a## and ##g_b## must be divisible by ##p##, hence ##c_{j+k} - g_a T_a - g_b T_b = a_j b_k## is divisible by ##p## which can't be, because neither ##a_j## nor ##b_k## is.

OK, but should the statement "f( x ) and g( x ) are primitive polynomials" be interpreted such that terms below i & j are divisible by the same prime?

E.G.

f( x ) = 2 x3 + 7 x2 + 4 x + 2

g( x ) = 11 x3 + 5 x2 + 9 x + 3

below i = 2, f( x ) is divisible by 2

below j = 2, g( x ) is divisible by 3

Here they are not divisible by the same prime, but each of them are primitive (and imprimitive up to i or j = 1 )

Using my notation:

a2 b2 = 35

ga = 2

Ta = 9

gb = 3

Tb = 11

U = Ta + ( a2 b2 + gb Tb ) / ga = 9 + [ ( 7 ) ( 5 ) + ( 3 ) ( 11 ) ] / ( 2 ) = 9 + 68 / 2 = 43

c2 + 2 = ga U = ( 2 ) ( 43 ) = 86

The presumption was that c2 + 2 would be divisible by ga, which would mean that U would be an integer. This presumption was supposed to end being proven false.

Mentor
2021 Award
OK, but should the statement "f( x ) and g( x ) are primitive polynomials" be interpreted such that terms below i & j are divisible by the same prime?
No. Primitive polynomials cannot be divided by any prime, that's the definition.
The assumption is that ##f(x) \cdot g(x)## is divided by a prime ##p_0## (in order to show that this cannot be the case either and thus proving that there is no ##p_0,## which in turn means that ##f(x) \cdot g(x)## is primitive, too.)

Because ##f(x)## and ##g(x)## are primitive, the ##p_0## from our assumption cannot divide them, i.e ##p_0## cannot divide all coefficients. Therefore there must be a first index ##j## for ##f(x)## and ##k## for ##g(x)## so that the coefficients ##a_j## and ##b_k## are not divided by ##p_0##.
Since we took the first, all from ##0## to ##j-1##, ##0## to ##k-1,## resp. are divisible by ##p_0##. This makes your ##g_a## and ##g_b## divisible by ##p_0,## too, and in the end ##a_j \cdot b_k## divisible by ##p_0.## Since ##p_0## doesn't divide neither ##a_j## nor ##b_k## because we choose them not to do, it cannot divide their product - a contradiction, i.e. the assumptions that there is a ##p_0## dividing ##f(x) \cdot g(x)## was wrong.

(I wrote ##p_0## simply to emphasize that it is a special prime number assumed to exist, dividing the product, not the single polynomials. The proof then shows it cannot exist. Since there isn't any special prime, it means there isn't any at all.)

swampwiz
No. Primitive polynomials cannot be divided by any prime, that's the definition.
The assumption is that ##f(x) \cdot g(x)## is divided by a prime ##p_0## (in order to show that this cannot be the case either and thus proving that there is no ##p_0,## which in turn means that ##f(x) \cdot g(x)## is primitive, too.)

Because ##f(x)## and ##g(x)## are primitive, the ##p_0## from our assumption cannot divide them, i.e ##p_0## cannot divide all coefficients. Therefore there must be a first index ##j## for ##f(x)## and ##k## for ##g(x)## so that the coefficients ##a_j## and ##b_k## are not divided by ##p_0##.
Since we took the first, all from ##0## to ##j-1##, ##0## to ##k-1,## resp. are divisible by ##p_0##. This makes your ##g_a## and ##g_b## divisible by ##p_0,## too, and in the end ##a_j \cdot b_k## divisible by ##p_0.## Since ##p_0## doesn't divide neither ##a_j## nor ##b_k## because we choose them not to do, it cannot divide their product - a contradiction, i.e. the assumptions that there is a ##p_0## dividing ##f(x) \cdot g(x)## was wrong.

(I wrote ##p_0## simply to emphasize that it is a special prime number assumed to exist, dividing the product, not the single polynomials. The proof then shows it cannot exist. Since there isn't any special prime, it means there isn't any at all.)

My example showed that ga = 2 & gb = 3, so there is no prime that divides both of them. Are you trying to say that this lemma would not apply to my example because they don't share a common divisor (i.e., up to the point at which they become primitive)? But the lemma says that this applies to any primitive polynomials. Are not my f( x ) & g( x ) primitive, and therefore covered by the lemma definition?

swampwiz
OK, I think I finally have it! I have no idea why that author felt the need to give such a complicated explanation.

If there are 2 primitive polynomials φ( x ) & ψ( x ) such that f( x ) = φ( x ) ψ( x ) and then f( x ) were presumed to be imprimitive, then there must be some integral polynomial h( x ) and a prime number p such that f( x ) = p h( x ), which would imply that either φ( x ) or ψ( x ) must be the product of p and some integral polynomial, thereby contradicting the initial proposition that the pair were both primitive.

Is it this simple?

Mentor
2021 Award
OK, I think I finally have it! I have no idea why that author felt the need to give such a complicated explanation.

If there are 2 primitive polynomials φ( x ) & ψ( x ) such that f( x ) = φ( x ) ψ( x ) and then f( x ) were presumed to be imprimitive, then there must be some integral polynomial h( x ) and a prime number p such that f( x ) = p h( x ), which would imply that either φ( x ) or ψ( x ) must be the product of p and some integral polynomial, thereby contradicting the initial proposition that the pair were both primitive.

Is it this simple?
The "difficulty" comes in what I highlighted in your question. Why would this be implied? The answer to it is the "complicated" proof the author gave. Of course it is as simple, but you have to rule out, that you cannot "create" a divisor ##p_0## in the product, because the coefficients of the product polynomial aren't simply products of the coefficients of the factor polynomials but sums of them. So one has to show that summation doesn't "create" a divisor where there have not been one in the summands. This is what it's all about!

(Concerning your previous post: It doesn't matter whether ##2 = g_a## or ##3 =g_b##. The assumption (to achieve the contradiction) is that there is one divisor of the product knowing there isn't one for the single factors.)

swampwiz
OK, now I really think I have it. I had misinterpreted the meaning of the what i & j represent; they represent not the first term that makes the polynomials primitive, but rather the first term that does not divide some proposed prime p, and for the polynomials to be primitive, all there needs to be is that this i & j exist for every prime - which makes sense since if there were a p in which this i & j didn't exist, the polynomials would not be primitive! So what is happening is that this analysis goes forward for every prime (which means that for "almost all" primes, i & j are both simply 0). My notion of an independent ga & gb was incorrect, as the parameters should be the p that is proposed, and thus my condition of both ga & gb being equal in essence was coincidentally correct for the case of the proposed prime being that value. The summation to get Ta & Tb was also correct, but both of these parameters should have been multiplied by the proposed prime p, an hence, what should be done is for every prime p

ci + j = ai bj + p ( Ta & Tb )

if the product of the polynomials is not primitive, then there must be a non-empty set of primes for which

ci + j % p = 0

ci + j % p = [ ai bj + p ( Ta & Tb ) ] % p = ( ai bj ) % p

but by the very definition of i & j (for every prime) is that they don't divide that specific prime, so ( ai bj ) % p != 0 and thus
ci + j % p != 0, which is a contradiction of the premise, and thus the product must be primitive.