What’s Special About 561? … It’s A Number That That Tricks The Fermat Prime Number Test

What’s Special About 561? … It’s A Number That Tricks The Fermat Prime Number Test

As an active researcher, I spend a few hours each week reading research papers. In fact each week, I select a new paper that is creating some impact, and I also pick a classic paper. My latest classic paper is from 1910, and written Robert D Carmichael [here][1]:

It outlines a Carmichael number and which is composite number n (and which is a number that is not a prime number) and that is defined as:

for all integers a which are relatively prime to n. This is also defined as the Fermat primality test and is used to determine if a number is a prime number.

The smallest Carmichael number is 561, and which is made up of 3×11×17. In fact, every Carmichael number is made up of three factors. If we try 561, we cannot use a value which a factor of 3, 11 or 17. So if we try b=4, we get:

and which equals 1. A value of a=8 will also work as its factors are 2 (2×2×2). But a=6 will not work as it shares a factor of 3 with 561. The following is the code [here]:

import libnum
import sysimport libnum
import sys

max = 2000

if (len(sys.argv)>1):
  max=int(sys.argv[1])

def isPrime(n):
   if n <= 1 or n % 1 > 0:
      return False
   for i in range(2, n//2):
      if n % i == 0:
         return False
   return True

def isCarmichael( n) : 
	b = 2
	while b < n : 
		if (libnum.gcd(b, n) == 1) : 
			if (pow(b, n - 1, n) != 1): 
				return 0
		b = b + 1
	return 1

print (f"Finding Carmichael numbers up to {max}")

for i in range (3,max):
  if (isPrime(i)): continue
  if (isCarmichael(i)):
    print (f"{i} factors=",end=' ')
    for factors in libnum.factorize(i):
      print (factors,end=' ')
    print()

And a sample run [here]:

Finding Carmichael numbers up to 3000
561 factors= 3 11 17 
1105 factors= 5 13 17 
1729 factors= 7 13 19 
2465 factors= 5 17 29 
2821 factors= 7 13 31

In this case, we see 561 is 3×11×17, but will pass Fermat’s test for primality. Carmichael numbers thus pass the Fermat test for a prime number, but they are not!

The first few are {561, 1105, 1729, 2465, 2821}, and would each pass a Fermat test for prime numbers. While 561 is the smallest Carmichael number, it has since been proven that there is an infinite number of these [here]:

A Carmichael number has, at most, a 50% chance of passing the Solovay-Strassen primality test.

The Miller-Rabin test — one of the most popular in finding primes —gives a maximum of a 25% chance of a Carmichael number passing as a prime. The Solovay-Strassen test [2] does the Fermat test, and then adds a test of:

If we run a test on 561, we says that it is prime (and it is not!) [here]:

If we now test:

import sys
import libnum
a=2

n=561

def legendre_symbol(a, p):
# Returns 1 if a has a square root modulo p, -1 otherwise.

ls = pow(a, (p - 1) // 2, p)
    return -1 if ls == p - 1 else ls

if (len(sys.argv)>1):
  n=int(sys.argv[1])

if (len(sys.argv)>2):
  a=int(sys.argv[2])

print ("a = ",a)
print ("n = ",n)

if (libnum.gcd(a,n)!=1):
 print ("a and n share a factor");
 sys.exit()

val=pow(a,(n-1)//2, n)
val2=pow(a,n-1, n)
leg=legendre_symbol(a,n)

print (f"Euler test: {a}^({n-1}) (mod {n}) = {val2}")
print (f"Jacobi test: {a}^({(n-1)//2}) (mod {n}) =  {val}")
print (f"Legendre symbol =  {leg}")

if (val==(n-1)): val=-1

if (val==leg and val2==1):
 print (f"\n{n} is probably prime")
else:
 print (f"\n{n} is not prime")

We get:

a =  5
n =  561
Euler test: 5^(560) (mod 561) = 1
Jacobi test: 5^(280) (mod 561) =  67
Legendre symbol =  67

561 is probably prime

References

[1] Carmichael, R. D. (1910). Note on a new number theory function. Bulletin of the American Mathematical Society, 16(5), 232–238.

[2] Solovay, R., & Strassen, V. (1977). A fast Monte-Carlo test for primality. SIAM journal on Computing, 6(1), 84–85.

Subscribe: https://billatnapier.medium.com/subscribe