MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Assuming two polynomials $P_1,P_2 \in \mathbb{Z}_p[r]$ of degree $n$, with no common factors, we know that there exist polynomials $Q_1,Q_2$ s.t.: $Q_1P_1 + Q_2P_2 =1$. From Bezout's identity we also know that $deg(Q_i)<n$ for $i=1,2$.

I am wondering how the above is generalized in the case of more than two polynomials. More specifically, given polynomials $P_i$ for $i=1,...,t$ of degree $n$ with $GCD(P_1,...,P_t) = 1$ there exist polynomials $Q_i$ s.t.: $\sum_{i=1}^tQ_iP_i = 1$. What is the maximum degree of these polynomials $Q_i$? Notice that polynomials $P_i$ may have some common factors when taken pairwise, however there is no common factor shared by all $t$ of them,

I can think of examples of where at least some of the $Q_i$'s have degree larger than $n$ but for all the cases I can come up with, the total sum of their degrees is less than $tn$. That is, $\sum_{i=1}^tdeg(Q_i) < tn$, however I am not able to come up with a proof for this claim.

Can someone point out some direction towards such a proof or invalidate it if it false?

share|cite|improve this question

You can just recursively compute the gcd of $t\ge 2$ polynomials by $$ \gcd(P_1, P_2, \dots , P_t) = \gcd( P_1, \gcd(P_2, \dots , P_t)), $$ starting with $\gcd(P_{t-1},P_t)$, $\gcd(P_{t-2}, \gcd(P_{t-1},P_t))$ etc. If you do this with the extended Euclidean algorithm you obtain the Bezout-coefficients, i.e., polynomials $Q_1,\ldots ,Q_t$, and one can estimate the degree (also the degree of a gcd of univariate polynomials can be estimated by Barnett's theorem, see

Edit: The estimate on the degrees obtained in this way may not be optimal, of course. However, as soon as one can find $P_i$ and $P_j$ with $\gcd(P_i,P_j)=1$, one has $1=Q_iP_i+Q_jP_j=\sum_{k=1}^tQ_kP_k$ with all other $Q_k=0$, and $\sum_{k=1}^t\deg (Q_k)\le 2n$. Otherwise each pair $(P_i,P_j)$ has a non-trivial gcd, and this should help to reduce the total degree of the $Q_i$'s.

share|cite|improve this answer
Thanks for the answer but it does not really address my point. I am interested in explicitly constructing polynomials $Q_i$ and not in computing the GCD (after all, I already know the GCD is 1 in the situation I am working at). Of course recursively applying the extended Euclidean will give the GCD and help compute the polynomials $Q_i$. If at each step I compute polynomials $L_i,R_{i+1}$ s.t. $L_iP_i + R_{i+1}P_{i+1} = gcd(P_i,P_{i+1}$ for $i=t-1,...,1$, the polynomials $Q_i$ will be computed as a multiplication of the $L_i$'s and $R_i$'s. I am interested in an upper bound on their degree. – Jonathan Naysmith Jul 16 '13 at 13:40
So are you saying the the degree of each $Q_i$ can be be up to $(t-1)n$ (due to $t-1$ multiplications of up to $n$ degree polynomials)? – Jonathan Naysmith Jul 16 '13 at 14:15
Not each $Q_i$. Try $t=3$ with $P_1,P_2,P_3$ and $gcd(P_2,P_3)=R_2P_2+R_3P_3$ $1=gcd(P_1,P_2,P_3)=Q_1P_1+Q_2R_2P_2+Q_2R_3P_3$. – Dietrich Burde Jul 16 '13 at 14:21

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.