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