Proving a number is divisible by 48

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

 

[Hurkyl]

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

 

[mathwonk]

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

 

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

 

[johnnyICON]

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

Right :D

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

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.

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.

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?

 

[Hurkyl]

I have tried a few numbers

There are only 6 numbers to try...

 

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

 

[johnnyICON]

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

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

that's as far as i can go

 

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

 

[johnnyICON]

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.

I wasn't aware of this property.

 

[Hurkyl]

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

 

[mathwonk]

have you heard of induction?

 

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

 

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

 

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

 

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

 

[Gokul43201]

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?

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

 

[johnnyICON]

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?

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?

 

[johnnyICON]

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

I see that you added some integers kp, lpx and mpx^2 to the original equation. And that's 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)$$

 

[Gokul43201]

I see that you added some integers kp, lpx and mpx^2 to the original equation. And that's 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)$$

Yes, that's correct. And that's why matt's little trick does not alter the residue, while making the quadratic conveniently factorizable.

 

[johnnyICON]

Do I have to apply mod 5 to every term?

For example, $$3^{2n} + 7$$, could I apply mod p to the 7 only and still have it being congruent?
i.e.,
p = 8;
$$3^{2n} + 7 \equiv 3^{2n} -1 (mod~8)$$?
or do I have to apply it to the 3 as well, that is, ... oh wait... it is already mod 8... but I could change it to
$$3^{2n} + 7 \equiv -4^{2n} -1 (mod~8)$$ correct?

 

[arildno]

Since 0*p is divisible with p, yes.

 

[johnnyICON]

Since 0*p is divisible with p, yes.

Sorry, I just edited my post. Which post were you responding to?

 

[Gokul43201]

Do I have to apply mod 5 to every term?

For example, $$3^{2n} + 7$$, could I apply mod p to the 7 only and still have it being congruent?
i.e.,
p = 8;
$$3^{2n} + 7 \equiv 3^{2n} -1 (mod~8)$$?

You are not "applying mod p to the 7 only". You are adding integers to the LHS that are congruent to 0 modulo p. Start from the definition of a congruence modulo n : What does $a \equiv b ~(mod~n)~$ mean ?

 

[Gokul43201]

$$3^{2n} + 7 \equiv -4^{2n} -1 (mod~8)$$ correct?

How did you get this ?

 

[arildno]

Sorry, I just edited my post. Which post were you responding to?

I was responding to your unedited post.

Do as Darth Gokul saith, be sure you understand the definition of congruence.

 

[johnnyICON]

n divides a-b, ahh

 

[johnnyICON]

How did you get this ?

$$3 \equiv 3 (mod~8)$$
$$7 \equiv$$-1 $$(mod~8)$$

 

[johnnyICON]

LOL, which pretty much states that I did not apply mod 8 to just the 7. Sorry, I'm a goof

 

[johnnyICON]

My professor has posted up the proof to this question and I am not understanding one thing: The part where I have to prove that $$6|k^3 + 5k$$. His proof states that k must take one of six forms, that is 6m, 6m+1, 6m+2, 6m+3, 6m+5, and must be divisible by 6 when substituted in for k.

The case thing is what I don't understand. Why does this prove that $$6|k^3 + 5k$$?