Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

$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

share|cite|improve this question
up vote 1 down vote accepted

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$.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


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.