7
$\begingroup$

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.

  • 0
    $a(a+1)=a^2+a$.2012-01-23

4 Answers 4

1

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

31

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.

  • 13
    I don't understand the downvotes. The hint is excellent and would be a proof if the induction were spelled out. Anyone care to explain?2012-01-24
6

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

  • 2
    @Paul Probably the reason that Bill did not *immediately* point out the specifics of the problem with your argument is that he thought that it would provide you with$a$better learning experience if you discovered it for yourself, using the hint that he provided. As you can see from his posts here, Bill is really big on hints. This can be$a$very effective way to teach (speaking from first-hand experience).2012-01-24
6

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

  • 3
    @robjohn: Your point would hold if this question came up in a deductive text in elementary number theory. However it seems extremely unlikely that this question would serve at any point in a proof of the Fundamental Theorem of Arithmetic.2012-12-26