Carmichael number

A natural number is called a Carmichael number , named after the mathematician Robert Daniel Carmichael , if it is a Fermat pseudoprime number with respect to all bases that are relatively prime to it. Carmichael numbers play a role in the analysis of primality tests .

Every Carmichael number is square-free and the product of at least three prime numbers. The smallest Carmichael number is the number 561 = 3 11 17. In 1994 Carl Pomerance , WR Alford, and Andrew Granville proved the existence of infinitely many Carmichael numbers.

It is easy to see a Carmichael Number knowing its prime factorization . This is thanks to Korselt's theorem (see below). It is also relatively easy to generate Carmichael numbers, especially since algorithms like the one according to J. Chernick exist. However, it is problematic - especially with large numbers - to recognize whether a number is a Carmichael number. The Carmichael numbers have this difficulty in common with the prime numbers, because either a factorization is carried out or the little Fermat's theorem is applied to the number, whereby the bases that do not point to a primality and that do not appear in prime numbers are used , must test for divisibility . In practice, distinguishing an undecomposed Carmichael number from a prime number is made easier by the fact that there are no strong Carmichael numbers. For every Carmichael number one can always find a coprime basis , so that the prime number property (using the Jacobi symbol and the notation for congruence ) is violated. ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle a^{(n-1)/2}\equiv \left({\tfrac {a}{n}}\right){\pmod {n}}}$

definition

Definition
A composite natural number is called a Carmichael number if the following congruence is fulfilled for all coprime numbers here called "base": ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle a,}$

${\displaystyle a^{n-1}\equiv 1{\pmod {n}}}$ .

Example
As mentioned, the smallest is Carmichael number. For all bases that have no prime factor in common, the following applies . ${\displaystyle n:=561=3\cdot 11\cdot 17}$ ${\displaystyle a,}$ ${\displaystyle n}$ ${\displaystyle a^{n-1}\equiv 1{\pmod {n}}}$

561 is divisible by 3, 11, 17, 33, 51, and 187. However, the congruence does not apply to these factors: 3 ⁵⁶⁰ ≡ 375 mod 561, 11 ⁵⁶⁰ ≡ 154 mod 561, 17 ⁵⁶⁰ ≡ 34 mod 561, etc.

Theorem of Korselt

Alwin Reinhold Korselt proved the following theorem as early as 1899 :

A natural number is a Carmichael number if and only if it is not prime and free of squares and all of its prime divisors are true that the number divides. ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle p-1}$ ${\displaystyle n-1}$

Tightening
due to the identity applies to every prime factor of a natural number : ${\displaystyle n-1={\frac {n}{p}}-1+(p-1){\frac {n}{p}}}$ ${\displaystyle p}$ ${\displaystyle n}$

${\displaystyle n-1\equiv {\frac {n}{p}}-1{\pmod {\ }}p-1.}$

Thus, the second part of Korselt's theorem can also be formulated as: A number is a Carmichael number if and only if it applies to each of its prime divisors: divides . ${\displaystyle n}$ ${\displaystyle p-1}$ ${\displaystyle {\frac {n}{p}}-1}$

Carmichael found the first number in 1910, 561, which corresponds to the properties of Korselt's theorem.

The sequence of the Carmichael numbers

Carmichael numbers have at least three prime factors, none of which are double. As mentioned in the introduction, it has been known since 1994 that there are an infinite number of Carmichael numbers.

The table shows the Carmichael numbers (sequence A002997 in OEIS ) below 100000 and relates them to the Carmichael function and the Euler's function . ${\displaystyle \lambda }$ ${\displaystyle \varphi }$

Carmichael number ${\displaystyle n}$	Prime factors	${\displaystyle \lambda (n)}$	${\displaystyle (n-1)/\lambda (n)}$	${\displaystyle \varphi (n)}$	${\displaystyle \varphi (n)/\lambda (n)}$
561	3⋅11⋅17	80	7th	320	4th
1105	5-13-17	48	23	768	16
1729	7-13-19	36	48	1296	36
2465	5⋅17⋅29	112	22nd	1792	16
2821	7⋅1331	60	47	2160	36
6601	7⋅23⋅41	1320	5	5280	4th
8911	7⋅19⋅67	198	45	7128	36
10585	5⋅29⋅73	504	21st	8064	16
15841	7⋅31⋅73	360	44	12960	36
29341	13-37-61	180	163	25920	144
41041	7⋅11⋅13⋅41	120	342	28800	240
46657	13-37-97	288	162	41472	144
52633	7⋅73103	1224	43	44064	36
62745	3⋅5⋅47⋅89	2024	31	32384	16
63973	7⋅13⋅19⋅37	36	1777	46656	1296
75361	11⋅13⋅17⋅31	240	314	57600	240

Generation of Carmichael Numbers

Chernick's method

