Post Number:**#3** by **Zawadx** » Wed Feb 22, 2017 12:03 am

My solution is a bit... lengthy:

Let $P(m,n)$ denote the statement that $f(m-n)|f(m)-f(n)$.

$P(m,0) \Rightarrow f(m)|f(0)$ for all $m$ (Lame Lemma 0)

$P(0,m) \Rightarrow f(-m)|f(0) - f(m) \Rightarrow f(-m)|f(m)$ for all $ m \in \mathbb{Z} $ (Using Lame Lemma 0)

So, for fixed $m$, $f(-m)|f(m)$ and $f(m)|f(-m)$ and $f(m), f(-m) > 0$. Thus, $f(m)=f(-m)$. (Lame Lemma 1)

Serious Lemma 1:$f(m)|f(mn)$ for all $n \in \mathbb{N}$.

Proof: Now we shall prove this by induction. The base case is trivial. Assuming it holds for $n$,

$P(mn+m, mn) \Rightarrow f(m)|f(mn+m) - f(mn) \Rightarrow f(m)|f(mn+m)$

Then it holds for $n+1$. (Sub-QED)

Serious Lemma 2: Given $z|a \in \mathbb{N}, f(a) \neq f(z) \Rightarrow f(z-a) = f(z)$ and $f(z-a) \neq f(z) \rightarrow f(a) = f(z)$

Proof: By Serious Lemma 1, $f(z)|f(a)$ and $f(z)|f(z-a)$.

Let $f(a) = xf(z)$ and $f(z-a)=yf(z)$ for $x,y \in \mathbb{N}$

Now,

$P(z-a, z) \Rightarrow f(a)|f(z-a)-f(z) \Rightarrow y-1 = kx$ for $k \in \mathbb{N}_0$

$P(a, z) \Rightarrow f(z-a)|f(a) - f(z) \Rightarrow x-1= ly$ for $l \in \mathbb{N}_0$

Suppose $k, l > 0$ This would mean $x>y$ and $y>x$, a contradiction! So one o $k, l$ equals $0$. The lemma follows from this. (sub-QED)

Serious Lemma 3: If $n < k \Rightarrow f(n)=f(1) [n \in \mathbb{N}]$ for some maximal $k$, then $f(a) \neq f(1) \Leftrightarrow k|a$

Note that if $k$ exists to fulfill the condition, then $f(n)=f(1)$ for all $n$ and we are trivially done.

Now, $k|a \Rightarrow f(k)|f(a) \Rightarrow f(a) > f(1)$

Since $f(mk) \neq f(1)$, by Serious Lemma 2 we have $f(mk+1) = f(mk+2) = f(mk+3) = \dots = f(mk + k -1) = f(1)$ . Thus we are done (sub-QED).

Now we are ready to solve the problem. Suppose for $n>0$ maximal value*** is obtained $f(n)$ with minimal $n$ for some number $r$. Then all the other numbers with maximal value of $f(n)$ are multiples of $r$ (by Serious Lemma 1).

Now, since the only non-f(1) values of $f$ are multiples of $k$, we define a more interesting $f_1(n) = f(kn), n \in \mathbb{N}_0$. Then the process continues. So we can define $f_i$, and the corresponding $k_i$ and $r_i$. Note that as $i$ increases, $r_i$ decreases by factor of $k_{i-1}$. Eventually it must reach $1$, at which point the process terminates. At that point we conclude that $f(m) \leq f(n) \Rightarrow f(m)|f(n)$, since $f(m) \leq f(n)$ is only possible if they were last found in different levels of $f_i$, which means $m|n$.

*** Bwwaaahhh infinities