Show N has Prime Numbers


by C R P
Tags: college, loot, math, proof, relatively prime
C R P
C R P is offline
#1
Jan8-13, 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
Phys.Org News Partner Mathematics news on Phys.org
Researchers help Boston Marathon organizers plan for 2014 race
'Math detective' analyzes odds for suspicious lottery wins
Pseudo-mathematics and financial charlatanism
Petek
Petek is offline
#2
Jan8-13, 08:50 PM
Petek's Avatar
P: 360
Hint: If m is a positive integer, then m and m+1 are relatively prime.
C R P
C R P is offline
#3
Jan8-13, 09:25 PM
P: 5
Quote Quote by Petek View Post
Hint: If m is a positive integer, then m and m+1 are relatively prime.
very true, but I think the problem is more difficult than this.

"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?

haruspex
haruspex is offline
#4
Jan8-13, 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?
pwsnafu
pwsnafu is offline
#5
Jan8-13, 10:19 PM
Sci Advisor
P: 778
Quote Quote by C R P View Post
very true, but I think the problem is more difficult than this.

"Show that every set of n+1 positive integers, chosen from a set of 2n consecutive integers"
The statement means: I give you a set S = {a, a+1, a+2, ..., a+2n-1} and you pick a subset with n+1 elements.

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
K-th Prime Proofs & Co-Prime 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