Proving the Largest Natural Number m for Divisibility of n^3-n

[Punkyc7]

Find the largest natural number m such that n^3 -n is divisible by m for n element N. Prove your assertion.



How exactly do you begin this

im thinking the largest m could possible be is n^3 -n, but I am not sure.

To be divisible we know that

mk=n^3-n for some k

 

[Dick]

Well, sure n^3-n divides n^3-n. But I doubt that's what they mean. I think they mean a proper divisor, i.e. m<n^3-n. What number LESS than n^3-n divides n^3-n and can you show it's the largest possible?

 

[HallsofIvy]

How can you factor n^3- n?

 

[Punkyc7]

n(n^2-1) is that this question was asking for?

And from there you induction on n^3-n and show that n^2 -1 is the largest number

 

[micromass]

n(n^2-1) is that this question was asking for?

And from there you induction on n^3-n and show that n^2 -1 is the largest number

Take n=3, what is the largest proper divisor of n³-n then?

 

[Punkyc7]

would it be 12...which is not n^2-1

 

[micromass]

would it be 12...which is not n^2-1

But which is the half of n³-n. Can you show that the half is always the largest divisor??

 

[Punkyc7]

I going to guess you can. So we assume that (n^3-n)/2 is the largest and we want to show

(n+1^3-n+1)/2 is the largest divisor of n+1^3-n+1

 

[micromass]

I going to guess you can. So we assume that (n^3-n)/2 is the largest and we want to show

(n+1^3-n+1)/2 is the largest divisor of n+1^3-n+1

Isn't it obvious that \frac{n^3-n}{2} is the largest divisor?? The only thing you need to show is that 2 divides n³-n. That's what you need to show by induction.

 

[Punkyc7]

so we show that 2 divides when n is odd and when n is even.

Then we show 2 divides n+1^3-n+1?

 

[micromass]

so we show that 2 divides when n is odd and when n is even.

Then we show 2 divides n+1^3-n+1?

Indeed, you must show that (n+1)^3-(n+1) is even when n^3-n is.

 

[Punkyc7]

and do the same thing when its odd.

Now do I have to show that (n+1^3−n+1)/2 is the largest divisor of n+1^3-n+1, or do I just have to show two divides it.

 

[tiny-tim]

Hi Punkyc7!

Find the largest natural number m such that n^3 -n is divisible by m for n element N.

Doesn't it mean find the highest common factor of every value of n³ - n ?

 

[Punkyc7]

Hi tiny tim,

it should say for all n element N, I am going to edit that.


I can't edit it the edit button is gone so it should say

Find the largest natural number m such that n^3 -n is divisible by m for all n element N. Prove your assertion

 

[hunt_mat]

n^{3}-n=n(n^{2}-1)=(n-1)n(n+1)

 

[Punkyc7]

ok, so how is knowing the roots helpful?

 

[Char. Limit]

ok, so how is knowing the roots helpful?

Say that we have the product n*(n+1). If n is divisible by two, is the product? If n is NOT divisible by two, is the product? (AKA is n*(n+1)/2 an integer for all even natural numbers n? How about all odd natural numbers n?)

 

[Punkyc7]

im going to say yes to the first part

yes for the second part because even numbers can be divided by 2

so it would be an integer for all even natural number

wouldnt it also be true for odd

 

[Char. Limit]

im going to say yes to the first part

yes for the second part because even numbers can be divided by 2

so it would be an integer for all even natural number

wouldnt it also be true for odd

Indeed. So if n(n+1)/2 is an integer for all natural numbers n, isn't (n-1)(n+1)n/2 also an integer for all natural numbers n?

 

[Punkyc7]

I want to say yes

 

[Char. Limit]

I want to say yes

All right, let's say you say yes. If so, then (n^3-n)/2 (which is the same as what we made before) is an integer for all natural numbers n, and all we need to do is prove it is the LARGEST possible factor.

 

[Punkyc7]

but how do you know its the largest, wasnt that just our guess

 

[Char. Limit]

Well, consider this. (n^3-n)/2 is obviously a factor of n^3-n. So therefore, n^3-n = (n^3-n)/2 * b for some OTHER factor b. And this factor is rather obvious, isn't it? (Not to mention, when factoring a number n, the largest a factor can be (other than the obvious n) is n/2. I think you'll have to PROVE that, though)

 

