11
$\begingroup$

I had been researching over the Extended Euclidean Algorithm when I happened to observe that the Bézout Coefficients were always relatively prime.

Let $a$ and $b$ be two integers and $d$ their GCD. Now, $d = ax + by$ where x and y are two integers.

$$d = ax + by \implies 1 = \frac{a}{d}x + \frac{b}{d}y$$ So, $x$ and $y$ can be expressed to form 1 so their GCD is 1 and are relatively prime. ($\frac{a}{d}$ and $\frac{b}{d}$ are integers.)

Another great thing is that $\frac{a}{d}$ and $\frac{b}{d}$ are also relatively prime. So you see this goes on like a sequence till $a$ and $b$ become one.

Am I right? What else can be known from this fact? Is it useful? Can it be used to prove some other things?

$\endgroup$
3
  • $\begingroup$ Yes , you are in right. You prove a theorem , and every theorem is useful ! $\endgroup$
    – user217174
    Feb 28, 2016 at 9:21
  • $\begingroup$ @Aboozar I am not able to find any practical use of the given result. $\endgroup$
    – TheRandomGuy
    Feb 28, 2016 at 9:23
  • $\begingroup$ A useful consequence of the fact that, if $a,b$ are not both zero, then $a/\gcd(a,b)$ and $b/\gcd(a,b)$ are relatively prime is the following. If $a, b$ are not both zero, and $a$ divides $b c$, then $a/\gcd(a, b)$ divides $c$. $\endgroup$
    – Andreas Caranti
    Feb 28, 2016 at 10:23

1 Answer 1

Reset to default
0
$\begingroup$

You are partially right.Not necessarily. Bezout's identity also mentioned, "more generally, the integers of the form $$ n=ax + by$$ are exactly the multiples of $d$."

This implies if $\gcd(x,y)=d'$, then $n$ is also a multiple of $d'$. Therefore, $$n=ax+by=\gcd(a,b)\gcd(x,y)n'$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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