Proving a number is divisible by 48

  • Thread starter johnnyICON
  • Start date
In summary: The only thing I am still wondering about is where you got the kp, lpx and mpx^2 from?In summary, the conversation is discussing how to prove that for an integer n, if even, then n(n^2 + 20) is divisible by 48. The conversation covers various methods, including substitution and using congruencies, to try and prove this statement. It is eventually suggested to use the fact that the product of three consecutive numbers must be divisible by 6.
  • #1
johnnyICON
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.
 
Physics news on Phys.org
  • #2
Well, if it's divisible by 48, then it should be equal to 0 mod 48, right?
 
  • #3
is it true for k=1?, k=2?,...
 
  • #4
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
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
I have tried a few numbers

There are only 6 numbers to try...
 
  • #7
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
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: that's as far as i can go
 
  • #9
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
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
Sure you were. P = 0 (mod P), right?
 
  • #12
have you heard of induction?
 
  • #13
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
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
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
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
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
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
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 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:
[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
johnnyICON said:
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:
[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
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
Since 0*p is divisible with p, yes.
 
  • #23
arildno said:
Since 0*p is divisible with p, yes.

Sorry, I just edited my post. Which post were you responding to?
 
  • #24
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
johnnyICON said:
[tex]3^{2n} + 7 \equiv -4^{2n} -1 (mod~8)[/tex] correct?
How did you get this ?
 
  • #26
johnnyICON said:
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.
 
  • #27
n divides a-b, ahh :smile:
 
Last edited:
  • #28
Gokul43201 said:
How did you get this ?

[tex] 3 \equiv 3 (mod~8)[/tex]
[tex] 7 \equiv [/tex]-1 [tex](mod~8)[/tex]
 
  • #29
LOL, which pretty much states that I did not apply mod 8 to just the 7. Sorry, I'm a goof :biggrin:
 
  • #30
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 [tex]6|k^3 + 5k[/tex]. 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 [tex]6|k^3 + 5k[/tex]?
 
Last edited:
  • #31
You're missing out 6m+4, but the point is if you were to put any of those numbers into the formula k^3+5k you get a number divisible by 6. He's just doing the "unclever" way of solving the problem, that is to say he's doing modulo arithmetic without telling you he's doing modulo arithmetic.

Every given any number n and another number p we can express n=pq+r where q and r are integers 0<=r<p and q is then uniquely determined. That is just kindergarten mathematics (which is far more mathematically mature than knowing how to write out decimals if you ask me) where r is the remainder after dividing by p.

All he is now claiming is that whatever the remainder is after dividing by 6 (ie what class it is in modulo r) we get something divisible by 6, eg

if k=6m+1

k^3+5k= (6m+1)^3+5(6m+1) = (6m^3) +3(6m)^2+4(6m)+1+5(6m)+5

obvisouly anyting with a 6m in it is divisible by 6 so that just leaves 1+5 part, which is also divisible by 6.

Hopefully you see that if I expand (6m+r)^3 i get something divisible by 6 plus r^3, and the 5k=30m+5r, so I just need to show that r^3+5r is divisible by 6 for r from 0 to 5.
 
  • #32
Oooh.. so those forms, 6m, 6m+1, etc., are all possible ways of expressing any number in terms of 6?
That is q=6, the uniquely determined integer? But that doesn't mean that n is divisible by 6?

Oh I get it... so for any integer k, k can be expressed using one of the six forms.
(Now help me with my understanding of why we do this...) We use q=6 so that we may be able to find 6 as a common term... I'm afraid to say it but I think I have the idea...
 
  • #33
johnnyICON said:
Oooh.. so those forms, 6m, 6m+1, etc., are all possible ways of expressing any number in terms of 6?
That is q=6, the uniquely determined integer? But that doesn't mean that n is divisible by 6?

In matt's notation p=6, you're dividing your number k by 6, so it's of the form k=6m+r, where r=0, 1, 2, 3, 4, or 5 (you're using m for his q). All we're going to care about for this problem is the r, the m won't matter. k is divisible by 6 exactly when r=0.

Note if k=6m+r then k=r mod 6.

johnnyICON said:
Oh I get it... so for any integer k, k can be expressed using one of the six forms.
(Now help me with my understanding of why we do this...)

We are interested in k^3+5k mod 6, specifically we'd like to show it's zero. Since we are only interested mod 6, we can replace k by r and get k^3+5k=r^3+5r mod 6. In otherwords, the remainder you get when you divide k^3+5k by 6 is dependant only upon the remainder you get when you divide k by 6. e.g. 4^3+5(4)=10^3+5(10) mod 6. So writing k in one of these 6 forms allows us to ignore the unimportant (for this problem) m part and focus on the r. Since we have only 6 options for r, we can try them all and see that in each case we get 0 mod 6.
 
  • #34
matt grime said:
He's just doing the "unclever" way of solving the problem, that is to say he's doing modulo arithmetic without telling you he's doing modulo arithmetic.

It seems like a good way to introduce modular arithmetic. This comes as a personal experience. Once i was explaining to a friend, why m(m+1)...(m+n) is divisible by n(in our discrete maths class). I started with "consider their remainders modulo n, one of them must be zero, so we are done!". His reaction **blank**. Ok, so i started, see i can express any number as nk,nk+1,nk+2,...,nk+(n-1) and his reaction "what? how can u do that?". I gave him some examples and he looked at me as if i did some magic! So now i had to show why this is true which took me to the equation,
Dividend = Divisor*Quotient + Remainder
Now he was well aware of this, then i made a connection of this equation with the above proposed "i can express any number as...". Then i had to get back to the original question. To this day, i still hope he understood what i said that day.

-- AI
 

FAQ: Proving a number is divisible by 48

How do you prove that a number is divisible by 48?

To prove that a number is divisible by 48, you can use the divisibility rules for 48, which state that the number must be divisible by both 3 and 16. You can also divide the number by 48 and check if the remainder is 0.

What is the divisibility rule for 48?

The divisibility rule for 48 states that a number is divisible by 48 if it is divisible by both 3 and 16.

Can a number be divisible by 48 if it is not divisible by 3?

No, a number cannot be divisible by 48 if it is not divisible by 3. This is because 3 is a prime factor of 48 and must be present in the number for it to be divisible by 48.

Is there a shortcut to proving a number is divisible by 48?

Yes, there is a shortcut to proving a number is divisible by 48. If the last two digits of the number are divisible by 4, and the sum of all its digits is divisible by 3, then the number is divisible by 48.

Can a decimal number be divisible by 48?

Yes, a decimal number can be divisible by 48. To determine if a decimal number is divisible by 48, you can convert it to a fraction and then use the divisibility rules for 48 on the numerator and denominator.

Back
Top