One of my favorite books of all time is Doerfler's Dead Reckoning, or Calculating Without Instruments. This is a serious mathematical book, not one of those fly-by-night, snake-oil books on how to become a genius in 21 days or less. The topic of the book is just what it says, but its breadth is breathtaking. Full mastery of its contents would seem to take a lifetime. But with full mastery, one could do 3d navigation in one's head. Logarithms and trigonometry on your feet and in your head are just a few of the topics covered.
I was reminded of Doerfler's book when I read the following beautiful demonstration that 2^32+1 is not prime in Ian Stewart's Concepts of Modern Mathematics, on page 38. Ian Stewart is another of those authors whose every book is worth reading. But here we see how to prove that 641 divides 4,294,967,297 = 2^32+1 by just doing easy math in our heads! This fact is important when worrying about Pseudo-Random Number Generators as I have blogged extensivly, so it has very immediate, practical consequences for programmers.
Recall that arithmetic modulo p, a prime, forms a field. That means that addition, subtraction, multiplication, and division -- that's the big one -- all work intuitively. If the modulus is not prime, division does not always work, so we avoid non-prime moduli. In particular, the proof warns us to avoid arithmetic mod 2^32+1, which, otherwise, would be very natural on 32-bit computers.
First, we notice that 641 is prime. We can prove this by the "license-plate-factoring" children's game I've blogged earlier. As a reminder, that game entails just knowing the multiplication table of the first 11 primes, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, and 31. 641 is going to be our modulus. We will do all the math in our heads.
We then notice that 641 = 1 + 5 * 2^7 = 1+5*128 = 1+640. Let's write this mod 641:
0 is congruent to 1+5*2^7 mod 641 => (subtract 1 from both sides)
-1 is congruent to 5 * 2^7 mod 641 => (divide both sides by 5)
-1/5 is congruent to 2^7 mod 641 (because division always works) =>
-2/5 is congruent to 2^8 mod 641 => (raise both sides to the fourth power)
(-2/5)^4 = -2^4 / 5^4 is congruent to (2^8)^4 = 2^32 mod 641
Now we notice that 2^4 + 5^4 = 16 + 625 = 641 is congruent to 0 mod 641, so, dividing both sides by 5^4, we get 2^4/5^4 + 1 is congruent to 0 mod 641, so, 2^4/5^4 is congruent to -1 mod 641, so, finally,
-1 is congruent to 2^32 mod 641, or
2^32 + 1 is congruent to 0 mod 641, which is the same as saying that 641 divides 4,294,967,297, but we didn't have to do division.
This little proof just made my morning, and I hope it makes yours.
I started to read "Types and Programming Languages" by Benjamin Pierce, and was immediately struck by the exceptional clarity of this author. I can almost recommend anything by him sight unseen, especially after I picked this concise paper on the lambda and the pi calculus off his website. If you want to firm up your grasp on foundations of programming, go, get, read; do not delay, do not let the book sit around on your shelf for months the way I did :)