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.

No comments:

Post a Comment