# proving a number is divisible by 48

by johnnyICON
Tags: divisible, number, proving
P: 79
 Quote by Gokul43201 $$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 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)$$
Emeritus
PF Gold
P: 11,154
 Quote by 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)$$
Yes, that's correct. And that's why matt's little trick does not alter the residue, while making the quadratic conveniently factorizable.
 P: 79 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?
 Sci Advisor HW Helper PF Gold P: 12,016 Since 0*p is divisible with p, yes.
P: 79
 Quote by arildno Since 0*p is divisible with p, yes.
Sorry, I just edited my post. Which post were you responding to?
Emeritus
PF Gold
P: 11,154
 Quote by 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)$$?
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 ?
Emeritus
PF Gold
P: 11,154
 Quote by johnnyICON $$3^{2n} + 7 \equiv -4^{2n} -1 (mod~8)$$ correct?
How did you get this ?
HW Helper
PF Gold
P: 12,016
 Quote by johnnyICON 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.
 P: 79 n divides a-b, ahh
P: 79
 Quote by Gokul43201 How did you get this ?
$$3 \equiv 3 (mod~8)$$
$$7 \equiv$$-1 $$(mod~8)$$
 P: 79 LOL, which pretty much states that I did not apply mod 8 to just the 7. Sorry, I'm a goof
 P: 79 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$$?
 Sci Advisor HW Helper P: 9,398 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: 79 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...
HW Helper
P: 1,996
 Quote by johnnyICON 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.

 Quote by johnnyICON 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.
P: 646
 Quote by matt grime 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

 Related Discussions General Physics 8 Calculus 19 General Math 12 Calculus & Beyond Homework 11 Calculus & Beyond Homework 5