IMO 1993 SL 13

Origin: IRE

Problem

Let S be the set of all pairs (m, n) of relatively prime positive integers m, n with n even and m < n. For s = (m, n) \inS write n = 2kn0, where k, n0 are positive integers with n0 odd and define f(s) = (n0, m + n −n0). Prove that f is a function from S to S and that for each s = (m, n) \inS, there exists a positive integer t \leqm+n+1 such that f t(s) = s, where f t(s) = (f ◦f ◦\cdot \cdot \cdot ◦f)    t times (s). If m+n is a prime number that does not divide 2k−1 for k = 1, 2, . . ., m+ n−2, prove that the smallest value of t that satisfies the above conditions is / m+n+1 , where [x] denotes the greatest integer less than or equal to x.

Solution

For an odd integer N > 1, let SN = {(m, n) \inS | m + n = N}. If f(m, n) = (m1, n1), then m1 + n1 = m + n with m1 odd and m1 \leqn 2 < N 2 < n1, so f maps SN to SN. Also f is bijective, since if f(m, n) = (m1, n1), then n is uniquely determined as the even number of the form 2km1 that belongs to the interval [ N+1 2 , N], and this also determines m. Note that SN has at most / N+1 elements, with equality if and only if N is prime. Thus if (m, n) \inSN, there exist s, r with 1 \leqs < r \leq / N+5 such that f s(m, n) = f r(m, n). Consequently f t(m, n) = (m, n), where t = r −s, 0 < t \leq / N+1

/ m+n+1 . Suppose that (m, n) \inSN and t is the least positive integer with f t(m, n) = (m, n). We write (m, n) = (m0, n0) and f i(m, n) = (mi, ni) for i = 1, . . . , t. Then there exist positive integers ai such that 2aimi = ni−1, i = 1, . . . , t. Since mt = m0, multiplying these equalities gives 2a1+a2+\cdot\cdot\cdot+atm0m1 \cdot \cdot \cdot mt−1 = n0n1 \cdot \cdot \cdot nt−1 \equiv(−1)tm0m1 \cdot \cdot \cdot mt−1 (mod N). (1)

It follows that N | 2k \pm 1 and consequently N | 22k −1, where k = a1 + \cdot \cdot \cdot + at. On the other hand, it also follows that 2k | n0n1 \cdot \cdot \cdot nt−1 | (N −1)(N −3) \cdot \cdot \cdot (N −2[N/4]). But since (N −1)(N −3) \cdot \cdot \cdot
N −2 / N 0 1 \cdot 3 \cdot \cdot \cdot
/ N−2

• 1  = 2 \cdot 4 \cdot \cdot \cdot (N −1) 1 \cdot 2 \cdot \cdot \cdot N−1 = 2 N−1 2 , we conclude that 0 < k \leq N−1 2 , where equality holds if and only if {n1, . . . , nt} is the set of all even integers from N+1 to N −1, and conse- quently t = N+1 4 . Now if N ∤2h −1 for 1 \leqh < N −1, we must have 2k = N −1. Therefore t = N+1 4 .