Challenging exercise about polynomials

[geoffrey159]

Homework Statement

If $P,Q$ are polynomials of $\mathbb{Z}[X]$, and $p$ is a prime number that divides all the coefficients of $PQ$, show that $p$ divides the coefficients of $P$ or the coefficients of $Q$.

Homework Equations

$c_n = \sum_{k=0}^{n} a_k b_{n-k}$ is the n-th coefficient of $PQ$, where the $(a_k)_{k=0..N}$ are the coefficients of $P$, and the $(b_k)_{k=0..M}$ are the coefficients of $Q$

The Attempt at a Solution

That exercise gave me a serious headache, but it was an interesting one. Some people may want to try it for themselves.

@ homework helplers: Do you agree with my solution ?

Spoiler: my solution

I'll do it by induction.

• Since $p$ divides $c_0 = a_0b_0$, and since $p$ is prime, then $p$ divides $a_0$ or $b_0$.

• Assume that $p|a_0, ..., a_n$ or $p|b_0,...,b_n$.
  If $n \ge \min\{\text{deg}(P),\text{deg}(Q)\}$ then there is nothing to prove, so we will assume that $n < \min\{\text{deg}(P),\text{deg}(Q)\}$. That last inequality and the fact that $\text{deg}(PQ) = \text{deg}(P)+\text{deg}(Q)$ tell us that $2n+2 \le \text{deg}(PQ)$

Case 1: $p|a_0, ..., a_n$ and there is $k \in \{0...n\}$ such that $p|b_0,...,b_{k-1}$ and $p\not | \ b_k$.
Since $p$ divides $c_{n+k+1} = (a_0b_{n+k+1} + ... + a_n b_{k+1}) + a_{n+1} b_k + (a_{n+2} b_{k-1} +...+a_{n+k-1}b_0)$ , then $p | a_{n+1}b_k$, and with Gauss lemma, $p|a_{n+1}$

Case 2: $p|a_0, ..., a_n$ and $p|b_0,...,b_n$.
Since $p$ divides $c_{2n+2} = (a_0b_{2n+2} + ... + a_n b_{n+2}) + a_{n+1} b_{n+1} + (a_{n+2} b_{n} +...+a_{2n+2}b_0)$, then $p | a_{n+1}b_{n+1}$. Since $p$ is prime, it divides $a_{n+1}$ or $b_{n+1}$

Case 3 and 4: They are the symetric cases but assuming this time that $p|b_0,...,b_n$
​

• So by induction, $p$ divides the coefficients of $P$ or the coefficients of $Q$

​

​

 

[STEMucator]

Homework Statement

If $P,Q$ are polynomials of $\mathbb{Z}[X]$, and $p$ is a prime number that divides all the coefficients of $PQ$, show that $p$ divides the coefficients of $P$ or the coefficients of $Q$.

Homework Equations

$c_n = \sum_{k=0}^{n} a_k b_{n-k}$ is the n-th coefficient of $PQ$, where the $(a_k)_{k=0..N}$ are the coefficients of $P$, and the $(b_k)_{k=0..M}$ are the coefficients of $Q$

The Attempt at a Solution

That exercise gave me a serious headache, but it was an interesting one. Some people may want to try it for themselves.

@ homework helplers: Do you agree with my solution ?

Spoiler: my solution

I'll do it by induction.

• Since $p$ divides $c_0 = a_0b_0$, and since $p$ is prime, then $p$ divides $a_0$ or $b_0$.

• Assume that $p|a_0, ..., a_n$ or $p|b_0,...,b_n$.
  If $n \ge \min\{\text{deg}(P),\text{deg}(Q)\}$ then there is nothing to prove, so we will assume that $n < \min\{\text{deg}(P),\text{deg}(Q)\}$. That last inequality and the fact that $\text{deg}(PQ) = \text{deg}(P)+\text{deg}(Q)$ tell us that $2n+2 \le \text{deg}(PQ)$

Case 1: $p|a_0, ..., a_n$ and there is $k \in \{0...n\}$ such that $p|b_0,...,b_{k-1}$ and $p\not | \ b_k$.
Since $p$ divides $c_{n+k+1} = (a_0b_{n+k+1} + ... + a_n b_{k+1}) + a_{n+1} b_k + (a_{n+2} b_{k-1} +...+a_{n+k-1}b_0)$ , then $p | a_{n+1}b_k$, and with Gauss lemma, $p|a_{n+1}$

Case 2: $p|a_0, ..., a_n$ and $p|b_0,...,b_n$.
Since $p$ divides $c_{2n+2} = (a_0b_{2n+2} + ... + a_n b_{n+2}) + a_{n+1} b_{n+1} + (a_{n+2} b_{n} +...+a_{2n+2}b_0)$, then $p | a_{n+1}b_{n+1}$. Since $p$ is prime, it divides $a_{n+1}$ or $b_{n+1}$

