5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think $f(n) \le n^{2014}$ is unnecessary. You have proved that $f(1)=1$. For all $n \gt 1$, $n+2014$ is a tighter upper bound than $n^{2014}$. Right? $\endgroup$ – Guy Mar 12 '14 at 15:43
  • $\begingroup$ Yes.so this is not use work,Thank you $\endgroup$ – china math Mar 12 '14 at 15:47
  • $\begingroup$ You're welcome. :) But this question looks very interesting. I will try. $\endgroup$ – Guy Mar 12 '14 at 15:49
  • $\begingroup$ Oh,Thank you,I Looking forward to your answer $\endgroup$ – china math Mar 12 '14 at 15:50
  • $\begingroup$ I haven't solved it yet, but I noticed another mistake. $\gcd(1,n)$ is $1$, not $n$ $\endgroup$ – Guy Mar 12 '14 at 15:58
6
+25
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @MatemáticosChibchas You suppose right $\endgroup$ – Ewan Delanoy Mar 20 '14 at 12:01
  • $\begingroup$ 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!!! $\endgroup$ – Matemáticos Chibchas Mar 20 '14 at 13:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.