Math Mutation: 253: Making Jewelry With Fermat

Audio Link

Whenever you hear the name of the 17th century French mathematician Pierre de Fermat, the first thing that comes to your mind is probably Fermat’s Last Theorem. That, as I’m sure you remember, is his well-known unproven hypothesis about aⁿ+ bⁿ = cⁿ not having whole number solutions for n>2. That one is rightfully famous for having stumped the math community for hundreds of years, until Princeton professor Andrew Wiles finally proved it in the 1990s. But Fermat was no one-theorem wonder. He was quite an accomplished mathematician, and came up with many other interesting results, most of which are proven a lot more easily than his Last Theorem. In particular, one of his best-known other ideas, “Fermat’s Little Theorem”, is arguably a much better legacy. Aside from having been proven by Leibniz and Euler within a century of its proposal, its applicability in forming primality tests has made it a foundation of some of the algorithms used in modern cryptography. These algorithms form the basis of systems like the RSA encryption used in many secure internet protocols.

So, what is Fermat’s Little Theorem? Like his Last Theorem, it’s actually pretty easy to state: For any prime number p and integer n, n^p- n is always divisible by p. So, for example, let’s choose p = 3 and n = 5. The theorem states that 5³- 5 will be divisible by 3. Assuming you haven’t forgotten all your elementary arithmetic, you probably see that since 5³- 5 is 120, which is 3 times 40, the theorem works. Since the theorem is true for all primes, it implies a basic test you can use to prove a number is composite, or non-prime: if you are examining a potentially prime number p, pick another “witness” number n and check whether the condition of the Little Theorem holds true. If it doesn’t, we know p isn’t prime. Of course, this is a probabilistic test— you can get lucky with a nonprime number, like 341 which passes the test (with n = 2) but is equal to 31 times 11. So you need to calculate the odds and choose samples accordingly. Modern algorithms use more sophisticated techniques, but still build on this foundation.

The reason Fermat’s Little Theorem came to mind recently was that I was browsing the web and saw a very nice common-sense proof of the theorem at the “Art of Problem Solving” site. Like most math majors, I did learn about some proofs of this theorem in college classes, and it’s not too hard to jot down the proper equations, simplify, and prove it inductively using the algebra. But I always prefer intuitive non-algebraic proofs where I can find them: though there’s no logical excuse to doubt the bulletproof algebra, my primitive human brain still feels more satisfied with a proof we can visualize. So, how can we prove that for any prime number p and integer n, n^p- n is always divisible by p, without using algebra?

Let’s visualize a jewelry-making class, where you are given a necklace that can fit up to p beads, each of which can come in n colors. Actually, to help visualize, let’s use concrete numbers initially: your necklace can fit 3 beads, each of which can come in up to 5 colors. There are thus a total of 5³permutations of beads you can put together on a necklace: 5 choices for the first bead, times 5 for the second, times 5 for the third. 5 of these 5³combinations are necklaces where all the beads are the same color, so let’s put those aside for now. If you look at any example configuration from the remaining 5³ - 5 available, you will see that it actually must be one representative of a family of 3 necklaces. For any necklace where all 3 beads are not identical, you can rotate it 3 ways, with each rotation being a valid combination. Since every possible combination must be part of such of a family of 3, and there are no combinations from 2 families that can be equivalent, the number of remaining combinations must be divisible by 3. Thus, 5³ - 5 is divisible by 3, and the theorem holds. Since this argument works for any prime p and integer n, it effectively proves the theorem.

Anyway, if you’re not already convinced, hopefully after doodling a few necklaces on a scratchpad, or taking your daughter to a jewelry-making class, you can see why the theorem holds. I always like it when I see a simple intuitive argument like this for what seems at first to require messy algebra— even though we can’t know Fermat’s thought processes for sure, I wouldn’t be surprised if he did this kind of visualization when first coming up with the concept.

And this has been your math mutation for today.

References:

Math Mutation

Sunday, July 21, 2019

253: Making Jewelry With Fermat

3 comments: