7th APMO 1995 Problem 2 Find the smallest n such that any sequence a 1 , a 2 , ... , a n whose values are relatively prime square-free integers between 2 and 1995 must contain a prime. [An integer is square-free if it is not divisible by any square except 1.] Solution
: n = 14. We can exhibit a sequence with 13 terms which does not contain a prime: 2·101 = 202, 3·97 = 291, 5·89 = 445, 7·83 = 581, 11·79 = 869, 13·73 = 949, 17·71 = 1207, 19·67 = 1273, 23·61 = 1403, 29·59 = 1711, 31·53 = 1643, 37·47 = 1739, 41·43 = 1763. So certainly n ≥ 14. If there is a sequence with n ≥ 14 not containing any primes, then since there are only 13 primes not exceeding 41, at least one member of the sequence must have at least two prime factors exceeding 41. Hence it must be at least 43·47 = 2021 which exceeds 1995. So n =14 is impossible. 7th APMO 1995 © John Scholes jscholes@kalva.demon.co.uk 11 Apr 2002