0
$\begingroup$

I have the following equation, where I know all of the variables are integers:

$a - b = c*d - e*f$

Can I use Bezout's Identity on the right hand side or is that only permitted when the terms are being added?

Would it give?:

$a - b = gcd(c, -e) * k$

$a - b = gcd(c, e) * k$

(The $k$ is to indicate that Bezout's identity says the result is a multiple of the $gcd$ rather than the $gcd$ exactly)

That is, can I move the negative into the gcd arguments, and then since gcd is the same regardless of the signs of its parameters, get rid of the negative? If so, why is is this all safe? My intuition is that it should work but I'm having trouble justifying it to myself.

Normally I would just say that it's just equivalent to adding a negative number so the identity must apply, but I want to use the Extended Euclidean Algorithim to compute $d$ and $f$ when $a, b, c, e$ are known, and I'm unsure what effect it will have on the algorithm if I plug in $-e$ instead of just $e$ (or I should be plugging in $e$ and taking the negative of the result instead?).

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

To solve $a - b = cd - ef$ put $x = a-b$ and $y = -e$ then solve $cd + yf = x$ using the usual method and then reverse the substitutions to get the answer.

Further, is general $\gcd(x,y) = \gcd(x,-y)$ because $y$ has been multiplied by $-1$ a unit (invertible element).

$\endgroup$
5
  • $\begingroup$ Substitution does make things more clear but doesn't seem to get me all the way there. I can write $ax_1 + by_1 = gcd(a, b) * k_1$, and I can say $c = -b$ and use substitution to get $ax_2 + cy_2 = gcd(a, c) * k_2$, then plug $-b$ back in for $c$ and get $ax_2 - by_2 = gcd(a, -b) * k_2 = gcd(a, b) * k_2$, but it's unclear what the relationship between $x_1, y_1, k_1$ and $x_2, y_2, k_2$ are. $x_2$ and $y_2$ correspond to the $d$ and $f$ in the original example and are the numbers I actually want, but the identity/algo only let me compute $x_1$ and $y_1$, and I don't see how to substitute back. $\endgroup$
    – Joseph Garvin
    Commented Nov 10, 2012 at 23:09
  • $\begingroup$ Added a note about $k$, in the main question so you could better see what I mean. $\endgroup$
    – Joseph Garvin
    Commented Nov 10, 2012 at 23:24
  • $\begingroup$ I guess the question here is whether $gcd(a, b)$ and $gcd(a, -b)$ produce the same bezout coefficients, and thus the same $x, y, k$. Although if it did that would seem to imply that when $ax + by = gcd(a, b)*k$ is true that $ax - by = gcd(a, b) * k$ is also true, which would mean you could toggle the +/- sign in Bezout's identity, which doesn't seem right. $\endgroup$
    – Joseph Garvin
    Commented Nov 11, 2012 at 0:00
  • $\begingroup$ @JosephGarvin, to substitute back you just use $e = -y$. $\endgroup$
    – sperners lemma
    Commented Nov 11, 2012 at 8:33
  • $\begingroup$ This is what I was confused about, looks safe: math.stackexchange.com/questions/37806/… $\endgroup$
    – Joseph Garvin
    Commented Nov 11, 2012 at 17:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .