×

# Combinatorics #6

Suppose $$S=a_{1},a_{2},\cdots,a_{15}$$ is a set of $$15$$ distinct positive integers chosen from $$2,3,\cdots,2014$$ such that every two of them are coprime. Prove that $$S$$ contains a prime number. (Note: Two positive integers $$m,n$$ are coprime if their only common factor is $$1$$.

Note by Victor Loh
3 years, 5 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

Damn my first solution was lost in the preview...had to rewrite.

Note that two numbers are coprime if they have no alike prime factors. If we assume $$S$$ are all composite, then we can represent each $$a_i=p_i*q_i*k$$ where all $$p_i,q_i$$ are distinct primes and $$p_i\le q_i$$ Hence $$2014\ge a_i>p_i^2\Rightarrow p_i\le 43$$. Since $$43$$ is the 14th prime, but there are $$15$$ numbers, hence there must exists $$1\le r<s\le15$$ such that $$p_r=p_s$$ which is a contradiction.

- 3 years, 5 months ago

You forgot that $$p_i=q_i$$ is a possibility.

- 3 years, 5 months ago

I did specify that $$p_i\le q_i$$. Note that the intent for doing all this is to show that the smallest prime factor of each $$a_i$$ must be under $$43$$.

- 3 years, 5 months ago

You can simply use logic to solve this. Assuming $$S$$ has no primes, the maximum number of distinct numbers it can contain is $$14$$. Logically thinking, for $$S$$ to contain as many numbers of possible, we would square prime numbers, thus maximising the number of prime factors as the prime factors of a prime squared would be itself only. We are given that the 15th prime is $$47$$ and $$47 \times 47$$ gives us $$2209$$ which is bigger than $$2014$$.

(Sorry if some of my reasoning is unclear)

- 3 years, 5 months ago