Proof by Contraposition

Date: 03/06/2002 at 11:55:10
From: Adam Parhi
Subject: Number Theory 

Hi!

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

Thanks,
Adam

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.

I hope this helps.  Please write back if you'd like to talk about this 
more.

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