# proving there exists an integer $k$ such that $ak^2+bk+c\equiv 0 \pmod{2^n}$ by induction

$n$ is a given positive integer. how to prove by using mathematical induction that there exists an integer $k$ such that $ak^2+bk+c\equiv 0 \pmod{2^n}$, where $b$ is odd and at least one of $a, c$ is even

-

First check directly that the result holds for $n=1$.

We do the induction step. Let $x$ be an integer such that $$ax^2+bx+c\equiv 0\pmod{2^{n-1}}.$$ We would like to show that there is an integer $y$ such that $ay^2+by+c\equiv 0\pmod{2^n}$.

If $2^n$ already divides $ax^2+bx+c$, we are finished. So we need only worry about the case where $ax^2+bx+c\equiv 2^{n-1}\pmod{2^n}$.

Try for a $y$ of the shape $x+t$. So we want $$a(x+t)^2+b(x+t)+c\equiv 0\pmod{2^n}.$$ But $ax^2+bx+c\equiv 2^{n-1}\pmod{p}$. So we want the difference $$[a(x+t)^2+b(x+t)+c]-[ax^2+bx+c]$$ to be congruent to $2^{n-1}$ modulo $2^n$. That is, we want to choose $t$ so that $$a(2xt+t^2)+bt\equiv 2^{n-1}\pmod{2^n}.$$ Note that $t=2^{n-1}$ works, since $b$ is odd and $2t$ and $t^2$ are each divisible by $2^n$.

-

Preliminary. We have $x\mid \big(f(x+h)-f(h)\big)$ in polynomial rings (set $x=0$ to see), so

$$\begin{array}{c l} f(x+h)& =f(x)+h\frac{f(x+h)-f(x)}{h} \\ & =f(x)+hg(x,h) \\ & =f(x)+hg(x,0)+h^2\frac{g(x,h)-g(x,0)}{h}.\end{array}$$

Hence if $h^2\equiv0\bmod \ell$, we get $f(x+h)\equiv f(x)+hf\,'(x)\bmod \ell$.

Thus $f(k+2^n)\equiv f(k)+b2^n\bmod 2^{n+1}$. Using $ab\mid ac\iff b\mid c$ with $a=2^n$, we obtain

$$\begin{cases} 2^{n+1}\mid f(k) & \iff & 2\mid \frac{f(k)}{2^n} \\[5pt] 2^{n+1}\mid f(k)+b2^n & \iff & 2\mid \frac{f(k)}{2^n}+b. \end{cases}$$

Remember $b$ is odd, so one of $\displaystyle\frac{f(k)}{2^n}$ or $\displaystyle\frac{f(k)}{2^n}+b$ is even.

-