Here's a math problem for all of the math geeks out there!?

Question

I just want to see how good all of us are at math. I found this question looking at tests from old competitions:

If n is an integer and its absolute value is greater than or equal to 2, prove that (n^5)-n is divisible by 30.

Modulo is on the right track

Gopal, I said 30, not 3

Miley, don't waste my time. Answer if you actually plan on answering.

I think we have a winner. Benoit, if you delete that last "neither", I'll choose you

Rajkiran, I said GREATER THAN OR EQUAL to 2, not just equal to 2

Yeah, Benoit's got it. As soon as I can choose a best answer, it'll be this user.

I don't think they really intended for 0 to be divisible by 30 in this case, or else ALL integers would work

Answer 1

n^5 - n
= n(n^4-1)
= n(n^2-1)(n^2+1)
= n(n-1)(n+1)(n^2+1)

We must prove that one of these four factors is even; that one is a multiple of 3; and one is a multiple of 5. The product will be multiple of 2*3*5 = 60.

Three of the factors are consecutive numbers (n-1, n, n+1) as factors. One of these must be a multiple of 3 and one of them must be even. Therefore the result is a multiple of 6.

If one of n-1, n or n+1 is a multiple of 5, the proof is over. Assume then that none of them is. Then either n=5i+2 or n=5i+3 for some integer i. The factor (n^2 + 1) then becomes
(5i+2)^2 + 1
= 25i^2 + 20i + 4 +1
= 25i^2 +20i + 5
= 5 * (5i^2 + 4i + 1)

or

(5i+3)^2 + 1
= 25i^2 + 30i + 9 +1
= 25i^2 +30i + 10
= 5 * (5i^2 + 6i + 2)

Both of these are multiples of 5 - therefore, if none of (n-1), n or (n+1) is a multiple of 5, then n^2+1 is.

QED.

Just saw the hint to go for induction, let's try it!

for n=2 we have n^5 - n = 32-2 = 30 OK.

Assume it works for n, i.e. n^5-n is a multiple of 30, then
(n+1)^5 - (n+1)
= n^5 + 5n^4 + 10 n^3 + 10 n^2 + 5n + 1 - n + 1
= (n^5 - n) + 5n(n^3 + 2n^2 + 2n + 1)
= (multiple of 30) + 5n(n+1)(n^2 + n + 1).
n(n+1) is certainly even. Is it a multiple of 3? if not this means n=3i+1 for some i. Therefore the third factor equals (3i+1)^2 + 3i + 1 + 1 = 9i^2 + 9i + 3 is a multiple of 3. So that big ugly thing is a multiple of 5, 2 and 3 - and thus of 30.

Works too for negatives too, since (-n)^5 - (-n) = - (n^5-n).

EDIT: Want a third proof???

If n= r mod a (meaning r is the remainder of n/a) then n^5-n = (r^5 -r) mod a

Setting a=2:
If r=0 then n^5-n = 0^5-0 mod 2 = 0 mod 2
If r=1 then n^5-n = 1^5-1 mod 2 = 0 mod 2
Hence n^5-n is a multiple of 2 in all cases

For a=3
If r=0 then n^5-n = 0^5-0 mod 3 = 0 mod 3
If r=1 then n^5-n = 1^5-1 mod 3 = 0 mod 3
If r=2 then n^5-n = 2^5-2 mod 3 = 30 mod 3 = 0 mod 3
Hence n^5-n is a multiple of 3 in all cases

For a=5
If r=0 then n^5-n = 0^5-0 mod 5 = 0 mod 5
If r=1 then n^5-n = 1^5-1 mod 5 = 0 mod 5
If r=2 then n^5-n = 2^5-2 mod 5 = 30 mod 5 = 0 mod 5
If r=3 then n^5-n = 3^5-3 mod 5 = 240 mod 5 = 0 mod 5
If r=4 then n^5-n = 4^5-4 mod 5 = 1020 mod 5 = 0 mod 5
Hence n^5-n is a multiple of 5 in all cases.

Being a multiple of 2, 3 and 5, n^5-n is therefore a multiple of 30.

Answer 2

numbers that are divisible by 30, all digits must add up to a multiple of 3 and the last digit must be a 0
if n = 2
2^5 = 32
32 - 2 = 30 correct

if n = 3
3^5 = 243
243 - 3 = 240 correct

if n = 5
5^5 = 3125
3125 - 5 = 3120

if n = 7
7^5 = 16807
16807 - 7 = 1680

Answer 3

