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 sysmax = 2000if (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 Truedef 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 1print (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=2n=561def 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 lsif (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=-1if (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 = 67561 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