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!

Composite numbers and divisibility (2 problems)

  1. Sep 6, 2009 #1
    First of all, I hope this problem is supposed to be here - I'm Swedish and in Sweden "calculus" & "precalculus" are rather odd terms. Anyway..


    1. The problem statement, all variables and given/known data
    Prove that n3 - n is divisible by 6 if n is a natural number, and divisible by 24 if n is an odd natural number.


    2. Relevant equations



    3. The attempt at a solution
    There were two problems similar to this before this one and I attempted to solve it in the way I solved those (and the way the book solved them, as well), which was to split n into its even case and odd case.

    Even case:

    n = 2k

    (2k)3 - 2k = 8k3 - 2k , which obviously didn't help me much. But, as I'd used earlier for previous exercises, k can either be even or odd. If k is, say, even, k = 2s

    8(2s)3 - 2(2s) = 64s3 - 4s .. and I can continue on, but nothing is divisible by 6..

    And I've done the same for k = 2s + 1, which also doesn't work out. And I tried the odd case I mentioned earlier (n=2k +1) and that doesn't work out and I'm so close to screaming in frustration it's not even funny..






    1. The problem statement, all variables and given/known data
    Show that if n is a composite number it has a divisor greater than or equal to n½.

    2. Relevant equations


    3. The attempt at a solution
    My problem is that, yes, I absolutely and completely agree with the statement due to logic, but I've not a clue where to start the proof.. I'm not asking for someone to show me the proof, but a tip as to where to start?
     
    Last edited: Sep 6, 2009
  2. jcsd
  3. Sep 6, 2009 #2

    rock.freak667

    User Avatar
    Homework Helper

    Try proof by induction

    assume true for n=k

    Hk: k3-k=6A (A= integer)

    so Hk+1=(k+1)3-(k+1)

    expand and see if you can use k3-k=6A to show that Hk+1 is 6*something.
     
  4. Sep 6, 2009 #3
    I wanted to use mathematical induction, but we're not supposed to have learnt it yet (I just started a course at university, and we did induction at my previous school).

    And so, I tried MI, with the result: 6A + 3k2 + 3k .. divisible by 3, but not by 6.

    This problem is behaving very strangely, because at the same time I can plug in numbers and see that it is in fact true x/
     
  5. Sep 6, 2009 #4
    Make a substitution k=k3-6A, and see what you will come up with. :smile:

    6A+3(k3-6A)2+3(k3-6A) ?
     
  6. Sep 6, 2009 #5
    For the divisible by six, did you try just factoring the expression? Then your subbing in trick (2k+1) will work for the second half.

    For your second proof (that a composite number has a factor greater than [tex]\sqrt{n}[/tex], did you try contradiction?
     
  7. Sep 7, 2009 #6

    VietDao29

    User Avatar
    Homework Helper

    Well, as pointed out by rock.freak667 in some earlier post, Proof of Induction can be used here.

    But, if you really want to solve the problem by splitting up into 2 cases, where n is even, and n is odd, you can try to factor. Like this:

    Notice that the final expression is already divisible by 2, so what's left is to prove that the rest is divisible by 3. And it's done. So,

    (2k)3 - 2k = 8k3 - 2k
    = 2(4k3 - k)
    = 2k(4k2 - 1)
    = 2k(2k - 1)(2k + 1)

    Look at the final expression, can you see why it's divisible by 6?

    Hint:
    - Is it divisible by 2? Why?
    - Is it divisible by 3? And why?

    ---------------------------

    And for the case where n is odd, you can tackle it in pretty much the same manner. Let's see if you still get suck. :)

    ---------------------------

    If n is a composite number, then there must exists some number a, and b, such that: n = ab, right? :)

    Now, let's do a little bit thinking, can both a, and b be less than n½?
     
    Last edited: Sep 7, 2009
  8. Sep 7, 2009 #7

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    I wouldn't use induction.

    [itex]n^3- n= n(n^2- 1)= (n-1)n(n+1)[/itex], the product of three consecutive numbers. You should show that, of any three consecutive numbers, at least one must be even and at least one must be a multiple of 3 so their product is a multiple of 6.

    If n is odd, then both n-1 and n+1 are even. Further, of two consecutive even numbers, 2k and 2k+2, one is a multiple of 4. (Look at the cases where k is even or odd.)
     
  9. Sep 7, 2009 #8
    Thanks for that last thing, that's exactly what I needed! :)

    And no, both a and b can't be less than n½, because there's no way it could become n. The thing is, I fully understand the logic, that either it's n½ * n½ or a>n½ * b<n½ (or the other way around, obviously).. but I can't get how to put it in mathematical language ..
     
  10. Sep 7, 2009 #9

    VietDao29

    User Avatar
    Homework Helper

    Ok, that's what we call http://en.wikipedia.org/wiki/Proof_by_contradiction" [Broken], i.e, you are asked to prove some statement P. Now, you assume that you don't have P (i.e, P is false), and from there, try to find the contradiction.

    So, start from assuming that: "that composite number has a divisor greater than or equal to n½" is a false statement. Can you write out the negation of that statement? And then, what happens?
     
    Last edited by a moderator: May 4, 2017
  11. Sep 9, 2009 #10
    Oh yeah, I'd completely forgotten Proof by Contradicton.. hum. We never focused on it much.

    Anyway, I'd say something like:

    n=ab, a<n½, b<n½

    so, n < n½ * n½, but since it's the same base, n½ * n½ should be n1, and there's our contradiction.

    That's at least how I remember proof by contradiction..
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Composite numbers and divisibility (2 problems)
  1. Division problem (Replies: 6)

Loading...