[Punkyc7]

wouldnt b=2 is that what you mean by obvious?

wait how would prove the next highest factor in n/2

im so confused

 

[tiny-tim]

(just got up :zzz: …)

i still think you're misunderstanding the question

2 is the highest common factor of all values of n² + n

so what is the highest common factor of all values of n³ - n ?

 

[Punkyc7]

I don't know
n+1?

how would you even go about finding this out... do we check for odd and even



because we get
2k((2k)^2-1)
8k^3+12k^2+6k+1


does that mean that the highest factor is one because they don't share anything?

 

[tiny-tim]

im not sure how we knew 2 is the highest common factor of all values of n^2 + n

what's the highest common factor of 11² + 11 and 13² + 13 ?

 

[Punkyc7]

so you just right down all the factors and see which ones they both share

i have it in a few minutes

 

[Punkyc7]

they both share 2

 

[tiny-tim]

ok, now 11³ - 11 and 14³ - 14 ?

 

[hunt_mat]

You can easily show that n^{3}-n is even for all natural numbers n, ehast is the highest divisor of an even number?

 

[tiny-tim]

… ehast is the highest divisor of an even number?

i know west is west, but ehast is ehast ?

 

[hunt_mat]

It should have said, what is the highest divisor of an even number

 

[Punkyc7]

so 2 is the highest divisor of n^3-n?

 

[micromass]

so 2 is the highest divisor of n^3-n?

Is 2 the highest divisor of 24?

 

[hunt_mat]

let n>4 be an even number, then it can be written n=2k, what is the highest divisor of n?

 

[Punkyc7]

no 12 was

hunt_mass would it be k?

 

[hunt_mat]

It would be. You are almost at your proof.

 

[Punkyc7]

so its (n^3-n)/2=k


now do you do induction on k or n?
im thinking n

 

[hunt_mat]

basically, once you show it's even (you have not yet done this) then that would be your answer.

 

[Punkyc7]

do i have to show n^3-n is even or (n+1)^3-(n+1) is even or both?

 

[hunt_mat]

show that it is even for arbitrary n, so I would write n=2k+1 for example...

 

[Punkyc7]

but which one do i show is even the induction one or the original one?

 

[hunt_mat]

They are both the same. Work with n^{3}-n for now.

 

[Punkyc7]

so (2k)^3-2k= 2k((2k)^2-1) which is even


(2k+1)^3-(2k+1)=(2k+1)((2k+1)^2-1)

(2k+1) is always odd

((2k+1)^2-1)=4k^2+4k+1-1=2k(2k+2) which is even

since an even times an odd is even
this implies n^3-n is always even

 

[I like Serena]

I've been studying the problem statement and I agree with tiny-tim (^TM).

The only way the problem makes some "sense" to me, is if you try to find the greatest number m which divides n³-n for all n.

 

[hunt_mat]

As this has been shown to be an even number, the highest value must be half that amount.

 

[Punkyc7]

wait... so is it half of the amount or 2 right...

 

[hunt_mat]

depending on which is the bigger value.

 

[Alex B]

Sorry to dig up an old thread, but I just saw this interesting problem in Bartle & Sherbert's textbook and did a Google search to see if anyone got the same answer as me.

I'm not sure if the problem was ever stated clearly, but it is: find the largest natural number m such that m divides n^3 - n FOR ALL natural numbers n. Notice that n is not a free variable; it is bounded to a universal quantifier. Therefore, it does not make sense to have an answer that depends on n, which is undefined outside of that quantified statement. In other words, our answer should be an EXPLICIT natural number.

Now, suppose we have our answer m. So no matter what n we choose, m divides n^3 - n. For example, let's choose n = 2. Then n^3 - n = 2^3 - 2 = 6. Thus, m divides 6. But the only positive divisors of 6 are 1, 2, 3, and 6.

Note that 1 divides every number, so m obviously exists, and also m >= 1. What is left is to figure out which (if any) of the numbers 2, 3, or 6 has the property that it is a divisor of n^3 - n FOR ALL natural numbers n (using induction). Finally, our answer m is the largest of the numbers that have that property.