Can it proved that the GCD does not divide the integer coefficients in the linear form of the GCD?

Question

Let $d = (a,b)$ then $d = ax +by$ for some $x,y \in \mathbb{Z}$

I want to prove that $d \nmid x,y$.

Motivation I'm trying to solve the following problem:

If $a$ is prime to $b$ and $y$, $b$ is prime to $x$, then prove that $ax+ by$ is prime to $ab$.

My solution goes like this:

Let $(ax + by, ab) = d > 1$, then $d = z_1 (ax + by) + z_2(ab)$ for some $z_1,z_2 \in \mathbb{Z}$

Rearranging we get $d = a(z_1x + z_2b) + b(z_2a + z_1y)$

Then if we divide by $d$ that means that the RHS must be equal to $1$. In other words $d$ must divide the RHS. We see that $d \nmid a,b,x,y$ since that would imply that they have a common factor $> 1$. That means that $d \mid z_1, z_2$. However if $d \nmid x,y$, I am done with the proof, since the only value $d$ can take is $1$.

I appreciate any help.

Answer 1

$(a,\,ax+by) = (a,by) = 1\ $ since $\,a\,$ is coprime to $\,b,y$

$(b,\,ax+by) = (b,ax) = 1\ $ since $\,b\,$ is coprime to $\,a,x$

Since $\,a,b\,$ are coprime to $\,ax+by\,$ so too is their product.

Answer 2

Here is another solution. Suppose $p$ is a common prime factor of $ax+by$ and $ab$.

• If $p$ divides $a$, then it must divide $by = (ax+by) - ax$. Hence it divides one of $b$ or $y$. But it also divides $a$, so it's a common prime factor of $a$ and either $b$ or $y$, which is impossible since we assumed $(a,b) = (a,y) = 1$.
• If $p$ does not divide $a$, it has to divide $b$. Thus it divides $ax = (ax+by) - by$. Since $(a,p) = 1$, $p$ has to divides $x$. But now $p$ is a common prime factor of $b$ and $x$, a contradiction since we assumed $(b,x) = 1$.

Both cases lead to a contradiction, so $ax+by$ and $ab$ have no common prime factors, i.e. they are coprime.