Question 13
(IRE 3) Let $S$ be the set of all pairs $(m,n)$ of relatively prime positive integers $m,n$ with $n$ even and $m\lt n$. For $s=(m,n)\in S$ write $n=2^kn_0$, 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\le\frac{m+n+1}{4}$ such that $f^t(s)=s$, where
$$f^t(s)=(\underbrace{f\circ f\circ\cdots\circ f}_{t})(s).$$
The underbrace indicates $t$ compositions.
If $m+n$ is a prime number that does not divide $2^k-1$ for $k=1,2,\ldots,m+n-2$, prove that the smallest value of $t$ that satisfies the above conditions is $\left[\frac{m+n+1}{4}\right]$, where $[x]$ denotes the greatest integer less than or equal to $x$.
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\le\frac{m+n+1}{4}$ such that $f^t(s)=s$, where
$$f^t(s)=(\underbrace{f\circ f\circ\cdots\circ f}_{t})(s).$$
The underbrace indicates $t$ compositions.
If $m+n$ is a prime number that does not divide $2^k-1$ for $k=1,2,\ldots,m+n-2$, prove that the smallest value of $t$ that satisfies the above conditions is $\left[\frac{m+n+1}{4}\right]$, where $[x]$ denotes the greatest integer less than or equal to $x$.