Resolver la congruencia cuadrática general mod $2^k$

Question

Bajo qué condiciones en $a,b,c,k$, existe una solución a $$ax^2+bx+c\equiv 0 \pmod{2^k}?$$

Relacionados con las cosas que yo creo que es cierto:

1. Si $2$ fueron en lugar de un extraño prime, existe una solución, precisamente cuando el discriminante $b^2-4ac$ es un residuo cuadrático módulo que extraño prime, completando el cuadrado y Hensel del lexema.

2. Si $b=0$, esto se simplifica a $x^2\equiv d \pmod{2^m}$. Dependiendo de si $m=1$, $m=2$, o $m\ge 3$, hay pruebas en $d$ a determinar si existen soluciones. por ejemplo, enlace o pregunta relacionada con la

3. Si todos los tres de $a,b,c$ son incluso, podemos dividir por $2$ y reducir el $k$ por 1. Por lo tanto podemos suponer que al menos uno de $a,b,c$ es impar.

4. Si $a,b$ son ambos inclusive, a continuación, $c$ debe ser, incluso, la reducción para el caso 3.

5. Si $a$ es impar y $b$ es incluso, podemos dividir por $a$ y completar el cuadrado, la reducción para el caso 2.

Una respuesta para $b$ impar por lo tanto, sería suficiente, empedradas junto con el anterior; sin embargo sería mejor tener una solución unificada.

Answer 1

Una respuesta parcial solamente. El trato con el caso de un extraño $b$.

Supongamos primero que $a$ es incluso.

Consideremos la función polinómica $f(x)=ax^2+bx$ a partir de los residuos anillo de la clase $R=\mathbf{Z}_{2^m}$ a sí mismo. Afirmo que esta función es bijective. Como el anillo de $R$ es finito, es suficiente para mostrar que $f$ es inyectiva. Para ver esto consideremos la posibilidad de que $$ f(x)\equiv f(y)\pmod{2^m}. $$ Esto significa que $$2^m\mid f(x)-f(y)=a(x^2-y^2)+b(x-y)=(x-y)(b+a(x+y)).$$ Aquí el segundo factor $b+a(x+y)$ es siempre impar, como $a(x+y)$ es siempre igual, y $b$ fue asumido para ser impar. Así, por $2^m$ brecha $f(x)-f(y)$ es necesario (y, obviamente, también suficiente)$2^m\mid(x-y)$. Pero no es nuestra pretensión.

Desde el bijectivity de $f$ que se deduce que las soluciones de la congruencia $$ f(x)\equiv -c \pmod{2^m} $$ formar un único residuo de la clase modulo $2^m$ independientemente del valor de $c$.

Veamos a continuación asumen que $a$ $b$ son ambos impares.

Claramente $ax^2+bx$ es entonces siempre igual, así que para esta ecuación para ser resueltos debemos tener $2\mid c$. Yo reclamo que una solución de $x$ (de hecho, dos soluciones distintas) siempre existen para cualquiera incluso $c$.

Para ver esto vamos a estudiar la función de $p(x)=ax^2+bx$. Considerar la posibilidad de que $p(x)=p(y)$ para algunos de los elementos $x,y\in R$. Esto es equivalente a $$ 2^m\mediados de p(x)-p(y)=(x-y) ((x+y)+b). $$ Aquí siempre $x-y\equiv x+y\pmod2$. Como $a$ $b$ son ambos impares, esto implica que los dos factores, $x-y$$a(x+y)+b$, se han opuesto a las paridades. Por lo tanto, se deduce que $2^m$ debe dividir uno de ellos, y podemos concluir que cualquiera de las $y\equiv y_1\equiv x\pmod{2^m}$ o $ay\equiv-b-ax\pmod{2^m}$. Como $\gcd(a,2^m)=1$, el último de la congruencia tiene un único $y_2\in R$ como una solución. Además $y_2\not\equiv x\pmod{2}$, lo $y_1\not\equiv y_2\pmod{2^m}.$

Así vemos que, como una función de $R$ a sí mismo, el polinomio $p$ alcanza todos los valores de su rango de exactamente el doble (de dos a uno). Por lo tanto,$|p(R)|=|R|/2$. Como el rango es un subconjunto de incluso el residuo de clases, podemos concluir que $p(R)=2R$.

Como conclusión, podemos decir que cuando ambos $a$ $b$ son impares, el original de la congruencia tiene dos no congruentes soluciones, si $c$ es aún, y ninguno si $c$ es impar.