Common Divisor Question

  • Thread starter rbzima
  • Start date
  • #1
84
0

Homework Statement



We select n + 1 different integers from the set {1,2,...,2n}. Prove that there will always be two among the selected integers whose largest common divisor is 1.

Homework Equations



None

The Attempt at a Solution



I was thinking that this problem has something to do with the pigeonhole principle, however I'm pretty stuck here and don't even know where to get started...
 

Answers and Replies

  • #2
354
0
You're correct that it uses the pigeonhole principle.

What are the possible gcd's for an arbitrary pair of integers from the set {1,2,...,2n}?
 
  • #3
84
0
Figured it out... Thanks for the help...

Essentially, gcd(k, k+1) is a good candidate! =)
 
  • #4
354
0
Exactly!
 

Related Threads on Common Divisor Question

  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
24
Views
3K
  • Last Post
Replies
2
Views
884
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
19
Views
5K
Replies
11
Views
4K
Replies
0
Views
1K
  • Last Post
Replies
8
Views
1K
Top