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.
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.
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?
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!
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... thats as far as i can go
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.
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.
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?
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?
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.
[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 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?
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.