September | 2016 | College Math Teaching

September 23, 2016

Carmichael Numbers: “not quite” primes…

Filed under: algebra, elementary number theory, number theory, recreational mathematics — collegemathteaching @ 9:49 pm

We had a fun mathematics seminar yesterday.

Andrew Shallue gave a talk about the Carmichael numbers and gave a glimpse into his research. Along the way he mentioned the work of another mathematician…one that I met during my ultramarathon/marathon walking adventures! Talk about a small world..

So, to kick start my brain cells, I’ll say a few words about these.

First of all, prime numbers are very important in encryption schemes and it is a great benefit to be able to find them. However, for very large numbers, it can be difficult to determine whether a number is prime or not.

So one can take short cuts in determining whether a number is *likely* prime or not: one can say “ok, prime numbers have property P and if this number doesn’t have property P, it is not a prime. But if it DOES have property P, we hare X percent sure that it really is a prime.

If this said property is relatively “easy” to implement (via a computer), we might be able to live with the small amount of errors that our test generates.

One such test is to see if this given number satisfies “Fermat’s Little Theorem” which is as follows:

Let $a$ be a positive integer and $p$ be a prime, and suppose $a \neq kp$ , that is $a \neq 0 (mod p)$ Then $a^{p-1} = 1 (mod p)$

If you forgotten how this works, recall that $Z_p$ is a field if $p$ is a prime, so $a \in Z_p, a \neq 0 (mod p)$ means that the set $\{a, 2a, 3a, ...(p-1)a \}$ consists of $\{1, 2, 3, ...(p-1) \}$ . So take the product $(a)(2a)(3a)...((p-1)a)) = 1(2)(3)..(p-1)a^{p-1} = 1(2)(3)...(p-1) (mod p)$ . Now note that we are working in a field, so we can cancel the $(1)(2)...(p-1)$ factor on both sides to get $a^{p-1} = 1 (mod p)$ .

So one way to check to see if a number $q$ might be a prime is to check all $a^{q-1}$ for all $a \leq q$ and see if $a^{q-1} = 1 mod q$ .
Now this is NOT a perfect check; there are non-prime numbers for which $a^{q-1} = 1 mod q$ for all $a \leq q$ ; these are called the Carmichael numbers. The 3 smallest such numbers are 561, 41041 and 825265.