let $\tau (n)$ be the maximum value at the set of prime factor of $n$.lemma (1)for all $n$ we have $2012>\tau (f(n))$ otherwise $\exists t$ is prime such that $t\mid f(k),t\mid f(br)$ and $ f(at+r)=at+r+t_{1}, f(bt+v)=bt+v+t_{2}$ and $0\leq t_{1},t_{2}< 2012$ so $t\mid r+t_{1}-v-t_{2}$ and $v\geq r\Rightarrow t_{1}-t_{2}+r-v< 2012$ we are done for lemma (1). $n=p_{1}^a_{1}p_{2}^{a{2}}...p^{a_{k}}$ .we know that $gcd(f(n),f(p_{i}^{a_{i}}))=d> 1$ and $gcd(f(p_{j}^{a_{j}}),f(p_{i}^{a_{i}}))=1$ .if there is $q\mid f(n)$ and $q$ dose not divides $n$ ($q$ is prime)and $p$ is the primary root of $q$.we let $v_{2}(q-1)=s$ .consider the numbers $f(p{}^{2{}^{s+1}}),f(p{}^{2{}^{s+2}}),...f(p{}^{2{}^{s+u}}),...$ .Between these numbers there are infinity $c_{i},c_{j}$ such that $f(p{}^{2{}^{s+c_{j}}})\equiv f(p{}^{2{}^{s+c_{i}}})$(because $0\leq f(m)-m\leq 2012$ for all $m$ .)the set of these number is $A$ . there are two numbers $f(p{}^{2{}^{s+c_{j}}}),f(p{}^{2{}^{s+c_{i}}})\in A$ and $f(p{}^{2{}^{s+c_{j}}})-p{}^{2{}^{s+c_{j}}}\equiv -(f(p{}^{2{}^{s+c_{i}}})-p{}^{2{}^{s+c_{i}}})$ (because $0\leq f(m)-m\leq 2012$ for all $m$ .) .so $q\mid p{}^{2{}^{m}}+p{}^{2{}^{r}}\Rightarrow p{}^{2{}^{m}}\equiv -p{}^{2{}^{r}}(mod(q))$ and we have $gcd(p,q)=1$ so $ p{}^{2{}^{m}-2^r}\equiv -1(mod(q))$ . lemma(2) there exists $x$ such that $x^{n}\equiv a(mod(q))$ if and only if $a^{\phi (q)/d}\equiv 1(mod(q)),d=gcd(n,\phi (q))$ so we have $ p{}^{2{}^{m}-2^r}\equiv -1(mod(q))$ and $(-1)^{\phi (q)/gcd(2^m-2^r,\phi (q))}\not\equiv 1(mod (q))$ because $v_{2}(2^m-2^r)=r> s$

i don't understand shekast-istadegi

I don't entirely follow shekast-istadegi's solution either. Here is an alternate solution (parts of which I guess can be simplified). Suppose the contrary. Let $n$ be a natural number and $p$ a prime such that $p$ divides $f(n)$, but $p$ does not divide $n$. Let $S$ denote the set of all primes that divide $f(p^k)$ for some positive integer $k$. Since $(p,n) = 1$, it follows that $p \not\in S$. We claim that $S$ is finite. If not, let $q_1, q_2, \ldots, q_{2013}$ be distinct elements of $S$. Let $m$ be a positive integer such that $m \equiv 1 \pmod{p}$ and $m \equiv -(i-1) \pmod{q_i}$ for $1 \le i \le 2013$. Then $(m,p^k) = 1$ for any positive integer $k$, so $q_i$ do not divide $f(m)$ for $1 \le i \le 2013$. This is a contradiction since $m \le f(m) \le m + 2012$. We thus have that $S$ is finite. Let $S = \{q_1, q_2, \ldots, q_r\}$. We shall now show that there exists primes $l_1, l_2, \ldots, l_{2012} \not\in S$, and a positive integer $k$ such that $p^k + j \equiv 0 \pmod{l_j}$ for $1 \le j \le 2012$. If this is true, then $l_j$ divides $f(p^k)$ for some $1 \le j \le 2012$, a contradiction. We construct $l_1, l_2, \ldots, l_{2012}$ by induction. To start with, let $v_{q_i}(p + 1) = \alpha_i$ for $1 \le i \le r$. Let $M_1 = 1 + \prod_{i = 1}^r (q_i^{\alpha_i + 1} - q_i^{\alpha_i})$. Then we have $v_{q_i}(p^{M_1} + 1) = \alpha_i$ for $1 \le i \le r$. Hence there exists a prime $l_1$ which is not in $S$ such that $l_1$ divides $p^{M_1} + 1$. Now for the final induction step. Suppose that we have primes $l_1, l_2, \ldots, l_{s-1} \not\in S$ and an integer $M$ such that $p^M + j \equiv 0 \pmod{l_j}$ for $1 \le j \le s-1$. Let $v_{q_i}(p^M + s) = \beta_i$ for $1 \le i \le r$. Let $M_s = M + \prod_{j=1}^{s-1} (l_j - 1) \prod_{i = 1}^r (q_i^{\beta_i + 1} - q_i^{\beta_i})$. Then $p^{M_s} + j \equiv 0 \pmod{l_j}$ for $1 \le j \le s-1$. Further, we have that $v_{q_i}(p^{M_s}+s) = \beta_i$ for $1 \le i \le r$ and hence it follows that that there exists a prime $l_s \not\in S$ such that $p^{M_s} + s \equiv 0 \pmod{l_s}$. This completes the induction step.

