Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?).

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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).

share|improve this answer
    
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. –  Joseph Garvin Nov 10 '12 at 23:09
    
Added a note about $k$, in the main question so you could better see what I mean. –  Joseph Garvin Nov 10 '12 at 23:24
    
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. –  Joseph Garvin Nov 11 '12 at 0:00
    
@JosephGarvin, to substitute back you just use $e = -y$. –  sperners lemma Nov 11 '12 at 8:33
    
This is what I was confused about, looks safe: math.stackexchange.com/questions/37806/… –  Joseph Garvin Nov 11 '12 at 17:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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