Proving a number is divisible by 48

  • Thread starter johnnyICON
  • Start date
  • #1
79
0
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.
 

Answers and Replies

  • #2
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
Well, if it's divisible by 48, then it should be equal to 0 mod 48, right?
 
  • #3
mathwonk
Science Advisor
Homework Helper
11,064
1,254
is it true for k=1?, k=2?,...
 
  • #4
shmoe
Science Advisor
Homework Helper
1,992
1
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
79
0
Hurkyl said:
Well, if it's divisible by 48, then it should be equal to 0 mod 48, right?
Right :D

mathwonk said:
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.

shmoe said:
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?
 
  • #6
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
I have tried a few numbers
There are only 6 numbers to try...
 
  • #7
shmoe
Science Advisor
Homework Helper
1,992
1
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
79
0
Hurkyl said:
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 [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
 
  • #9
841
0
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
79
0
ramsey2879 said:
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.
:cry:
 
  • #11
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
Sure you were. P = 0 (mod P), right?
 
  • #12
mathwonk
Science Advisor
Homework Helper
11,064
1,254
have you heard of induction?
 
  • #13
79
0
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
matt grime
Science Advisor
Homework Helper
9,395
3
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
79
0
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?
 
  • #16
matt grime
Science Advisor
Homework Helper
9,395
3
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
Gokul43201
Staff Emeritus
Science Advisor
Gold Member
7,051
18
johnnyICON said:
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?
[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:
  • #18
79
0
matt grime said:
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?
 
  • #19
79
0
Gokul43201 said:
[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 ?
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:
  • #20
Gokul43201
Staff Emeritus
Science Advisor
Gold Member
7,051
18
johnnyICON said:
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]
Yes, that's correct. And that's why matt's little trick does not alter the residue, while making the quadratic conveniently factorizable.
 
  • #21
79
0
Do I have to apply mod 5 to every term?

For example, [tex]3^{2n} + 7[/tex], could I apply mod p to the 7 only and still have it being congruent?
i.e.,
p = 8;
[tex]3^{2n} + 7 \equiv 3^{2n} -1 (mod~8)[/tex]?
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
[tex]3^{2n} + 7 \equiv -4^{2n} -1 (mod~8)[/tex] correct?
 
Last edited:
  • #22
arildno
Science Advisor
Homework Helper
Gold Member
Dearly Missed
9,970
132
Since 0*p is divisible with p, yes.
 
  • #23
79
0
arildno said:
Since 0*p is divisible with p, yes.
Sorry, I just edited my post. Which post were you responding to?
 
  • #24
Gokul43201
Staff Emeritus
Science Advisor
Gold Member
7,051
18
johnnyICON said:
Do I have to apply mod 5 to every term?

For example, [tex]3^{2n} + 7[/tex], could I apply mod p to the 7 only and still have it being congruent?
i.e.,
p = 8;
[tex]3^{2n} + 7 \equiv 3^{2n} -1 (mod~8)[/tex]?
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 [itex]a \equiv b ~(mod~n)~ [/itex] mean ?
 
  • #25
Gokul43201
Staff Emeritus
Science Advisor
Gold Member
7,051
18
johnnyICON said:
[tex]3^{2n} + 7 \equiv -4^{2n} -1 (mod~8)[/tex] correct?
How did you get this ?
 

Related Threads on Proving a number is divisible by 48

Replies
7
Views
9K
Replies
6
Views
22K
Replies
2
Views
2K
  • Last Post
Replies
2
Views
3K
Replies
11
Views
24K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
23
Views
16K
Replies
5
Views
4K
Top