Another solution: Assume that for some $n$ and prime $q$, $q | f(n)$ but $q$ doesn't divide $n$. Since $(q, n) = 1$, we get that $(q, f(q)) = 1$. Now here is my main idea: we keep composing $f$ to get more numbers who are relatively prime. It would nice if the sequence $S = \{q, f(q), f^2(q), f^3(q), \ldots \}$ only had terms who are pairwise relatively prime. This may not be the case though. It is almost the case though. Note that by (a), for $i < j$, $(f^i(q), f^j(q)) = 1$ if $(f^{j-i}(q), q) = 1$. Because of this, assume that the terms are not relatively prime. Before proceeding, I claim that $S$ has infinitely many prime factors. Note that since $n \le f(n) \le n+2012$, the density of $S$ is at least $\frac{1}{2012}$. But it's obvious that the number only having a certain finite set of prime factors has density $0$, contradiction. Now take the smallest $d > 0$ such that $q | f^d(q)$. Now keep going along in $S$ until we find a term with a new prime factor $p$ (because of infinitely many prime factors). Call this term $f^e(q)$. Then $p | f^e(q)$. (Then $e$ is minimal) Now we look at the new sequence $S' = \{p, f(p), f^2(p), \ldots \}$. We claim that all the terms in $S'$ are relatively prime. As above, we assume that $p | f^i(p)$ for contradiction. Then $(f^i(p), f^e(q)) > 1 \implies q | f^{i-e}(p)$ or $p | f^{e-i}(q)$. Then latter is impossible by minimality. So let $c = i-e$, and therefore $q | f^c(p)$. Now take a minimal $c' > 0$ such that $q | f^{c'}(p)$. Therefore, $(f^d(q), f^{c'}(p)) > 1 \implies p | f^{d-c'}(q)$ or $q | f^{c'-d}(p)$. Both easily contradict minimality. Now, look at the terms $f^x(p), f^{x+1}(p), \ldots, f^{x+2014}(p)$. These terms are all relatively prime, and we choose them such that they all have only large prime factors. Then by CRT, find an $n$ such that $f^{x+1}(p) | n$ $f^x(p), f^{x+2}(p), f^{x+3}(p) | n+1$ $f^{x+4}(p)|n+2$ $\vdots$ $f^{x+2014}(p) | n+2012$. BY CRT, and $n$ exists, and one can easily check that $n$ cannot take any values from $n$ to $n+2012$ by using (a). So we get a contradiction, and we are done.

This is used as a lemma which I prove here http://artofproblemsolving.com/community/c6h580311p3426135

By considering $f(p)$ for all primes $p$, it follows that there are infinitely many primes that divide some term of $f$. Take primes $p_i > i$ such that $p_i\mid f(n_i)$ and the $p_i, n_i$ are all distinct for $i=1,...,2012$. Then by Dirichlet there are infinitely many primes $p$ such that $p_i\mid p+i$. On the other hand, by taking $p>n_i$, it follows $\gcd(f(p), f(n_i))=1$; thus $f(p)\neq p+i$ as otherwise $p_i\mid f(p)$. Thus $f(p)=p$. We can do this infinitely many times, generating infinitely many primes $p$ that satisfy $f(p)=p$. Now suppose $f(p)=m$ for some prime $p$ such that $p\nmid m$. Take $a$ such that $p_i\mid am+i$ and $p\nmid a$ for $p, p_i$ distinct and $f(p_i)=p_i$ and $i=1,2,...,2012$ - this is doable by CRT. By taking $p_i>i$, we cannot have $p_i\mid am$ or otherwise $p_i\mid i$. Thus $\gcd(am, p_i)=1$, so $\gcd(f(am), p_i)=1$. Thus $f(am)=am$. On the other hand, $\gcd(p, am)=1$ as $p\nmid a$ and $p\nmid m$. But $f(p)=m$ and $f(am)=am$, contradiction unless $m=1$, impossible as $m = f(p)\ge p>1$. Thus $p\mid f(p)$. Finally, suppose a prime $q\mid f(p)$ and $q\neq p$. Since $q\mid f(q)$, it follows $q\mid \gcd(f(p), f(q))$. But then $\gcd(p,q)=1$, contradiction! Thus, $f(p)=p^k$ for some $k$. Therefore, if $p\mid f(n)$, $p$ must divide $n$; otherwise, $\gcd(n,p)=1$, so $\gcd(f(n), f(p))=1$, contradicting $p\mid f(n)$ and $p\mid f(p)$.

The first condition follows that if $\gcd (f(m),f(n))>1$ then $\gcd (m,n)>1$. Assume the contrary, there exists $p \mid m+l=f(m)$ for some $m,p$ so that $p \nmid m$. Now, we pick $2013^2-1$ distinct primes $p_{i,j}>2012$ for $0 \le i,j \le 2012$ (except $p_{0,0}=1$) so that $\gcd (p_{i,j}, pm)=1$ for all $0 \le i,j \le 2012$. According to CRT, there exists $n_0$ so that $p \nmid n_0$ and $p_{i,0}p_{i,1}p_{i,2} \cdots p_{i,2012} \mid n_0+i$ for all $0 \le i \le 2012$. Next, we pick $n_1$ so that $\gcd (n_1,n_0)=1, p \mid n_1, \gcd (n_1,m)=1$ (we can choose such $n_1$ because $p \nmid m$) and $p_{0,i}p_{1,i},p_{2,i} \cdots p_{2012,i} \mid n_1+i$ for all $0 \le i \le 2012$. If $f(n_1) \ne n_1$, we can see that $\gcd \left( n_0+i,n_1+j \right)>1$ for all $0 \le i,j \le 2012, j \ne 0$ but $\gcd (n_0,n_1)=1$, a contradiction to (a). Thus, we must have $j=0$ or $f(n_1)=n_1$. However, $\gcd (n_1,m)=1$ and $\gcd \left( f(n_1),f(m) \right)= \gcd (n_1,f(m)) \ge p$, a contradiction to (a). Thus, there doesn't exists $p,m$ so that $p \mid f(m)$ and $p \nmid m$. We obtain the desired result.

We'll deal with $p>2012, p<2012$ separately. First, suppose there exists $p_1>2012, p_1\not | N$ with $p_1|f(N)$. Our goal is to construct some more "bad" primes. Let $M = \phi (\text{lcm} (1,2,...2013)^2N^{2013})$ and consider the prime factorization of $f(p_1^{kM})$ for large $k$. Clearly for any $p<2012$ or $p|N$, we have $v_p (f(p_1^{kM})) \le \text{max}_{0\le i\le 2012} v_p ((p_1^{kM}-1)+(i+1))= v_p (i+1)$, where the final equality holds since $\text{lcm} (1,2,...2013)^2N^{2013}|p_1^{kM}-1 \implies v_p (p_1^{kM}-1) \ge v_p (\text{lcm} (1,2,...2013)^2 N^{2013})>v_p (i+1)$. Therefore, $p^{v_p (f(p_1^{kM}))}$ is bounded for all such $p$, so by size arguments, for a large enough $n_1=km$ we can find a prime $p_2>2012$ dividing $f(p_1^{n_1})$. It's clear that $p_2\neq p_1$ because if they were equal, then by a) we would have $\gcd (p_1^{n_1} , N)>1$, a contradiction. Now, suppose we've found $k$ pairwise distinct primes $p_1,p_2,...p_k$ such that $p_1|f(N)$, $\gcd (p_i,N)=1$ for all $i$, and for each $i=2,3,...k$, there exists $n_{i-1}$ with $p_k | f(p_{i-1}^{n_{i-1}})$. We'll show that one can find a new prime $p_{k+1}>2012$ and some $n_k$ satisfying $p_{k+1}\not | n, p_{k+1} | f(p_k^{n_k})$. This is easy; simply let $n_k$ be a large multiple of $M$ and $\phi ((p_1p_2...p_{k-1})^{2012})$; then similarly to above, if $p\le 2012$, $p|N$, or $p\in \{p_1,p_2,...p_{k-1}\}$, we'll have by Euler's Theorem $v_p ( f(p_k^{n_k})) \le \text{max}_{0\le i\le 2012} v_p ( (p_k^{n_k}-1) + (i+1)) = \text{max}_{0\le i\le 2012} v_p (i+1)$, which is constant, and if $p_k| f(p_k^{n_k})$, then since $p_k| f(p_{k-1}^{n_{k-1}})$, by a) we deduce $\gcd (p_k^{n_k}, p_{k-1}^{n_{k-1}})>1$, a contradiction as $p_{k-1}\neq p_k$. In either case, for large enough $n_k$, by size arguments $f(p_k^{n_k})$ must have a prime divisor $p_{k+1}$ which is not equal to one of the $p$'s. Now take a number $n$ satisfying $p_1|n, p_2|n+1, p_3|n+2, ... p_{2013} |n+2012$, and add the condition $N|n+1$; some such $n$ exists by CRT since the numbers $N,p_1,p_2,...p_{2013}$ are pairwise coprime. Suppose $f(n)=n+i$ for some $i>0$, so then $p_{i+1} | f(n), p_{i+1} | f(p_i^{k_i})\implies \gcd (n, p_i^{k_i})>1\implies p_i|n$, a contradiction as $p_i|n+i-1$ and $p_i \ge 2013 >i-1$. Therefore we conclude $f(n)=n$, so $p_1|f(n), f(N)\implies \gcd (n,N)>1$, a contradiction. Now we've shown for any $p>2012$ that $p|f(n)\implies p|n$. We only have to deal with primes $2\le p\le 2012$ now. Take any such prime $p_0$ and suppose for some $n'$ that $p_0|f(n'), p_0\not | n'$. Select primes $p_1,p_2,...p_{2012}>2012$ coprime to $n'$, and find some $n$ by CRT with $p_i|n+i$ for each $i$ and $n'|n-1$. Then if $f(n)=n+i$ for some $i>0$, we deduce that $p_i|f(n)\implies p_i|n$, but $p_i|n+i$, so this is a contradiction. It follows that $f(n)=n\implies p_1|f(n)$, so $p_1|f(n')\implies \gcd (n,n')>1$, a contradiction, so we're done.

In what follows, a positive integer $n$ is called a prime power if $n=p^k$ for some prime $p$ and positive integer $k$. Claim: Our $f$ takes prime power values for prime power inputs. Further, if $f(p)$ is a power of prime $q$ ($p$ is a prime), $f(p^k)$ is a power of $q$ for all $k\in\mathbb N$. Proof: (Warning: the proof of this part is fairly combinatorial and clumsily explained, but I guess it conveys the main idea better than a rigorous proof.) By CRT, it's not hard to find $2012$ consecutive numbers, none of which are prime powers: just set $N\equiv -i\pmod{p_iq_i}$ for some distinct primes $p_iq_i$. So there are arbitrarily large runs of non-prime power numbers. Let $N$ be a prime power so that $N+1,\cdots ,N+2012$ are all non-prime powers. Consider all the prime powers in $\{1,\cdots ,n\}$, partitioned into boxes like so $$\begin{array}{c} \boxed{2,2^2,\cdots ,2^i,\cdots }\\ \boxed{3,3^2,\cdots ,3^i,\cdots } \\ \vdots \\ \boxed{p_k,p_k^2,\cdots p_k^i,\cdots } \end{array}$$There are $k$ boxes here. So there are only $k$ primes $\le N$. Consider the set $A=\{2,3,\cdots p_k\}$; it holds $k$ numbers that are pairwise relatively prime, so their images are also pairwise relatively prime. But the only primes available for their images are $2,3,\cdots ,p_k$, since $f(p_k)\le N+2012$ and the numbers $N,N+1,\cdots N+2012$ don't supply any new primes. So the image of each of them must be divisible by a unique prime among $2,\cdots ,p_k$. So for any $p\in A$, $f(p)=\sigma (p)^k$, where $\sigma$ is some permutation on $A$. Now if $f(p^i)$ has some other prime divisor than that assigned to $f(p)$, it must clash with some some other prime in another box, which is impossible since they are in different boxes. This proves our claim, since $N$ can be as large as we like. $\square$ Now we'll prove that each prime gets mapped to its own power. Suppose not; then there is a prime so that $f(p)=q^m$ and $q$ is a prime $\ne p$. Then for any $k$, $f(p^k)=q^\ell$ (for some $\ell$ depending on $k$) because of the previous paragraph. Of course, this forces $$p^k<q^\ell\le p^k+2012\implies \ell\in \left( \frac{\log p^k}{\log q},\frac{\log (p^k+2012)}{\log q}\right].$$But the length of this interval is $\frac{\log\left(1+\frac{2012}{p^k}\right)}{\log q}$ which gets as tiny as we want for $k\to\infty$, and the leftmost point of this interval is simply $k\log _qp$ whose fractional part can get as small as we want for some $k$ as large as we wish, since $\{ k\alpha \}$ is dense in $(0,1)$ for $\alpha\in \mathbb R\setminus\mathbb Q$. Therefore we can have $k$ so that that interval fails to contain an integer, creating a serious existential crisis for $\ell $, which proves our claim. $\square$ Now it's time to finish. Suppose there is $n\in\mathbb N$ and a prime $p$ so that $p|f(n)$ but $p\not| n$. Then $(n,p)=1\implies (f(n),f(p))=1$, which contradicts $p|f(n)$ and $f(p)=p^k$, and we're done! $\blacksquare$

If there exists an infinite number of primes $p$ such that $p$ does not divide $f(p)$ we can find primes $p_1,p_2, ...,p_{2013}$ such that $p_i$ does not divide $f(p_j)$ for any $1\le i,j\le 2013$. Indeed, suppose that we have found primes $p_1,p_2, ... , p_t$ with this property. Look now at primes $q$ such that $q$ does not divide $f(q)$ and $q>p_1,...,p_t$. There exists at most one such prime with $p_i|f(q)$; if there were two, say $q,r$, we have $(q,r)=1$ so $(f(q),f(r))=1$, but $p_i|f(q),p_i|f(r)$, a contradiction. Therefore, choosing $p_{t+1}$ big enough we are assured that $p_i$ does not divide $f(p_{t+1})$ for any $1\le i\le t$. Take $q_i$ a prime divisor of $f(p_i)$ for all $1\le i\le 2013$ . Obviously, $q_1,q_2,...,q_{2013}$ are distinct because $(f(p_i),f(p_j))=1$ for $i\ne j$ and $q_i\ne p_j$ for any $1\le i,j\le 2013$ by the way we chose $p_1,p_2,...,p_{2013}$. By CRT we can find $n$ such that $n\equiv 1(\mathrm{mod}\ p_1p_2...p_{2013})$ and $n\equiv -i+1 (\mathrm{mod}\ q_i)$ for all $1\le i\le 2013$. Because $p_i$ does not divide $n$, we have $(f(n),f(p_i))=1$, hence $(f(n),q_i)=1$ for all $i$. However, $f(n)\in \{ n,n+1,...,n+2012\}$ and $n+i$ is divisible by $q_{i+1}$ for all $0\le i\le 2012$, a contradiction. Therefore there exists a finite number of primes $p$ such that $p$ does not divide $f(p)$. Suppose that $p|f(p)$ for all $p\ge N$. If $n<N$ and $p|f(n)$, we have that $p<N$. If $p\ge N$ then $p|f(p)$; in the same time, $p\ge N>n$ so $(p,n)=1$, whence $(f(p),f(n))=1$, so $(p,f(n))=1$, a contradiction. Let $q_1,q_2,...,q_k$ be the primes less than $N$ and let $t_i$ be the number of distinct prime divisors of $f(q_i)$. On one hand, $t_i\ge 1$ as $f(q_i)\ge q_i>1$, so $t_1+...+t_k\ge k$. On the other hand, by the previous observation, the prime divisors of $f(q_1),...,f(q_k)$ have to be among $q_1,...,q_k$ and $f(q_i)$ and $f(q_j)$ are coprime for $i\ne j$ , so $t_1+...+t_k\le k$. We must have equality, so $t_i=1$ for all $i$, i.e. each $f(q_i)$ is a power of a prime. We conclude that $f(q_i)=q_{\sigma (i)}^{\alpha_i}$ with $\sigma \in S_k$. Suppose there exists $i\ne j$ such that $\sigma (i)= j$. The only prime divisor of $f(q_i^t)$ is $q_j$ for any $t$. Indeed, $(q_i^t,q_{\ell})=1$ for all $\ell\ne i$, so $(f(q_i^t),f(q_{\ell}))=1$ for all $\ell\ne i$, so $f(q_i^t)$ can't be divisible by other prime than $q_j$ less than $N$. It also can't be divisible by a prime $p$ greater than $N$ because $p|f(p)$ and $(p,q_i)=1$. Thus $f(q_i^t)=q_j^{\gamma}$.

that we can find $\beta,t\in \mathbb{N}$ such that $q_j^{\beta}<q_i^t<q_i^t+2012<q_j^{\beta+1}$ . However, $f(q_i^t)$ has to be a power of $q_j$, so we have again arrived at a contradiction, whence $\sigma(i)=i$ for all $i$. We finally conclude that $p|f(p)$ for all primes $p$ and the conclusion follows easily.

First, note that it is easy to construct by CRT and Dirichlet infinitely many primes $p$ such that none of $p+1,\ldots,p+2012$ are prime powers. Then, note that $2\le f(2),\ldots,f(p)\le p+2012$ (inputs are primes up to $p$) are pairwise relatively prime, so each must be a power of a different prime among $2,\ldots,p$ which are the only primes in $[2,p+2012]$. This forces $f(p)=p$, as $p+1,\ldots,p+2012$ are not prime powers. By a similar argument, we have that if $p<p_1<\ldots p_k<q$ are primes with $f(p)=p$ and $f(q)=q$, then $f(p_1),\ldots,f(p_k)$ each are a power of a different prime among $p_1,\ldots,p_k$. Now, suppose that $f(p)$ is a power of $q$ for primes $p\ne q$, and let $r,s>2012$ be prime fixed points with $s>qr>p$. Then, considering the numbers $f(2),\ldots,f(qr),\ldots,f(s)$ where the list consists of all primes from $2$ to $s$ except $q,r$ and including $qr$, we have that $f(qr)$ only has factors of $p,r$. As $r>2012$, the only number in $[qr,qr+2012]$ divisible by $r$ is $qr$. But this is divisible by $q$, so if $f(qr)=qr$ then we have a contradiction as $p$ is relatively prime to $qr$. Thus, $f(qr)$ is a power of $p$. Now, we must have $f(q)$ is a power of $p$ as otherwise some other prime $t$ satisfies $f(t)$ is a power of $p$, a contradiction as $t$ would be relatively prime to $qr$. Thus, if $p>q$ are sufficiently large, then $p^2>p+2012$, so we must have $f(q)=p$. Thus, $f(p)\ge q^2>q+2024\ge p+2012$, a contradiction. Hence, $f(p)=p$ for sufficiently large primes $p$. Now, suppose that $p>q$ is not sufficiently large, so $f(q)$ is a power of $p$ by the above. Then, we have that $f(qr)$ is a power of $p$ for all sufficiently large primes $r$. It is easy to find such an $r$ with $p^k<qr<qr+2012<p^{k+1}$, obtaining a contradiction, as desired. We're clearly done now, as $f(p)$ is a power of $p$ for any prime $p$.

First since $f(1)$ and $f(1)$ are relatively prime, $f(1) = 1$. Furthermore, $f(n) > 1$ for $n > 1$, so each $f(n)$ is divisible by a prime for $n > 1$. For each prime $p$ and positive integer $k$, define the $p^k$-space, $S(p^k)$, to be the set of prime divisors of $f(p) f(p^2) \dots f(p^k)$. Let $p_1 = 2, p_2 = 3, p_3 = 5, \dots$ be the primes in increasing order. Lemma 1. There exist infinitely many $i$ such that $p_{i+1} - p_i > 2012$. Proof. Simply choose $p_i$ to be the largest prime less than $n! + 2$ for arbitrarily large $n \ge 2014$. Then the numbers $n! + 2, n! + 3, \dots, n! + 2014$ are composite, so $p_{i+1} > n! + 2014 > p_i + 2012$. Lemma 2. For every positive integer $N$, the spaces of the first $N$ primes each consist of exactly one prime. Furthermore, if we associate each $p$-space with the prime it contains, then for some $n > N$, the spaces of the first $n$ primes permute the first $n$ primes. Proof. First, the different $p$-spaces are disjoint because of condition (a). Next, choose $n > N$ such that $p_{n+1} - p_n > 2012$. Because $f(p) \le p + 2012$ by condition (a), $f(p_i) < p_{n+1}$ for $1 \le i \le n$. Hence, no prime larger than $p_n$ can be in the space of any of the first $n$ primes. This means the union of the spaces of the first $n$ primes is a subset of the first $n$ primes. However, the union of disjoint spaces has at least $n$ elements (since spaces are non-empty), and the set of the first $n$ primes has exactly $n$ elements. Therefore, the union must equal the set of the first $n$ primes. As a result, each of the spaces contains exactly one prime, and these primes permute the first $n$ primes. This proves the Lemma. Lemma 3. $S(p^k) = S(p)$ for primes $p$ and $k \ge 2$. Proof. Clearly $S(p)$ is a subset of $S(p^k)$. Suppose on the contrary that $q \in S(p^k)$ but $q \notin S(p)$. By Lemma 2, there exists a prime $r$ such that $S(r) = \{ q \}$. This means $f(r) = q$. Since $q \notin S(p)$, we have $p \neq r$. But $f(p^i)$ for some $i \ge 1$ is divisible by $q$, contradiction to condition (a) since $r$ and $p$ are relatively prime. Therefore, the $p^k$-space must contain exactly one element. The above argument also establishes that $S(p^k) = S(p)$ for any $k \ge 2$. Lemma 4. $S(p) = \{ p \}$ for any prime $p$. Proof. Suppose $S(p) = \{ q \}$, $q \neq p$. This and Lemma 3 means $f(p^k)$ is a power of $q$ for all positive integers $k$. In particular, if we let $N = q^{11}$, then $f(p^{M \phi(N)})$ is a power of $q$ for all positive integers $M$. Since $f(p^{M \phi(N)}) > p^M$, by choosing $M$ large we can have $f(p^{M \phi(N)})$ divisible by $N$. However, notice that by Euler's theorem, $p^{M \phi(N)} + s \equiv 1 + s \neq 0 \pmod N$, for $0 \le s \le 2012$, because $N \ge 2^{11} = 2048 > 2013$. Thus, $f(p^{M \phi(N)})$ is not divisible by $N$, contradiction. This shows that $S(p) = \{ p \}$ for any prime $p$. To conclude, we simply observe that if $p \nmid n$, then $p$ and $n$ are relatively prime, and so $f(p)$ and $f(n)$ are relatively prime. However, $f(p)$ is divisible by $p$ by Lemma 4, so $p \nmid f(n)$. Thus, the result follows by contrapositive.

v_Enhance wrote: Let $\mathbb N$ be the set of positive integers. Let $f: \mathbb N \to \mathbb N$ be a function satisfying the following two conditions: (a) $f(m)$ and $f(n)$ are relatively prime whenever $m$ and $n$ are relatively prime. (b) $n \le f(n) \le n+2012$ for all $n$. Prove that for any natural number $n$ and any prime $p$, if $p$ divides $f(n)$ then $p$ divides $n$. Fix a pair $(p,m)$ with $p$ prime and $p \mid f(m)$ but $p \nmid m$. Then we choose primes $p_{i,j}>2012mp$ for $1 \le i \le 2012, 0 \le j \le 2012$ and pick $N,M$ as follows: $$M \equiv 1 \pmod{m}$$$$N \equiv 1 \pmod{M}$$$$M+i \equiv N+j \equiv 0 \, \, (\bmod \, p_{i,j})$$and $p \mid M$. Observe that if $f(M)>M$ then $\gcd(f(N), f(M))>1$ contradicting $\gcd(N,M)=1$. Thus, $f(M)=M$ and now $\gcd(M,m)=1$ so $\gcd(f(M), f(m))=1$. But $p \mid M$ and $p \mid f(m)$ so we obtain the desired contradiction! $\blacksquare$

Through the solution, let $q, p_i$ denote primes. We will spam CRT and this following fact which follows from (a) (call this $\star$ ) through the solution: If $q | f(p)$ and $q | f(m)$ then $p | m$. Let $G = \{ q : q \text{ divides f(p) for some prime p} \}$, and for $q \in G$, let $g(q)$ be THE prime such that $q | f(g(q))$. It's easily seen that $G$ is infinite. Call a prime number pathetic if $g(q) \neq q$. Claim There are finitely many pathetic primes Proof : Assume not. Then construct $2013$ primes $p_0, p_1, \cdots, p_{2012}$ as follows: Initially $i = 0$.Firstly delete all elements of $G$ which are smaller than $10^{100000}$. Then set $p_i$ to be the smallest element of $G$ such that $g(p_i) \neq p_i$. Delete $p_i$ and all primes $q$ such that $g(q) = g(p_i)$ from $G$. Then delete $g(p_i)$ from $G$, if it's there. Increment $i$ by one and go to the beginning of this para. By construction, $p_0, p_1, p_2, \cdots, p_{2012}, g(p_0), g(p_1), \cdots, g(p_{2012})$ are all distnict. Pick an $x$ by CRT such that for all $0 \leq i \leq 2012$, we have $$ x \equiv -i \mod p_i $$$$ x \equiv 1 \mod g(p_i)$$ Now, let $j = f(x) - x$. By construction, $p_i | f(x)$. By $\star$, $g(p_i) | x$. But that's impossible by construction, and our initial claim was false $\blacksquare$ Claim There ain't any pathetic prime. Proof : Suppose $q$ is a pathetic prime with $g(q) = p \neq q$. Let $p_0, p_1, \cdots, p_{2012}$ be a bunch of huge ($\geq 10^{10000}$) nonpathetic primes. By CRT, pick $x$ such that $$ x \equiv 0 \mod q $$$$ x \equiv 1 \mod p$$$$ x \equiv i \mod p_i $$($1 \leq i \leq 2012$) Then let $j = f(x) - x$. If $j \neq 0$, then $p_j | f(x) \overset{\star}{\Rightarrow} p_j | x$, but which is a contradiction since $|p_j - x| < 2013 << p_j$. So $j = 0$, and $f(x) = x$. Then $q | f(x)$, and by $\star$, $p$ divides $x$, but which is a contradiction to the construction. $\blacksquare$ So returning to the main problem, if $p | f(m)$, then by $\star$ and $p | f(p)$, we get $p | m$ as desired.

The key CRT step is the same in this solution, but I think the argument leading up to it is a little cleaner. We argue by contradiction, and assume there is some prime $p_0\mid f(n)$ but $p_0\nmid n$. Then there is some prime $q_0\mid f(p_0)$ with $q_0\neq p_0$. Claim: There are infinitely many primes dividing $f(p)$ for some prime $p$. Proof: This is clear since $\gcd(f(p), f(q))=1$ for primes $p$ and $q$. $\blacksquare$ By the claim, we can select primes $p_i$ and $q_i$ that satisfy $$q_1\mid f(p_1), q_2\mid f(p_2), \dots, q_{2012}\mid f(p_{2012})$$with all the $q_i$ distinct (but the $p_i$ may equal the $q_i$). Now by Chinese remainder theorem we can construct $n$ such that \begin{align*} n+1&\equiv 0\pmod {q_i} \\ n &\not \equiv 0 \pmod {p_i} \end{align*}for $0\le i\le 2012$ (recalling that $p_0\neq q_0$). But since $p_i\nmid n$ for all $i$, $q_i\nmid f(n)$ for all $i$, which contradicts $n\le f(n)\le n+2012$.

Ankoganit wrote: In what follows, a positive integer $n$ is called a prime power if $n=p^k$ for some prime $p$ and positive integer $k$. Claim: Our $f$ takes prime power values for prime power inputs. Further, if $f(p)$ is a power of prime $q$ ($p$ is a prime), $f(p^k)$ is a power of $q$ for all $k\in\mathbb N$. Proof: (Warning: the proof of this part is fairly combinatorial and clumsily explained, but I guess it conveys the main idea better than a rigorous proof.) By CRT, it's not hard to find $2012$ consecutive numbers, none of which are prime powers: just set $N\equiv -i\pmod{p_iq_i}$ for some distinct primes $p_iq_i$. So there are arbitrarily large runs of non-prime power numbers. Let $N$ be a prime power so that $N+1,\cdots ,N+2012$ are all non-prime powers. Consider all the prime powers in $\{1,\cdots ,n\}$, partitioned into boxes like so $$\begin{array}{c} \boxed{2,2^2,\cdots ,2^i,\cdots }\\ \boxed{3,3^2,\cdots ,3^i,\cdots } \\ \vdots \\ \boxed{p_k,p_k^2,\cdots p_k^i,\cdots } \end{array}$$There are $k$ boxes here. So there are only $k$ primes $\le N$. Consider the set $A=\{2,3,\cdots p_k\}$; it holds $k$ numbers that are pairwise relatively prime, so their images are also pairwise relatively prime. But the only primes available for their images are $2,3,\cdots ,p_k$, since $f(p_k)\le N+2012$ and the numbers $N,N+1,\cdots N+2012$ don't supply any new primes. So the image of each of them must be divisible by a unique prime among $2,\cdots ,p_k$. So for any $p\in A$, $f(p)=\sigma (p)^k$, where $\sigma$ is some permutation on $A$. Now if $f(p^i)$ has some other prime divisor than that assigned to $f(p)$, it must clash with some some other prime in another box, which is impossible since they are in different boxes. This proves our claim, since $N$ can be as large as we like. $\square$ Now we'll prove that each prime gets mapped to its own power. Suppose not; then there is a prime so that $f(p)=q^m$ and $q$ is a prime $\ne p$. Then for any $k$, $f(p^k)=q^\ell$ (for some $\ell$ depending on $k$) because of the previous paragraph. Of course, this forces $$p^k<q^\ell\le p^k+2012\implies \ell\in \left( \frac{\log p^k}{\log q},\frac{\log (p^k+2012)}{\log q}\right].$$But the length of this interval is $\frac{\log\left(1+\frac{2012}{p^k}\right)}{\log q}$ which gets as tiny as we want for $k\to\infty$, and the leftmost point of this interval is simply $k\log _qp$ whose fractional part can get as small as we want for some $k$ as large as we wish, since $\{ k\alpha \}$ is dense in $(0,1)$ for $\alpha\in \mathbb R\setminus\mathbb Q$. Therefore we can have $k$ so that that interval fails to contain an integer, creating a serious existential crisis for $\ell $, which proves our claim. $\square$ Now it's time to finish. Suppose there is $n\in\mathbb N$ and a prime $p$ so that $p|f(n)$ but $p\not| n$. Then $(n,p)=1\implies (f(n),f(p))=1$, which contradicts $p|f(n)$ and $f(p)=p^k$, and we're done! $\blacksquare$ Your proof is wrong

hellomath010118 wrote: Your proof is wrong Care to elaborate?

Suppose $r\mid f(x)$ but $r\nmid x$ where $r$ is a prime. We'll derive a contradiction from this. Note that $\gcd(f(p),f(q))=1$ where $p$ and $q$ are any primes. From this, pick $2012$ primes $p_1,\ldots,p_{2012}$ such that $f(p_i)$ has all of its prime factors much larger than $x$ and $r$, and also $p_i$ much larger than $x$ and $r$. Furthermore, pick large enough primes so that $f(p_i)$ and $p_j$ are relatively prime for $j\ne i$. Now, let $\alpha$ be the unique residue mod $M:=\prod_{i=1}^{2012}p_if(p_i)$ such that $\alpha\equiv -i\pmod{p_if(p_i)}$ for all $i$ (this exists by CRT). Note that $\gcd(\alpha,M)=1$ since all the prime factors of $p_if(p_i)$ are much larger than $i\le 2012$. Now, if $n\equiv\alpha\pmod{M}$, then clearly $\gcd(n,p_i)=1$ for all $i$ by the previous sentence, so $\gcd(f(n),f(p_i))=1$ for all $n$. We see that \[f(n)\equiv\alpha,\alpha+1,\ldots,\alpha+2012\pmod{M}.\]If $f(n)\equiv\alpha+j$ for $1\le j\le 2012$, then $\alpha+j\equiv 0\pmod{p_jf(p_j)}$, so $\gcd(f(n),f(p_j))>1$. Thus, $f(n)\equiv\alpha\equiv n\pmod{M}$. Since $M$ is very large, this means that $f(n)=n$. Thus, there exists an $M$ with all of its prime factors much larger than $r$ and $x$, and a number $\alpha$ relatively prime to $M$ such that $f(n)=n$ for all $n\equiv\alpha\pmod{M}$. By CRT, pick \begin{align*} n&\equiv\alpha\pmod{M} \\ n&\equiv 1\pmod{x} \\ n&\equiv 0\pmod{r}, \end{align*}which we can do since $\gcd(r,x)=1$, and all the prime factors of $M$ are way larger than $r$ and $x$, so $\gcd(M,x)=\gcd(M,r)=1$. Now, $\gcd(n,x)=1$, but \[\gcd(f(n),f(x))=\gcd(n,f(x))\ge\gcd(n,r)=r,\]so we have our desired contradiction.

lemma: there's exist infinitly many primes such that $p_{i+1}-p_{i}>2012$ the proof: consider $p_i$ the biggest prime smaller than $n!+2$ for $n \ge 2013$ we have $p_{i+1}$ is greater than $(n+1)!$ let $p,q $ denotes different primes claim(1): $\forall p$ there exists $a$ such that $p|f(a)$ suppose $p_i$ doesnt divide any $f(x) \forall x \in N$ then $f(p_{i+j}) \ge p_{i+j+1}$ but for large enough $j$ we would have $p_{i+j+1} > p_{i+j} +2012$ contradiction claim(2):$f(p)$ is a power of a prime suppose $f(p) $ has two distinct prime and we will have a contradiction same as claim(2) claim(3): $f(p^m)=f(p)^k$ if $q|f(p^m)$ and $q$ doesn't divide $f(p)$4 then we will have a contradiction in the same way as claim(1) because $gcd(f(p^m),f(q))=1$ claim(4): $f(p)=p$ suppose $f(p)=q>p$ then $f(p^n)=q^m$ then $\forall n$ there exists m such that $p^n +2012 > q^m > p^n$ which is clearly false finally, if there's $q|f(n)$ $gcd(f(n),f(q)) \neq 1$ then $q|n$ and we win

Here's my solution when I was a high school student. For sake of contradiction, suppose $p|f(n)$, $p\not| n$ for a prime $p$ and $n\in\mathbb{N}$. Let $S=\{q: q$ is a prime divisor of $f(p^k)$ for some positive integer $k\}$. Since $\gcd(p,n)=1$, for every positive integer $k$, $\gcd(f(n),f(p^k))=1 \Rightarrow \gcd(p,f(p^k))=1$. So, $p\not\in S$. Claim 1. $|S|\leq 2012$

Claim 3. Suppose there exists distinct primes $p_1,\cdots,p_s>P$ and a positive integer $k$ such that $p^k\equiv -i(\text{mod} p_i )$ for every $1\leq i\leq s$. Then, there exists a prime $p_{s+1}$ and a positive integer $k'$ such that $p_{s+1}>P$, $p_{s+1}\not\in\{p_1,\cdots,p_s\}$, $p^{k'}\equiv -i(\text{mod} p_i )$ for every $1\leq i\leq s+1$

