Let the function $f:N^*\to N^*$ such that (1) $(f(m),f(n))\le (m,n)^{2014} , \forall m,n\in N^*$; (2) $n\le f(n)\le n+2014 , \forall n\in N^*$ Show that: there exists the positive integers $N$ such that $ f(n)=n $, for each integer $n \ge N$. (High School Affiliated to Nanjing Normal University )
Problem
Source: China Nanjing , 12 Mar 2014
Tags: function, algebra, polynomial, number theory proposed, number theory, China TST
19.03.2014 16:43
19.03.2014 19:21
Also, 61plus's Lemma above is actually USA TSTST 2012/3.
20.03.2014 07:08
yup tats true. any idea what can be the motivation if we havent seen the lemma?
26.03.2014 14:25
It is quite easy problem for number 3 of Chinese Team Selection Test. Considering cyclotomic polynomial makes half of the solution.
07.03.2015 00:16
I will prove that $N=(2014)^{(2014)^{(2014)}}$ is an acceptable constant. Firstly, assume there exists a prime $p$ and a natural $n$ such that $p|f(n)$ but $p$ doesn't divide $n$. Then let $p_{i.j}$ ($0 \le i,j \le 2017$) be $2018^2$ distinct primes, all greater than $\text{max}\{np,2014\}$. Consider the equations $m' \equiv -i/p (\bmod p_{i,1}...p_{i,2017}) $ for $i=0,...,2014$ $m' \equiv 1 (\bmod np)$ and, by CRT and Dirichlet, there are infinitely many primes $m'$ that satisfy said equations. (This is because, if $m'$ is a solution to the equation and it is not coprime to the modulus, then $p_{i,j} | -i/p$ for some $i,j$, which is readily seen to be false). Let $m'$ be such a number and let $m=m'p$. Notice that $p_{i,1}...p_{i,2017} | m+i$ for $i=0,...,2014$, and $m \equiv p (\bmod np)$. Then, $f(m)$ must be divisible by at least $2015$ distinct prime numbers, all greater than $np$ and distinct from $p$ and $m'$. By CRT, we can construct $a$ a natural such that $a,...,a+2014$ are all divisible by at least one of these $2015$ primes. Also, we can choose $a \equiv 1 (\bmod pm')$.Therefore, $f(a)$ and $f(m)$ cannot possibly be coprime, and thus $a$ and $m=pm'$ cannot be coprime, a contradiction! So our original assumption was false, and thus, for all $n$, $\boxed{p|f(n) \Rightarrow p|n}$. A quick corollary is that if $(n,2014!)=1$ then $p | f(n) \Rightarrow p | n \Rightarrow p | f(n)-n < 2014$ and this readily implies $f(n)=n$. This also implies that if $f(n) \neq n$, then $f(n)$ is only divisible by primes $p < 2014$. Now take any $n$ such that $f(n) \neq n$. We can choose primes $p_1,...,p_{2014} > \text{max}\{2014,n\}$ and by CRT, we can choose $m$ such that $m$ is congruent to anything we want $\bmod Q$ (for any $Q$ coprime to $p_1...p_{2014}$) and $p_i | m+i$ for $i=1,...,2014$. If $f(m)>m$, then a prime $>2014$ divides $f(m)$, contradiction. Therefore, $f(m)=m$, and so $(m,f(n))<(m,n)^{2014}$. If there is a prime $p$ such that $v_p(f(n))>2014v_p(n)$ then we can take $m \equiv p^{v_p(f(n))} (\bmod np^{v_p(f(n))-v_p(n)})$ and this gives $p^{v_p(f(n))} \le (m,f(n)) \le (m,n)^{2014} = p^{2014v_p(n)}$, a contradiction. Therefore, $v_p(f(n)) \le 2014v_p(n)$ for all $p$, and so $p^x | f(n) \Rightarrow p^{x/2014} | n \Rightarrow p^{x/2014} | f(n)-n < 2014 \Rightarrow p^{x/2014}<2014 \Rightarrow p^x < 2014^{2014}$ and so $f(n) < (2014)^{(2014)^{(2014)}}$, and so the proof is finished. Therefore, with our 6 boxes we can always reach a configuration where the 6th box has $n$ coins, where $f(n)=n$.
26.03.2015 05:56
Lemma 1: For any prime $ p $ and positive integer $ n, $ we have that $ p \vert f(n) \Longrightarrow p \vert n. $ Proof: Assume for the sake of contradiction that there exists an $ n \in \mathbb{N} $ and a prime $ p $ such that $ p \vert f(n) $ and $ (n, p) = 1. $ Because $ (f(n), f(p^k)) \le (n, p^k)^{2014} = 1 $ we have that $ (f(n), f(p^k)) = 1 $ for any $ k \in \mathbb{N} $ and so $ p \nmid f(p^k) $ for any $ k \in \mathbb{N}. $ Let $ A = \{f(p^k) : k \in \mathbb{Z}^{+}\} $ and let $ B = \{q : \exists a \in A \hspace{1 mm} \text{such that} \hspace{1 mm} q \vert a, q \hspace{1 mm} \text{is prime}\}. $ Assume for the sake of contradiction that set $ B $ contains infinitely many elements. Note that $ p \notin B. $ Consider $ 2015 $ distinct primes from $ S $ and label them $ q_1, q_2, \dots, q_{2015}. $ By CRT there exists an $ m \in \mathbb{N} $ such that $ m \equiv 1 \mod{p} $ and $ m \equiv -i + 1 \mod{q_i} $ for all $ i \in \{1, 2, \dots, 2015\}. $ But since $ m \le f(m) \le m + 2014 $ this means that there exists an $ i \in \{1, 2, \dots, 2015\} $ such that $ q_i \vert f(m). $ Now take a $ k \in \mathbb{Z}^{+} $ such that $ q_i \vert f(p^k) $ (we know that such a $ k $ exists from the definition of $ q_i $). We have that $ q_i \le (f(m), f(p^k)) \le (m, p^k)^{2014} = 1, $ contradiction. This shows that $ B $ has finitely many elements, so let $ B = \{q_1, q_2, \dots, q_r\} $ for some $ r \in \mathbb{Z}^{+}. $ Now I claim that for any $ s \in \mathbb{Z}^{+}, $ there exist primes $ x_1, x_2, \dots, x_s \notin B $ such that there exists a $ k \in \mathbb{N} $ such that $ p^k + i \equiv 0 \mod{x_i} $ for all $ i \in \{1, 2, \dots, s\}. $ I prove this claim by induction. For the base case of $ s = 1, $ note that by Kobayashi's Theorem since the set of prime factors of elements of the sequence $ p^k $ for $ k = 1, 2, \dots $ is finite, the set of prime factors of the sequence $ p^k + 1 $ for $ k = 1, 2, \dots $ is infinite which allows us to pick a suitable $ k $ and $ x_1. $ For the inductive step, assume we have a $ k $ such that $ p^k + i \equiv 0 \mod{x_i} $ for every $ i \in \{1, 2, 3, \dots, t\} $ for some positive integer $ t < s. $ Then Kobayashi's Theorem again on the sequence $ p^{k + (x_1 - 1)(x_2 - 1)\dots(x_t - 1)j} + t + 1 $ for $ j = 1, 2, \dots $ allows us to pick a suitable $ j $ and $ x_{t + 1}. $ Using this fact with $ s = 2014 $ allows us to pick a $ k $ such that every integer in the interval $ [p^k, p^k + 2014] $ is divisible by some $ x_i $ which contradicts the fact that these $ x_i $ are not in $ B. $ Hence the lemma is proven. Lemma 2: $ f $ is injective on the interval $ [2014^{2014}, \infty) $ Proof: Assume there exist distinct integers $ a, b > 2014^{2014} $ such that $ f(a) = f(b). $ Then $ f(a) = (f(a), f(b)) \le (a, b)^{2014} \le 2014^{2014}, $ contradiction. Lemma 2 implies that if there exists an integer $ m \ge 2014^{2014} $ such that $ f(m + i) = m + i $ for all $ i \in \{1, 2, \dots, 2014\} $ then $ f(n) = n $ for all $ n \in [2014^{2014}, m]. $ If a prime $ p > 2014 $ divides $ f(n) $ for some $ n \in \mathbb{N} $ then by Lemma 1 we have that $ p \vert f(n) - n \le 2014 \Longrightarrow f(n) = n. $ Therefore $ f(n) \ne n $ only if all prime factors of $ f(n) $ are less than $ 2014. $ Now it is a standard result that the gaps between consecutive $ 2014 $-smooth numbers (numbers with no prime factor greater than $ 2014 $) grow arbitrarily large (otherwise the sum of their reciprocals would diverge) and coupling this with the observation in the last paragraph we obtain the desired result. In fact, we have proven that $ N = 2014^{2014} $ is suitable.
03.02.2018 16:29
I would be glad if someone checked if this is correct. This seems to be at least a little bit different from the others. Call a natural number $m$ great if the numbers $m, m +1, m + 2, \ldots m + 2014$ have at least $4029$ distinct prime divisors each. I'll prove the following 3 things in my proof: 1. If $m$ is great, then $f(m) = m$. 2. The natural density of great numbers is $1$. 3. If $f(n + k) = n + k$ for all $1 \leq k \leq 2014$, where $n \geq 2014^{2014}$, then $f(n) = n$ Let's first show why the result follows from these facts. Since the density of great numbers is $1$, for each $M$, we can find $2014$ consecutive great numbers $m + 1, m + 2, \ldots, m + 2014$, and $m > M$. (If we couldn't, it would mean that the density of non-great numbers would be at least $\frac{1}{2014}$ or something like that, which is a contradiction). Thus, it follows that for all $2014^{2014} \leq n \leq M$ holds $f(n) = n$. As $M$ can be arbitrarily large, we are done. Now we will prove the lemmas. Lemma 1. Assume $m$ is great. For the number $m + k$, where $0 \leq k \leq 2014$ we will denote by $p_{k, i}, 1 \leq i \leq 2015$ some $2015$ distinct prime divisors of $m + k$, where $p_{k, i} > 2014$ for all $i$. $m + k$ has such divisors, as it has at least $4029$ distinct prime divisors in total. Now, if some $p_{a, b}$ divides both numbers $m + i$ and $m + j$ for some $0 \leq i, j \leq 2014$, should $p_{a, b}$ also divide $j - i$. But as $p_{a, b} > 2014$, this is impossible if $i \neq j$. Thus all $p_{a, b}$ are distinct. We will pick $n$ as follows: $n \equiv 1$ (mod $m$) $n + i \equiv 0$ (mod $p_{j, i}$) for all $1 \leq j \leq 2014$, where $i$ runs from $1$ to $2014$. $n \equiv 0$ (mod $p_{i, 2015}$) for all $1 \leq i \leq 2014$. This is allowed by Chinese remainder theorem. Why? We proved earlier that all $p_{a, b}$ are distinct. Also, if $p_{a, b}$ divides $m$ for some $a > 0$, then would be $p_{a, b} | m + a$, and thus $p_{a, b} \leq a \leq 2014$, a contradiction. Thus the moduli are coprime. Now, assume $f(m) = m + c$ and $f(n) = n + d$. Assume $c > 0$. As $n \equiv 1$ (mod $m$), the gcd of $m$ and $n$ is $1$. Due to the inequality given in the problem statement, it must hold that the gcd of $m + c$ and $n + d$ is $1$. If $d > 0$, $p_{c, d}$ divides $n$ and $m$. If $d = 0$, $p_{c, 2015}$ divides $n$. Thus this is a contradiction. Therefore, $c = 0$, and the lemma is proved. Lemma 2. Call an integer $m$ good, if $m$ has at least $4029$ distinct prime divisors. It is sufficient to prove that good numbers have density of $1$ (then, non-good numbers have density of $0$, and non-great numbers would also have density of $0$, as one non-good number produces at most $2015$ new non-great numbers). It's a well-known result that the density of good numbers is $0$. Lemma 3. (Apparently also covered in the previous solution, but I write it here for completeness.) Pick an $n$ that satisfies $f(n + k) = n + k$ for all $1 \leq k \leq 2014$, and $n \geq 2014^{2014}$. Now, assume $f(n) = n + b$, where $b > 0$. Plug $m = n + b$, $n = n$ in the inequality of the problem statement. Now, $(f(m), f(n)) = n + b$, and $(m, n)^{2014} \leq 2014^{2014}$. Therefore we would need $n + b \leq 2014^{2014}$, which is a contradiction as $n + b \geq 2014^{2014} + 1$. The result follows
17.04.2023 10:01
Let $C=2014$. The key claim is that $rad(f(n)) \mid rad(n)$. Assume for contradiction there exists a prime $q_1$ such that $q_1\mid f(n), q_1\nmid n$ (*). Lemma: Let $S$ be the set of primes dividing $f(n)$ for some $n\in \mathbb{N}$. Then $S$ is infinite. Proof: Assume for contradiction that $S$ is finite. Then $S$ is bounded i.e. there exists $K$ such that for all $p\in S, p<K$. Pick primes $p_1,\cdots,p_{C+1}>K$ such that $p_j \mid n+j-1$. Then at least one of $p_1,\cdots,p_{C+1}$ must be in $S$. Let $k_1=n$. With this lemma in mind, for each $j=2,\cdots,C+1$, we can construct a prime $q_j$ such that $$\max\{ k_{j-1},\prod\limits_{k=1}^{j-1} q_k^{C^2}\} < q_j$$and $k_j$ such that $q_j\mid f(k_j)$. Consider $m$ such that $q_j \mid m+j-1$ for $j=1,\cdots,C+1$. Suppose $f(m)=m+j-1$. Then $q_j \mid \gcd(f(m),f(k_j))$, so $\gcd(m,k_j) \ge q_j^{1/C}$ We therefore have $\gcd(m+kP,k_j) \ge q_j^{1/C}$ for all $k\in \mathbb{N}$, where $P=\prod q_j$. This in particular implies that $\gcd(P,k_j)\ge q_j^{1/C}$, because for every prime $r$ not dividing $p$ but dividing $k_j$, I can construct $k$ such that $r\nmid m+kP$, so we only need to worry about $\gcd(q_1q_2 \cdots q_{C+1}, k_j)$ Since $k_j < q_t$ for all $t=j+1,\cdots,C+1$, it follows that $\gcd(q_1q_2 \cdots q_{C+1}, k_j) = \gcd(q_1\cdots q_j, k_j)$. If $q_j \nmid k_j$, then $\gcd(q_1\cdots q_j, k_j) \le q_1\cdots q_{j-1} < q_j^{1/C}$, absurd! Therefore, $q_j \mid k_j$ and $q_j \mid m$. But we are also given that $q_j \mid m+j-1$, so $q_j\mid j-1 \iff j=1$. It follows that $q_1 \mid k_1 = n$, contradicting (*). Now, fix $N>C^{C^C}$. Suppose $n>N$ and $d=f(n)-n>0$. Then $rad(f(n)) \mid \gcd(f(n),n) \le f(n)-n \le C$, so $rad(f(n))$ have at most $C$ prime factors. By pigeonhole principle, there exists a prime $p$ such that $p^{\nu_p(f(n))} > f(n)^{1/C}$. Since $\gcd(f(n),n) \le C$ is bounded, it follows that $p^{\nu_p(n)} < C$. We pick $t$ such that $\nu_p(t) > C^{C^C}$, the only prime factor $n,t$ have in common is $p$, and for each $j=1,\cdots,C$, $t+j$ is divisible by a very large prime $p_j>>N$ (which is greater than $C\ge j$, so does not divide $t$). By our key claim, $f(t)$ cannot be $t+j$ for any $j=1,\cdots,C$, so $f(t)=t$. Thus, $\gcd(n,t)^C < C^C$ while $\gcd(f(n),f(t)) > f(n)^{1/C}$. This is a size contradiction when $n>C^{C^C}$, so we are done.
02.11.2024 23:34
Solved while walking. Notice that for $(m,n)=1$ we have $(f(m),f(n))=1$. Claim 1: $p \mid f(n)$ for a prime $p$, implies $p \mid n$ Proof: Follows from USA TSTST 2012/3 Claim 2: $f$ is injective on $[2014^{2014}+1,\infty]$. Proof Assume $f(i)=f(j)$ for $2014^{2014}+1 < i \leq j$then by the second condition, $|i-j|\leq 2014$, and so $(i,j)\leq 2014$ this implies that $2014^{2014}+1 \leq f(i) \leq (i,j)^{2024} \leq 2014^{2014}$, contradiction! now construct $p_i \mid x+i$ for $i$ from $1$ to $2014$, which is of course possible by CRT, where $p_i$ are some large primes, then clearly $p_j$ does not divide $x+i$, for $i \neq j$ due to size, hence implying that $f(x+i)=x+i$ for $i$ varying from $1$ to $2014$, now as we can take larger primes than before so there exist infinite such $x$, which implies the problem due to injectivity of $f$ on large enough values.
05.11.2024 12:24
Very easy for CTST p3. Lemma: There exist a positive integer $L$ such that $f(L),f(L+1),.....$ are all distinct. Proof: Say $f(a)=f(b), a \neq b$ so $f(a) \leq (a,b)^{2014}$ as $|b-a|$ is bounded and LHS grows large if $L$ is large we are done. Lemma : range of $f$ contains all but finite positive integers. Proof: Say $S=\{f(L),f(L+1),...\}$ The number of positive integers in $S$ , $\leq N$ for a large positive integer $N$ is atleast $N-\mathcal{O}(1)$ hence done Lemma: For positive integers $n$ , $\phi(n) \leq \phi(f(n))$. By considering density $1-\frac{1}{\phi(n)} \leq 1-\frac{1}{\phi(f(n))}$ done. Lemma: For large primes $p$ , $f(p)=p$. Proof: Using last lemma $f(p)=q$ where $q$ is a prime too. Assume the contrary so $(f(n),q) \leq (n,p)^{2024}$ Pick a large positive integer $t$ such that none of $qt,qt-1,...,qt-2014$ is divisible by $p$ say $f(k)=qt$ subsitute $n=k$ and done. Lemma: For large primes $p$ if $p|f(n) \implies p|n$ . Proof: Assume the contrary $(p,f(n))\leq (p,n)^{2014}$ giving us needed contradiction. Now from here we see that for a large positive integer $n$ if it has a large enough prime divisor , then $f(n)=n$ . Proof: say $f(k)=n$ , from there we get contradiction. Finally to finish it off Consider large numbers $N$ whose all prime divisors are small by koboyashi all numbers $N-2014,....,N-1$ have large prime divisors so its only preimage can be $N$ or $f(N)=N$