Los restos de los coeficientes binomiales.

Question

Motivación: es fácil notar que un polinomio mapa de $f: \mathbb{Z} \to \mathbb{Z}$ no tienen solo entero coeficiente. Por ejemplo, $f(x) = \frac{x(x-1)}{2}$ tiene racional de los coeficientes y de los mapas de $ \mathbb{Z}$$\mathbb{Z}$. Esto le da una sencilla razón de un polinomio con coeficientes enteros no dar a todos los posibles restos modulo algún número $m$: por ejemplo, $x^2 - x = 2\frac{x(x-1)}{2}$ siempre $0$ modulo $2$, y en un espíritu similar $f(x) = x^2$ siempre $0$ o $1$ modulo $4$. Más generalmente, se puede demostrar que un polinomio mapa de $f: \mathbb{Z} \to \mathbb{Z}$ $\mathbb{Z}$- combinación lineal de los polinomios $\binom{x}{d}$$d \in \mathbb{N}$.

Estoy buscando una clase de polinomios $f: \mathbb{Z} \to \mathbb{Z}$ que tienen la propiedad de que para cualquier $m \in \mathbb N$ y el resto en el $r \in \{0,1,\dots,m-1\}$ existe alguna $a \in \mathbb N$ tal que $f(a) \equiv r \pmod{m}$. Lo anterior muestra que $f(n) = n^d$ no tienen muchas posibilidades de trabajo, sino $f(n) = \binom{n}{d}$ podría.

Pregunta: ¿Es cierto que para cualquier $d \in \mathbb N$ cualquier $m,r \in \mathbb N, r < m$, el mapa de $f(n) = \binom{n}{d}$ tiene la propiedad de que $f(a) \equiv r \pmod{m}$ algunos $a \in \mathbb{Z}$ ?

Answer 1

La respuesta es no. Tomemos por ejemplo la $d = 2, m = 5, r = 4$. De manera más general, para cualquier $d$, usted puede encontrar una infinidad de valores de $m$, por lo que, al menos, $d-1$ valores $r$ $0 \le r < m$ no tienen solución a $\binom{x}{d} \equiv r \pmod m$. Siga más detalles.

Para $d = 0$, la respuesta es trivialmente no: $f(x) = \binom{x}{0} = 1$ todos los $x$, por lo que no podemos tener una solución a $f(x) \equiv r \pmod m$ al $r \not\equiv 1 \pmod m$.

Para $d=1$, la respuesta es trivialmente sí: $f(x) = \binom{x}{1} = x$ todos los $x$, lo que para cualquier $(r,m)$, una solución a $f(x) \equiv r \pmod m$ es tomar $x = r$.

Para $d\ge 2$ es cuando se pone interesante. Vamos a empezar con $d = 2$. A continuación,$f(x) = \binom{x}{2} = \frac{x(x-1)}{2}$, y queremos saber si la ecuación de $f(x) \equiv r \pmod m$ siempre tiene una solución para cualquier $(r,m)$. Mirando la secuencia de los valores de $f(x)$, esto es OEIS A161680. Si usted mira su secuencia de los últimos dígitos (correspondiente a $m = 10$), ver (esto es más conveniente si se ven como una lista) que es periódica con período de $20$, y la única últimos dígitos que aparecen son ${0, 1, 3, 5, 6}$. Los otros dígitos ${2, 4, 7, 8, 9}$ nunca aparecen. De hecho, esto es fácil de demostrar: para$x \equiv y \pmod {20}$, $x(x-1) \equiv y(y-1) \pmod {20}$ que es equivalente a $\dfrac{x(x-1) - y(y-1)}{20}$ ser un número entero, y por lo tanto a $\dfrac{\frac{x(x-1)}2 - \frac{y(y-1)}{2}}{10}$ ser un número entero, lo que significa que $\frac{x(x-1)}{2} \equiv \frac{y(y-1)}{2} \pmod {10}$. Así que la secuencia es de hecho periódica con período de $20$. Y después de esto, es sólo una cuestión de inspección a ver que el único últimos dígitos que ocurre es que el anterior.

En general, por el mismo razonamiento, la secuencia de $\binom{x}{2} \bmod m$ $2m$ como un período. (En otras palabras, $x \equiv y \pmod {2m} \implies \binom{x}{2} \equiv \binom{y}{2} \pmod m$.) En particular, teniendo en $m = 5$, observamos que la secuencia de $\binom{x}{2}$$0, 0, 1, 3, 1, 0, 0, 1, 3, 0, 0\dots$, por lo que de hecho es periódica con período de $5$, y el resto a $2$ $4$ nunca ocurren.

