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\ \ $ since $\rm\: \ \dfrac{b}c\, =\, \color{#0A0}{\dfrac{b\ (a+1)}c} -\ b\ \color{#C00}{\dfrac{a}c}\, \in\, \mathbb Z\! -\! b\,\Bbb Z\,\subset\, \Bbb Z$

Hence, by induction, $\rm\ \ c^k\ |\ b\ (a+1)\ \Rightarrow\ c^k\ |\ b\:.\ $ Yours is the 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$.

  • 4
    Alas, this argument is either incorrect, incomplete, or circular. It would help to elaborate so it is clear what you intend.2012-01-23
  • 9
    Don't you see the gap? Hint: does your argument work for the slightly more general case in my answer where $\rm\ 2\to c\:.$ It's still not clear to me *precisely* what you propose as proof since you leave too much unsaid. Precision is crucial, especially at this level. Without such, there's no way to distinguish a correct proof (missing details) from one that is incorrect, circular, etc.2012-01-23
  • 2
    @Dan The point is that one needs to justify such inferences, and such justification is lacking in the above answer. Without such justification the proof can be rightfully criticized as above. At this elementary level it is *essential* to *explicitly* mention such. Again, see my answer.2012-01-23
  • 15
    You claim that because $a+1$ is not divisible by $2$, if $a(a+1)$ is divisible by $2^k$, then $a$ is divisible by $2^k$. Let me rephrase in such a way that I don't change any of what you have claimed. Because $b$ is not divisible by $6$, if $ab$ is divisible by $6^k$, then $a$ is divisible by $6^k$. However, let $a=9$ and $b=4$. $b$ is not divisible by $6$, and $ab$ is divisible by $6^2$, your argument would conclude that $9$ is divisible by $6^2$. In what way is $2$ different than $6$?2012-01-24
  • 17
    My guess (but perhaps I have misinterpreted him) is that Bill's point is that your proof implicitly uses the fact that $2$ is prime and hides an inductive step. It is not that there is a mistake per se in your proof, but that the same formal argument does not quite work in similar settings, showing that there are hidden assumptions. (It comes down, as said in Bill's answer below, to a use of the Euclidean algorithm to *prove* these "obvious" facts about factorization of integers)2012-01-24
  • 10
    I find Bill Dubuque's first comment on this answer useful and insightful.2012-01-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$.

  • 2
    This question is of such an elementary nature, the [Fundamental Theorem of Arithmetic](http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic) seems like overkill.2012-01-24
  • 3
    @robjohn: Maybe so, but it's such a _convenient_ tool. Sure, you could light a fire by rubbing two sticks together, but why bother (except to learn how it's done) when you can use a lighter?2012-02-11
  • 2
    If, when proving very elementary results, one uses a result that is far more advanced, there is a great risk of getting caught in a circular argument, where the simple result is, in some part, used to prove the more advanced one.2012-02-11
  • 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