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

[_Andreas]

Homework Statement

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

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

 

[gabbagabbahey]

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

 

[Borek]

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

n is even.

 

[_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$$?

 

[gabbagabbahey]

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

 

[_Andreas]

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

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

 

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

 

[_Andreas]

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.

Why does it imply that?

 

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

 

[_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?

 

[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).

 

[_Andreas]

Aaah, I get it now! Thank you!