J. Chernick found a relatively simple system for constructing Carmichael numbers in 1939:

If the three numbers and are prime numbers, their product is a Carmichael number. ${\displaystyle 6m+1,12m+1}$ ${\displaystyle 18m+1}$ ${\displaystyle (6m+1)(12m+1)(18m+1)}$

For example, 1729 = 7 * 13 * 19 has this structure. It is interesting that the Carmichael number 172081 = 31 · 61 · 91 the condition “almost fulfilled”: 91 is not prime, but Fermat's pseudoprime to base 3.

Michon's method

Gérard P. Michon found a similar method to construct Carmichael numbers:

If and the three are numbers and prime numbers, their product is a Carmichael number. ${\displaystyle m\equiv 326\ mod\ 616}$ ${\displaystyle 7m+1,8m+1}$ ${\displaystyle 11m+1}$ ${\displaystyle (7m+1)(8m+1)(11m+1)}$

${\displaystyle m}$must then be divisible by 3, otherwise one of the three factors is divisible by 3.
Example: for are the three numbers and are prime and their product is a Carmichael number. A Carmichael number with 1000 digits generated with this method is ${\displaystyle m=24966}$ ${\displaystyle 174763,199729}$ ${\displaystyle 274627}$

${\displaystyle (12936\cdot 10^{329}-59827428149)\cdot (14784\cdot 10^{329}-68374203599)\cdot (20328\cdot 10^{329}-94014529949).}$

Newer constructions

Based on an idea by Paul Erdős , much larger Carmichael numbers can be constructed with the help of group theoretical considerations and modern computer algorithms. In July 2012, after extensive exhaustion of already known methods, a Carmichael number with more than 10 billion prime factors and almost 300 billion decimal places was presented.

Asymptotic number

Erdős suspected as early as 1956 that there are many Carmichael numbers are infinite, and that their number is below a barrier no exponent exists with in any capacity . ${\displaystyle C(x)}$ ${\displaystyle x}$ ${\displaystyle a<1}$ ${\displaystyle C(x)<x^{a}}$ ${\displaystyle x}$

The proof of Alford / Granville / Pomerance provides the lower estimate of the number function for all sufficiently large . This result was improved in 2005 to be large enough . Calculations to suggest a growth with the lower estimate , so that Daniel Shanks was convinced that it was a very safe upper estimate for the number function. However, through discussion with the authors mentioned, he was convinced that Erdös' conjecture might correspond to the true asymptotics. In 2002, Granville and Pomerance published an analysis of the distribution of the Carmichael numbers on the basis of further plausible and well-founded assumptions, which provided a result (no proof) both in accordance with Erdős' argument and in accordance with the empirical results for small and thus that of Shank's highlighted apparent contradiction resolved. ${\displaystyle C(x)>x^{2/7}}$ ${\displaystyle x}$ ${\displaystyle C(x)>x^{0.33}}$ ${\displaystyle x}$ ${\displaystyle x=10^{15}}$ ${\displaystyle x^{1/3}}$ ${\displaystyle x^{1/2}}$ ${\displaystyle x}$

swell

1. ^ WR Alford, A. Granville, C. Pomerance: There are Infinitely Many Carmichael Numbers , Ann. Math. 139 , 703-722, 1994.
2. ^ Derrick Henry Lehmer : Strong Carmichael numbers. J. Austral. Math. Soc. 21 (Series A) (1976), pp. 508-510
3. ↑ For (simple) proof see Eric W. Weisstein: "Carmichael number" (→ Weblinks).
4. ↑ Steven Hayman, Andrew Shallue: Constructing a ten billion factor Carmichael number (PDF file; 91 kB) Poster at the ANTS X conference, San Diego, July 2012
5. ^ See Crandall, Pomerance: Prime Numbers , p. 122
6. ^ Glyn Harman: On the number of Carmichael numbers up to x , Bull. London Math. Soc. 37 , 641-650, 2005.
7. ^ A. Granville, C. Pomerance: Two contradictory conjectures concerning Carmichael numbers. (PDF; 347 kB) Math. Comp. 71 (2002), No. 238, pp. 883-908

literature

• Paulo Ribenboim : The New Book of Prime Number Records. 3rd edition. Springer, New York NY et al. 1996, ISBN 0-387-94457-5 .
• Richard Crandall , Carl Pomerance : Prime Numbers. A Computational Perspective. Springer, New York NY et al. 2001, ISBN 0-387-94777-9 .

See also

• Lucas-Carmichael number
• Dumpling number

Web links

Wikibooks: Table of Carmichael Numbers  - Learning and Teaching Materials

• Eric W. Weisstein: "Carmichael number" (MathWorld)
• GJO Jameson: Finding Carmichael numbers. (PDF file; 128 kB) and Carmichael numbers with three prime factors. (pdf; 211 kB)