The sequences a0, a1, a2, ... and b0, b1, b2, ... are defined by a0 = 1, b0 = 4, an+1 = an2001 + bn, bn+1 = bn2001 + an. Show that no member of either sequence is divisible by 2003.
Solution
2003 is prime, so a2002 = 1 mod 2003 for any a not divisible by 2003. Thus an+1 = an-1 + bn mod 2003, bn+1 = bn-1 + an mod 2003. Put cn = anbn. Then cn+1 = cn + 1/cn + 2 = (cn + 1)2/cn mod 2003. So if cn ≠ 0 mod 2003, then cn+1 ≠ 0 mod 2003 unless cn = -1 mod 2003. Then if cn+1 = -1 mod 2003, we must have (cn2 + 3cn + 1)/cn = 0 mod 2003, so cn2 + 3cn + 1 = 0 mod 2003. Note that c0 = 4. So it is sufficient to show that there are no solutions to x2 + 3x + 1 = 0 mod 2003, or equivalently to (x - 1000)2 = 10002 - 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 51001 = -1 mod 2003, for then if we had x2 = 5, we would have x2002 = -1 mod 2003, whereas we know that x2002 = 1 mod 2003. We note that 1001 = 7·11·13. We start by showing that 57 = 8 mod 2003. We have 55 = 3125 = 1122 mod 2003, so 56 = 5610 = 1604 mod 2003, so 57 = 8020 = 8 mod 2003.
We calculate successively 211 = 2048 = 45 mod 2003, so 222 = 2025 = 22 mod 2003. Multiplying by 22 is relatively easy, so 244 = 484, 266 = 10648 = 633, 288 = 13926 = -95, 2110 = -2090 = -87, 2132 = -1914 = 89, 2143 = 4005 = -1 all mod 2003. Hence 811·13 = -1 mod 2003, so 51001 = -1 mod 2003, as required, and we are done.
© John Scholes
jscholes@kalva.demon.co.uk
1 Jan 04
Last corrected 1 Jan 04