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.

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.

share|improve this question
    
$a(a+1)=a^2+a$. –  Holdsworth88 Jan 23 '12 at 2:40

4 Answers 4

up vote 8 down vote accepted

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

share|improve this answer
4  
Alas, this argument is either incorrect, incomplete, or circular. It would help to elaborate so it is clear what you intend. –  Bill Dubuque Jan 23 '12 at 3:22
8  
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. –  Bill Dubuque Jan 23 '12 at 3:59
13  
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$? –  robjohn Jan 24 '12 at 0:47
16  
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) –  user16299 Jan 24 '12 at 0:51
9  
I find Bill Dubuque's first comment on this answer useful and insightful. –  user23211 Jan 24 '12 at 1:03

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

share|improve this answer
2  
This question is of such an elementary nature, the Fundamental Theorem of Arithmetic seems like overkill. –  robjohn Jan 24 '12 at 1:53
2  
@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? –  Ilmari Karonen Feb 11 '12 at 0:22
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. –  robjohn Feb 11 '12 at 0:40
2  
@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. –  Marc van Leeuwen Dec 26 '12 at 7:03

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.

share|improve this answer
12  
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? –  robjohn Jan 24 '12 at 15:54
2  
I don't understand the hints, but colors the bright colors are excellent so +1. ;) –  David H Jul 10 '13 at 10:54

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

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.