# proof - Bézout Coefficients are always relatively prime

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?

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

## 1 Answer

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'$$