Context: In a paper I'm reading the author indirectly asserts that if $ax + by \equiv 1 \pmod n$ has infinitely many solutions $(x,y)$ with $x$ and $y$ relatively prime (we are given that the congruence has at least one solution). I can see why if we had a relatively prime solution $(p,q)$, we would have infinitely many of them (take $(p, q + knp)$ for $k \in \mathbb Z$; the gcd of this pair does not depend on $k$). So the claim would be proven if I could also show that the existence of any solution $(p,q)$ implies the existence of a relatively prime one.
In the spirit of the relatively prime case above, I tried considering the set $(p – kb, q + ka)$ with $k \in \mathbb Z$, but I'm not sure how the gcd of the pair varies with $k$. The "obvious" try of dividing out the gcd of $(p,q)$ doesn't work either, because the congruence is not always satisfied.
Best Answer
If you don't mind using a sledgehammer you can argue as follows. Take any solution $(x_0,y_0)$. Certainly $\gcd(x_0,y_0,n)=1$. This means that $\gcd(x_0,g)=1$ where $g=\gcd(y_0,n)$. By Dirichlet's theorem on primes in arithmetic progressions, there are infinitely many integers $r$ with $y_0+rn=gp$ with $p$ prime. Take such an $r$ with $p\nmid x_0$. Then take $(x,y)=(x_0,y_0+rn)$.