0
$\begingroup$

You are given any $51$ integers taken from $1, 2, \ldots, 100$. Prove that there are two that are relatively prime.

$\endgroup$
  • 2
    $\begingroup$ Have you tried using standard techniques like the pigeonhole principal? $\endgroup$ – amarney Mar 27 '17 at 16:07
  • $\begingroup$ Hello and welcome to math.stackexchange. Please tell us what you have tried, where you are stuck, whether you have solve a similar problem before. $\endgroup$ – Hans Engler Mar 27 '17 at 16:12
  • $\begingroup$ @user5555: Such broad suggestions are never very helpful. Especially as the pigeonhole principle is not required here. $\endgroup$ – TonyK Mar 27 '17 at 16:13
  • $\begingroup$ Presumably you need the additional constraint that the integers are all distinct. $\endgroup$ – Bungo Mar 27 '17 at 16:25
  • 1
    $\begingroup$ @Bungo: That is implied by "You are given any $51$ integers." $\endgroup$ – TonyK Mar 27 '17 at 16:41
6
$\begingroup$

Hint: any two consecutive integers $n,n+1$ are relatively prime.

$\endgroup$
  • 1
    $\begingroup$ I would argue the next step uses the pigeonhole principle or something equivalent to it $\endgroup$ – Henry Mar 27 '17 at 16:21
1
$\begingroup$

Hint : Make pairs like (1,2) (3,4) (5,6)......(99,100), Now you have 50 such pairs. Use pigeonhole principle

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