# 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." –  Gerry Myerson 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. –  darij grinberg Dec 11 '10 at 22:58
Replace "every ring" by "every Noetherian ring". –  darij grinberg 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) –  Aaron Meyerowitz 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? –  Aaron Meyerowitz 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? –  Aaron Meyerowitz Dec 12 '10 at 9:15