GCD of Linear Combinations

The proposition is TRUE .

To establish the equality $gcd(x,y)=gcd(X,Y)$ , we'll show:

For any positive integer $d$ , $d \mid x$ and $d \mid y \iff$ $d \mid X$ and $d \mid Y$ . In other words, if $d$ is a common divisor of $x$ and $y$ , then it's also a common divisor of $X$ and $Y$ ; and if $d$ is a common divisor of $X$ and $Y$ , then it's also a common divisor of $x$ and $y$ .

---

Proof of If $d$ is a common divisor of $x$ and $y$ , then it's also a common divisor of $X$ and $Y$ .

We have, $d \mid x$ . Then $d \mid ax$ and $d \mid a^\prime x$ , for any integers $a$ and $a^\prime$ .

We also have, $d \mid y$ . Then $d \mid by$ and $d \mid b^\prime y$ , for any integers $b$ and $b^\prime$ .

So, $d \mid ax+by=X$ and $d \mid a^\prime x + b^\prime y=Y$ , as required.

---

Proof of If $d$ is a common divisor of $X$ and $Y$ , then it's also a common divisor of $x$ and $y$ .

$d \mid X=ax+by$ and $d | Y=a^\prime x+ b^\prime y$ .

But $d \mid ax+by \implies d\mid b^\prime(ax+by)=ab^\prime x+bb^\prime y$ .

And $d \mid a^\prime x+b^\prime y \implies d\mid b(a^\prime x+b^\prime y)=a^\prime bx+bb^\prime y$ .

Now, $d\mid ab^\prime x+bb^\prime y$ and $d\mid a^\prime bx+bb^\prime y \implies d \mid (ab^\prime x+bb^\prime y)-(a^\prime bx+bb^\prime y)=(ab^\prime-a^\prime b)x=x$ [As $ab^\prime - a^\prime b=1$ ].

So, $d \mid x$ . Similarly, $d \mid y$ . $\square$