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?


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 http://www.sciencedirect.com/science/article/pii/S0747717102905420).

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.

  • $\begingroup$ 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. $\endgroup$ – Jonathan Naysmith Jul 16 '13 at 13:40
  • $\begingroup$ 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)? $\endgroup$ – Jonathan Naysmith Jul 16 '13 at 14:15
  • $\begingroup$ 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$. $\endgroup$ – Dietrich Burde Jul 16 '13 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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