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.

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

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.

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

Please, check our community Discord for help requests!

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

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

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

Feedback

▲