Prove that among any five consecutive positive integers there is one integer which is relatively prime to the other four integers.

Two integers are called relatively prime if the greatest common divisor of $m$ and $n$ is $1$. Prove that among any five consecutive positive integers there is one integer which is relatively prime to the other four integers. (Hint: For any two positive integers $m < n$, any common divisor has to be less than or equal to $n - m$).

The question has already been asked before here, but I do not understand the steps. Is there a simpler approach? Or can anyone explain any of the answers provided in the linked question in details?

The problem is I'm not comfortable with Pigeon-hole principle or GCD (and divisibility) or modular arithmetic. Assume I do not know any of these.

• The first solution in the question you link to seems very clear and complete. What is it you don't understand?
– lulu
Apr 27, 2017 at 17:32
• @lulu Let's start with "since these two are consecutive odd numbers, thus they are coprime". Apr 27, 2017 at 17:34
• "Assume I do not know any of these"... considering that being relatively prime is defined using GCD's... I would think you are out of luck if you want to avoid using GCD's entirely. It shouldn't take much time to familiarize yourself with those topics and return to this question later. Apr 27, 2017 at 17:35
• Ok...if $(m,m+2)$ are both odd then any common divisor would have to divide $2$, hence must equal $1$.
– lulu
Apr 27, 2017 at 17:37
• @Astrobleme Any common divisor of two numbers is also a divisor of their difference. Hence if the difference is $2$, the only possible common divisors are $1$ and $2$. But $2$ is ruled out for odd numbers Apr 27, 2017 at 17:37

Call the middle number $n$.

Now, if $n$ is odd, then $n$ is co-prime with $n-1$ and $n+1$ since the difference is only $1$. But $n$ is coprime with $n-2$ and $n+2$ as well, since all of them being odd means they don't have a common prime factor of $2$, and since the difference between $n$ and the other two is only $2$, there cannot be any other common prime factor.

If $n$ is even, then $n-1$ or $n+1$ are both odd, and at least one of them is not divisible by $3$, since with a difference of $2$, they can't both be divisible by $3$. So the one that is not divisible by $3$ has no prime factors smaller or equal to $3$, and since the difference with all the others is at most $3$, that one shares no common prime factors with any of the others, and is therefore coprime with all the others. So: if $n$ is even then either $n-1$ or $n+1$ (or both) are coprime with all the others.

• @Improve Oh shoot! Yes, you're right ... the question was different! Apr 27, 2017 at 17:44

If two number differ by $1$, they are relatively prime. If they differ by $2$, their greatest common divisor is either $1$ or $2$. And if they differ by $3$, their greatest common divisor is either $1$ or $3$. Therefore, given five consecutive numbers:

If the middle number is odd, then it is relatively prime to the two adjacent numbers on each side of it.

If the middle number is even, then at least one of the two odd numbers adjacent to it is not divisible by $3$. That odd number (or either of them, if neither is divisible by $3$) is relatively prime to the other four numbers.

Let the numbers be $$n-2, n-1, n, n+1, n+2$$

Case I: $n$ is odd , then $n$ is prime to all the $4$ other integers, as is easy to see.

Case II, $n-1$ and $n+1$ are odd. $n-1$ is prime to all except maybe $n+2$, both of which may be divisible by $3$. Similarly $n+1$ is prime to the others except maybe $n-2$, both of which may be divisible by $3$. However not all of these numbers can be divisible by $3$ so one of $n-1$ or $n+1$ will satisfy the requirements.