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

### Proof by Contraposition

```
Date: 03/06/2002 at 11:55:10
Subject: Number Theory

Hi!

How can I prove that n^6 + 2n^5 - n^2 - 2n is divisible by 120?

Thanks,
```

```
Date: 03/07/2002 at 17:17:25
From: Doctor Paul
Subject: Re: Number Theory

The easiest way to prove this is a proof by contraposition. A
statement and its contrapositive are logically equivalent. So proving
the following statement will in fact prove your statement:

if n is not prime then 2^n - 1 is not prime.

Assume n is not prime. Then n = p*q where p and q are both greater
than or equal to two.

then 2^n - 1 = 2^(p*q) - 1 =

(2^p - 1) * [2^(p*(q-1)) + 2^(p*(q-2)) + ... + 2^p + 1]

Notice that the next to the last term in the [] above is 2^p. This can
be thought of as:

2^(p*(q-(q-1))) = 2^p

It's easier to see what's going on with an actual example.

2^15 - 1 = 2^(3*5) - 1 =

(2^3 - 1) * (2^12 + 2^9 + 2^6 + 2^3 + 1)

Similarly, the last term in the [] above can be rewritten:

2^(p*(q-(q-0))) = 2^0 = 1

Since p > 1 we know that 2^p - 1 is not one and thus we have a
non-trivial factorization for 2^n - 1 which shows that 2^n - 1 is
composite when n is composite.  This completes the proof.

more.

- Doctor Paul, 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