- #1

- 79

- 0

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.

- Thread starter johnnyICON
- Start date

- #1

- 79

- 0

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.

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

- #5

- 79

- 0

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

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.mathwonk said:is it true for k=1?, k=2?,...

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

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

There are only 6 numbers to try...I have tried a few numbers

- #7

shmoe

Science Advisor

Homework Helper

- 1,992

- 1

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

Haha, you're going to have to excuse me Hurkyl, I'm just a beginner with congruencies. Do you mind elaborating a little more?Hurkyl said:Well, if it's divisible by 48, then it should be equal to 0 mod 48, right?

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

- #9

- 841

- 0

- #10

- 79

- 0

I wasn't aware of this property.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.

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

- #14

matt grime

Science Advisor

Homework Helper

- 9,395

- 3

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

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

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

[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]johnnyICON said:

So let's say I had something like [tex]5x^2 + 7x + 1[/tex], can I replace 5, 7 and 1 by a congruence?

Do you see why this is true ?

Last edited:

- #18

- 79

- 0

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

Because 3 * 2 = 6, therefore it must also be divisible by 6? Is that correct?

- #19

- 79

- 0

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

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

Yes, that's correct. And that's why matt's little trick does not alter the residue, while making the quadratic conveniently factorizable.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]

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

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

Sorry, I just edited my post. Which post were you responding to?arildno said:Since 0*p is divisible with p, yes.

- #24

Gokul43201

Staff Emeritus

Science Advisor

Gold Member

- 7,051

- 18

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

- #25

Gokul43201

Staff Emeritus

Science Advisor

Gold Member

- 7,051

- 18

How did you get this ?johnnyICON said:[tex]3^{2n} + 7 \equiv -4^{2n} -1 (mod~8)[/tex] correct?

- Replies
- 2

- Views
- 7K

- 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