MathDB
Composited function and relatively prime positive integers

Source: IMO Shortlist 1993, Ireland 3

March 16, 2006
functionmodular arithmeticnumber theoryIterationfunctional equationIMO Shortlist

Problem Statement

Let SS be the set of all pairs (m,n)(m,n) of relatively prime positive integers m,nm,n with nn even and m<n.m < n. For s=(m,n)∈Ss = (m,n) \in S write n=2k⋅non = 2^k \cdot n_o where k,n0k, n_0 are positive integers with n0n_0 odd and define f(s)=(n0,m+n−n0). f(s) = (n_0, m + n - n_0). Prove that ff is a function from SS to SS and that for each s=(m,n)∈S,s = (m,n) \in S, there exists a positive integer t≤m+n+14t \leq \frac{m+n+1}{4} such that ft(s)=s, f^t(s) = s, where ft(s)=(f∘f∘⋯∘f)⏟t times(s). f^t(s) = \underbrace{ (f \circ f \circ \cdots \circ f) }_{t \text{ times}}(s). If m+nm+n is a prime number which does not divide 2k−12^k - 1 for k=1,2,…,m+n−2,k = 1,2, \ldots, m+n-2, prove that the smallest value tt which satisfies the above conditions is [m+n+14]\left [\frac{m+n+1}{4} \right ] where [x]\left[ x \right] denotes the greatest integer ≤x.\leq x.
Back to ProblemsView on AoPS