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?).
Answer
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).
No comments:
Post a Comment