8
$\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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Yes , you are in right. You prove a theorem , and every theorem is useful ! $\endgroup$ – user217174 Feb 28 '16 at 9:21
  • $\begingroup$ @Aboozar I am not able to find any practical use of the given result. $\endgroup$ – TheRandomGuy Feb 28 '16 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 '16 at 10:23

Your Answer

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

Browse other questions tagged or ask your own question.