19
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I guess in case 3 you mean $f(1)=2$ and $f(2)=1$? $\endgroup$ – Eric S. Mar 29 '16 at 10:01
  • $\begingroup$ $f(n)=n$ is a trivial solution. Can we see your proofs ? $\endgroup$ – Yves Daoust Mar 29 '16 at 10:05
  • $\begingroup$ @Eric S. Yes! Thank you $\endgroup$ – Roman83 Mar 29 '16 at 10:05
  • $\begingroup$ Preliminary easy result: if $p$ is an odd prime, then $f(p) \geq p$ if and only if $p \mid f(p)$. $\endgroup$ – Patrick Stevens Mar 29 '16 at 10:12
  • $\begingroup$ @Yves Daoust: Which of cases I write the proof? $\endgroup$ – Roman83 Mar 29 '16 at 10:23
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ How can you conclude that $f(3)=2$ or $3$ ? what about larger values ? $\endgroup$ – Yves Daoust Mar 29 '16 at 14:04
7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ @PatrickStevens I agree. Now it seems much neater. Thank you! $\endgroup$ – Sangchul Lee Mar 29 '16 at 14:32

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.