# Show that 2^(k-1) doesn't divide n(n-1)/2

1. Oct 12, 2008

### _Andreas

1. The problem statement, all variables and given/known data

$$2^{k-1}$$ divides n, while $$2^k$$ does not. Show that $$2^{k-1}$$ does not divide $$\frac{n(n-1)}{2}$$.

3. The attempt at a solution

That $$2^{k-1}$$ divides n implies that $$n=2^{k-1}m$$, where m is an integer.

$$\frac{n}{2^k}=\frac{m}{2}$$, which implies that $$2$$ does not divide m, which in turn implies that $$k\geq 1$$.

$$\frac{\frac{n(n-1)}{2}}{2^{k-1}}=\frac{m}{2}(n-1)$$

However, the last expression seems like it could still be an integer, given the premises above. Am I missing something?

(Intermediate steps are not shown because I've recalculated them several times and found them to be correct. I'm pretty sure there must be something else that's wrong or missing.)

Last edited: Oct 12, 2008
2. Oct 12, 2008

### gabbagabbahey

you've already shown that m is not divisible by 2; so how could (m/2)(n-1) be an integer?

3. Oct 12, 2008

### Staff: Mentor

$$\frac {\frac {n(n-1)} {2}}{2^{k-1}} = \frac {n(n-1)} {2^k}$$

n is even.

4. Oct 12, 2008

### _Andreas

Of course, m is an odd integer if it isn't divisible by 2, so if n is even I have shown what I'm supposed to show. But how can n be even if $$k\geq 1$$?

5. Oct 12, 2008

### gabbagabbahey

n=2^(k-1)m which is an integer, m multiplied by some (positive integer) power of 2...hence n must be even

6. Oct 13, 2008

### _Andreas

But if k=1 I then have 2^0*m=m.

7. Oct 13, 2008

### gabbagabbahey

Your condition should be that k>1...k≠1 because k=1 implies that you are counting k^0=1 as a non-trivial divisor of n.

8. Oct 13, 2008

### _Andreas

Why does it imply that?

9. Oct 13, 2008

### gabbagabbahey

Because if k=1, 2^(k-1)=2^0=1....which is a trivial divisor (every integer is divisible by 1), so your non-trivial cases are k>1 not k≥1.

10. Oct 13, 2008

### _Andreas

Yes, 1 is a trivial divisor, but why is it that k=1 implies that I'm counting 1 as a non-trivial divisor?

11. Oct 13, 2008

### gabbagabbahey

Because one of the premises of your proof is that n is divisible by 2^(k-1); but if k=1, then that premise is trivial.

Considering that you are trying to show that n(n-1)/2 is not divisible by 2^(k-1); it seems reasonable that you assume that the problem refers to a non-trivial 2^(k-1).

12. Oct 13, 2008

### _Andreas

Aaah, I get it now! Thank you!