Proving a number is divisible by 48

  1. I am trying to prove that for an integer n, if even, then n(n^2 + 20) is divisible by 48.

    I have done all the obvious, that is subtituting n with 2k for some integer k, which yields 8k(k^2 + 5). And this is where I get stuck.

    Where do I go next? k^2 + 5 does not factor.
     
  2. jcsd
  3. Hurkyl

    Hurkyl 16,090
    Staff Emeritus
    Science Advisor
    Gold Member

    Well, if it's divisible by 48, then it should be equal to 0 mod 48, right?
     
  4. mathwonk

    mathwonk 9,703
    Science Advisor
    Homework Helper

    is it true for k=1?, k=2?,...
     
  5. shmoe

    shmoe 1,994
    Science Advisor
    Homework Helper

    You're down to trying to show 8k(k^2+5) is divisible by 48. It's enough to should that k(k^2+5) is divisible by 6, which can be done by considering this equation mod 6.
     
  6. Right :D

    Yes, it is true for 1 and 2. Haha, that's where I usually get into some trouble, making things general. I can find millions of examples, but it takes me forever to find a way to make it into a generalization.

    Ok, so I've tried this. I made a statement that since 8k(k^2+5) is divisible by 8, then I need to show that 6 divides k(k^2+5).I have tried a few numbers, 1 for example and it leaves a remainder of 1.

    Right now, I'm trying to apply a rule for whether or a not a number is divisible by 6 to k(k^2+5). Am I straying from what you intended me to do?
     
  7. Hurkyl

    Hurkyl 16,090
    Staff Emeritus
    Science Advisor
    Gold Member

    There are only 6 numbers to try...
     
  8. shmoe

    shmoe 1,994
    Science Advisor
    Homework Helper

    If your rule for determining if a number is divisible by 6 involves doing something to the digits, then you're going the wrong way.

    Maybe try breaking it up into even smaller problems, can you show k(k^2+5) is divisible by 2?

    (related question, can you show for any n that n(n+1) is divisible by 2?)

    edit-I'm going slower than Hurkyl's post last post is suggesting. Try to understand his post first if you can!
     
  9. Haha, you're going to have to excuse me Hurkyl, I'm just a beginner with congruencies. Do you mind elaborating a little more?

    I know I need to show that [tex]n(n^2+20) \equiv 0 \mod \48[/tex]. With n being even, then [tex]2k(2k^2+20) \equiv \0 \mod \48[/tex] for some integer k...

    :cry: thats as far as i can go
     
  10. To sum up Shmoe's suggestion, if it is always the case for any k, that at least one of the two factors k and K^2+5 is divisible by 2; and, also that at least one of the two factors is divisible by 3, then the product is necessarily divisible by 2*3. Hint you should of course know that for any P, if k^n = a mod P then (k+P)^n = a mod P as every term of the polynominal expansion of the later equation, except k^n, = 0 mod P.
     
  11. I wasn't aware of this property.
    :cry:
     
  12. Hurkyl

    Hurkyl 16,090
    Staff Emeritus
    Science Advisor
    Gold Member

    Sure you were. P = 0 (mod P), right?
     
  13. mathwonk

    mathwonk 9,703
    Science Advisor
    Homework Helper

    have you heard of induction?
     
  14. Yes I have, but my professor has not yet taught us induction. So I am probably not supposed to use it. I heard it's much easier doing this proof by induction as well. :( Just my luck.
     
  15. matt grime

    matt grime 9,396
    Science Advisor
    Homework Helper

    One thing you seem not to have noticed yet is that when you're dealing with an expression, such as x^2+5, modulo some number you can replace any term with an equivalent one modulo that number. For instance, we need to show that k^k^2+5) is divisible by 6, ie is zero mod 6. 5 is the same thing as -1 mod 6, so that

    k(k^2+5)=k(k^2-1) mod 6

    and k^2-1=(k+1)(k-1)

    so we are trying to show that k(k-1)(k+1) is divisible by 6. But it's the product of three consecutive numbers so what must be true about them, I mean can there be three consecutive odd numbers?
     
  16. Oh wow, I didn't know I could do that.

    So let's say I had something like [tex]5x^2 + 7x + 1[/tex], can I replace 5, 7 and 1 by a congruence?
     
  17. matt grime

    matt grime 9,396
    Science Advisor
    Homework Helper

    Yes, but it is only equivalent modulo whatever it is you're doing it modulo

    x^2+5 is the same as x^2-1 mod 6 (and mod 3, and mod 2 as well) but they are not equivalent mod 7 for instance.
     
  18. Gokul43201

    Gokul43201 11,141
    Staff Emeritus
    Science Advisor
    Gold Member

    [tex]5x^2 + 7x + 1 \equiv 5x^2 + 7x + 1 + kp + lpx + mpx^2 + ... ~~(mod~p) ~\equiv (5+mp)x^2 + (7+lp)x + (1+kp) + ... ~~(mod~p)[/tex]

    Do you see why this is true ?
     
    Last edited: May 25, 2005
  19. I can derive a conclusion from this statement you made.. That is we know that at least one of these must be an even number, as well I can see how it is divisible by 3 and 2. Ahhh nevermind, now I see how it is divisible by 6. I think I do.

    Because 3 * 2 = 6, therefore it must also be divisible by 6? Is that correct?
     
  20. I see that you added some integers kp, lpx and mpx^2 to the original equation. And thats perfectly fine from what I understand. Then you grouped like-terms together in the last congruence.

    Let's see if I can apply it. Let's say p = 5, does that mean then it is congruent to:
    [tex]0 + 2x + 1 (mod~5)[/tex]?

    How I derived this:
    [tex]5 \equiv 0 (mod~5)[/tex] therefore [tex]5x^2 \equiv 0x^2 (mod~5) = 0[/tex]
    [tex]7 \equiv 2 (mod~5)[/tex] therefore [tex]7x \equiv 2x (mod~5)[/tex]
    [tex]1 \equiv 1 (mod~5)[/tex]
     
    Last edited: May 25, 2005
  21. Gokul43201

    Gokul43201 11,141
    Staff Emeritus
    Science Advisor
    Gold Member

    Yes, that's correct. And that's why matt's little trick does not alter the residue, while making the quadratic conveniently factorizable.
     
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook

Have something to add?