Prove that for every natural numbers $a$ and $b$, there are infinitely many numbers $s$, such $\gcd(a+s,b+s)=1$ and $a\neq b$

I tried to use Bezout's theorem but I can't get to the result

  • $\begingroup$ no it isn t a fixed number we can change it , it depends to the value of and b $\endgroup$ – contestant IMO 2020 Sep 11 '18 at 12:28
  • $\begingroup$ @AbderrahmaneDriouch That is not what your question says. In your question, $s$ cannot depend on $a$ or $b$. $\endgroup$ – Batominovski Sep 11 '18 at 12:29
  • $\begingroup$ This question does not make sense, please edit for clarity. $\endgroup$ – lulu Sep 11 '18 at 12:30
  • 1
    $\begingroup$ Voting to close the question as it is unclear what you are asking. If you can, please edit your post for clarity. $\endgroup$ – lulu Sep 11 '18 at 12:33
  • 2
    $\begingroup$ I edited the question - is this what you wanted to ask? And don't demand solutions from people, no one here is obligated to solve YOUR problems for YOU. $\endgroup$ – asdf Sep 11 '18 at 12:33

As rightfully pointed out in the other answer, the statement trivially does not hold when $a = b$. Thus we must make the assumption that $a \neq b$. Then, my original answer holds:

Without loss of generality, $a > b$. A property of the greatest common divisor tells us that $$ \gcd(a + s, b + s) = \gcd((a + s) - (b + s), b + s) = \gcd(a - b, b + s). $$ Hence, if $p$ is any prime that does not divide $a - b$, we can choose $s = p - b$, and then $$ \gcd(a + s, b + s) = \gcd(a - b, p) = 1. $$ Since there are infinitely many primes, this shows that there are infinitely many such $s$.


As stated the claim is obviously false: $a$ and $b$ may be equal, in which case the GCD is $|a+s|$ (assuming you meant integer $s$, otherwise the problem doesn't make sense), and that is equal to $1$ for exactly two values of $s$.

So you must also have the assumption that $a \ne b$. Let's assume $a < b$.

There are infinitely many primes greater than $b$. For any such prime $p$, let $s = p - b$. Then $\gcd(a+s,b+s)=\gcd(a+p-b, p) = 1$, because $p$ is prime and $ 1 < a+p-b < p$

  • $\begingroup$ thanks......... $\endgroup$ – contestant IMO 2020 Sep 11 '18 at 13:28
  • $\begingroup$ Thank you for the correct addition; I hope you don't mind that I've edited it into my answer. $\endgroup$ – Mees de Vries Sep 11 '18 at 13:29
  • 1
    $\begingroup$ @MeesdeVries - Of course, especially since you also specifically referenced the other answer, you didn't simply change yours. That is the proper way to deal with such situations IMO. I wrote my answer and posted it without seeing yours. Then I saw yours and noticed it is very similar; but I left mine up, since I don't see the need to go through $a-b$. My thought was to go directly to $b+s$ being a prime, so the GCD should automatically be $1$, with essentially no other justification needed. $\endgroup$ – mathguy Sep 11 '18 at 13:34

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.