5
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ interesting and useful notes! $\endgroup$ – KonKan Sep 19 '16 at 7:24
  • $\begingroup$ 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$). $\endgroup$ – Lærne Sep 19 '16 at 11:23
  • $\begingroup$ @Lærne: According to the link it should read $n\leq f(n)\leq n+2012$. $\endgroup$ – String Sep 19 '16 at 11:43
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Any explanation for someone coming up with this solution ? $\endgroup$ – jedna dve Sep 19 '16 at 13:07

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.