<s>[INST] Find all functions $f: \mathbb N \rightarrow \mathbb N$ such that $f(n!)=f(n)!$ Find all functions $f: \mathbb N \rightarrow \mathbb N$ (where $\mathbb N$ is the set of positive integers) such that $f(n!)=f(n)!$ for all positive integers $n$ and such that $m-n$ divides $f(m)-f(n)$ for all distinct positive integers $m,n$.
My work so far:
$f(1!)=f(1)=f(1)!$ and $f(2!)=f(2)=2$. Then $f(1)=1$ or $f(1)=2$ or $f(2)=1$ or $f(2)=2$.
Case 1: $f(1)=f(2)=1$. I proved $f(n) \equiv 1$
Case 2: $f(1)=f(2)=2$. I proved $f(n) \equiv 2$
Case 3: $f(1)=2$ and $f(2)=1$. I proved that this case is impossible.
Case 4: $f(1)=1$ and $f(2)=2$. I need help here.
 [/INST] [Sangchul Lee's proof below is substantially nicer than this one.]
Assume $f(1) = 1, f(2) = 2$.
It is a fact that $4 \mid f(6)-f(2) = f(3)! - 2$, so $f(3)! \equiv 2 \pmod{4}$.
Therefore $f(3) = 2$ or $3$.
Also $2 \mid f(3)-f(1) = f(3)-1$, so $f(3)$ is odd; hence $f(3) = 3$.

The following five theorems are to be viewed jointly as an inductive step.

Lemma 1: $$f(r)! \equiv (r-1)! \pmod{r!-(r-1)!}$$

Proof:
Generally, $$n \mid f(r)! - f(r!-n)$$
so $$f(r!) \equiv f(r!-n) \pmod{n}$$
so $$f(r)! \equiv f(r!-n) \pmod{n}$$
Letting $n = r!-(r-1)!$, obtain $$f(r)! \equiv f((r-1)!) = f(r-1)! \pmod{r!-(r-1)!}$$
Inductively, $f(r-1) = r-1$, so $$f(r)! \equiv (r-1)! \pmod{r!-(r-1)!}$$

Lemma 2: $$f(r) \equiv r \pmod{2}$$

This is immediate from the fact that $2 \mid f(r)-f(r-2)$, and inductively $f(r-2) = r-2$, so $$f(r) \equiv r \pmod{2}$$

Lemma 3: $$f(r) \geq r$$

Indeed, if $f(r) < r-1$, then $f(r)! \leq (r-2)!$; but $(r-2)! < r! - (r-1)!$ and so the statement of Lemma 1 that $f(r)! \equiv (r-1)! \pmod{r!-(r-1)!}$ is precisely the statement that $f(r)! = (r-1)!$, which is precisely the statement that $f(r) = r-1$. This is a contradiction.
Also, by Lemma 2, $f(r) \not = r-1$; so $f(r) \geq r$.

Lemma 4: $f(r) < 2(r-1)$.

We have by Lemma 1 $$f(r)! \equiv (r-1)! \pmod{r!-(r-1)!}$$
But if $f(r) \geq 2(r-1)$ then $(r-1)! (r-1) \mid f(r)!$, so $f(r)! \equiv 0 \pmod{(r-1)! (r-1)}$.

Theorem 5: If $r > 5$, have $f(r) = r$.

Let $p$ be any prime less than $r$.
Then $$r - (r-p) \mid f(r)-f(r-p)$$
so (inductively) $$p \mid f(r) - r$$
Therefore $f(r) \equiv r \pmod{p}$ for any prime $p < r$.
By the Chinese remainder theorem, this fixes the value of $f(r)$ modulo $\prod_{p < r} p$.
But $\prod_{p<r} p > 2(r-1)$ for $r > 5$, by Bertrand's postulate and induction.
Indeed, there is a prime between $\frac{r}{2}$ and $r$, so $$\prod_{p < r} p \geq \left( \prod_{p < r/2} p \right) \times \frac{r}{2} > 2 \left(\frac{r}{2} - 1 \right) \times \frac{r}{2} = (r-2) \times \frac{r}{2}$$
which, for $r>5$, is bigger than $2(r-1)$.
Therefore, since $f(r) < 2(r-1)$, this fixes the value of $f(r) = r$.

We still have the base cases $r=4$ and $r=5$ to deal with.


*

*$r=4$ gives, by Lemmata 2, 3 and 4, $f(4) = 4$.

*$r=5$ gives $f(5) = 5$ or $7$; but $f(5) \equiv 5 \pmod{3}$ and so it can't be $7$.


This completes the five base cases $r=1, \dots, 5$, and hence the proof.
</s>