By Claim 2 and 3, there exists distinct primes $p_1,\cdots,p_{2012}\not\in S$ and a positive integer $k$ such that $$p^k \equiv -i(\text{mod} p_i ),\quad^\forall i=1,\cdots,2012$$Therefore, $f(p^k)\not= p^k+i$ for every $i=1,\cdots,2012$. Hence $f(p^k)=p^k$. This contradicts to $p\not\in S$.

Solution without CRT: Let $S(p)$ be the set of primes $q$ that divide $f(p^{k})$ for some $k$. First, observe that $S(p)\cap S(q) = \emptyset$ (since $\gcd(p^{i}, q^{j}) = 1$, so $\gcd(f(p^{i}), f(q^{j})) = 1$). I claim that $p\in S(p)$. If for every prime $q\in S(p) > 2013$, and if $p\not\in S(p)$ then consider some $p^{k}$ such that $p^{k} \equiv 1\mod q$ for all $q\in S(p)$. Since $q > 2013$, this means that for any $p^{k} + r$, where $0 \leq r \leq 2012$, we have $p^{k} + r \not\equiv 1\mod q$, however those are the only possible values of $f(p^{k})$ (per the second condition), which gives a contradiction. Thus, $p \in S(p)$ for any $S(p)$ where all its elements are greater than $2012$. Then, we are left with the sets $S(p_{1}), S(p_{2}), \ldots S(p_{k})$, which all contain an element less than $2012$. Since they are disjoint, there are only finite such primes. Then, if $p_{i}\not\in S(p_{i})$, for all $n$ we have $f(p_{i}^{n}) = p_{i}^{n} + r$, where $0 < r \leq 2012$. There are infinite possible values for $n$, so for some $r$, there are infinite values of $n$ such that $f(p_{i}^{n}) = p_{i}^{n} + r$. Then, by Kobayashi, there are infinitely many primes dividing $p_{i}^{n} + r$ (since finite primes divide $p_{i}^{n}$), which also means $S(p_{i})$ is an infinite set. However, since there are only a finite number of $S(p)$ where $p\not\in S(p)$, and all of those sets are disjoint, there can only be finite many values in $S(p_{i})$, a contradiction. Thus, $p_{i}\in S(p_{i})$. Now, since $p\in S(p)$, and all sets are disjoint, this means no $q\neq p$ exists where $q \in S(p)$, or else $S(p)\cap S(q)\neq \emptyset$. Thus, the only prime that divides $f(p^{k})$ is $p$. Then, consider $f(n) = f(p_{1}^{e_{1}}p_{2}^{e_{2}}\ldots p_{i}^{e_{i}})$. If $q \neq p_{1}, p_{2}, \ldots p_{i}$ where $q | f(n)$, then $\gcd(f(n), f(q)) \neq 1$, but $\gcd(n, q) = 1$, a contradiction. Thus, for every prime $p$ that divides $f(n)$, we must have $p | n$, which is what we wanted to prove.

