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

### 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/
```
Associated Topics:
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