k is the positive root of the equation x2 - 1998x - 1 = 0. Define the sequence x0, x1, x2, ... by x0 = 1, xn+1 = [k xn]. Find the remainder when x1998 is divided by 1998.
Solution
Put p(x) = x2 - 1998x - 1. Then p(1998) = -1, p(1999) = 1998, so 1998 < k < 1999. Also k is irrational (using the formula for the root of a quadratic). We have xn = [k xn-1], so xn < k xn-1 and > k xn-1 - 1. Hence xn/k < xn-1 < xn/k + 1/k, so [xn/k] = xn-1 - 1.
k = (1998k + 1)/k = 1998 + 1/k. Hence kxn = 1998xn + x/k. Hence xn+1 = [kxn] = 1998xn + [xn/k] = 1998xn + xn-1 - 1. Hence xn+1 = xn-1 - 1 mod 1998. So x1998 = 1 - 999 = 1000 mod 1998.
© John Scholes
jscholes@kalva.demon.co.uk
24 Oct 2002