Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
    
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

1 Answer 1

up vote 3 down vote accepted
+50

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.