# Show N has Prime Numbers

• C R P
In summary, the problem states that given a set of 2n consecutive integers, choosing a subset of n+1 positive integers will always result in at least one pair that are relatively prime. This is proven by the fact that for any given integer, its consecutive integer is always relatively prime, making it impossible to choose a subset without a pair that are relatively prime.
C R P
(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

Last edited by a moderator:
Hint: If m is a positive integer, then m and m+1 are relatively prime.

Petek said:
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?

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?

C R P said:
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.

## 1. What is the definition of a prime number?

A prime number is a positive integer that is only divisible by 1 and itself. In other words, it has no other factors except for 1 and itself.

## 2. How do I determine if a number is prime or not?

To determine if a number is prime, you can use a process called trial division. This involves dividing the number by every integer from 2 up to its square root. If the number is not divisible by any of these integers, then it is prime.

## 3. What is the significance of prime numbers in mathematics?

Prime numbers play a crucial role in number theory, which is the study of numbers and their properties. They are also used in cryptography, which is the process of encoding and decoding information, making prime numbers important for data security.

## 4. Can prime numbers be negative?

No, prime numbers are defined as positive integers. Negative numbers can be considered primes in different number systems, but in the traditional sense, prime numbers are only positive.

## 5. Are there an infinite amount of prime numbers?

Yes, there are an infinite amount of prime numbers. This has been proven by mathematicians and is known as Euclid's theorem. There is no largest prime number and they continue on infinitely.

Replies
1
Views
1K
Replies
1
Views
1K
Replies
24
Views
2K
Replies
4
Views
1K
Replies
3
Views
1K
Replies
7
Views
1K
Replies
23
Views
3K
Replies
6
Views
972
Replies
1
Views
262
Replies
2
Views
1K