# Proof that there are infinitely many $k$'s such that $a + k$ and $b + k$ are coprime

I need to show that for any $$a, b \in \mathbb{Z}^+$$ with $$a \neq b$$ there are infinitely many $$k \in \mathbb{Z}$$ such that $$a + k$$ and $$b + k$$ are relatively prime to each other.

I came up with a proof that uses the fact that there are infinitely many primes and that we can always choose $$k$$ such that $$a + k$$ is prime and therefor $$b + k$$ is relatively prime to $$a + k$$ (assuming that $$a > b$$).

But I was given the hint $$\gcd(x, y) = \gcd(x, y - zx)$$ which I don't use in the proof that I came up with. Hence my question is, if there is a way to show this fact by only using this hint and some other basic facts about the gcd.

Assume that $$a>b$$. There are infinitely many numbers $$m>a$$ such that $$\gcd(m,a-b)=1$$ (since $$a-b$$ only has finitely many prime factors). In other words, there are infinitely many $$k$$'s such that $$\gcd(a+k,a-b)=1$$. But$$\gcd(a+k,a-b)=\gcd\bigl(a+k,(a+k)-(b+k)\bigr)=\gcd(a+k,b+k).$$
• The reason there are infinitely many $m>a$ co-prime to $a-b$ is that $\{1+n|a-b|: n\in \Bbb N\}$ is infinite. – DanielWainfleet Jan 16 at 13:51