Encontrar todas las funciones $f: \mathbb N \rightarrow \mathbb N$ tal que $f(n!)=f(n)!$

Question

Encontrar todas las funciones $f: \mathbb N \rightarrow \mathbb N$ (donde $\mathbb N$ es el conjunto de enteros positivos) tal que $f(n!)=f(n)!$ para todos los enteros positivos $n$ que $m-n$ divide $f(m)-f(n)$ para todos los enteros positivos distintos $m,n$.

Mi trabajo hasta el momento:

$f(1!)=f(1)=f(1)!$ $f(2!)=f(2)=2$ . A continuación, $f(1)=1$ o $f(1)=2$ o $f(2)=1$ o $f(2)=2$.

Caso 1: $f(1)=f(2)=1$. Me resultó $f(n) \equiv 1$

Caso 2: $f(1)=f(2)=2$. Me resultó $f(n) \equiv 2$

Caso 3: $f(1)=2$ $f(2)=1$ . He demostrado que este caso es imposible.

Caso 4: $f(1)=1$ $f(2)=2$ . Necesito ayuda aquí.

Answer 1

He aquí una breve prueba, motivado por @PatrickStevensel argumento. (Aquí una parte de la novela es el Lema 2, y las otras partes son la simplificación de Patricio argumento.)

Suponga que $f(1) = 1$$f(2) = 2$.

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

Prueba. $4 \mid (f(6) - 2)$ $f(6) = f(3)!$ implica que el $f(3) = 2$ o $3$. Pero $2 \mid (f(3) - 1)$ implica que el $f(3)$ es impar. Por lo tanto,$f(3) = 3$.

Lema 2. Para cualquier $n$,$n \mid f(n)$.

Prueba. Dado $n$, elija $k$, de modo que $b := 3!^{\circ k} \geq n$ donde $!^{\circ k}$ indica el $k$veces factorial. A continuación,$n \mid b! = f(b!)$. Por lo tanto la escritura $f(n) - f(b!) = N(n - b!)$ para algunos entero $N$, tenemos

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

Lema 3. $f(n) = n$ todos los $n$.

Prueba. Asumir lo contrario y deje $n$ ser el más pequeño entero positivo satisfacer $f(n) \neq n$. (En particular, $n \geq 4$.) Por el Lema 2, $f(n) \geq 2n$ y, por tanto,$(2n)! \mid f(n)!$. También, por la minimality de $n$,$f(n-1) = n-1$. A continuación, con $N := (n-1)(n-1)!$, tenemos

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

Esto contradice $N > (n-1)!$. Por lo tanto, no hay tal $n$ $f(n) \neq n$ existe.

---

Adenda. Supongo que sería la pena para explicar cómo he llegado con Lema 2. De hecho, he hecho un importante desvío. Deje $p$ ser arbitraria prime. A continuación, con la habitual $p$-ádico de la norma, la hipótesis dice que

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

Es decir, la función $f$ es de Lipschitz en el subconjunto denso $\Bbb{N}$$\Bbb{Z}_p$. Por lo $f$ extiende de manera exclusiva a una función continua $f_p : \Bbb{Z}_p \to \Bbb{Z}_p$ que también satisface $\text{(*)}$. Ahora, por el Lema 1, podemos optar $x_j \in \Bbb{N}$ tal que $|x_j|_p \to 0$$|f(x_j)|_p \to 0$$j \to \infty$. Por la continuidad, esto implica que $f_p(0) = 0$. Conectando a $\text{(*)}$, tenemos

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

Como esto es cierto para todos los $n \in \Bbb{N}$, y para todos los prime $p$, esto implica $n \mid f(n)$.

Ahora la decodificación de esta analítica de la prueba en términos de congruencia da la prueba del Lema 2.

Answer 2

[Sangchul Lee la prueba a continuación es sustancialmente mejor que este.]

Suponga $f(1) = 1, f(2) = 2$.

Es un hecho que $4 \mid f(6)-f(2) = f(3)! - 2$, lo $f(3)! \equiv 2 \pmod{4}$. Por lo tanto, $f(3) = 2$ o $3$.

También se $2 \mid f(3)-f(1) = f(3)-1$, lo $f(3)$ es impar; por lo tanto $f(3) = 3$.

---

Los cinco siguientes teoremas son para ser vistos de manera conjunta como un paso inductivo.

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

Prueba: Generalmente, $$n \mid f(r)! - f(r!-n)$$ por lo $$f(r!) \equiv f(r!-n) \pmod{n}$$ por lo $$f(r)! \equiv f(r!-n) \pmod{n}$$

Dejando $n = r!-(r-1)!$, obtenga $$f(r)! \equiv f((r-1)!) = f(r-1)! \pmod{r!-(r-1)!}$$

Inductivamente, $f(r-1) = r-1$, lo $$f(r)! \equiv (r-1)! \pmod{r!-(r-1)!}$$

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

Este es inmediata a partir del hecho de que $2 \mid f(r)-f(r-2)$, y de manera inductiva $f(r-2) = r-2$, lo $$f(r) \equiv r \pmod{2}$$

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

De hecho, si $f(r) < r-1$,$f(r)! \leq (r-2)!$; pero $(r-2)! < r! - (r-1)!$ y por lo tanto la declaración de Lema 1 $f(r)! \equiv (r-1)! \pmod{r!-(r-1)!}$ es, precisamente, la afirmación de que $f(r)! = (r-1)!$, que es precisamente la afirmación de que $f(r) = r-1$. Esta es una contradicción.

También, por el Lema 2, $f(r) \not = r-1$; por lo $f(r) \geq r$.

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

Tenemos por Lema 1 $$f(r)! \equiv (r-1)! \pmod{r!-(r-1)!}$$

Pero si $f(r) \geq 2(r-1)$$(r-1)! (r-1) \mid f(r)!$, lo $f(r)! \equiv 0 \pmod{(r-1)! (r-1)}$.

Teorema 5: Si $r > 5$,$f(r) = r$.

Deje $p$ ser cualquier prime menos de $r$. A continuación, $$r - (r-p) \mid f(r)-f(r-p)$$ para (inductivamente) $$p \mid f(r) - r$$

Por lo tanto, $f(r) \equiv r \pmod{p}$ para cualquier prime $p < r$.

Por el teorema del resto Chino, esto corrige el valor de $f(r)$ modulo $\prod_{p < r} p$.

Pero $\prod_{p<r} p > 2(r-1)$$r > 5$, por el postulado de Bertrand y de inducción. De hecho, es una de las principales entre el$\frac{r}{2}$$r$, lo $$\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}$$ que, por $r>5$, es mayor que $2(r-1)$.

Por lo tanto, desde el $f(r) < 2(r-1)$, esto corrige el valor de $f(r) = r$.

---

Todavía tenemos la base de casos $r=4$ $r=5$ a tratar.

• $r=4$ da, por Lemmata 2, 3 y 4, $f(4) = 4$.
• $r=5$ da $f(5) = 5$ o $7$; pero $f(5) \equiv 5 \pmod{3}$, por lo que no puede ser $7$.

Esto completa las cinco de la base de casos $r=1, \dots, 5$, y por lo tanto la prueba.