Carmichael Number
Tool for testing and calculating Carmichael numbers. A Carmichael number (also called an strong pseudo-prime number) is a number N such as A^(N-1) ≡ 1 mod N for all integer A.
Carmichael Number - dCode
Tag(s) : Arithmetics
Thanks to your feedback and relevant comments, dCode has developed the best 'Carmichael Number' tool, so feel free to write! Thank you!
Carmichael Number Checker
Integer Number (up to 1000 digits)
See also: Prime Factors Decomposition — Prime Numbers Search — Euler's Totient
What is a Carmichael number? (Definition)
A Carmichael number is an integer $ n $ which is composed (therefore not a prime number) such that for any integer $ a $, the following formula is true $$ a^{{n-1}} \equiv 1 \mod{n} \iff a^{{n}} \equiv a \mod{n} $$
So, for any integer $ p $ coprime with $ n $, the property $ n \mid p^n-p $ is verified (which reads $ n $ divides $ p^n-p $ so $ p^n-p $ is a multiple of $ n $)
Example: $ 8911 $ is a Carmichael number $ 8911 = 7 \times 19 \times 67 $
Sometimes the expression is rewritten $ n \mid p^{n–1}–1 $ which allows to realize that a Carmichael number satisfies Fermat's little theorem: $$ p^{n-1}- \equiv 0 \mod {n} $$
Carmichael numbers are also called strong pseudo-prime numbers or Euler-Jacobi pseudo-prime numbers.
How to check that a number is a Carmichael number? (Algorithm)
There is no formula to quickly find all Carmichael numbers but it is possible to use an algorithm which is conditioned by a primality test and the verification of $ a^{{n-1}} \equiv 1 \mod{n} $
There are infinitely many Carmichael numbers (proof from Alford et al. 1994)
What are the first known Carmichael numbers?
The smallest Carmichael number is $ 561 $ which has for prime factors decomposition $ 561 = 3 \times 11 \times 17 $
Here is the list of Carmichael's numbers up to 1 million: 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881, 512461, 530881, 552721, 656601, 658801, 670033, 748657, 825265, 838201, 852841, 9976
OEIS Sequence A002997 here (link)
Why are the numbers called Carmichael?
Robert Daniel Carmichael was an American mathematician who published a study on these numbers in 1912.
dCode retains ownership of the online 'Carmichael Number' tool source code. Except explicit open source licence (indicated CC / Creative Commons / free), any algorithm, applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, translator), or any function (convert, solve, decrypt / encrypt, decipher / cipher, decode / encode, translate) written in any informatic language (PHP, Java, C#, Python, Javascript, Matlab, etc.) no data, script or API access will be for free, same for Carmichael Number download for offline use on PC, tablet, iPhone or Android !
Prime Factors Decomposition
Euler's Totient
Prime Numbers Search
Multiples of a Number
Rounding Calculator
Luhn Number Checksum
Divisors of a Number
LCM (Lowest Common Multiple)
Modulo N Calculator
Euclidean Division
carmichael,pseudo,prime,strong,euler,jacobi,robert,561
Source : https://www.dcode.fr/carmichael-number