Search for a tool
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.

Results

Carmichael Number -

Tag(s) : Arithmetics

Share
dCode and more

dCode is free and its tools are a valuable help in games, maths, geocaching, puzzles and problems to solve every day!
A suggestion ? a feedback ? a bug ? an idea ? Write to dCode!

Please, check our dCode Discord community for help requests!
NB: for encrypted messages, test our automatic cipher identifier!

Feedback and suggestions are welcome so that dCode offers the best 'Carmichael Number' tool for free! Thank you!

# Carmichael Number

## Carmichael Number Checker

### 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

### Why are the numbers called Carmichael?

Robert Daniel Carmichael was an American mathematician who published a study on these numbers in 1912.

## Source code

dCode retains ownership of the "Carmichael Number" source code. Except explicit open source licence (indicated Creative Commons / free), the "Carmichael Number" algorithm, the applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, breaker, translator), or the "Carmichael Number" functions (calculate, convert, solve, decrypt / encrypt, decipher / cipher, decode / encode, translate) written in any informatic language (Python, Java, PHP, C#, Javascript, Matlab, etc.) and all data download, script, or API access for "Carmichael Number" are not public, same for offline use on PC, mobile, tablet, iPhone or Android app!
Reminder : dCode is free to use.

## Cite dCode

The copy-paste of the page "Carmichael Number" or any of its results, is allowed (even for commercial purposes) as long as you cite dCode!
Exporting results as a .csv or .txt file is free by clicking on the export icon
Cite as source (bibliography):
Carmichael Number on dCode.fr [online website], retrieved on 2023-09-30, https://www.dcode.fr/carmichael-number

## Need Help ?

Please, check our dCode Discord community for help requests!
NB: for encrypted messages, test our automatic cipher identifier!