Register to reply

Show N has Prime Numbers

by C R P
Tags: college, loot, math, proof, relatively prime
Share this thread:
C R P
#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
Heat distributions help researchers to understand curved space
Professor quantifies how 'one thing leads to another'
Team announces construction of a formal computer-verified proof of the Kepler conjecture
Petek
#2
Jan8-13, 08:50 PM
Petek's Avatar
P: 361
Hint: If m is a positive integer, then m and m+1 are relatively prime.
C R P
#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
#4
Jan8-13, 10:11 PM
Homework
Sci Advisor
HW Helper
Thanks
P: 9,863
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
#5
Jan8-13, 10:19 PM
Sci Advisor
P: 834
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