## 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.

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$.

• Brent says:

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.

2. Tim says: