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


Answers to Questions (FAQ)

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}-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)

Carmichael numbers are never divisible by a square (their decomposition into prime numbers has at least 3 factors).

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, 997633, etc.

OEIS Sequence A002997 here

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 credit 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 2024-11-07, 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!

Questions / Comments

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


https://www.dcode.fr/carmichael-number
© 2024 dCode — El 'kit de herramientas' definitivo para resolver todos los juegos/acertijos/geocaching/CTF.
 
Feedback