Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/