Problem: Let $\NN$ be the set of positive integers.
Let $f \colon \NN \to \NN$ be a function satisfying the following two conditions:
\begin{enumerate}[(a)]
 \ii $f(m)$ and $f(n)$ are relatively prime whenever $m$ and $n$ are relatively prime.
 \ii $n \le f(n) \le n+2012$ for all $n$.
\end{enumerate}
Prove that for any natural number $n$ and any prime $p$,
if $p$ divides $f(n)$ then $p$ divides $n$.

Solution: \paragraph{First short solution, by Jeffrey Kwan.}
Let $p_0$, $p_1$, $p_2$, \dots\ denote the
sequence of all prime numbers, in any order.
Pick \emph{any} primes $q_i$ such that
\[ q_0 \mid f(p_0), \quad q_1 \mid f(p_1), \quad
  q_2 \mid f(p_2), \; \text{ etc}. \]
This is possible since each $f$ value above exceeds $1$.
Also, since by hypothesis the $f(p_i)$ are pairwise coprime,
the primes $q_i$ are all pairwise distinct.

\begin{claim*}
  We must have $q_i = p_i$ for each $i$.
  (Therefore, $f(p_i)$ is a power of $p_i$ for each $i$.)
\end{claim*}
\begin{proof}
  Assume to the contrary that $q_0 \neq p_0$.
  By changing labels if necessary, assume
  $\min(p_1, p_2, \dots, p_{2012}) > 2012$.
  Then by Chinese remainder theorem we can choose
  an integer $m$ such that
  \begin{align*}
    m+i &\equiv 0 \pmod{q_i} \\
    m &\not\equiv 0 \pmod{p_i}
  \end{align*}
  for $0 \le i \le 2012$.
  But now $f(m)$ should be coprime to all $f(p_i)$,
  ergo coprime to $q_0 q_1 \dots q_{2012}$,
  violating $m \le f(m) \le m+2012$.
\end{proof}

All that is left to do is note that whenever $p \nmid n$,
we have $\gcd(f(p), f(n)) = 1$, hence $p \nmid f(n)$.
This is the contrapositive of the problem statement.


\paragraph{Second solution with a grid.}
Fix $n$ and $p$, and assume for contradiction $p \nmid n$.

\begin{claim*}
  There exists a large integer $N$ with $f(N) = N$,
  that also satisfies $N \equiv 1 \pmod n$ and $N \equiv 0 \pmod p$.
\end{claim*}
\begin{proof}
  We'll need to pick both $N$ and an ancillary integer $M$.
  Here is how: pick $2012 \cdot 2013$ distinct primes $q_{i,j} > n+p+2013$
  for every $i=1,\dots,2012$ and $j=0,\dots,2012$,
  and use it to fill in the following table:
  \[
    \begin{array}{c|cccc}
      & N+1 & N+2 & \dots & N+2012 \\ \hline
      M & q_{0,1} & q_{0,2} & \dots & q_{0,2012} \\
      M+1 & q_{1,1} & q_{1,2} & \dots & q_{1,2012} \\
      \vdots & \vdots & \vdots & \ddots & \vdots \\
      M+2012 & q_{2012,1} & q_{2012,2} & \dots & q_{2012,2012}
    \end{array}.
  \]
  By the Chinese Remainder Theorem, we can construct $N$
  such that $N+1 \equiv 0 \pmod{q_{i,1}}$ for every $i$,
  and similarly for $N+2$, and so on.
  Moreover, we can also tack on the extra conditions
  $N \equiv 0 \pmod p$ and $N \equiv 1 \pmod n$ we wanted.

  Notice that $N$ cannot be divisible by any of the $q_{i,j}$'s,
  since the $q_{i,j}$'s are greater than $2012$.

  After we've chosen $N$, we can pick $M$ such that $M \equiv 0 \pmod{q_{0,j}}$ for every $j$,
  and similarly $M+1 \equiv 0 \pmod{q_{1,j}}$, et cetera.
  Moreover, we can tack on the condition $M \equiv 1 \pmod N$,
  which ensures $\gcd(M,N) = 1$.

  What does this do?
  We claim that $f(N) = N$ now.
  Indeed $f(M)$ and $f(N)$ are relatively prime; but look at the table!
  The table tells us that $f(M)$ must have a common factor
  with each of $N+1, \dots, N+2012$.
  So the only possibility is that $f(N) = N$.
\end{proof}

Now we're basically done.
Since $N \equiv 1 \pmod n$, we have $\gcd(N,n) = 1$
and hence $1 = \gcd(f(N), f(n)) = \gcd(N, f(n))$.
But $p \mid N$ and $p \mid f(n)$, contradiction.