A Carmichael number is named after Robert Carmichael [here]. It is a composite number \(n\) (a number that is not a prime number) that is defined as \(b^{n-1} \equiv 1 \pmod {n}\) for all integers \(b\) which are relatively prime to \(n\). The smallest Carmichael number is 561, and which is made up of \(3 \times 11 \times 17\). In fact, every Carmichael number is made up of at least 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 \(4^{560} \pmod {561}\) and which equals 1. A value of \(b=8\) will also work as its factors are 2. But \(b=6\) will not work as it shares a factor of 3 with 561. Overall, Carmicheal numbers are numbers which will pass the Fermat test for primality (\(b^{n-1} \equiv 1 \pmod {n}\)).
Carmichael Numbers |
Theory
A Carmichael number is named after Robert Carmichael [here]. It is a composite number \(n\) (a number that is not a prime number) that is defined as \(b^{n-1} \equiv 1 \pmod {n}\) for all integers \(b\) which are relatively prime to \(n\). The smallest Carmichael number is 561, and which is made up of \(3 \times 11 \times 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:
\(4^{560} \pmod {561}\)
and which equals 1. A value of \(b=8\) will also work as its factors are 2 (\(2 \times 2 \times 2\)). But \(b=6\) will not work as it shares a factor of 3 with 561. Overall, Carmicheal numbers are numbers which will pass the Fermat test for primality (\(b^{n-1} \equiv 1 \pmod {n}\)).
Coding
The following is the code:
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:
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 \times 11 \times 17\).