$\gcd(a,b) =ax\!+\!by\Rightarrow \gcd(x,y)\!=\!1;\ $ $\gcd(a,b)\gcd(x,y)\mid ax\!+\!by$

Question

Suppose $a$ and $b$ are positive integers, and that $d=\gcd(a,b)$. Suppose we have found integers $x$ and $y$ such that $ax+by=d$. Prove that $x$ and $y$ are relatively prime.

Answer 1

If $k|x,y$, then $k|ax+by=d$, so we can write $d = kd' = ax'k + by'k$; hence $d'=ax'+by'$. Since $\gcd(a,b)|ax'+by' = d'$, then $d|d'$. Since $d'|d$, then $|d|=|d'|$.

Answer 2

Although you don't have to use proof by contradiction, it would be my first try.

Assume that $x$ and $y$ are not relatively prime. What does that mean? It means they have a common divisor larger than 1. So give that divisor a name, do some algebra, and see if you can reach a contradiction.

Post in the comments if you have problems.

Answer 3

Hint $\rm\ \,(x,y)\:\!\color{#c00}{(a,b)}\mid\overbrace{a\ x + b\ y}^{\large \color{#c00}{(a,b)}}\ \Rightarrow\ (x,y)\ |\ 1\ \:$ by cancelling $\rm\,\color{#c00}{(a,b)}\neq 0. \ \ \small\bf QED$

We used $\rm\ (a,b)\ |\ a, \ (x,y)\ |\ x\ \Rightarrow \ (a,b)\:(x,y)\ |\ \color{#0a0}{ax},\,$ by the Divisibility Product Rule.
In a similar way we infer also that $\ \rm (a,b)\,(x,y)\mid \color{#0aff}{by},\, $ so $\rm\,(a,b)(x,y)\mid \color{#0a0}{ax}+\color{#0af}{by}$.

Answer 4

Since, $d = (a, b)$ Let $a = dk_1, b = dk_2$ $\therefore ax + by = d \\ \Rightarrow dk_1x + dk_2y = d \\ \Rightarrow k_1x + k_2y = 1$

By Bezout's Theorem, x and y are relatively prime.