Call a prime $p$ foreign if there exists an $n$ such that $p |f(n)$ but $p \nmid n$ and call a number $n$ weird if there is a foreign prime dividing $f(n)$. The problem gives that if $p$ is a foreign prime. Then $p^k$ is weird for all $k$, this is easy to see. So now suppose there exists a foreign prime. I claim there will in fact exist infinitely many such primes. Suppose not and say $P$ is the finite set of such primes Note that for every $k$, there is some $1 \le z \le 2012$ such that $p^k + z$ has all its prime divisors in $P$. This is already a contradiction by Kobayashi on the one $z$ that comes infinitely many times, but I'll do a normal proof. Suppose $p_1, p_2, \cdots, p_m$ are the primes of $P$ excluding $p$. For each $p_i$, let the order of $p$ mod $p_i$ be $d_i$ and say $v_i = v_p(p^{d_i} - 1)$. Suppose we have $p_l | p^k + z$ and $p^{k+t} + z$, then $p_l | p^t - 1$ as well and if $p_l \nmid t$, then the $v_{p_l}$ of this thing is only $v_i$. So for all primes $p_i$, we pick $t$ such that this is true, which is easily seen to be possible. So we can make a large $a$ such that $p^a + z$ for any $1 \le z \le 2012$ has only prime divisors in a finite set $P$, and each has at most a fixed $v_p$, clearly impossible. So $P$ is infinite. Note that if $p,q \in P$, then any foreign prime divisor of $f(p^k)$ and $f(q^m)$ is distinct and in $P$. So let $q$ be a sufficiently large prime in $P$ and consider all primes in $P$ (say $s$ of them) and their powers containing new foreign divisors below $q$, this clearly has at least $s+2012$ numbers if $q$ is big enough, but each needs at least a new foreign prime, but this is impossible, so there are no foreign primes implying $p | f(n) \implies p | n$, as desired. $\blacksquare$

