Question: Let $a, b, c$ be three integers. Find all $x, y$ such that $ax+by=c$ and $\operatorname{gcd}(a, y) = \operatorname{gcd}(b, x) = 1$.
It is easy to see that if $\operatorname{gcd}(a, b) \not\mid c$, then this equation has no solutions. So suppose $\operatorname{gcd}(a, b) \mid c$. If we didn't require $a$ and $y$ (and $b$ and $x$) to be relatively prime, this question would be easy to solve. We just find one solution using the Euclidean division algorithm and then add the solutions of $ax+by=0$. However, this solution does not guarantee (obviously) that $a$ and $y$ are relatively prime. In fact, I believe it is possible to have no relatively prime solutions even if $\operatorname{gcd}(a, b) \mid c$.
One observation I made is this: Suppose $d$ divides $a$ and $c$. Then it divides $by$. Since $d$ divides $a$, it must be coprime to $y$, so $d$ divides $b$. Similarly, any divisor of $b$ and $c$ must also divide $a$. This implies that the pairwise $\operatorname{gcd}$s must be equal (i.e. $\operatorname{gcd}(a, b) = \operatorname{gcd}(a, c)=\operatorname{gcd}(b, c)$). However, I don't know if this is a sufficient assumption.
How can I decide when this equation has relatively prime solutions, and if it does, find all of them?
If $d=\gcd(a.c)$ then $d\mid by.$ But if $\gcd(a,y)=1$ then $\gcd(d,y)=1$ and thus you get $\gcd(a,c)\mid b.$
Likewise, you must have $\gcd(b,c)\mid a.$
This shows that we must have $$\gcd(a,b,c)=\gcd(a,b)=\gcd(a,c)=\gcd(b,c)$$ for there to be a solution.
We can reduced to the question:
Here, $a=DA, b=DB, c=DC,$ and $D=\gcd(a,b).$ This is equivalent because if $p\mid y$ and $p\mid A$ then $p\mid C,$ so $A,C$ are not releatively prime. So we know $\gcd(A,y)=1$ so $\gcd(a,y)=\gcd(AD,y)=\gcd(D,y),$ and all we need is $\gcd(D,y)=1$ and likewise, $\gcd(D,x)=1.$
For example when $A=12,B=5,C=7,D=180,$ then we are seeking $t$ such that $(1+5t,180)=1$ and $(-1-12t,180)=1.$ But this is equivalent to $(1+5t,6)=1$ and $(1+12t,5)=1.$. So you can have $t\equiv 0,2\pmod{6}$ and $t\not\equiv 2\pmod 5.$ So a Chinese Remainder Theorem application should give $8$ possibilities, modulo $30.$ You get numbers $t$ of the form $6s+12$ and $6s+2$ when $s$ is not divisible by $5,$ or $t\equiv 0,6,8,10,14,18,20,24\pmod {30}.$
That case is relatively easy because $D_A=5$ and $D_B=6$ are relatively prime. But in quite a few small cases, we will even get $D_A=D_B=D.$ Then it isn't so much a Chinese Remainder Theorem question as an question of coincidence of the two solution sets, modulo $D.$
For example, if $A.B,C$ are all odd, then one of $x,y$ must be even, so it isn't possible to find a solution when $D$ is even.
If $p$ is a prime factor of $D$ but not $A$ or $B,$ then $x_0+Bt\not\equiv 0\pmod. p$ and $y_0-At\not\equiv 0\pmod p$ excludes either $1$ or $2$ if $p\mid Ax_0+ By_0=C$ or not, respectively.
If $p$ divides $D$ and $A,$ but not $B,$ then since $(y_0,A)=1,$ we get that $y_0$ is a unit modulo $p.$ So we get $p-1$ possible values of $t$ modulo $p.$
Likewise if $p\mid D$ and $p\mid B.$
It is not possible for $p\mid A$ and $p\mid B,$ so this is all the relevant cases.
So if $D$ has $p_1,p_2,\dots,p_n$ as distinct prime factors, the number of possible $t\pmod{p_1\dots p_n}$ is:
$$(p_1-a_1)(p_2-a_2)\cdots(p_n-a_n)$$ where $$a_i=\begin{cases}2&p_i\not\mid ABC\\1&\text{otherwise} \end{cases}$$
This covers the case when $A,B,C$ odd and $D$ even, because then $p=2$ gives $a=2,$ and a value of $0.$
This shows that if all the prime factors of $D$ are factors of $ABC,$ then the number of values modulo $D$ is $\phi(D).$
If $D_1=p_1\cdots p_n,$ and $D_2=D_1/\gcd(D_1,ABC),$ then we can see the number of values for $t$ modulo $D_1$ is:
$$\sum_{d\mid D_2}\mu(d)\phi(D_1/d)$$
This formula also show that, except when $A,B,C$ are odd and $D$ is even, there is always a solution.
The density of the the values $t$ is $$(1-a_1/p_1)(1-a_2/p_2)\cdots(1-a_n/p_n).$$
Another example, $A=7,B=8,C=3, D=30.$ We start with $x_0=-3,y_0=3.$ The we are seeking $t$ such that $-3+8t$ and $3-7t$ are both relatively prime to $30.$ Modulo $2$, we have $t\equiv 0\pmod 2.$ Modulo $3,$ we have $t\equiv 1,2\pmod 3.$ Finally $t\equiv 0,2,3\pmod 5.$ So we get $t\equiv 2,8,10,20,22,28\pmod{30}.$ That's $(2-1)(3-1)(5-2)$ solutions for $t$ modulo $30,$ since $2,3\mid ABC$ and $5\not\mid ABC.$
Not sure the fastest way to solve this. Certainly, you can do it by factoring $D$ into primes and solving the remainder theorem problems. but there may be a faster.