La generalización de Lagrange del teorema $(1768)$?

Question

Aquí está el teorema :

Deje $p$ un primer número y $u_0,...,u_n$, una lista de números enteros tales que a $p\not \mid u_n$. Entonces : $u_nx^n+...+u_1x+u_0 \equiv 0\pmod p$ admite que en la mayoría de las $n$ soluciones de $\pmod p$.

La prueba puede realizarse mediante la inducción en $n$ y la propiedad de la primer número $p$.

Ahora, me pregunto cómo funcionará si tenemos en cuenta un número entero $k$ en lugar de $p$. La declaración se tendrá :

Deje $k$ un entero y $u_0,...,u_n$, una lista de números enteros tales que a $\gcd(k,u_n)=1$. Entonces, ¿cuántas soluciones $\pmod k$ la ecuación : $u_nx^n+...+u_1x+u_0 \equiv 0\pmod k$ admite ?

Creo que se puede empezar con la descomposición teorema $k=p_1^{a_1}...p_l^{a_l}$. Tal vez se le dará un sistema en el CRT estilo.

Aquí está mi intento :

Primer hecho importante : si $k\mid u_n\Leftrightarrow p_1^{a_1}...p_l^{a_l}\mid u_n\Rightarrow \exists i\in \{1,...,l\}, \ p_i^{l_i}\mid u_n$.

Para un factor de $p_i^{a_i}$ tratamos de encontrar el número de soluciones $\pmod{p_i^{a_i}}$ de la ecuación : $u_nx^n+...+u_1x+u_0\equiv 0 > \pmod{p_i^{a_i}}$.

Por inducción en $n$ me han :

-Para $n=0$ : la ecuación se convierte en : $u_1x\equiv -u_0 \pmod{p_i^{a_i}}$.

La ecuación se convierte en $u_1x\equiv -u_0 \pmod{p_i^{a_i}}$. Pero tenemos $\gcd(u_1,p_i)=1$ y por la propiedad de Bézout podemos deducir que $\gcd(u_1,p_i^{a_i})=1$. Por lo $u_1$ tiene una inversa elemento y podemos tome $x\equiv -u_1^{-1}u_0 \pmod{p_i^{a_i}}$, lo que representa una solución (la única).

-Para $n=n+1$ : la ecuación se convierte en $u_{n+1}x^{n+1}+u_nx^n+...+u_1x+u_0\equiv 0 \pmod{p_i^{a_i}}$.Si Me considere la posibilidad de $y$ una solución de la ecuación con la multiplicidad $e=1$ por ejemplo, tenemos el hecho de que podemos factorizar la ecuación por $(x-y)^{e}$ .

Da $(x-y)^{e}P(x)\equiv 0 \pmod{p_i^{a_i}}$ $P$ un grado $n$ polinomio y con el más alto coeficiente de $u_{n+1}$ tal que $\gcd(p_i^{a_i},u_{n+1})=1$. De manera que la ecuación admite en la mayoría de las $n+1$ soluciones de $\pmod{p_i^{a_i}}$.

Por lo que hay en la mayoría de las $n$ soluciones para$\pmod{p_i^{a_i}}$, y para cada uno de los $i\in \{1,...,l\}$.

Si quiero usar el CRT se da un systeme de $l$ líneas donde cada los polinomios de admitir que en la mayoría de las $n$ soluciones. ¿Cómo puedo concluir $\pmod k$ (no es un campo) ?

Si suponemos que para cada una de las $p_i^{a_i}$ hay en la mayoría de las $n$ soluciones que podemos factorizar la $l$ líneas con $n$ factores.

Por desgracia, este hecho es falso (ver el $(x-1)(x-2)(x-4)\equiv 0 \pmod{9}$ han $4$ soluciones en lugar de $3$).

Aquí está el principal sistema :

$\left\{\begin{array}{rl} u_{n}(x-x_{1_1})(x-x_{1_2})...(x-x_{1_n}) &\equiv 0 \pmod{p_1^{a_1}} \\ &\vdots \\ u_{n}(x-x_{i_1})(x-x_{i_2})...(x-x_{i_n}) &\equiv 0 \pmod{p_i^{a_i}} \\ &\vdots \\ u_{n}(x-x_{l_1})(x-x_{l_2})...(x-x_{l_n}) &\equiv 0 \pmod{p_l^{a_l}} \\ \end{array} \right.$

Y, por ejemplo, por Euclides del lema (para el caso de $(a_i)_{i\{1,...,l\}}=1$) para contar el número de sistemas : para $u_{n}(x-x_{1_1})$ tenemos $(n^{(l-1)})$ sistemas con una solución. Es el mismo para cada una de las $u_{n}(x-x_{i_j})$ $j\in \{1,...,n\}, \ i=1$ a la derecha.Si es el caso se le dará $n^l$ soluciones.

Gracias de antemano !

Answer 1

Por el CRT, el número de soluciones de mod $k$ es el producto de los números de las soluciones de mod $p_i^{a_i}$. Así que reducir a trabajar mod $p^a$. Pero usted desea hacer su suposición $\gcd(k, a_n) =1$, no $k \not\mid a_n$.

Supongamos que el polinomio $f(x)$ tiene el grado $n$. Mod $p$ puede tener hasta $n$ lineal factores, contados por la multiplicidad. Cada solución de mod $p^{a}$ es también una solución de mod $p$. Hensel del lema dice que si $f(r) \equiv 0 \mod p$$f'(r) \not\equiv 0 \mod p$, no hay una única solución de $f(x)=0 \mod p^a$ tal que $x \equiv r \mod p$. Pero si $f'(r) \equiv 0 \mod p$ ($r$ es un múltiplo de la raíz de mod $p$), no puede ser más: tal vez como muchos como $p^{a-1}$. Así que si $a > 1$ tenemos un atado de $p^{a-1} n/2$ soluciones de mod $p^a$. Probablemente este no sea el mejor posible, pero es un comienzo.

Answer 2

El teorema del resto Chino reduce la solución de conteo para el primer potencias $k = p^a$.

Supongamos que $f(x)$ es monic (o invertible grado más alto coeficiente de mod $p$) y el de la factorización de $f(x) \mod p =(x - r_1)^{e_1} (x-r_2)^{e_2} \cdots (x - r_h)^{e_h} \cdot g(x)$ donde $r_i$ son distintos mod $p$ enteros, y $g(x)$ no tiene soluciones mod $p$.

El número de $N_t$ de soluciones de $f(x)=0$ mod $p^t$ (suma de $i$ el número de soluciones de $(x-r_i)^{e_i} = 0 \mod p^t$) = $\sum p^{t - \lceil t/e_i \rceil}$, independiente de $g(x)$. Para la renta fija de grado de la $d$ el número de soluciones se maximiza cuando se $f(x)=(x-r_1)^d$.