El polinomio de menor grado desaparece en los enteros mod$n$?

Question

Este problema proviene del Seminario sobre problemas de DJ Newman.

Problema: ¿Cuál es el polinomio monónico de grado más bajo$p(x)$, de manera que el valor de$p(x)$ es divisible por$100$ siempre que$x$ sea un número entero?

(El número$100$ no es particularmente especial. Puede intentar resolverlo cuando$100$ es reemplazado por un entero arbitrario$n$.)

Answer 1

SUGERENCIA: Tenemos $x^5\equiv x\pmod 5$$x^5\equiv x\pmod 2$, por lo tanto $$x^{10}-2x^6+x^2=(x^5-x)^2$$ es un múltiplo de a $100$ para todos los enteros $x$.

Sigue siendo para mostrar que ningún grado $\le 9$ obras. He aquí cómo reducir este a $d\le 5$:

Deje $p$ ser monic de grado mínimo $d$ $p(x)\equiv0\pmod{100}$ todos los $x\in\mathbb Z$. Wlog. $p(0)=0$. A continuación, la primera diferencia $\Delta p(x)=p(x+1)-p(x)$ es también un múltiplo de $100$ para todos los números enteros, pero no es monic. De hecho, se inicia con $d\cdot x^{d-1}$ ( $(x+1)^d-x^d=dx^{d-1}+\ldots$ ). Suponga $5<d<10$. Como $\gcd(d,25)=1$, encontramos a$u,v$$ud+25v=1$. A continuación, $u\Delta p + 25vx^{d-1}$ es monic, divisible por $25$ a los números enteros y tiene un grado $d-1$. Modulo $4$, todos los monomials son congruentes en interger argumentos a uno de $1, x, x^2, x^3$ (debido a $x^4\equiv x^2\pmod 4$), por lo tanto la divisibilidad por $4$ puede lograrse mediante la adición de un grado $3$ polinomio $q$. Por lo tanto $u\Delta p + 25vx^{d-1}+q$ es monic, de grado $d-1$ y un múltiplo de $100$ a los números enteros - contradicción. Llegamos a la conclusión de que $d\ge 10$ (y se hacen) o $d\le 5$.