0

I was going through Bezout's identity and I had a question. Can we simplify $gcd(a*b,c+b*(d-e))$ using Bezout's identity? When I use the identity $gcd(a+m*b,b)=gcd(a,b)$ I am left with $gcd(a*b,c+b*(d-e))=gcd(a*b,c)$. Similarly, $gcd(a*b,c+b*(d+e))=gcd(a*b,c)$ i.e. both seem to be the same. But if I substitute with numbers to verify these identities, both give different answers i.e. $gcd(a*b,c+b*(d+e))\neq gcd(a*b,c+b*(d-e))$. Can someone please point out when I am going wrong?

Thanks

John Bull
  • 33
  • 1
    Can you please explain how you "used the identity... " to obtain $\gcd(ab, c+b(d-e))=\gcd(ab, c)$? I bet that, when you get to the bottom of how you used $\gcd(a+mb, b)=\gcd(a,b)$, you will realise your mistake. –  Jun 14 '23 at 21:03
  • One way of doing that is: (a) Rewrite the identity you want to use so that it doesn't use the same letters (e.g. $\gcd(x+my)=\gcd(x,y)$, and then (b) prescribe what you need to substitute for $x$ and $y$ to obtain what you've obtained. That is to avoid the possibility that you could mix up the letters. –  Jun 14 '23 at 21:06
  • 2
    Write the identity using a completely different set of variables, say $\gcd(x + zy, y) = \gcd(x, y)$ and then write down how you have identified the new variables $x$, $y$ and $z$ with the expressions in the formula you are trying to simplify. I think you will find that the identity doesn't actually apply. – Rob Arthan Jun 14 '23 at 21:06
  • @StinkingBishop: great minds type alike! $\ddot{\smile}$. – Rob Arthan Jun 14 '23 at 21:07
  • I see that I have $ab$ instead of simply $b$ and so that the identity won't work. Am I right? But in any case, is there a simplification? – John Bull Jun 14 '23 at 21:07
  • I don't think there is any useful simplification for your formula. – Rob Arthan Jun 14 '23 at 21:10
  • Not that I know of. Maybe there is in some special cases. Say, if $c=0$ this boils down to $\gcd(ab, b(d-e))=b\gcd(a, d-e)$. Are $a,b,c,d,e$ in your example numbers or expressions? - if the latter, there may be a simplification if we assume that additional information. Also, a "simplification" is in the eye of the beholder, something things need to get more complicated before they get simpler. If this is all part of a bigger problem you are working on (rather than just a question out of curiosity), maybe you could let us know what problem you are actually solving. –  Jun 14 '23 at 21:11
  • Well, I am trying understand the solutions of Pell's equations, and I came across this expression in a very old book. The $a,b,c,d,e$ are numbers and I was wondering since $gcd(ab,c+b(d−e))$ has a kind of common factor $'b'$ whether it is possible to eliminate it from one of either $ab$ or $c+b(d-e)$? Seems unfortunately it is not possible :-( – John Bull Jun 15 '23 at 07:01

0 Answers0