14th Mexico 2000 Problem B1 Given positive integers a, b (neither a multiple of 5) we construct a sequence as follows: a 1 = 5, a n+1 = a a n + b. What is the largest number of primes that can be obtained before the first composite member of the sequence?
5 Solution We find that the first few terms are a 1 = 5, a 2 = 5a+b, a 3 = 5a 2 +ab+b, a 4 = 5a 3 +a 2 b+ab+b, a 5 = 5a 4 +a 3 b+a 2 b+ab+b = 5a 4 + b(a 4 -1)/(a-1), a 6 = 5a 5 +a 4 b+a 3 b+a 2 b+ab+b. Now if a ≠ 1 mod 5, then a 4 = 1 mod 5, so a 5 = 0 mod 5. If a = 1 mod 5, then a 6 = b(a 4 +a 3 +a 2 +a+1) = b(1+1+1+1+1) = 0 mod 5. So either a 5 or a 6 is a multiple of 5 (and obviously greater than 5, so composite). Thus we can get at most 5 initial primes. We find that for a = 6, b = 7 we get 5, 37, 229, 1381, 8293, which are all prime (although checking the last two is a considerable slog, we have to test 8293 for prime divisors up to 89). 14th Mexican 2000 © John Scholes jscholes@kalva.demon.co.uk 29 February 2004 Last corrected/updated 29 Feb 04