## Saturday, March 11, 2006

### Primessss... Topic: Number Theory. Level: Olympiad.

Problem: (1995 APMO - #2) Let$a_1, a_2, \ldots, a_n$ be a sequence of integers with values between $2$ and $1995$ such that:

(i) Any two of the $a_i$'s are realtively prime,
(ii) Each $a_i$ is either a prime or a product of distinct primes.

Determine the smallest possible values of $n$ to make sure that the sequence will contain a prime number.

Solution: We claim that $n = 14$. A sequence with $13$ values is

$41(43), 37(47), 31(53), 29(59), 23(61), 19(67), 17(71), 13(73), 11(79), 7(83), 5(89), 3(97), 2(101)$.

Suppose that there exist $14$ composite numbers satisfying the given condition. Consider the smallest prime divisors of each of the $14$ numbers. They must be distinct to fulfill the relatively prime condition. But since $41$ is the $13$th prime, one of the numbers must have smallest prime divisor $\ge 43$. Then that number is at least $43 \cdot 47 > 1995$. Contradiction.

Hence $n = 14$, as claimed. QED.