Actually in other version I saw first , the question asked for determining all functions and when I reached to this proposition , I wondered how can I introduce them all :/ ? till I saw the official one. Anyway ... astonishing problem ! Suppose that there exist a number $m\in \mathbb{N}$ with prime factors $p_1 , ... , p_k$ , such that $f(m)$ has a prime factor $q$ , distinct from this $k$ factors. Now for $i \le 2012$ and $j \le 2013$ , choose arbitrary primes $q_{(i,j)}>2012$ distinct from $p_1 , ... , p_k$ and $q$ , so by CRT there exist a natural number $n$ , such that $q|n$ , $gcd(n,m)=1$ and for each $i \le 2012$ we have : $$n \equiv -i \pmod {q_{(i,1)}...q_{(i,2013)}} $$' So we'll show that $f(n)=n$ , suppose not and for a $1\le i \le 2012$ we have $f(n)=n+i$. So again by CRT , there exist a natural number $t$ such that for each $0\le j \le 2012$ we have : $$t \equiv -j \pmod{q_{(i , j+1)}}$$Now notice that we can choose such a $t$ , that $gcd(t , n)=1$ since prime factors $q_{(i,j)}$ don't divide $n$ , because $n \equiv -i \pmod{q_{(i,j)}}$ and $q_{(i,j)}>2012 \ge i$. As the result if $f(t)=t+j$ since $gcd(t , n)=1$ , then $gcd(f(n) , f(t))=1$ which is a contradiction while $q_{(i,j+1)} | gcd(n+i , t+j)$. So $f(n)=n$ and when $n , m$ are relatively prime , $n , f(m)$ are relatively prime too , which is a contradiction again while $q | gcd(n , f(m))$. So there doesn't exist such a prime $q$ for each $m$ and we're done.

