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.

About Brent

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

View all posts by Brent →

10 Responses to New baby, and primality testing

Thibault Vroonhove says:

September 30, 2017 at 4:21 pm

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$ .
- Brent says:
  
  September 30, 2017 at 4:42 pm
  
  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.
Tim says:

September 30, 2017 at 4:32 pm

Congratulations on your little one!
- Brent says:
  
  September 30, 2017 at 4:44 pm
  
  Thanks!
Anthony says:

September 30, 2017 at 4:36 pm

Congratulations, Brent. There’s no feeling in the world like that of being a new father.
- Brent says:
  
  September 30, 2017 at 4:44 pm
  
  Thank you!
yenergy says:

October 12, 2017 at 12:53 pm

Congratulations! Welcome to the parenting club!
- Brent says:
  
  October 13, 2017 at 9:52 pm
  
  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