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.

Carmichael Number - dCode

Tag(s) : Arithmetics

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

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.

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.

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)

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)

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

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 !

Please, check our community Discord for help requests!

carmichael,pseudo,prime,strong,euler,jacobi,robert,561

Source : https://www.dcode.fr/carmichael-number

© 2020 dCode — The ultimate 'toolkit' to solve every games / riddles / geocaching / CTF.

Feedback

▲