---

Edit: Aún más general, siempre $\gcd(m, d!) = 1$, la secuencia de $\binom{x}{d} \bmod m$ $m$ como un período. Prueba: si $x \equiv y \pmod m$, $x-k \equiv y-k \pmod m$ todos los $k$, por lo que $$x(x-1)(x-2)\dots(x-d+1) \equiv y(y-1)(y-2)\dots(y-d+1) \pmod m$$ Ahora como $\gcd(d!, m) = 1$, se puede "dividir" a ambos lados por $d$. Con más precisión, $d$ tiene una inversa modulo $m$, es decir, un número $d'$ tales $dd' \equiv 1 \pmod m$, por lo que multiplicando ambos lados de la ecuación anterior por $d'$, obtenemos $$\binom{x}{d} \equiv \binom{y}{d} \pmod m.$$

Tenga en cuenta que para $x = 0$$x = 1$,$\binom{x}{d} = 0$, para cualquier $d \ge 2$. Esto significa en particular que no todos los $m$ valores (restos) en el período (en la lista de$\binom{0}{d} \mod m$$\binom{m-1}{d} \mod m$) son distintos, por lo que algunas resto debe de faltar. De hecho, tenemos $\binom{x}{d} = 0$$0 \le x \le d-1$, así como este resto $0$ es repetido $d$, significa que por lo menos $d-1$ restos que faltan.

Esto significa que para cualquier $d$, si tomamos cualquier $m$ que $\gcd(m, d!) = 1$, hay, al menos, $d-1$ valores de $r$ para el cual la ecuación de $\binom{x}{d} \equiv r$ no tiene solución.

Answer 2

El más simple contraejemplo que se me ocurre es $m=p$, $d=p-1$, $p$ prime.

Cuando escribimos $n$ $k$ base $p$ $$ n=\sum_{i\ge0}n_ip^i,\qquad k=\sum_{i\ge0}k_ip^i $$ con $0\le k_i, n_i<p$ todos los $i$, tenemos el conocido congruencia $$ {n\elegir k}\equiv\prod_{i\ge0}{n_i\elegir k_i}\pmod p, $$ donde ${n_i\choose k_i}$ se interpreta como el cero, si $k_i>n_i$.

Con $k=p-1$ esto da $$ {n\elegir p-1}\equiv{n_0\elegir p-1}\prod_{i\ge1}{n_i\elegir 0}={n_0\elegir p-1}. $$ Esto es distinto de cero sólo si $n_0=p-1$, en cuyo caso es $1$. Por lo tanto, siempre $p>2$ de los residuos de $2,3,\ldots,p-1\pmod p$ nunca ocurren.

Answer 3

Esto conteste tu motivación y en particular sobre la cuestión.

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

Considere el polinomio $g(x)=f(x+1)-f(x)$. Mirando los números primos $p$, lo suficientemente grande, de modo que todos los denominadores de los coeficientes de $f$ son de primer a $p$, podemos suponer $f$ tiene coeficientes enteros a partir de ahora. Queremos que la congruencias $f(x)=r\ (\text{ mod }p)$ a los que tienen soluciones para todos los $r=0,1,\ldots,p-1$. A continuación, $f(0),f(1),\ldots,f(p-1)$ debe dar a todos los restos de $0,1,\ldots,p-1$. En particular, todos ellos deben ser diferentes. Por lo tanto, $g(0),g(1),\ldots,g(p-1)$ no son cero mod $p$. De lo contrario, no obtener todos los restos de $f$.

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

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

Tome $g(M)$ $M$ muy grande tal que $g(M)$ es divisible por un gran primer $p$ con las condiciones anteriores (que este es el primer prime con todos los denominadores de los coeficientes de $f$). A continuación, $f(x)=r$ no siempre va a ser solucionable mod este primer $p$.

Por lo tanto, $g$ es constante. Por lo tanto $f$ es lineal. De esto podemos conseguir que el coeficiente de $f$ debe $1$ (de lo contrario mod un primo que divide a este coeficiente no obtener todos los restos) y obtenemos la solución $f(x)=x+a$, lo que hace el trabajo.