If $n\ge1$ is an integer, show that among $n,n+1,n+2$ and $n+3$, there is one which is coprime to the other three.

Question

If $n\ge1$ is an integer, show that among $n,n+1,n+2$ and $n+3$, there is one which is coprime to the other three.

Obvious facts : a. Consecutive numbers are coprime, b. There are two numbers among these four that leave the same remainder when divided by $3$, c. One of these four numbers has to be a multiple of four.

But these are not enough to solve the problem. Please help.

Answer 1

Bear in mind $\gcd(m, m+2) = \gcd(m,2)$ so $m$ and $m+2$ are coprime if and only if $m$ is odd.

Now if $m$ is even then $m\pm 1$ will be odd.

And, as you pointed out $m$ is coprime to $m\pm 1$.

So consider a nice term near the middle: $n+1$ or $n+2$.

If $n+1$ is odd then $n+1$ is coprime to $n+3$ as well as to $n$ and $n+2$.

But if $n+1$ is even then $n+2$ is odd. And then $n+2$ is coprime to $n$ as well as to $n+1$ and $n+3$.

So either $n+1$ or $n+2$ will be coprime to all terms depending upon which of them s odd.

For the sake of thoroughness. If $3\not \mid n$ and $n$ is odd then $n$ is coprime to $n+1, n+2, n+3$. And if $3\not \mid n$ and $n$ is even then $n+3$ is coprime to $n, n+1, n+2$.

Answer 2

Your a., coupled with

• either $n$ is coprime to $n+2$, or $n+1$ is coprime to $n+3$

is enough to solve your problem.

Answer 3

One of $n+1$, $n+2$ is odd and therefore is co-prime to the integer two steps away.

---

By the way, the claim still holds for five consecutive integers $n,n+1,n+2,n+3,n+4$: If $n+2$ is odd, it is co-prime to the other numbers at distance $\le 2$. If $n+2$ is even, then one of the odd numbers $n+1$, $n+3$ is not a multiple of $3$ and co-Prime to all integers at distance $\le 3$.

Answer 4

Whichever of the middle two is odd is coprime to the others. It doesn't share a factor of 2 with any of them, and it cannot share a factor greater than 2 because its distances to them are at most 2.

Answer 5

Since $\gcd(a,b)|a-b$, the only prime factors any $2$ of these values can share are $2$ and $3$. Thus, it suffices to show one of these integers is divisible by neither. If $n$ is divisible by $3$, so is $n+3$, but either $n+1$ or $n+2$ must be odd and therefore coprime with the other $3$. If $n$ is not divisible by $3$, then only one number is divisible by $3$ and the $3$ values that aren't can't all possibly be even.

This raises a more interesting question as to how many consecutive numbers need to be chosen such that no one number is coprime to the rest. Six isn't enough. If the smallest number is not divisible by $5$, no $2$ of the numbers share a factor of $5$. If it is, you still have $4$ consecutive values that aren't. Either way, if $n$ is still the smallest, one of $n+1,n+2,n+3,$ and $n+4$ would necessarily be divisible by neither $2$ nor $3$ by the arguments above and therefore coprime to the rest.