For $a,b,m,n \in \mathbb{Z}^+$, does there always exist $x,y \in \mathbb{Z}^+$ with ${\rm gcd}(x,y) = 1$ but ${\rm gcd}(ax+m,by+n) > 1$?

Question

Given $a,b,m,n \in \mathbb{Z}^+$, is it possible to always find a relatively prime pair of positive integers $x,y$ so that $ax+m$ and $by+n$ are not relatively prime?

Answer 1

Yes, we can. Suppose $p$ is a prime number and not a divisor of any number in the problem. There exists an integer $x$ such that $p\mid ax+m$. Furthermore, there exists an integer $z$ such that $p\mid b(xz+1)+n$. Let $y=xz+1$.

To be precise, we are using Bezout's Theorem. 1) Because $gcd(a, p)=1$, there exists integers $x$ and $w$ such that $$ax+pw=-m,$$ which implies $p|ax+m$.

2) Note that $gcd(p, bx)=1$, there exists integers $z$ and $u$ such that $$(bx)z+pu = -(b + n),$$ which implies $p\mid b(xz+1)+ n$