- #1

- 60

- 0

Prove that n^3-n is divisible by 6 for every integer n. Is it induction to be used here?...

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter symplectic_manifold
- Start date

- #1

- 60

- 0

Prove that n^3-n is divisible by 6 for every integer n. Is it induction to be used here?...

- #2

HallsofIvy

Science Advisor

Homework Helper

- 41,847

- 967

- #3

- 60

- 0

Now that I submitted this thread and can't delete it:

Is it generally right?:

If 6 divides n^3-n then, since divisibility is transitive and 2 divides 6 , 2 must also divide n^3-n. Let n be even then n^3 is even and n^3-n is also even. Let n be odd then n^3 is odd and hence n^3-n is even. Since every even number is divisible by 2 it follows that 6 divides n^3-n.

- #4

shmoe

Science Advisor

Homework Helper

- 1,992

- 1

symplectic_manifold said:If 6 divides n^3-n then, since divisibility is transitive and 2 divides 6 , 2 must also divide n^3-n. Let n be even then n^3 is even and n^3-n is also even. Let n be odd then n^3 is odd and hence n^3-n is even. Since every even number is divisible by 2 it follows that 6 divides n^3-n.

You're going at this backwards assuming 6 divides n^3-n then showing 2 divides it?

You've managed to show 2 divides n^3-n by considering n even or odd, but to show 6 divides n^3-n you need to also show 3 divides n^3-n. Consider Hall's factorization, can you show 3 divides (n-1)n(n+1) for any n?

- #5

- 60

- 0

n3-n= n(n2-1)= n(n-1)(n+1)= (n-1)(n)(n+1), three consecutive integers. What does that tell you?

oh that was even more easier! nice...that n^3-n is always even?...

- #6

- 60

- 0

You've managed to show 2 divides n^3-n by considering n even or odd, but to show 6 divides n^3-n you need to also show 3 divides n^3-n. Consider Hall's factorization, can you show 3 divides (n-1)n(n+1) for any n?

I dont have an idea of the Hall's factorization...could you tell me more about it or post me a link to a resource?

well, this is a problem at the very beginning of Nathanson's Elementary Methods in Number Theory, which I've just started reading....since I have no idea of number theory. It actually has no prerequisites for this problem except transitivity, division algorithm and induction principle...well there is also a theorem about an m-adic representation of numbers...but I dont think it needs to be used here...

- #7

shmoe

Science Advisor

Homework Helper

- 1,992

- 1

n^3-n=(n-1)n(n+1). So for any n, we must have both n-1 and n dividing n^3-n. n-1 and n are consequetive integers, hence one of them is divisible by 2. Therefore n^3-n is divisible by 2.

Does this give you any ideas on how to handle the 3 case?

- #8

- 60

- 0

- #9

shmoe

Science Advisor

Homework Helper

- 1,992

- 1

symplectic_manifold said:

That's correct. n successive integers starting at m look like m, m+1, ..., m+n-1. Use the division algorithm to write m=n*q+r, where 0<r<=n (note I've changed r slightly from the usual form). Then m+n-r is divisible by n and 0<=n-r<n so m+n-r is one of m, m+1, ..., m+n-1

- #10

- 60

- 0

- #11

- 60

- 0

...and doesnt that mean that m+1,...,m+n-1 are all divisible by n?

- #12

shmoe

Science Advisor

Homework Helper

- 1,992

- 1

symplectic_manifold said:OK, but why did you change r?

Because it worked with the sequence I had already typed and seemed easier than going back to modify it. If you believe the division algorithm will give you an r with 0<=r<n you should be able to wrangle this to a different r with 0<r<=n, there's little difference.

Or you could change the consecutive numbers to m+1, m+2, ... m+n

Share:

- Replies
- 6

- Views
- 3K