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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.