Given integers $a$, $k$, and $n$, and given that $a(a+1)=n(2^k)$, how do I prove that (assuming $a$ is even), $2^k|a$?
I read this in a proof, and I can't figure out how to verify it myself.
Given integers $a$, $k$, and $n$, and given that $a(a+1)=n(2^k)$, how do I prove that (assuming $a$ is even), $2^k|a$?
I read this in a proof, and I can't figure out how to verify it myself.
Let $a=2^x*b$ with $b$ odd and $x \ge 1$, and let $y = x - k$. Now the equation can be written as $n = 2^y*b*(a+1)$. Because both $b$ and $a+1$ are odd and $n$ is an integer, $y \ge 0$. But then $a = 2^x*b = 2^k*2^y*b$ and therefore $2^k \vert a$.
Hint $\: \ $ If $\rm\:\ \color{#C00}{c\ |\ a}\ \:$ then $\rm\:\ \color{#0A0}{c\ |\ b\ (a\!+\!1)}\ \,\Rightarrow\,\ c\ |\ b, \ $ by $\rm\: \ \dfrac{b}c\, =\, \color{#0A0}{\dfrac{b\ (a\!+\!1)}c} -\ b\ \color{#C00}{\dfrac{a}c}\, \in\, \color{#0a0}{\Bbb Z}\! -\! b\,\color{#c00}{\Bbb Z}\,\subset\, \Bbb Z$
Hence, by induction, $\rm\ \ c^k\ |\ b\ (a\!+\!1)\ \Rightarrow\ c^k\ |\ b.\ $ OP is special case $\rm\ c = 2,\ \: b = a$
Remark $ $ More generally: $\rm\ c^k\ |\ b\ d\ \, \Rightarrow \ c^k\ |\ b\ \:$ if $\rm\:\ gcd(c,d) = 1\ \ $ by Euclid's Lemma.
If $a$ is even, then $a+1$ is odd which is not divisible by $2$. Therefore, if $a(a+1)=n(2^k)$, i.e. if $a(a+1)$ is divisible by $2^k$, we must have $a$ us divisible by $2^k$, since $a+1$ is not divisible by $2$.
For example, take $a=24$, then $a+1=25$ and $a(a+1)=75(2^3)$. Since $a+1=25$ is odd, it is not divisible by $2$. Therefore, $2^3$ must divide $a=24$.
Consider the prime factorization of $a + 1$. Since $a$ is even, $a + 1$ is not. Now consider the prime factorization of $a(a + 1)$: $2^k$ must appear somewhere, and no 2 is contributed by the factorization of $a + 1$, so that $2^k$ must appear in the prime factorization of $a$.