Suppose that there exists some natural $n$ and prime $p$ such that $p \mid f(n)$ but $p \nmid n$. Pick distinct large primes $p_{i,j}\gg \max\{n,p,2012\}$ for all $0 \leq i,j \leq 2012$ except for $i=j=0$. Now pick $a$ (by CRT) such that \begin{align*} a &\equiv 0 \pmod{p},\\ a &\equiv 1 \pmod{n},\\ a &\equiv -i \pmod{p_{i,j}}, \end{align*}where the last congruence holds for all choices of $(i,j)$. Now let the prime divisors of $a$ be $p_{0,1},\ldots,p_{0,2012},q_1,\ldots,q_k$, where clearly $q_i$ is not one of the $p_{i,j}$ primes for all $i$. PIck $b$ (again by CRT) such that \begin{align*} b &\equiv -j \pmod{p_{i,j}},\\ b &\equiv 1 \pmod{q_i}, \end{align*}again across all choices of $(i,j)$ and $i$ respectively. It is clear that $a$ and $b$ are coprime, so $f(a)$ and $f(b)$ should be as well. On the other hand, $p_{i,j}$ divides $a+i$ and $b+j$, so we need $f(a)=a$ (and $f(b)=b$). On the other hand, $a$ and $n$ are relatively prime as well, so $f(a)$ and $f(n)$ should be too, but $p$ divides both: contradiction. Thus no such $(n,p)$ exist and we are done. $\blacksquare$ Remark: This solution is strongly motivated by the guiding intuition that we should be able to construct $a$ and $b$ such that $a+i$ and $b+j$ share a prime factor by CRT. Actually thinking about this for a bit more reveals just how much freedom there is in this construction, so the rest of the problem is just figuring out how to use that freedom to add a few necessary conditions.

