1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ The first solution in the question you link to seems very clear and complete. What is it you don't understand? $\endgroup$ – lulu Apr 27 '17 at 17:32
  • $\begingroup$ @lulu Let's start with "since these two are consecutive odd numbers, thus they are coprime". $\endgroup$ – Hungry Blue Dev Apr 27 '17 at 17:34
  • 1
    $\begingroup$ "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. $\endgroup$ – JMoravitz Apr 27 '17 at 17:35
  • 1
    $\begingroup$ Ok...if $(m,m+2)$ are both odd then any common divisor would have to divide $2$, hence must equal $1$. $\endgroup$ – lulu Apr 27 '17 at 17:37
  • 1
    $\begingroup$ @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 $\endgroup$ – Hagen von Eitzen Apr 27 '17 at 17:37
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @Improve Oh shoot! Yes, you're right ... the question was different! $\endgroup$ – Bram28 Apr 27 '17 at 17:44
0
$\begingroup$

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.

$\endgroup$

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.