
#1
Jan813, 07:49 PM

P: 5

(For the following problem I don't just want a flat out answer, but steps and Ideas on how to solve it. The problem was given by my Universities newspaper and for solving it you get free Loot and stuff) The Problem: Show that every set of n+1 positive integers, chosen from a set of 2n consecutive integers, contains at least one pair of relatively prime numbers. relatively prime means: "Two integers are relatively prime if they share no common positive factors (divisors) except 1" Example: 8 and 15 are relatively prime. 8 = 2 * 2 * 2 15 = 3 * 5 Example: 9 and 12 are NOT relatively prime 9 = 3 * 3 12 = 2 * 2 * 3  My thinking thus far: None really I've just started 



#3
Jan813, 09:25 PM

P: 5

"Show that every set of n+1 positive integers, chosen from a set of 2n consecutive integers" wouldn't this mean the set would be... n= 0 1 2 3 4 Set=0,2,6,8 then you would do the n+1 one on that set? Or something to that extent? 



#4
Jan813, 10:11 PM

Homework
Sci Advisor
HW Helper
Thanks ∞
P: 9,172

Show N has Prime Numbers
Petek's hint is right. If you wanted to choose a subset without picking any pair that's relatively prime, what does that tell you about the option of picking consecutive numbers from the set?




#5
Jan813, 10:19 PM

Sci Advisor
P: 778

The point of the problem is that no matter what you do, your subset always contains a pair which are relatively prime. 


Register to reply 
Related Discussions  
Show that m and n relatively prime if and only if no prime divides both  Calculus & Beyond Homework  8  
Kth Prime Proofs & CoPrime Numbers  Linear & Abstract Algebra  4  
a prime number which equals prime numbers  General Math  10  
A formula of prime numbers for interval (q; (q+1)^2), where q is prime number.  Linear & Abstract Algebra  0  
Prime Numbers in the Diophantine equation q=(n^2+1)/p and p is Prime  Linear & Abstract Algebra  5 