Case 3 and 4: They are the symetric cases but assuming this time that $p|b_0,...,b_n$
​

• So by induction, $p$ divides the coefficients of $P$ or the coefficients of $Q$

​

​

I really think you could elaborate more here:

If $n \ge \min\{\text{deg}(P),\text{deg}(Q)\}$ then there is nothing to prove, so we will assume that $n < \min\{\text{deg}(P),\text{deg}(Q)\}$. That last inequality and the fact that $\text{deg}(PQ) = \text{deg}(P)+\text{deg}(Q)$ tell us that $2n+2 \le \text{deg}(PQ)$

You seem to jump without explaining much detail. Perhaps show there is nothing to prove where you claim, and show some additional inequalities.

If I may offer an alternative argument, there is an easier way to express the requirement. I will provide an intro to the proof if you are interested:

Supposing $p$ is a prime number that divides all the coefficients of $PQ$, we wish to show $p$ divides the coefficients of $P$ or the coefficients of $Q$.

Please note: When I write something like $p|Q$ below, I am strictly speaking about dividing the coefficients.

Suppose $p|Q$, but $p \nmid P$. We must show $p|Q$.

Since $p \nmid P$, $\exists s, t \in \mathbb{Z} \space | \space 1 = \cdots$.

The proof is almost complete, but there would be no fun in just seeing the answer.

 

[geoffrey159]

I really think you could elaborate more here ...
You seem to jump without explaining much detail. Perhaps show there is nothing to prove where you claim, and show some additional inequalities.

Hi, thanks for replying !

I meant that if $n \ge \min\{\text{deg}(P),\text{deg}(Q)\}$, and with the induction hypothesis, $p$ divides by definition all the coefficients of $P$ or $Q$. The interesting part is when $n < \min\{\text{deg}(P),\text{deg}(Q)\}$.

If $n < \min\{\text{deg}(P),\text{deg}(Q)\}$ then $\text{deg}(PQ) = \text{deg}(P)+\text{deg}(Q) \ge 2 \min\{\text{deg}(P),\text{deg}(Q)\} \ge 2 (n+1) = 2n +2$, and since $p$ divides all the coefficients of $PQ$, $p | c_{0},...,c_{2n+2}, ..., c_{\text{deg}(PQ)}$

If I may offer an alternative argument, there is an easier way to express the requirement. I will provide an intro to the proof if you are interested:
...
Suppose $p|Q$, but $p \nmid P$. We must show $p|Q$.
Since $p \nmid P$, $\exists s, t \in \mathbb{Z} \space | \space 1 = \cdots$.
The proof is almost complete, but there would be no fun in just seeing the answer.

I was almost sure there was some easier proof, but did not manage to find it. Please explain.

 

[STEMucator]

Hi, thanks for replying !

I meant that if $n \ge \min\{\text{deg}(P),\text{deg}(Q)\}$, and with the induction hypothesis, $p$ divides by definition all the coefficients of $P$ or $Q$. The interesting part is when $n < \min\{\text{deg}(P),\text{deg}(Q)\}$.

If $n < \min\{\text{deg}(P),\text{deg}(Q)\}$ then $\text{deg}(PQ) = \text{deg}(P)+\text{deg}(Q) \ge 2 \min\{\text{deg}(P),\text{deg}(Q)\} \ge 2 (n+1) = 2n +2$, and since $p$ divides all the coefficients of $PQ$, $p | c_{0},...,c_{2n+2}, ..., c_{\text{deg}(PQ)}$

I was almost sure there was some easier proof, but did not manage to find it. Please explain.

Suppose $p|Q$, but $p \nmid P$. We must show $p|Q$.

Since $p \nmid P$, $\exists s, t \in \mathbb{Z} \space | \space 1 = Ps + pt \Rightarrow Q = PQs + pQt$.

Now, $p$ divides the right hand side, so $p$ also divides $Q$.

Q.E.D.

 

[geoffrey159]

You seem to jump without explaining much detail ...

That works for you too !I don't understand the notations that are used. What I get is the following

You say $p| c_0,...,c_{\text{deg}(P)+\text{deg}(Q)}$ and you assume $p\not | a_0,...,a_{\text{deg}(P)}$, and you want to show $p|b_0,...,b_{\text{deg}(Q)}$
So what I understand is :
There is some $a_k$ such that $\text{gcd}(p,a_k) = 1$, so that the family $(a_0,...,a_{\text{deg}(P)},p)$ is relatively prime.
And now I understand you use Bezout theorem. You say there are $s_0,...,s_{\text{deg}(P)},t$ in $\mathbb{Z}$ such that
$1 = a_0 s_0 + ... +a_{\text{deg}(P)}s_{\text{deg}(P)} + tp$

What's the next step?