# Large integer solution to a problem on Chinese Remainder Theorem

I was going through the following link :

http://www.mit.edu/~evanchen/handouts/CRT/CRT.pdf

and was trying to understand the solution to the second problem which goes as :

Let 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 \leq f(n) \leq 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$.

For the solution of the problem , I don't know what invoked the author to come up with the idea of constructing big integers such that $F(N) =N$, Why does the largeness of an integer facilitate that integer to be a fixed point for this function $F$ ? I got that CRT enables us to select integers $M$ and $N$ satisfying the modulo conditions for primes but when the range of N has not been specified how was it asserted that primes greater than 2012 cannot divide $N$ and what was the logic behind $N$ dividing $P$ and choosing $M$ ? Can anyone give me a picture of the strategy used in this proof ?

• interesting and useful notes! – KonKan Sep 19 '16 at 7:24
• I don't understand the statement of your problem. You define some $N$, but do not use it afterwards, and you bound $f$ by $+2012$, which create an inconsistency with the fact that $f(n) \geq n$ (I take that $n$ is any $n \in \mathbb N$ since $\mathbb N$ is the domain of $f$). – Lærne Sep 19 '16 at 11:23
• @Lærne: According to the link it should read $n\leq f(n)\leq n+2012$. – String Sep 19 '16 at 11:43

Somehow you got the reason for $N$ being huge backwards. The fact is that $N$ happens to be huge because of the heavy use of CRT to make $M,N$ satisfy a series of conditions.
BTW it was not asserted that primes greater than $2012$ cannot divide $N$. But since the $q_{i,j}$'s each divide some number in the set $\{N+1,...,N+2012\}$ and are at the same time greater than $2012$, hence they cannot also divide $N$.
The structure of the proof was to construct $M,N$ that are relatively prime, $N$ having $p$ as a factor but being relatively prime to $n$, and making sure that in the specified output range $$(f(M),f(N))\in\{M,...,M+2012\}\times\{N,...,N+2012\}$$ one would find common factors of $f(M)$ and $f(N)$ unless $f(N)=N$. For each assumption in this construction CRT was applied thus forcing $M,N$ to be huge. Note how $M$ was merely a tool to construct $N$ with $f(N)=N$.
This in turn allowed the author to reach the contradiction of $n,N$ being relatively prime, but $f(n),f(N)$ not being so.
BTW we could easily extend condition (b) to $n-s\leq f(n)\leq n+t$ and essentially use the same proof.