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) \in S$ write $n = 2^k \cdot n_o$ where $k, n_0$ are positive integers with $n_0$ odd and define \[ f(s) = (n_0, m + n - n_0). \] Prove that $f$ is a function from $S$ to $S$ and that for each $s = (m,n) \in S,$ there exists a positive integer $t \leq \frac{m+n+1}{4}$ such that \[ f^t(s) = s, \] where \[ f^t(s) = \underbrace{ (f \circ f \circ \cdots \circ f) }_{t \text{ times}}(s). \] If $m+n$ is a prime number which does not divide $2^k - 1$ for $k = 1,2, \ldots, m+n-2,$ prove that the smallest value $t$ which satisfies the above conditions is $\left [\frac{m+n+1}{4} \right ]$ where $\left[ x \right]$ denotes the greatest integer $\leq x.$
Problem
Source: IMO Shortlist 1993, Ireland 3
Tags: function, modular arithmetic, number theory, Iteration, functional equation, IMO Shortlist
26.06.2006 13:34
it is similar to P1 vietnam TST 1999
27.06.2006 23:00
To avoid a long post, I will simply sketch how a solution of the problem works. Let's take a prime $p$ such as 17. Then it is evident that $f$ permutes the pairs $(1,16), (3,14), (5,12), (7,10)$. We have $f(1,16)=(1,16)$ from where $-1\equiv 2^4\pmod{17}$, and so 2 is not a primitive root modulo 17. Also $f(3,14)=(7,10)$, $f(7,10)=(5,12)$ and $f(5,12)=(3,14)$ from where $-1\equiv 2^12^12^2\equiv 2^{1+1+2}\equiv 2^4\pmod{17}$, and again we conclude that 2 is not a primitive root modulo 17. So we see that every cyclic sequence $s, f(s), f^2(s), f^3(s), \dots, f^n(s)=s$ is related with a congruence of the form $\pm 1\equiv 2^x\pmod p$, the sign being plus if the sequence has an even number of pairs and minus if there are an odd number of pairs in the sequence. Now we take a prime $p$ such that 2 is a primitive root modulo $p$, for example let's take the prime 29. All we have to prove is that $f$ permutes cyclically the pairs \[ (1,28), (3,26), (5,24), (7,22), (9,20), (11,18), (13,16) \] Consider the powers of 2 dividing 28, 26,..., 16, let's say $28=2^2\cdot 7$, $26=2^1\cdot 13$, $24=2^3\cdot 3$, $22=2^1\cdot 11$, $20=2^2\cdot 5$, $18=2^1\cdot 9$, $16=2^4$. The sum of the exponents of 2 is $2+1+3+1+2+1+4=14=\frac{29-1}2$. Now, the only possible congruence associated to a sequence of pairs permuted by $f$ is the congruence associated to a cyclic permutation of all the pairs \[ -1\equiv 2^{2+1+3+1+2+1+4}\equiv 2^{\frac{29-1}2}\pmod{29} \] FINAL NOTE: As a plus, the left member of the congruence should be -1, not +1, proving that every odd prime $p$ such that 2 is a primitive root modulo $p$ has associated a series of an odd number of pairs, so that $\left[\frac{p+1}4\right]$ is odd, or what is the same $p\equiv 3\,\text{or}\,5\pmod 8$.