IMO 1987 SL 23

Origin: YUG

Problem

Prove that for every natural number k (k \geq2) there exists an irrational number r such that for every natural number m, [rm] \equiv−1 (mod k). Remark. An easier variant: Find r as a root of a polynomial of second degree with integer coefficients.

Solution

If we prove the existence of p, q \inN such that the roots r, s of f(x) = x2 −kp \cdot x + kq = 0 are irrational real numbers with 0 < s < 1 (and consequently r > 1), then we are done, because from r + s, rs \equiv0 (mod k) we get rm + sm \equiv0 (mod k), and 0 < sm < 1 yields the assertion. To prove the existence of such natural numbers p and q, we can take them such that f(0) > 0 > f(1), i.e., kq > 0 > k(q −p) + 1 ⇒ p > q > 0. The irrationality of r can be obtained by taking q = p −1, because the discriminant D = (kp)2 −4kp + 4k, for (kp −2)2 < D < (kp −1)2, is not a perfect square for p \geq2.