Associated Topics || Dr. Math Home || Search Dr. Math

### Proving Divisibility

Date: 09/11/2003 at 05:35:24
From: Inari
Subject: divisibility

Prove:

1.  that (n^2 - n) is divisible by 2 for every integer n
2.  that (n^3 - n) is divisible by 6
3.  that (n^5 - n) is divisible by 30

I know that

n^2 - n = n(n-1)

Since n and n-1 are consecutive integers, one of them must be divisible
by 2, so their product is divisible by 2.

Likewise,

n^3 - n = (n-1)n(n+1).

Therefore, one of these factors is divisble by 2, one of the others is
divisible by 3, which implies that (n^3 - n) is divisble by 6 (i.e.,
it's divisible by both 2 and 3).

But I'm stuck on the third one.  I know that

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

How do I show that this is divisible by 2, 3, and 5, and thus by 30?

Date: 09/11/2003 at 12:48:43
From: Doctor Edwin
Subject: Re: divisibility

Hi, Inari.

Ooh, neat puzzle. You've done well so far -- well enough that I don't
want to spoil the fun by giving too much away. So here's your hint:
Think only about the last digit of n.

Write back if you're still stuck and I'll help unstick you.

- Doctor Edwin, The Math Forum
http://mathforum.org/dr.math/

Date: 09/12/2003 at 01:54:45
From: Inari
Subject: divisibility

Whatever the last digit of n is, (n^5 - n) will always have 0 as the
units digit.  This means that (n^5 - n) is divisible by both 2 and 5.

Also,

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

We've already shown that (n-1)n(n+1) is divisible by 3 (from the 2nd
part of the question).  Therefore, (n^5 - n) is divisible by 2, 3, and
5, and is therefore divisible by 30.  Is this correct?

Date: 09/12/2003 at 08:00:29
From: Doctor Edwin
Subject: Re: divisibility

Nice! And neater than my proof, which was unnecessarily complicated.
Good job.

- Doctor Edwin, The Math Forum
http://mathforum.org/dr.math/
Associated Topics:
College Number Theory
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search