Divisibility Proof

Date: 10/26/1999 at 21:30:20
From: Pat
Subject: Divisibility Properties

Prove that:

  1. n^5 - n is divisible by 30
  2. n^7 - n is divisible by 42

Using induction is not permitted. Only use divisibility to prove them. 
I'm not sure whether I need to use modulo or something else.

Date: 10/26/1999 at 22:05:22
From: Doctor Rob
Subject: Re: Divisibility Properties

Thanks for writing to Ask Dr. Math, Pat.

Factor these as follows:

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

Now n*(n-1)*(n-2) is always divisible by 6. There remains to show 
divisibility by 5 and 7. Fermat's Little Theorem takes care of that:

     If prime p does not divide a, then a^(p-1) = 1 (mod p).

This implies that n^p - n = 0 (mod p), for every n and every prime 
number p. Now use that with p = 5 and with p = 7. 

If you can't use that theorem, then you can observe that if n = 0, 1, 
or 4 (mod 5) then 5 | n*(n-1)*(n+1).

     5 | n^2 + 1 iff

     5 |   n^2 + 1 + 5*(1-n)
         = n^2 - 5*n + 6 
         = (n-2)*(n-3) iff 

     n = 2 or 3 (mod 5).

Thus no matter what n is congruent to modulo 5, 5 divides n^5 - n.

Similarly, if n = 0, 1, or 6 (mod 7) then 7 | n*(n-1)*(n+1).

     7 | n^2 + n + 1 iff

     7 |   n^2 - 6*n + 8
         = (n-2)*(n-4) iff

     n = 2 or 4 (mod 7).

     7 | n^2 - n + 1 iff

     7 |   n^2 - 8*n + 15
         = (n-3)*(n-5) iff

     n = 3 or 5 (mod 7).

Thus no matter what n is congruent to modulo 7, 7 divides n^7 - n.

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