Well, first of all, the result is even true for abs(n) = 0, or 1 because 30 divides 0.
To see it in general, note that
n^5 -n = (n-1)(n)(n+1)(n^2+1).
Of n and n + 1 one of these is divisible by 2.
Of n-1, n and n + 1, one of these is divisible by 3.
It remains to show that n^5 -n is divisible by 5.
Let n = 5t + k, where k = 0,1,2,3 or 4.
Then
n^5-n = (5t+k)^5 -(5t + k). If we expand this by the
binomial theorem, we see that all terms of this expansion are divisible by 5 except perhaps k^5-k.
So, all that's left is to check the 5 values of k.
For 0, and 1 k^5 -k is divisible by 5.
Also
2^5 -2 = 30,
3^5 -3 = 240,
and
4^5 - 4 = 1020,
all of which are divisible by 5.
So n^5-n is divisible by 2,3 and 5, hence by 30.
Finally,
Every integer a(a not 0) divides 0 because 0 = 0*a.
This result IS true for all integers. The restriction
to abs(n) >= 2 is not needed here.

Answer 4

This sounds like a job for an inductive argument!

Let's check if it works for 2. 2^5-2=30, 30/30=30. Check!

Assume for n, show for n+1.

Observe (n+1)^5-(n+1).

n^5+5n^4+10n^3+10n^2+5n+1-n-1 (Expanding)

=n^5+5n^4+10n^3+10n^2+4n
=30M+5n(n^3+2n^2+2n+1) (use the inductive hypothesis--n^5-n=30M)
=30M+5n(n+1)(n^2+n+1)

Now, if we can just show that n(n+1)(n^2+n+1) is divisible by 6, we're done. We can do induction again! This is the first time I've used induction within induction. Neato!

Base case:n=1. 1(2(3))=6, 6/6=1. Check, baby!

Assume it holds for k, show for k+1.

(k+1)(k+2)((k+1)^2+k+1+1)
=(k+1)(k+2)(k^2+3k+3)
=(k^2+3k+2)(k^2+3k+3)
=k^4+6k^3+14k^2+15k+6. By the inductive hypothesis, we know
k^4+2k^3+2k^2+k is divisible by 6. So we need to see if 4k^3+12k^2+14k is divisible by 6. Or, to see if 2k^3+6k^2+7k is divisible by 3.

Is this a third inductive step? Man alive.

Actually, no. I'll do this by cases. And mods.
If k is divisible by 3, we're done.
If k is a number which is one less than a number divisible by 3:

16+24+14=54~0mod3. (Remember, we're using mods--they're like remainders when dividing by 3 in this case.)

If k is a number one more than a number divisible by 3:
2+6+7=15~0mod3.

So no matter what, 2k^3+6k^2+7k is divisible by three. This works for all integers, INCLUDING 0, 1 and -1. 0 is divisible by 30.

Now we know that n(n^3+2n^2+2n+1) is divisible by 6, so 5 times that is divisible by 30.

Phew! That was insane.

Answer 5

Let P=n^5-n
=n(n^4-1)
=n(n^2-1)(n^2+1)
=n(n-1)(n+1)(n^2+1)

Atleast one of n, n-1 is even so this product P is divisible by 2.
Atleast one of n+1,n, n-1, is a multiple of 3 so this product P is divisible by 3.
So that nails down the divisibility by 6. Remains to show for 5:

If n=5k, good enough.
If n=5k+1, n-1=5k and good enough.
If n=5k+4, n+1=5k and good enough.

If n=5k+2,
n^2+1=25k^2+4+20k+1=5(5k^2+4k+1) and good enough.

If 5k+3, n^2+1=25k^2+9+30K+1=5(5k^2+4k+2) and good enough.

QED.

Answer 6

possible values of n (+or-)1 or (+or-)2 or 0

for the values (+or-)1 or 0 the term (n^5)-n is 0.. So Holds true for above condition...

for the +ve and -ve values of 2 we have (n^5)-n values (+or-) 30.. Hence Divisible by 30...

Answer 7

n^5-n=n(n^4-1)
=n(n^2+1)(n+1)(n-1)
if n=2
=2(5)(3)(1)=holds
depending on the value of n
n,(n+1) or (n-1) ,one of the three
is bound to be a multiple of 3
and so it will hold for all n

Answer 8

n^5-n = n(n^4-1) = n(n^2-1)(n^2+1)= n(n+1)(n-1)(n^2+1)

Doesn't see to help.

Try induction. Does it work for n=3? If so, then assume it works and show that that leads to it working for n+1, then you've done an inductive proof.

I ran it out on my TI-83:
n, f(n)
2, 30
3, 240
4, 1020
5, 3120
etc...

Yep, induction's the way to prove it.

Answer 9

abs(n) is greater than or equal to 2
for the sake of this problem, we'll assume > is the greater or equal to symbol
abs(n) > 2
2 < n < -2
(2 < n < -2)^5 = n^5
32 < n^5 < -32 = n^5
(2 < n < -2)(-1) = -n
-2 < -n < 2 = -n
32 - 2 < (n^5) - n < -32 + 2

30 < (n^5) - n < -30

well... i guess I'm a math geek.

Answer 10

i dont get it well im not a geek then :D