Finding relatively prime integers with specified remainders $\pmod{m}$.

Question

Let $m$ be a positive integer. Let $a,b$ be integers with $0 \leq a,b < m$, $a,b$ not both zero, $\gcd(a,b,m)=1$.

Do there necessarily exist integers $x,y$ such that
$x \equiv a \pmod{m}$
$y \equiv b \pmod{m}$
$(x,y)=1$?

Equivalently, are there integers $c,d,k,l$ such that $$ c(a+mk) + d(b+ml)=1? $$

EDIT: Consider two refinements.
1. What conditions on $a,b$ are necessary?
2. What if $m$ is prime?

Answer 1

Let $t$ be the product of all the primes dividing $b$ but not $a$ (if there are no such primes then $t$ is the empty product which, by convention, is $1$). Let $x=a+tm$, $y=b$. Then clearly $x\equiv a\pmod m$, and $y\equiv b\pmod m$, so we just have to check that $\gcd(x,y)=1$.

Let $p$ divide $y$. If $p$ also divides $a$, then it doesn't divide $t$, by the construction of $t$, and it doesn't divide $m$, since $\gcd(a,b,m)=1$, so it doesn't divide $tm$, so it doesn't divide $x=a+tm$. If $p$ doesn't divide $a$, then it does divide $t$ (by construction of $t$), so it divides $tm$, so again it doesn't divide $x=a+tm$. So no prime dividing $y$ divides $x$, so $\gcd(x,y)=1$.

Historical note: Andrzej Schinzel showed me this idea in 1976.

Answer 2

Suppose that $a$ and $m$ are relatively prime, and also $b$ and $m$. (This is a more stringent condition than what you want.)

By Dirichlet's Theorem on primes in arithmetic progressions, there are infinitely many primes of the form $a+sm$, also infinitely many primes of the form $b+tm$. So in fact there are distinct primes $x$ and $y$ that satisfy your conditions.

Undoubtedly gross overkill! But at least we get the strong answer that in this case we can make $x$ and $y$ prime.

More or less the same argument holds if at least one of $a$ and $b$ is relatively prime to $m$, say $b$. There are infinitely many primes of the form $b+tm$, so pick $x=a$, and $y$ any prime of the right shape that does not divide $a$.