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.
definition
Definition
A composite natural number is called a Carmichael number if the following congruence is fulfilled for all coprime numbers here called "base":
- .
Example
As mentioned, the smallest is Carmichael number. For all bases that have no prime factor in common, the following applies .
561 is divisible by 3, 11, 17, 33, 51, and 187. However, the congruence does not apply to these factors: 3 ^{560} ≡ 375 mod 561, 11 ^{560} ≡ 154 mod 561, 17 ^{560} ≡ 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.
Tightening
due to the identity applies to every prime factor of a natural number :
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 .
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 .
Carmichael number | Prime factors | ||||
---|---|---|---|---|---|
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.
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.
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
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 .
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.
swell
- ^ WR Alford, A. Granville, C. Pomerance: There are Infinitely Many Carmichael Numbers , Ann. Math. 139 , 703-722, 1994.
- ^ Derrick Henry Lehmer : Strong Carmichael numbers. J. Austral. Math. Soc. 21 (Series A) (1976), pp. 508-510
- ↑ For (simple) proof see Eric W. Weisstein: "Carmichael number" (→ Weblinks).
- ↑ 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
- ^ See Crandall, Pomerance: Prime Numbers , p. 122
- ^ Glyn Harman: On the number of Carmichael numbers up to x , Bull. London Math. Soc. 37 , 641-650, 2005.
- ^ 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
Web links
- 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)