Search for a tool
Carmichael Number

Tool for testing and calculating Carmimichael numbers. A Carmimichael 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 you

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 community Discord for help requests!


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

Carmichael Number

Carmichael Number Checker


Tool for testing and calculating Carmimichael numbers. A Carmimichael number (also called an strong pseudo-prime number) is a number N such as A^(N-1) ≡ 1 mod N for all integer A.

Answers to Questions

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

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 source code of the script Carmichael Number online. Except explicit open source licence (indicated Creative Commons / free), any algorithm, applet, snippet, software (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, translator), or any function (convert, solve, decrypt, encrypt, decipher, cipher, decode, code, translate) written in any informatic langauge (PHP, Java, C#, Python, Javascript, Matlab, etc.) which dCode owns rights will not be released for free. To download the online Carmichael Number script for offline use on PC, iPhone or Android, ask for price quote on contact page !

Need Help ?

Please, check our community Discord for help requests!

Questions / Comments

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


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