Find all functions $f: \mathbb N \rightarrow \mathbb N$ such that $f(n!)=f(n)!$

Solution 1:

Here is a short proof, motivated by @PatrickStevens' argument. (Here a novel part is Lemma 2, and the other parts are simplification of Patrick's argument.)

Assume that $f(1) = 1$ and $f(2) = 2$.

Lemma 1. $f(3) = 3$.

Proof. $4 \mid (f(6) - 2)$ and $f(6) = f(3)!$ implies that $f(3) = 2$ or $3$. But $2 \mid (f(3) - 1)$ implies that $f(3)$ is odd. Therefore $f(3) = 3$.

Lemma 2. For any $n$, we have $n \mid f(n)$.

Proof. Given $n$, choose $k$ so that $b := 3!^{\circ k} \geq n$, where $!^{\circ k}$ denotes the $k$-fold factorial. Then $n \mid b! = f(b!)$. Hence writing $f(n) - f(b!) = N(n - b!)$ for some integer $N$, we have

$$ f(n) \equiv f(n) - f(b!) = N(n - b!) \equiv 0 \pmod{n}. $$

Lemma 3. $f(n) = n$ for all $n$.

Proof. Assume otherwise and let $n$ be the smallest positive integer satisfying $f(n) \neq n$. (In particular, $n \geq 4$.) By Lemma 2, $f(n) \geq 2n$ and hence $(2n)! \mid f(n)!$. Also, by the minimality of $n$, we have $f(n-1) = n-1$. Then with $N := (n-1)(n-1)!$, we have

$$ (n-1)! = f((n-1)!) - f(n!) + f(n)! \equiv N + 0 \equiv 0 \pmod{N}. $$

This contradicts $N > (n-1)!$. Therefore no such $n$ with $f(n) \neq n$ exists.

Addendum. I guess it would worth it to explain how I come up with Lemma 2. In fact, I made a significant detour. Let $p$ be arbitrary prime. Then with the usual $p$-adic norm, the assumption says that

$$ |f(m) - f(n)|_p \leq |m - n|_p, \quad m, n \in \Bbb{N}. \tag{*} $$

That is, the function $f$ is Lipschitz on the dense subset $\Bbb{N}$ of $\Bbb{Z}_p$. So $f$ uniquely extends to a continuous function $f_p : \Bbb{Z}_p \to \Bbb{Z}_p$ which also satisfies $\text{(*)}$. Now by Lemma 1, we can choose $x_j \in \Bbb{N}$ such that $|x_j|_p \to 0$ and $|f(x_j)|_p \to 0$ as $j \to \infty$. By continuity, this implies that $f_p(0) = 0$. Plugging this to $\text{(*)}$, we have

$$ |f_p(n)|_p \leq |n|_p, \quad n \in \Bbb{Z}_p. $$

Since this is true for all $n \in \Bbb{N}$ and for all prime $p$, this implies $n \mid f(n)$.

Now decoding this analytic proof in terms of congruence gives the proof of Lemma 2.

Solution 2:

[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.