New baby, and primality testing

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 p be a prime and a some positive integer not divisible by p. Then a^{p-1} \equiv 1 \pmod p, that is, a^{p-1} is one more than a multiple of p.

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.

Advertisements

About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in meta, number theory, primes and tagged , , , . Bookmark the permalink.

9 Responses to New baby, and primality testing

  1. Thibault Vroonhove says:

    We have that G = \{1,...,p-1\} with multiplication modulo p is a group when p is prime. Since a \bmod p \neq 0, we have a \bmod p \in G. Then a^{p-1} \bmod p = (a \bmod p)^{p-1} \bmod p = 1 because the order of a \bmod p in G divides G‘s size that is p-1.

  2. Tim says:

    Congratulations on your little one!

  3. Anthony says:

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

  4. yenergy says:

    Congratulations! Welcome to the parenting club!

    • Brent says:

      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. =)

  5. Pingback: Four formats for Fermat | The Math Less Traveled

Leave a reply. You can include LaTeX $latex like this$. Note you have to literally write 'latex' after the first dollar sign!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s