# Explicit Bezout Cofactors

This is a rather severe revision of a question I asked recently. We know over the integers that $\gcd(a^2,b^2)=\gcd(a,b)^2$. We might prove this via unique factorization. In building the theory of prime factorization we use the fact that $\gcd(a,b)$ exist. This fact is sometimes proved with the slick (to a beginner) move that there must be a minimal element in $\lbrace d\mid d>0 \text{ and }d=as+bt\rbrace$ and it must be a common divisor and indeed the greatest such. This also shows that there is a linear combination $\gcd(a,b)=as+bt$. I'm sure standard terminology exists but allow me to call any such pair $(s,t)$ Bezout cofactors for the pair $(a,b)$. Of course with the extra condition $|s|<b$ we also have $|t|<a$ and two cofactor pairs, one with $s<0<t$ and one with $t<0<s$. The same things are true in more general settings such as polynomials. The slick argument above gives no indication how to find $s,t$ but we do know the extended Euclidean algorithm. To hone in on my question I'll stick to the case that $\gcd(a,b)=1$ : Given that $a,b$ are integers with cofactors $s,t$ such that $as+bt=1$, there are also cofactors $s',t'$ for $a^2,b^2$. One proof would be that evidently $\gcd(a,b)=1$ so also $\gcd(a^2,b^2)=1$ (via a small bit of theory) and hence the slick argument gives that $s',t'$ exist (and the Euclidean algorithm will only take about twice as long to find $s',t'$ as it will for $s,t$). However it is easy to check that $a^2\cdot s^2(as+3bt)+b^2\cdot t^2(3as+bt)=1$ And this establishes the existence of $s',t'$ constructively given only the fact that $a,b,s,t$ belong to some ring, pairwise commute, and satisfy $as+bt-1=0$. (An aside: I believe I can prove that no $s'$ and $t'$ cubic in $a,b,s,t$ make $a^2s'+b^2t'=1$) My question has to do with similar translations to polynomial identities. I'll start with a specific instance based on $ab=\gcd(a,b) lcm(a,b)$ and then attempt to state my general question.

The following is true over the integers: if $\gcd(u,v)=1$ and $au=bv$ then there is a $w$ with $a=vw$. Is the following true as well: if $A,B,U,V,S,T$ are commuting variables and we are given the expressions $US+VT-1$ and $AU-BV$, is there an (explicit) expression $W=W(A,B,S,T,U,V)$ such that $A-VW$ is in the ideal of $\mathbb{Z}(A,B,U,V,S,T)$ generated by $AS+BT-1$ and $AU-BV$?

Note that $au=bv$ would be $lcm(a,b)$, also $b=uw$ and $w=\gcd(a,b)$.

Consider theorems of integer divisibility whose premises and conclusions can be written as multinomial equations ($d \mid a$ becomes $a-da'=0$ , $\gcd(a,b)=1$ becomes $as+bt-1=0$ etc.), is there always (or when is there) a derivation of the conclusion purely from manipulation of $\mathbb{Z}$ multinomials?

This is partly idle curiosity, but I also find that sometimes an explicit constructive solution is very useful to improve results.

• @Aaron, I don't understand what the phrase, "given the expression $US+VT-1$" means, nor how it relates to whether there is "an (explicit) expression $W$ etc., etc." Dec 11 '10 at 21:27
• For the second question, what do you think of "if $ab=cd$, then there exist $u$, $v$, $w$, $t$ such that $a=uv$, $b=wt$, $c=uw$ and $b=vt$"? This is (modulo Noetherianness) equivalent to the assumption that the ring we are working over is a UFD. It clearly holds in $\mathbb Z$, but if we could derive it purely by algebraic manipulation, every ring would be a UFD. But is this a "theorem of integer divisibility" as you want it? You might wish to be more restrictive, e. g. by requiring that the conclusion doesn't have too many existential quantifiers. Dec 11 '10 at 22:58
• Replace "every ring" by "every Noetherian ring". Dec 11 '10 at 22:59
• @darij What if I don't assume Noetherian? What if I merely assume that I am in some integral domain, have 4 elements with $ab=cd$ and that the one pair $a,c$ has a common divisor which is a linear combination. So there are elements $x,y,u,v,w$ with $ax+cy=u$ $a=uv$ and $c=uw$. Does it follow from that alone that there must be a $t$ with $b=wt$ and $d=vt$? I think it does and that $t$ is an expression in $x,y,u,v,w,b,d$ (If I'm right, it is not that hard, but it would take me a few tries) Dec 12 '10 at 8:52
• @Gerry My comment to darj could be expressed as: Consider the axioms of an integral domain along named variables $a,b,c,d,x,y,u,v,w$ and additional axioms $ab=cd$,$ax+cy=u$ $uv=a$ and $uw=c$. Is it a theorem that there exists a $t$ with $b=wt$ and $d=vt$. I'll stick to lower case this time: My comment was that I could look at the integral domain $\mathcal{D}=\mathbb{Z}[a,b,c,d,x,y,u,v,w]$ and within it the ideal generated by the polynomials $ab-cd$, $ax+cy-u$, $uv-a$ and $uw-c$. Question, is there a $t\in\mathcal{D}$ such that $b-wt$ and $d-vt$ are both in that ideal? Dec 12 '10 at 9:11

For the first query: yes, $\rm\: A - V\ (AT+BS) = S\ (AU - BV) - A\ (SU + TV - 1)$
Now $\rm\ AU = BV = C\ \Rightarrow\ C\ (AT+BS) = BV AT + AU BS = AB\ (TV + US) = AB$
Hence $\rm\ \ \ C\: =\: lcm(A,B)\ \Rightarrow\ AT+BS\ =\ AB/C\ =\ gcd(A,B)$
For the second question: you may find useful the theory of Grobner bases over a $\rm\: PID$.
• Thanks, see my comment above to Gerry, I think it does have an easy answer. I've used Groebner bases before, but do you see a way to get that $t$ to pop out automatically using a Groebner base package? Dec 12 '10 at 9:15