Convertir $x \not\equiv 0$ mod $pq$ a un polinomio módulo

Question

$p,q \in \mathbb{P}$ , primos

Para $x \not\equiv 0 \bmod p$ puedes escribir $(x-1)(x-2) \dots (x - (p-1)) \equiv 0$ mod $p$

¿Hay alguna manera de hacer lo mismo para un módulo compuesto $pq$ ?

Nota: $(x-1)(x-2) \dots (x-p) \dots (x-q) \dots (x - (pq-1)) \equiv 0$ mod $pq$ no funciona. Si $x \equiv 0$ mod $pq$ entonces los términos $(x-p)$ y $(x-q)$ se convierten en $pq$ lo que hace que el polinomio $\equiv 0$ mod $pq$ .

También $x^{(p-1)(q-1)} \equiv 1$ mod $pq$ si $\gcd(x,pq) = 1$ no cubre el caso cuando $x = kp$ o $x = kq$ .

------- para aclarar ------------------------------------------

Encuentra un polinomio módulo pq tal que $x \equiv 0 $ (mod pq) es no una solución, pero todos los demás números son soluciones, es decir, un filtro.

Esto se puede hacer si el módulo es un único primo.

@André Nicolas demostró que no se puede hacer para un módulo compuesto.

Answer 1

Dejemos que $f(x)$ sea un polinomio. Supongamos que los primos distintos $p$ y $q$ son raíces de $f(x)\equiv 0\pmod{pq}$ .

Desde $(x-p)(x-q)$ es mónico, existe un polinomio $g(x)$ tal que $f(x)=(x-p)(x-q)g(x)+ax+b$ para algunos enteros $a$ y $b$ .

Desde $p$ y $q$ son raíces de $f(x)\equiv 0\pmod{pq}$ se deduce que $pq$ divide $ap+b$ y $pq$ divide $aq+b$ . Así que $p$ y $q$ ambos se dividen $b$ y por lo tanto $p$ y $q$ ambos se dividen $a$ .

De ello se desprende que $pq$ divide $f(pq)$ .

Nota: : En retrospectiva, hay una prueba de una línea. Ya que $f(0)\equiv 0\pmod{p}$ y $f(0)\equiv 0\pmod{pq}$ se deduce que $f(0)\equiv 0\pmod{pq}$ . Pero también podría mantener mi feo argumento de arriba: es lo que escribí primero.