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).$$

  • $\begingroup$ 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. $\endgroup$ – DanielWainfleet Jan 16 at 13:51
  • $\begingroup$ @DanielWainfleet That's another reason, although I must say that I find that justification better than mine. $\endgroup$ – José Carlos Santos Jan 16 at 13:53
  • $\begingroup$ The only reason I mentioned it is that the proposer wanted to see it done without using the fact that there are infinitely many primes....+1 $\endgroup$ – DanielWainfleet Jan 16 at 21:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.