Carmichael number
A natural number is called a Carmichael number, named after the mathematician Robert Daniel Carmichael, when all is a Fermat pseudoprime relative to their prime bases. Carmichael numbers play a role in the analysis of primality tests.
Every Carmichael number is square-free and the product of at least three primes. The smallest Carmichael number is the number 561 = 3:11:17. In 1994, Carl Pomerance, WR Alford, Andrew Granville and proved the existence of infinitely many Carmichael numbers.
It is easy to recognize a Carmichael number if you know their prime factorization. This is due to the set of Korselt (see below). It is also relatively easy to generate Carmichael numbers, especially as the algorithms exist after J. Chernick. It is problematic, however - to recognize whether it is a Carmichael number with a number - especially in large numbers. This difficulty have the Carmichael numbers with prime numbers together, because either one performs a factorization, or you turn the small Fermat's theorem on the number, where you and do not occur in prime numbers for the bases that do not have a primality must test for divisibility. In practice, distinguishing a undismantled Carmichael number of a prime number is easier because there are no strong Carmichael numbers. One can find a prime base at any Carmichael number N is always such that the prime property is violated (using the Jacobi symbol and the notation for congruence ).
Definition
Definition A composite natural number n is called a Carmichael number if for all is fulfilled prime to n numbers a, the following congruence:
Example As mentioned, 561 = 03/11/17 smallest Carmichael number. For all bases a, which have no prime factor in common with 561, applies namely a560 ≡ 1 mod 561
561 is divisible by 3, 11, 17, 33, 51 and 187. For these dividers the congruence does not apply: 3560 ≡ 375 mod 561, 11560 ≡ 154 mod 561, 17560 ≡ 34 mod 561, etc.
Set of Korselt
Proved already in 1899 Alwin Reinhold Korselt following sentence:
Intensification Based on the identity of n- 1 = n / p - 1 ( p-1) x N / p holds for every prime factor p is a natural number n:
Thus, the second part of Korselts set can also be formulated as: A number n is a Carmichael number if and only if for each of its prime divisors p -1 divides n / p - 1
Carmichael then with 561 found in 1910, the first number that corresponds to the properties of the theorem of Korselt.
The sequence of Carmichael numbers
Carmichael numbers have at least three prime factors. As mentioned in the introduction, it is known since 1994 that there are infinitely many Carmichael numbers.
The table shows the beginning of the sequence of Carmichael numbers ( sequence A002997 in OEIS ) is less 100000:
Generation of Carmichael numbers
Method of Chernick
J. Chernick 1939 was a relatively simple system to construct Carmichael numbers:
For example, 1729 = 7:13:19 this structure. It is interesting that the Carmichael number 172081 = 31.61.91 the condition " almost met ": 91 is not prime, but Fermat pseudoprime to the base 3
Method of Michon
Gérard P. Michon found a similar method to construct Carmichael numbers:
M must then be divisible by 3, since otherwise one of the three factors is divisible by 3. For example, for m = 24966 the three numbers 174763, 274627 and 199 729 are prime and their product is a Carmichael number. A generated with this method Carmichael number with 1,000 jobs is
Newer designs
Based on an idea of Paul Erdős group theoretical considerations and advanced computer algorithms far greater Carmichael numbers can be constructed using. In July 2012, a Carmichael number, after substantial Ausreizen already known methods was presented with more than 10 billion prime factors and nearly 300 billion decimal places.
Asymptotic number
Erdős conjectured in 1956 that there are infinitely many Carmichael numbers, and that their number C (x) below a barrier x no exponent a < 1 exists with the case of arbitrarily large x.
The proof of Alford / Granville / Pomerance provides the lower estimate of the number of function for all sufficiently large x. This result was improved in 2005, for sufficiently large x. Bills to create a growth with the lower estimate close, so that Daniel Shanks was convinced was a very safe upper estimate for the number function. However, he was persuaded by discussion with the above-mentioned authors assume that the conjecture of Erdos could correspond to the true asymptotic behavior. In 2002 published Granville and Pomerance an analysis of the distribution of Carmichael numbers with reference to further plausible and reasonable assumptions that ( no evidence ) provided a result, both according to the argument of Erdos and in line with the empirical results for small x, and so the dissolved by Shanks highlighted apparent contradiction.