IMO 2004 SL N4

Origin: POL | Category: Number Theory

Problem

Let k be a fixed integer greater than 1, and let m = 4k2 −5. Show that there exist positive integers a and b such that the sequence (xn) defined by x0 = a, x1 = b, xn+2 = xn+1 + xn for n = 0, 1, 2, . . . has all of its terms relatively prime to m.

Solution

Set a = 1 and assume that b \inN is such that b2 \equivb + 1 (mod m). An easy induction gives us xn \equivbn (mod m) for all n \inN0. Moreover, b is obviously coprime to m, and hence each xn is coprime to m. It remains to show the existence of b. The congruence b2 \equivb + 1 (mod m) is equivalent to (2b −1)2 \equiv5 (mod m). Taking 2b −1 \equiv2k, i.e., b \equiv2k2 + k −2 (mod m), does the job. Remark. A desired b exists whenever 5 is a quadratic residue modulo m, in particular, when m is a prime of the form 10k \pm 1.