[Home] [Puzzles & Projects] [Delphi Techniques] [Math Topics] [Library] [Utilities]
True or false? X4 - X2 is a multiple of 12 for every integer value of X. I ran across a similar question (but not the answer) in a newsgroup the other day. I liked it so well that I decided to write a program.
Background & Techniques
This isn't really much a program, but it is an interesting example of the power of factoring in mathematical proofs. Of course, a computer program can't really check every integer value of X, so we'll settle for checking as many as we can. Just remember, we may experimentally prove falsehood for any proposition about "all" or "none" of the members of an infinite set, but we can never experimentally prove it to be true.
For 32 bit integers (the normal Integer type), the maximum value is around 2 billion, so our X4 calculation should not get larger than this. To ensure that, we'll user the Power function to set a stopping value for X at the 4th root of the maximum integer value. We'll display an error message if we find a value of X4 - X2 that is not a multiple of 12. This loop only takes a few lines of code. If we find a value of X which is not a multiple of 12 we have proven the proposition false. If all values checked are multiples of 12, we haven't really proven anything (but it sure would make to suspect that it's true).
Just for fun, we'll also check using 64 bit integers(Int64 type). The primary difference here is that DO loop control variables must be 32 bit integers, so we'll use a WHILE loop to test all the values.
The most interesting part is the mathematical proof that the proposition is true. The proof goes like this: Factor the expression as X4-X2 as XX(X2-1) which factors further as XX(X-1)(X+1). If this expression is to be divisible by 12, it must be divisible by 4 and by 3. Let's see first if it is divisible by 3. Notice that the number in question has 3 consecutive integers as factors (X-1), X, and (X+1). For any 3 consecutive integers, one of them is divisible by 3. I'll put a more rigorous proof of that in the Math Topics section, but for now, just try a few sets of 3 consecutive integers and you'll agree ([2,3,4], [13,14,15], etc.).
So our number is divisible by 3, but is it divisible by 4? Assume X is even, then the XX part of the expression is divisible by 4, right? ("even" means X=2Y for some Y, so XX= (2Y) (2Y)=4YY which is a multiple of 4). But what if X is odd? Then the factors (X-1) and (X+1) are both even and, by the same reasoning, their product is a multiple of 4. The original expression is divisible by 3 and by 4, so it is divisible by 12. Q.E.D. as the mathematicians like to say, which stands for some Latin words that mean "That's what we set out to prove". The last word of Q.E.D. is Demostrandum - you can look up the others. (try "Q.E.D. abbreviation" in search)
Running/Exploring the Program
Suggestions for further exploration
Copyright © 2000-2013, Gary Darby
All rights reserved.