¿Cuándo un polinomio toma todos los residuos posibles módulo un número entero?

Question

(Esta pregunta está inspirada en una pregunta sobre restos de coeficientes binomiales pregunté hace poco).

Consideremos los mapas polinómicos $f:\ \mathbb{Z} \to \mathbb{Z}$ . Entre ellas se encuentran los polinomios con coeficientes enteros, pero también funciones como $f(x) = \frac{x(x-1)}{2} = \binom{x}{2}$ . Se puede demostrar que cualquier mapa polinómico de este tipo $\mathbb{Z} \to \mathbb{Z}$ es un $\mathbb{Z}$ -combinación lineal de los polinomios $\binom{x}{d}$ para $d \in \mathbb{N}$ . Me interesan los mapas polinómicos que asumen todos los residuos, módulo de todos los enteros. Más precisamente, un polinomio $f$ es interesante para mí si para cualquier número entero $m \geq 2$ y para cualquier número entero $0 \leq r < m$ existe un número entero $n$ con $f(n) \equiv r \pmod{m}$ . Uno de estos polinomios es $f(x) = x$ .

Como se explica en las otras preguntas mencionadas, los polinomios $f(x) = x^d$ no tienen la mencionada propiedad (para $d > 1$ ). Tenía la (ingenua) esperanza de que los polinomios ${x \choose d}$ servirían, pero tampoco funcionan.

Después de pensarlo un poco más, descubrí que el grado $2$ los polinomios nunca pueden funcionar. Esto se debe a que para $f(x) = ax^2 +bx +c$ la condición $f(n) \equiv r \pmod{p}$ puede reescribirse como $$\left(n+\frac{b}{2a}\right)^2 \equiv \frac{1}{a}\left(r-c+\frac{b^2}{4a}\right) \pmod{p}$$ (asumiendo los numeradores y denumeradores de $a,b,c$ son coprimos a $p$ ). Por lo tanto, $f(n)$ no tiene el residuo $r$ si $p$ es lo suficientemente grande y $\frac{1}{a}\left(r-c+\frac{b^2}{4a}\right)$ no es un residuo cuadrático módulo $p$ .

Esto me hace dudar de los polinomios de mayor grado. Aunque no se me ocurre un argumento general o un ejemplo de polinomio interesante.

Pregunta: ¿Existe un mapa polinómico $f:\ \mathbb{Z} \to \mathbb{Z}$ diferente a $f(x) = x$ con la propiedad antes mencionada de que para cualquier número entero $m \geq 2$ y para cualquier número entero $0 \leq r < m$ existe un número entero $n$ con $f(n) \equiv r \pmod{m}$ .

Answer 1

Queremos demostrar que $f(x)=x+a$ son las únicas posibilidades.

Consideremos el polinomio $g(x)=f(x+1)-f(x)$ . Mirando a los primos $p$ lo suficientemente grande como para que todos los denominadores de los coeficientes de $f$ son primordiales para $p$ podemos suponer que $f$ tiene coeficientes enteros a partir de ahora. Queremos las congruencias $f(x)=r\ (\text{ mod }p)$ tener soluciones para todos $r=0,1,\ldots,p-1$ . Entonces $f(0),f(1),\ldots,f(p-1)$ debe dar todos los restos $0,1,\ldots,p-1$ . En concreto, todos deben ser diferentes. Por lo tanto, $g(0),g(1),\ldots,g(p-1)$ no son cero mod $p$ . Si no, no sacamos todos los restos de $f$ .

Lema: Si $g$ no es constante, entonces podemos hacer $g(n)$ divisible por primos grandes arbitrarios.

Prueba: La prueba de este lema la escribí en esta respuesta a otro problema.

Toma $g(M)$ para $M$ muy grande como para que $g(M)$ es divisible por un primo muy grande $p$ con las condiciones anteriores (tal que este primo es primo con todos los denominadores en los coeficientes de $f$ ). Entonces $f(x)=r$ no siempre será solucionable mod este primo $p$ .

Por lo tanto, $g$ es constante. Por lo tanto, $f$ es lineal. De aquí se obtiene que el coeficiente principal de $f$ debe ser $1$ y obtenemos la solución $f(x)=x+a$ que funciona.