18th Iberoamerican 2003 Problem B3 The sequences a 0 , a 1 , a 2 , ... and b 0 , b 1 , b 2 , ... are defined by a 0 = 1, b 0 = 4, a n+1 = a n 2001 + b n , b n+1 = b n 2001 + a n . Show that no member of either sequence is divisible by 2003.
Problem 1030
Official solution
2003 is prime, so a 2002 = 1 mod 2003 for any a not divisible by 2003. Thus a n+1 = a n -1 + b n mod 2003, b n+1 = b n -1 + a n mod 2003. Put c n = a n b n . Then c n+1 = c n + 1/c n + 2 = (c n + 1) 2 /c n mod 2003. So if c n ≠ 0 mod 2003, then c n+1 ≠ 0 mod 2003 unless c n = -1 mod 2003. Then if c n+1 = -1 mod 2003, we must have (c n 2 + 3c n + 1)/c n = 0 mod 2003, so c n 2 + 3c n + 1 = 0 mod 2003. Note that c 0 = 4. So it is sufficient to show that there are no solutions to x 2 + 3x + 1 = 0 mod 2003, or equivalently to (x - 1000) 2 = 1000 2 - 1 = 502 mod 2003. In other words, we have to show that 502 is a quadratic non-residue mod 2003. The easiest way to do that is to use the law of quadratic reciprocity, but that is almost certainly outside the syllabus. We note that 4·502 = 5 mod 2003, so 502 is a square iff 5 is a square. It is sufficient to show that 5 1001 = -1 mod 2003, for then if we had x 2 = 5, we would have x 2002 = -1 mod 2003, whereas we know that x 2002 = 1 mod 2003. We note that 1001 = 7·11·13. We start by showing that 5 7 = 8 mod 2003. We have 5 5 = 3125 = 1122 mod 2003, so 5 6 = 5610 = 1604 mod 2003, so 5 7 = 8020 = 8 mod 2003. We calculate successively 2 11 = 2048 = 45 mod 2003, so 2 22 = 2025 = 22 mod 2003. Multiplying by 22 is relatively easy, so 2 44 = 484, 2 66 = 10648 = 633, 2 88 = 13926 = -95, 2 110 = -2090 = -87, 2 132 = -1914 = 89, 2 143 = 4005 = -1 all mod 2003. Hence 8 11·13 = -1 mod 2003, so 5 1001 = -1 mod 2003, as required, and we are done. 18th Ibero 2003 © John Scholes [email protected] 1 Jan 04 Last corrected 1 Jan 04