hopefully no mess up

Consider the set of primes much larger than $2012$, let this be $S$. Then, we use Dirichlet's theorem and Chinese Remainder theorem in what follows: Assume for the sake of contradiction, there are finitely many primes $p$ such that $f(p) = p$. Then, after a certain point, $f(p) \neq p$ for all primes above that point. So, take one such prime in $S$, $p_1$. Then let $f(p_1) = p_1+k_1$. Now given ${p_1, \dots, p_i}$ inductively pick $p_{i+1} \equiv -k_j \pmod{p_j+k_j}$ for all $j < i+1$. Let $f(p_{i+1}) = p_{i+1}+k_{i+1}$. Then, clearly the sequence ${p_i+k_i}$ contains all pairwise relatively prime integers since they are the image of a subset of the set of primes in $f$. Now, we cannot have $k_i = k_j$ with $i > j$, as then, $p_i+k_i$ is divisible by $p_j+k_j$. So, eventually we must have $k_i = 0$ for all $i > N$ for some $N$. Contradiction Now let $P$ be the set of primes such that $f(p) = p$. From the above statement, $P$ is infinite. So, clearly if $p \in P$, then if $p$ does not divide $n$, then $p$ cannot divide $f(n)$ either or else $f(n)$ and $f(p)$ will not be relatively prime. So, now, by Chinese remainder theorem, for any prime $p_0$ not in $P$ and letting $S$ be $p_1, p_2, \dots$, we take a number $x$ such that $x \equiv -i \pmod{p_i}$ for $i \leq 2012$, thus forcing $f(x) = x$. Now note that we can make sure that for a set of given primes $Q$ not having $p_0$, no prime in $Q$ divides $x$ by Chinese Remainder theorem, which is automatically ensured for $p_1, p_2, \dots, p_2012$ and for any other prime $q$ in it, we can just set $x \equiv -1 \pmod{q}$. Now, if there is a number $n$ and prime $p$ dividing $f(n)$ but not $n$, then clearly we cannot have $p$ in $P$, so we take some $x$ so that $p$ divides $x$ but no other prime dividing $n$ does. Now we have $f(x) = x$, so $\gcd{f(x), f(n)} = p$, but we picked $x$ so that $n$ and $x$ are relatively prime. Thus we must have $f(n)$ cannot be divisible by $p$ if $p$ divides $n$.

