1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Oct 12, 2008 #1
    1. The problem statement, all variables and given/known data

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

    3. The attempt at a solution

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

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

    [tex]\frac{\frac{n(n-1)}{2}}{2^{k-1}}=\frac{m}{2}(n-1)[/tex]

    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. jcsd
  3. Oct 12, 2008 #2

    gabbagabbahey

    User Avatar
    Homework Helper
    Gold Member

    you've already shown that m is not divisible by 2; so how could (m/2)(n-1) be an integer?
     
  4. Oct 12, 2008 #3

    Borek

    User Avatar

    Staff: Mentor

    [tex]\frac {\frac {n(n-1)} {2}}{2^{k-1}} = \frac {n(n-1)} {2^k}[/tex]

    n is even.
     
  5. Oct 12, 2008 #4
    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 [tex]k\geq 1[/tex]?
     
  6. Oct 12, 2008 #5

    gabbagabbahey

    User Avatar
    Homework Helper
    Gold Member

    n=2^(k-1)m which is an integer, m multiplied by some (positive integer) power of 2...hence n must be even
     
  7. Oct 13, 2008 #6
    But if k=1 I then have 2^0*m=m.
     
  8. Oct 13, 2008 #7

    gabbagabbahey

    User Avatar
    Homework Helper
    Gold Member

    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.
     
  9. Oct 13, 2008 #8
    Why does it imply that?
     
  10. Oct 13, 2008 #9

    gabbagabbahey

    User Avatar
    Homework Helper
    Gold Member

    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.
     
  11. Oct 13, 2008 #10
    Yes, 1 is a trivial divisor, but why is it that k=1 implies that I'm counting 1 as a non-trivial divisor?
     
  12. Oct 13, 2008 #11

    gabbagabbahey

    User Avatar
    Homework Helper
    Gold Member

    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).
     
  13. Oct 13, 2008 #12
    Aaah, I get it now! Thank you!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Show that 2^(k-1) doesn't divide n(n-1)/2
Loading...