I have neglected writing on this blog for a while, and here is why:
Yes, there is a new small human in my house! So I won’t be writing here regularly for the near future, but do hope to still write occasionally as the mood and opportunity strikes.
Recently I realized that I really didn’t know much of anything about fast primality testing algorithms. Of course, I have written about the Lucas-Lehmer test, but that is a special-purpose algorithm for testing primality of numbers with a very special form. So I have learned about a few general-purpose primality tests, including the Rabin-Miller test and the Baille-PSW test. It turns out they are really fascinating, and not as hard to understand as I was expecting. So I may spend some time writing about them here.
As a first step in that direction, here is (one version of) Fermat’s Little Theorem (FLT):
Let be a prime and some positive integer not divisible by . Then that is, is one more than a multiple of .
Have you seen this theorem before? If not, play around with some small examples to see if you believe it and why you think it might be true. If you have seen it before, do you remember a proof? Or can you come up with one? (No peeking!) There are many beautiful proofs; I will write about a few.