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!


Thanks to your feedback and relevant comments, dCode has developed the best 'Carmichael Number' tool, so feel free to write! Thank you!

Carmichael Number

Sponsored ads

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}- \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.

Source code

dCode retains ownership of the online 'Carmichael Number' tool source code. Except explicit open source licence (indicated CC / Creative Commons / free), any 'Carmichael Number' algorithm, applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, translator), or any 'Carmichael Number' function (calculate, convert, solve, decrypt / encrypt, decipher / cipher, decode / encode, translate) written in any informatic language (Python, Java, PHP, C#, Javascript, Matlab, etc.) and no data download, script, copy-paste, or API access for 'Carmichael Number' will be for free, same for offline use on PC, tablet, iPhone or Android ! dCode is free and online.

Need Help ?

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

Questions / Comments

Thanks to your feedback and relevant comments, dCode has developed the best 'Carmichael Number' tool, so feel free to write! Thank you!


Source : https://www.dcode.fr/carmichael-number
© 2021 dCode — The ultimate 'toolkit' to solve every games / riddles / geocaching / CTF.
Feedback