# Proving a number is divisible by 48

1. May 24, 2005

### johnnyICON

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. May 24, 2005

### Hurkyl

Staff Emeritus
Well, if it's divisible by 48, then it should be equal to 0 mod 48, right?

3. May 24, 2005

### mathwonk

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

4. May 24, 2005

### shmoe

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.

5. May 24, 2005

### johnnyICON

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?

6. May 24, 2005

### Hurkyl

Staff Emeritus
There are only 6 numbers to try...

7. May 24, 2005

### shmoe

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!

8. May 24, 2005

### johnnyICON

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 $$n(n^2+20) \equiv 0 \mod \48$$. With n being even, then $$2k(2k^2+20) \equiv \0 \mod \48$$ for some integer k...

thats as far as i can go

9. May 24, 2005

### ramsey2879

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.

10. May 24, 2005

### johnnyICON

I wasn't aware of this property.

11. May 24, 2005

### Hurkyl

Staff Emeritus
Sure you were. P = 0 (mod P), right?

12. May 24, 2005

### mathwonk

have you heard of induction?

13. May 25, 2005

### johnnyICON

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.

14. May 25, 2005

### matt grime

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?

15. May 25, 2005

### johnnyICON

Oh wow, I didn't know I could do that.

So let's say I had something like $$5x^2 + 7x + 1$$, can I replace 5, 7 and 1 by a congruence?

16. May 25, 2005

### matt grime

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.

17. May 25, 2005

### Gokul43201

Staff Emeritus
$$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)$$

Do you see why this is true ?

Last edited: May 25, 2005
18. May 25, 2005

### johnnyICON

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?

19. May 25, 2005

### johnnyICON

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:
$$0 + 2x + 1 (mod~5)$$?

How I derived this:
$$5 \equiv 0 (mod~5)$$ therefore $$5x^2 \equiv 0x^2 (mod~5) = 0$$
$$7 \equiv 2 (mod~5)$$ therefore $$7x \equiv 2x (mod~5)$$
$$1 \equiv 1 (mod~5)$$

Last edited: May 25, 2005
20. May 25, 2005

### Gokul43201

Staff Emeritus
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 this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?