5

Let $f:\mathbb Z^+\to\mathbb Z^+$ be a function satisfying the following conditions:

(i): For any positive integers $m$ and $n$,

$$\gcd\bigl((f(m),f(n)\bigr)\leq\bigl(\gcd(m,n)\bigr)^{2014}\,;$$

(ii): For any positive integer $n$, we have

$$n\le f(n)\le n+2014\,.$$

Show that there is a positive integer $N$, such for every integer $n\ge N$ we have $f(n)=n$.

my idea:let $m=n=1$,then we have $$\gcd(f(1),f(1))=f(1)\le (1)^{2014}\Longrightarrow f(1)=1$$ let $m=1$,then we have $$\gcd(f(1),f(n))=f(1)\le n^{2014}$$ then I can't

Thank you very much.

math110
  • 93,304

1 Answers1

6

I show below that $f(n)=n$ for any $n > 2014^{2014}$. My proof is very Chinese, it uses the Chinese remainder theorem all the time.

The hypotheses on the function imply

$$ (n,m)=1 \Rightarrow (f(n),f(m))=1\,. \tag{1} $$

There are infinitely many primes. In particular, there are sets of $2014\times 2015$ distinct primes $(q_{ij})_{1\leq i\leq 2014,0\leq j\leq 2014}$ with $q_{ij} > 2014$ for any $i,j$. We call these sets $Q$-systems. For any $Q$-system ${\cal Q}=(q_{ij})$, let us put

$$ \begin{array}{lcl} A_{\cal Q} &=& \lbrace n\geq 1 \ | \ q_{ij}\ \text{divides}\ n+i \ \text{for any}\ i,j \rbrace\,. \end{array} \tag{2} $$

If $n\in A_{\cal Q}$, then none of the $q_{ij}$ can divide $n$ (because otherwise they would have to divide also $i=(n+i)-i$, which is $\leq 2014$). So by the Chinese remainder theorem, there is a $m>n$ such that $m\equiv 1 \ ({\sf mod} \ n)$ and $m\equiv -j \ ({\sf mod} \ q_{ij})$ for all $i,j$. By construction $m$ and $n$ are coprime, so $f(m)$ and $f(n)$ are coprime also by $(1)$. Now by condition (ii) there is a $j_0\in\lbrace 0,1,\ldots ,2014\rbrace$ such that $f(m)=m+j_0$, hence $f(m)$ is divisible by all the $q_{ij_0}(1\leq i\leq 2014)$. So $q_{ij_0}$ does not divide $f(n)$ for any $i$, and hence $f(n)\neq n+i$. The only possibility left is $f(n)=n$. We have therefore shown :

$$ \text{If}\ n\in A_{\cal Q} \ \text{for some}\ Q\text{-system}\ {\cal Q}, \ \text{then}\ f(n)=n. \tag{3} $$

Since there are infinitely many primes, we can construct 2014 disjoint $Q$-systems ${\cal Q}_1,{\cal Q}_2, \ldots,{\cal Q}_{2014}$. Then, using the Chinese remainder theorem, we have an integer $a$ such that $a+1\in A_{{\cal Q}_1}, \ldots ,a+2014\in A_{{\cal Q}_{2014}}$. If we denote by $q$ the product of all the primes in all the ${\cal Q}_i$, any number $n$ congruent to $a$ modulo $q$ will satisfy the same properties as $a$ : we will have $n+i\in A_{{\cal Q}_i}$ for any $1\leq i\leq 2014$, and hence $f(n+i)=n+i$ by $(3)$. We have thus shown :

$$ \text{There are constants} \ a,q \ \text{such that for any }\ n\ \text{with } n\equiv a \ ({\sf mod}\ q), \ f(n+i)=n+i \ (1\leq i\leq 2014) \tag{4} $$

Finally, let $l$ be a number such that $f(l)\neq l$. Then $f(l)>l$, and we may construct a sequence of iterates $u_0=l,u_1=f(u_0),u_2=f(u_1),\ldots$, continuing as long as $f(u_{k})>u_k$. This sequence has length at most $q-2014$ by $(4)$ above, so it must stop at some $k$ with $f(u_k)=u_k$. We have $u_k=f(u_{k-1})=u_{k-1}+r$ with $1\leq r\leq 2014$. Then

$$ \begin{array}{lcl} u_k &=& {\gcd}(f(u_{k-1}),f(u_k) ) \\ &\leq& {\gcd}(u_{k-1},u_{k})^{2014} \\ &=& {\gcd}(u_{k}-r,u_k)^{2014} \\ &=& {\gcd}(r,u_k)^{2014} \\ &\leq& r^{2014} \leq 2014^{2014}. \end{array} \tag{5} $$

So $l\leq 2014^{2014}$, which concludes the proof.

Ewan Delanoy
  • 61,600
  • @MatemáticosChibchas You suppose right – Ewan Delanoy Mar 20 '14 at 12:01
  • A minor suggestion (I didn't dare to implement it on your answer): rewrite $(4)$ as: "There are constants $a,q$ such that $f(n)=n$ whenever $\overline n\in\bigl{\overline{a+1},\dots,\overline{a+2014}\bigr}\subseteq\mathbb Z/q\mathbb Z$". I think that this rephrasing explains a lot better your claim about the length at most $q-2014$ at the end of your proof. By the way, great demonstration!!! – Matemáticos Chibchas Mar 20 '14 at 13:58