We uploaded our solution https://calimath.org/pdf/USATSTST2012-3.pdf on youtube https://youtu.be/7_MtLjadof4.

First, we see that the second condition means $(f(m),f(n))>1\implies (m,n)>1$. Claim: There are infinitely many primes satisfying $f(p)=p$. Proof: Consider $S=\{f(q)-q| q \ \text{is any prime}\}$, let $f(p_1)-p_1,\dots,f(p_k)-p_k$ be all the elements of this set where $p_i'$s are distinct primes. Note that $(p_i,p_j)=1$ implies $(f(p_i),f(p_j))=1$. Pick $q\equiv p_i(mod \ f(p_i))$ for $1\leq i\leq k$. If $f(q)=q+f(p_m)-p_m$, then $(f(q),f(p_m))=(q+f(p_m)-p_m,f(p_m))\geq f(p_m)$ which results in a contradiction. Hence $f(q)=q$ for infinitely many $q$.$\square$ Choose $f(m)=m+d$. Pick $2012$ distinct primes with $f(m)\ll p_1<p_2<\dots<p_{2012}$ and $f(p_i)=p_i$ for each $1\leq i\leq 2012$. FTSOC $p|f(m)=m+d$ but $p\not | m$. Then, we can choose $A\equiv -i(mod \ p_i)$ for $1\leq i\leq 2012$ and $A\equiv 0(mod \ p)$ and $A\equiv 1(mod \ m)$ by Chinese Remainder Theorem. If $f(A)=A+c$ and $c>0$, then $(A+c,p_c)\geq p_c$ thus, $p_c|A$ however this is impossible since $p_c>2012$. Consequently, $f(A)=A$. Since $(f(A),f(m))=(A,m+d)\geq p$ we conclude that $(A,m)>1$ but $A\equiv 1(mod \ m)$ gives a contradiction as desired.$\blacksquare$

This problem might involve the most obscenely large numbers in any reasonable olympiad problem. Let $N = 2012$. Claim: There exist infinitely many positive integers $a$ such that $f(a) = a$. Proof: Let $p_1 = 2^{136279841}-1 < p_2 < \cdots$ be an infinite sequence of consecutive primes. For each $n \geq 0$, and pick an $a_n \equiv -i \pmod {p_{nN(N+1)+(N+1)(i-1)+j}}$ for $1 \leq i \leq N$ and $1 \leq j \leq N+1$. Concretely, we are picking $a_n$ to be $-1$ mod some product of $N+1$ primes, $-2$ mod another product of $N+1$ primes, and so on. Now, for each $a_n$ and $1 \leq i \leq N$, pick $b_{ni}$ such that \[b_{ni} \equiv -(j-1) \pmod {p_{nN(N+1)+(N+1)(i-1)+j}}\]so it follows that $\gcd(b_{ni} + j - 1, a_n + i) > 1$, as some prime (which I do not want to spend brain cells figuring out the index for) divides both numbers for $1 \leq j \leq N+1$. Assume for the sake of contradiction that $f(a_n) = a_n + i$ now. In particular, as $f(b_{ni}) = b_{ni} + j - 1$ for one of these $j$, it follows that $f(a_n)$ and $f(b_{ni})$ are not relatively prime, so $a_n$ and $b_{ni}$ must not be relatively prime. Ok now force $b_{ni} \equiv 1 \pmod {a_n}$, contradiction. (We can do this because all the prime factors of $a_n$ are not the primes $p_{\mathrm{blah}}$ which were part of our CRT construction.) So $f(a_n) \neq a_n+i$ for any $1 \leq i \leq N$, so $f(a_n) = a_n$, which proves the claim. $\blacksquare$ And you thought we were done with obscenely large numbers? For any positive integer $n$, let $\mathcal P$ be the set of all primes that divide one or more elements in the set $\{n+1, n+2, \dots, n+N\}$ but not $n$. Assume for the sake of contradiction that there exists a prime $p \mid f(n)$ and $p \nmid n$; then $p \in \mathcal P$. Now, pick a positive integer $a$ such that every prime in $\mathcal P$ divides $a$, no prime that divides $n$ divides $a$, and $a$ also satisfies $f(a) = a$. (To do this, just make $p_1$ bigger than everything in $\mathcal P$ and also all the primes that divide $n$. Hopefully it won't be bigger than $2^{136279841} - 1$.) Then $p \mid \gcd(f(n), a) = \gcd(f(n), f(a))$, so $a$ and $n$ cannot be relatively prime, contradicting our choice of $a$. Thus every prime $p$ that divides $f(n)$ must also divide $n$, done!