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.

### Like this:

Like Loading...

*Related*

##
About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

We have that with multiplication modulo is a group when is prime. Since , we have . Then because the order of in divides ‘s size that is .

Nice, that is indeed the classic group theory proof. It’s probably the shortest proof (that I know of) if you already know some basic group theory.

Congratulations on your little one!

Thanks!

Congratulations, Brent. There’s no feeling in the world like that of being a new father.

Thank you!

Congratulations! Welcome to the parenting club!

Thank you! I actually have a 6-year-old as well, but it’s been long enough that I pretty much completely forgot what having a newborn is like. =)

Pingback: Four formats for Fermat | The Math Less Traveled

Pingback: Four formats for Fermat: correction! | The Math Less Traveled