# elementary number theory – Finding \$(a,b)\$ in some given subset of \$mathbb{Z}^2\$ with a specific gcd.

Given the subset of $$mathbb{Z}timesmathbb{Z}supset S={(9(k+3),4k), kin mathbb{Z}}$$ I’m trying to find $$(x,y)in S$$ such that $$mathrm{gcd(x,y)}=18$$. The set $$S$$ arises as the set of solutions to the equation $$4x-9y=108,; x,yinmathbb{Z}$$. The equation isn’t particularly hard to solve, but I can’t quite figure out how to go about finding the couples $$(x,y)$$ with gcd 18.

Playing around a little I found that since I want $$18$$ to be the gcd of $$9(k+3)$$ and $$4k$$, 18 has to divide both, which implies $$k$$ is an odd number and $$2k=9q$$ with $$qinmathbb{Z}$$ but this still allows for the possibility of $$mathrm{gcd}(x,y)>18$$, that is, those are necessary condition but certainly not sufficient. And I’m not entirely sure where to go from there. This feels like it’s very easy and I’m just not seeing something obvious. Anyway, if anyone has a suggestion, a hint or something, I’d appreciate, thanks.

Posted on Categories Articles