# Solving the general quadratic congruence mod $2^k$

Under what conditions on $a,b,c,k$, is there a solution to $$ax^2+bx+c\equiv 0 \pmod{2^k}?$$

Related things that I believe to be true:

1. If $2$ were instead an odd prime, a solution exists precisely when the discriminant $b^2-4ac$ is a quadratic residue modulo that odd prime, by completing the square and Hensel's lemma.

2. If $b=0$, this simplifies to $x^2\equiv d \pmod{2^m}$. Depending on whether $m=1$, $m=2$, or $m\ge 3$, there are tests on $d$ to determine whether solutions exist. e.g. link or related question

3. If all three of $a,b,c$ are even, we may divide by $2$ and reduce $k$ by 1. Hence we may assume at least one of $a,b,c$ is odd.

4. If $a,b$ are both even, then $c$ must be even, reducing to case 3.

5. If $a$ is odd and $b$ is even, we can divide by $a$ and complete the square, reducing to case 2.

An answer for $b$ odd would therefore be enough, cobbled together with the above; however it would be nicer to have a unified solution.

-
–  lab bhattacharjee Apr 19 '13 at 18:59
I'm afraid I don't see a unified treatment. The cases vary so much all according to how it looks like after reduction modulo $2$. –  Jyrki Lahtonen Apr 21 '13 at 20:54

A partial answer only. Dealing with the case of an odd $b$.

Assume first that $a$ is even.

Let us consider the polynomial function $f(x)=ax^2+bx$ from the residue class ring $R=\mathbf{Z}_{2^m}$ to itself. I claim that this function is bijective. As the ring $R$ is finite, it suffices to show that $f$ is injective. To see this consider the possibility that $$f(x)\equiv f(y)\pmod{2^m}.$$ This means that $$2^m\mid f(x)-f(y)=a(x^2-y^2)+b(x-y)=(x-y)(b+a(x+y)).$$ Here the second factor $b+a(x+y)$ is always odd, as $a(x+y)$ is always even, and $b$ was assumed to be odd. So for $2^m$ to divide $f(x)-f(y)$ it is necessary (and obviously also sufficient) that $2^m\mid(x-y)$. But this proves our claim.

From the bijectivity of $f$ it follows that the solutions of the congruence $$f(x)\equiv -c \pmod{2^m}$$ form a single residue class modulo $2^m$ irrespective of the value of $c$.

Let us then assume that $a$ and $b$ are both odd.

Clearly $ax^2+bx$ is then always even, so for this equation to be solvable we must have $2\mid c$. I claim that a solution $x$ (in fact two distinct solutions) always exist for any even $c$.

To see this let us study the function $p(x)=ax^2+bx$. Consider the possibility that $p(x)=p(y)$ for some elements $x,y\in R$. This is equivalent to $$2^m\mid p(x)-p(y)=(x-y)(a(x+y)+b).$$ Here always $x-y\equiv x+y\pmod2$. As $a$ and $b$ are both odd, this implies that the two factors, $x-y$ and $a(x+y)+b$, have opposite parities. Therefore it follows that $2^m$ must divide one of them, and we can conclude that either $y\equiv y_1\equiv x\pmod{2^m}$ or $ay\equiv-b-ax\pmod{2^m}$. As $\gcd(a,2^m)=1$, the latter congruence has a unique $y_2\in R$ as a solution. Furthermore $y_2\not\equiv x\pmod{2}$, so $y_1\not\equiv y_2\pmod{2^m}.$

So we see that as a function from $R$ to itself, the polynomial $p$ attains all the values in its range exactly twice (two-to-one). Therefore $|p(R)|=|R|/2$. As the range is a subset of even residue classes, we can conclude that $p(R)=2R$.

As a conclusion we can say that when both $a$ and $b$ are odd, the original congruence has two non-congruent solutions, if $c$ is even, and none if $c$ is odd.

-
Another way of handling the case $a,b$ odd, $c$ even, would be to first take the reciprocal congruence $cx^2+bx+a=0$, show that its sole root (see the early part of my answer) is odd, so it has a modular inverse that is a root of the original congruence. Then the other solution can be found with long division. –  Jyrki Lahtonen Apr 21 '13 at 20:56