The question is if given two integers a and b, if I find a pair of integers $x$ and $y$ so $ax + by = 1$, is it always true that $gcd(a,b) = 1$?
This comes from a problem in which I had to prove that the system
$x \equiv 1 \quad (mod N)$
$x\equiv 2 \quad (mod N^2-1)$
has a solution without solving it. I tried to solve it by proving that $N$ and $N^2-1$ are coprimes and I got that $N*k -(N^2+1)*q = 1$ for some integers $k,q$
Thank you for reading.
If $ax+by=d$ then $\gcd(x,y)$ divides $d$. In this case, $d=1$, which forces $\gcd(x,y)=1$.