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.

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

2 Answers 2

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

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.