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

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.

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

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

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

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.

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-10-04,

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

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

© 2024 dCode — El 'kit de herramientas' definitivo para resolver todos los juegos/acertijos/geocaching/CTF.

Feedback