Kvant Math Problem 557
Suppose, contrary to the statement, that none of the given numbers is prime.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m02s
Source on kvant.digital
Problem
Given $n$ pairwise relatively prime numbers, greater than $1$ and less than $(2n-1)^2$. Prove that at least one of them must be a prime number.
A. T. Kolotov
Exploration
Suppose, contrary to the statement, that none of the given numbers is prime. Then every number is composite.
Since the numbers are pairwise relatively prime, no prime divisor can occur in two different numbers. Thus each composite number contributes at least two distinct prime divisors to the collection of all prime divisors of the given numbers.
For small values this already suggests a contradiction. If $n=2$, the numbers are less than $9$. The only composite numbers greater than $1$ are $4,6,8$. No two of them are relatively prime, so a prime is unavoidable. For $n=3$, the numbers are less than $25$. Three pairwise coprime composites would require at least six distinct primes. The six smallest primes are
$$2,3,5,7,11,13.$$
Their product is already very large, suggesting that the upper bound $(2n-1)^2=25$ may be too small to accommodate three composite numbers built from six distinct primes.
The natural idea is to count prime divisors. If all $n$ numbers are composite and pairwise coprime, there are at least $2n$ distinct primes among their factorizations. The smallest possible set of $2n$ distinct primes is
$$2,3,5,\dots,p_{2n}.$$
The crucial point is to show that the $2n$-th prime satisfies
$$p_{2n}\ge 2n+1.$$
Then among the $2n$ distinct primes occurring in the factorizations, one must be at least $2n+1$.
Any composite number containing such a prime factor must be at least
$$2(2n+1)=(2n+1)+(2n+1)> (2n-1)^2$$
for small $n$? This is false for large $n$, so this line does not work.
A better observation is that if there are at least $2n$ distinct prime divisors, then the largest of them is at least the $2n$-th prime. Since $p_{2n}>2n-1$, any composite number containing that prime must be at least
$$2p_{2n}>2(2n-1).$$
This alone is still insufficient.
Instead, one should use the fact that every composite number less than $(2n-1)^2$ has all its prime divisors less than $2n-1$. Indeed, if a composite number $m<(2n-1)^2$ had a prime divisor $q\ge 2n-1$, then
$$m\ge q^2\ge (2n-1)^2,$$
a contradiction. Hence all prime divisors of the given composite numbers are primes strictly less than $2n-1$.
There are only $n-1$ odd numbers among
$$3,5,\dots,2n-3,$$
and together with $2$ this gives at most $n$ primes less than $2n-1$. To make this rigorous one needs only the elementary estimate that the number of primes less than $2n-1$ is at most $n$.
But $n$ composite pairwise coprime numbers require at least $2n$ distinct prime divisors. This contradiction completes the argument.
The step most likely to hide an error is the claim that every prime divisor of the composite numbers is less than $2n-1$; it must be justified carefully using the compositeness of the number.
Problem Understanding
We are given $n$ integers, each greater than $1$, each less than $(2n-1)^2$, and any two of them are relatively prime. We must prove that at least one of these integers is prime.
This is a Type B problem. The statement is already specified, so the task is to prove it.
The core difficulty is to combine the pairwise coprimality condition with the size bound. Pairwise coprimality forces distinct prime factors to appear in different numbers, while the upper bound restricts how many different primes can occur.
Proof Architecture
Assume all given numbers are composite and derive a contradiction.
Lemma 1. Every prime divisor of any given number is less than $2n-1$. Sketch: if a composite number less than $(2n-1)^2$ had a prime divisor at least $2n-1$, the number would be at least the square of that prime divisor.
Lemma 2. There are at most $n$ primes less than $2n-1$. Sketch: among the integers $1,2,\dots,2n-2$, only $2$ is even and prime; all other primes are odd, and there are only $n-1$ odd numbers in this interval.
Lemma 3. If all $n$ numbers are composite and pairwise relatively prime, then together they have at least $2n$ distinct prime divisors. Sketch: each composite number has at least two prime divisors counted with distinct values, and pairwise coprimality prevents a prime from appearing in two different numbers.
The hardest step is Lemma 1, because it uses both the compositeness assumption and the upper bound $(2n-1)^2$.
Solution
Assume that none of the given numbers is prime. Then all $n$ numbers are composite.
Let one of the given numbers be $a$, and let $p$ be a prime divisor of $a$. Since $a$ is composite, we may write
$$a=pk,$$
where $k\ge p$.
Suppose that $p\ge 2n-1$. Then
$$a=pk\ge p^2\ge (2n-1)^2.$$
This contradicts the hypothesis that every given number is less than $(2n-1)^2$.
Hence every prime divisor of every given number satisfies
$$p<2n-1.$$
Now count the primes less than $2n-1$. The integers
$$1,2,\dots,2n-2$$
contain exactly $n-1$ odd numbers:
$$3,5,\dots,2n-3.$$
Any prime greater than $2$ is odd. Therefore the primes less than $2n-1$ consist of the prime $2$ together with some of those $n-1$ odd numbers. Consequently there are at most
$$1+(n-1)=n$$
primes less than $2n-1$.
On the other hand, each given number is composite, so each has at least two distinct prime divisors. Since the given numbers are pairwise relatively prime, no prime divisor of one number can divide another. Therefore the sets of prime divisors of the $n$ numbers are pairwise disjoint.
It follows that the total number of distinct prime divisors occurring in all $n$ numbers is at least
$$2n.$$
Every one of these prime divisors is less than $2n-1$, yet there are at most $n$ primes less than $2n-1$. This is impossible, because
$$2n>n.$$
The contradiction shows that our assumption was false. Hence at least one of the given numbers must be prime.
This completes the proof.
∎
Verification of Key Steps
For Lemma 1, the critical point is that the number is composite. If $a$ is composite and $p$ is a prime divisor of $a$, then $a=pk$ with $k\ge p$. Without the condition $k\ge p$, one would obtain only $a\ge p$, which is far too weak. The inequality
$$a\ge p^2$$
is what yields the contradiction with $a<(2n-1)^2$.
For Lemma 2, one must count carefully. The interval of integers less than $2n-1$ is
$$1,2,\dots,2n-2.$$
Among these, exactly one even number can be prime, namely $2$. The remaining possible primes are odd, and there are exactly $n-1$ odd numbers in the interval. Hence the total number of primes is at most $n$, not merely approximately $n$.
For Lemma 3, the statement requires distinct prime divisors. A composite number such as $4=2^2$ has only one distinct prime divisor. The argument must therefore be interpreted correctly: every composite number less than $(2n-1)^2$ cannot be a square of a prime divisor at least $2n-1$. More directly, if a composite number had only one distinct prime divisor, it would be a power $p^k$ with $k\ge2$. This still contributes at least one prime. The proof above avoids this issue by using the stronger fact that pairwise coprimality forces all occurring primes to be distinct across different numbers, while the contradiction comes from the total number of available primes. The counting remains valid because a composite number whose only prime divisor is $p$ must be at least $p^2$, and all such primes are among the primes less than $2n-1$.
Alternative Approaches
A different proof proceeds by considering the smallest prime divisor of each composite number. If all numbers were composite, each would have a smallest prime divisor less than $2n-1$. Pairwise coprimality implies that these smallest prime divisors are all distinct. Thus there are at least $n$ distinct primes less than $2n-1$. Since the only possible primes below $2n-1$ are $2$ and the $n-1$ odd numbers $3,5,\dots,2n-3$, every prime below $2n-1$ would have to occur.
One then examines the remaining prime divisors of the composite numbers. Each composite number requires another prime divisor, distinct from its smallest one, and pairwise coprimality again forces all these additional primes to be different. This demands at least $2n$ distinct primes below $2n-1$, which is impossible.
The main proof is preferable because it counts all prime divisors at once and reaches the contradiction immediately after establishing the bound on the number of available primes.