Prove that n^3-n is divisible by 6 for every integer n

  • Context: Undergrad 
  • Thread starter Thread starter symplectic_manifold
  • Start date Start date
  • Tags Tags
    Integer
Click For Summary

Discussion Overview

The discussion revolves around proving that \( n^3 - n \) is divisible by 6 for every integer \( n \). Participants explore various approaches, including induction, factorization, and properties of consecutive integers, while addressing the divisibility by both 2 and 3.

Discussion Character

  • Exploratory
  • Mathematical reasoning
  • Debate/contested

Main Points Raised

  • One participant suggests using induction to prove the divisibility of \( n^3 - n \) by 6.
  • Another participant factors \( n^3 - n \) as \( n(n-1)(n+1) \), noting that it represents three consecutive integers, which implies divisibility by 2.
  • There is a discussion on the necessity of showing that \( n^3 - n \) is divisible by 3 in addition to 2 to conclude that it is divisible by 6.
  • One participant expresses uncertainty about how to demonstrate that 3 divides \( n^3 - n \) and seeks clarification on Hall's factorization.
  • Another participant explains how to show that \( n^3 - n \) is divisible by 2 using Hall's factorization.
  • There is a proposal to generalize the idea that among any \( n \) successive integers, exactly one is divisible by \( n \), with a request for a formal proof.
  • Participants engage in a discussion about the division algorithm and the representation of integers, questioning the bounds of the remainder in the context of divisibility.

Areas of Agreement / Disagreement

Participants generally agree on the need to show both divisibility by 2 and 3 for \( n^3 - n \) to establish divisibility by 6. However, there is no consensus on the methods to demonstrate these divisibilities, particularly regarding the case for 3.

Contextual Notes

Some participants express uncertainty about the application of Hall's factorization and the division algorithm, indicating potential limitations in their understanding of these concepts.

symplectic_manifold
Messages
60
Reaction score
0
Prove that n^3-n is divisible by 6 for every integer n. Is it induction to be used here?...
 
Physics news on Phys.org
n3-n= n(n2-1)= n(n-1)(n+1)= (n-1)(n)(n+1), three consecutive integers. What does that tell you?
 
Oh, My!...shame on me!
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.
 
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?
 
Oh sorry, thanks, HallsofIvy, you seem to have won the race!...posted a few minutes earlier...I didn't see it. :)

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

...now that was my problem...how can I show that 3 divides n^3-n?...I need to show that the sum of the digits is divisible by 3...but the number is encoded in a formula!...so what can I do?

I don't 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 don't think it needs to be used here...
 
Here's how you could show n^3-n is divisible by 2 using Hall's factorization:

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?
 
Great!...Can I generalise it by saying that among any n successive integers there is exactly one divisible by n?...What is a formal proof for this?
 
symplectic_manifold said:
Great!...Can I generalise it by saying that among any n successive integers there is exactly one divisible by n?...What is a formal proof for this?

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
OK, but why did you change r?...It's 0<=r<=n-1, is it?...which gives 1<=n-r<=n and not 0<=n-r<n...cant get it. °_°
 
  • #11
...and doesn't that mean that m+1,...,m+n-1 are all divisible by n?
 
  • #12
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
 

Similar threads

Undergrad Can integers be defined as N[[sqrt(1)]]?
  • · Replies 25 ·
Replies
25
Views
2K
Undergrad ##S_{n}(\alpha)=\sum_{k=1}^{n} (-1)^{\lfloor{k\alpha\rfloor}}##
  • · Replies 2 ·
Replies
2
Views
3K
Undergrad How to show ##p(x)=g(x)x\pm 1\in\Bbb{Q}[x]## is irreducible in ##\Bbb{Q}_{\Bbb{Z}}[x]##?
  • · Replies 48 ·
2
Replies
48
Views
7K
High School Probability that 2 distinct integers are divisible by the same number
  • · Replies 9 ·
Replies
9
Views
3K
High School Elegant way to prove ##AB^{n}## commute
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Base Pi Integers: Isomorphism with Rationals?
  • · Replies 33 ·
2
Replies
33
Views
5K
MHB 412.0.6 Find all integers n for which this statement is true, modulo n.
  • · Replies 1 ·
Replies
1
Views
1K
For n>3, show that the integers n, n+2, n+4 cannot all be prime
  • · Replies 27 ·
Replies
27
Views
4K
MHB Prove Abelian Group: $(a \cdot b)^n = a^n \cdot b^n$
  • · Replies 1 ·
Replies
1
Views
2K
Proof That an Integer is Divisible by 2
  • · Replies 3 ·
Replies
3
Views
3K