If $\gcd(a,b)=1$, $\gcd(a,y)=1$ and $\gcd(b,x)=1$ then prove that $ax+by$ is prime to $ab$

Question

If $\gcd(a,b)=1$, $\gcd(a,y)=1$ and $\gcd(b,x)=1$ then prove that $ax+by$ is prime to $ab$.

I tried assuming Diophantine Equations for all the relations and representing everything in terms of $a$, but that didn't lead me anywhere. There must be an intuitive and elegant approach right?

Answer 1

$$gcd(ax+by, ab) | gcd(ax+by, a) gcd(ax+by, b).$$ On the other hand, $$gcd(ax+by, a)=gcd(by, a) | gcd(b, a)gcd(y, a) = 1,$$ similarly $gcd(ax+by, b)|1$. Thus $$gcd(ax+by, ab) | 1, $$ which implies $$gcd(ax+by, ab) = 1.$$

Answer 2

Since $1=\gcd(a,b)=\gcd(a,y)$, we have $$1 = \gcd(a, by) = \gcd(a, ax+by); $$ by symmetry, we have $$1=\gcd(b, ax+by).$$ Together, these give you the desired result $$1=\gcd(ab,ax+by)$$

Answer 3

Here is a "MAD" solution :

Let $a,b,c$ three integers such that : $\gcd(a,b)=\gcd(a,y)=\gcd(b,x)=1$.

Using Bachet-Bézout's identity, there exists $u,v,w,z,t,s \in \mathbb{Z}$ such that :

$au+yv=1,\ bw+xz=1,\ at+bs=1$.

We have : $(au+yv)(bw+xz)(at+bs)=a^2tubw+a^2utzx+abtvyw+atvzxy+aub^2sw+auzxbs+vyb^2sw+vyzxbs=ax(autz+tvzy)+by(bvsw+vzxs)+ab(\overbrace{atuw+ubsw+ytvw+xuzs}^{=K\in\mathbb{Z}})=ax(tz\overbrace{(au+yv)}^{=1})+by(vs\overbrace{(bw+xz)}^{=1}) +abK=axtz+byvs+abK=1$.

So we deduce that $\gcd(ab,ax,by)=1$. Moreover, we know that $\gcd(ab,ax)\neq 1\neq \gcd(ab,by)$ so we can say that $\gcd(ax,by)=1$.

By properties of $\gcd$, if $\gcd(ax,by)=1$ then $\gcd(ax,ax+by)=1$ $\bigg($Indeed, let $d=\gcd(ax,ax+by)$, by hypothesis, we know that $1$ divides $ax$ and $by$ so by definition of divisibility $1$ divides the linear combination $ax+by$. So $1\mid d$ (by definition of $\gcd$). On the other hand, $d$ divides $ax$ and $ax+by$, so in particular $d$ divides the linear combination $ax+by-ax$, so $d$ divides $by$. By definition of $\gcd$ $d$ divides $1$. That's why $d=1$ $\bigg)$. And we also have $\gcd(by,ax+by)=1$.

By Bachet-Bézout's identity we have two new relations. Indeed, there exists $e,f,g,h, \in \mathbb{Z}$ such that:

$axe+(ax+by)f=1,\ byg+(ax+by)h=1$.

So by multiplying we have :

$1=(axtz+byvs+abK)(axe+(ax+by)f)(byg+(ax+by)h)=\big(a^2x^2etz+axbyevs+a^2bKxe+(ax+by)\overbrace{(faxtz+fbyvs+fabK)}^{=K_1\in\mathbb{Z}}\big)(byg+(ax+by)h)=\big(a^2x^2etz+axbyevs+a^2bKxe+(ax+by)K_1\big)(byg+(ax+by)h)=a^2x^2bygez+axb^2y^2gevs+a^2b^2yKgxe+(ax+by)\overbrace{\big(ha^2x^2xtz+haxbyevs+ha^2bKxe+h(ax+by)K_1+bygK_1 \big)}^{=K_2\in\mathbb{Z}}=ab\overbrace{(ax^2ygez+xby^2gevs+abyKgxe)}^{=K_3\in \mathbb{Z}}+(ax+by)K_2=abK_3+(ax+by)K_2$.

So finally, $\gcd(ax+by,ab)=1$.

Answer 4

Suppose a prime $p$ divides both $ax+by$ and $ab$. Then $p$ divides $a$ or $b$.

Assume $p$ divides $b$. Since $\gcd(a,b)=1$, we have that $p$ does not divide $a$.

As $p\mid(ax+by)$, we get $p\mid ax$. Since $p$ does not divide $a$, we have $p\mid x$, which is a contradiction to $\gcd(b,x)=1$.

Similarly, if $p$ divides $a$, we get a contradiction to $\gcd(a,y)=1$.

Therefore no prime divides both $ax+by$ and $ab$.

Answer 5

Extended hints/questions for you:

What could be a common prime divisor of $ab$ and $ax+by$?

Assume that $p$ is one.

1. It has to be a factor of either $a$ or $b$. Why?
2. If $p$ is factor of $a$ then it is a factor of both $ab$ and $ax$. Why?
3. So $p$ needs to be a factor of $by$ also. Why?
4. Why is that a contradiction?

Then do the same for the case that $p$ is a factor of $b$

Answer 6

Hints: suppose $\;d\;$ is a prime divisor (or $\;1$) of both $\;ab\,,\,\,ax+by\;$ :

$$\begin{cases}I&ab=md\\{}\\II&ax+by=nd\end{cases}\;\;\;\implies \text{if}\;\;d\mid b\;,\;\;\text{then by II also}\;\;d\mid ax$$

in which both cases we'd get $\;d=1\;$ since we're given $\;(a,b)=(bx)=1\;$ .

If $\;d\mid y\;$, then also $\;d\mid ax\implies d\mid x\;$ , since $\;(a,y)=1\;$ . But also $\;d\mid ab\implies d\mid a\;or\;d\mid b\;$ , and both lead us to $\;d=1\;$ .

Answer 7

By Euclid and $\,(\color{#c00}{a,b})=1$ we find $\ \ \begin{align} (ax+by,a) = (\color{#c00}by,\color{#c00}a) = (y,a) = 1\\ (ax+by,b) = (\color{#c00}ax,\color{#c00}b) = (x,b) = 1\end{align}$

Since $\,ax+by\,$ is coprime to $\,a,b\,$ it is coprime to their product, again by Euclid.

Remark $\ $ We used these basic Euclid gcd laws $\rm\,(a,b) = (a',\,b)\ \ if\ \ a\equiv a'\pmod{b}\ $ and $\rm\,(ad,b) = (d,b)\,\ $ if $\,\rm\ (d,b) = 1.\quad$