Carmichael number
In number theory, a Carmichael number is a composite number Template:Tmath which in modular arithmetic satisfies the congruence relation:
for all integers Template:Tmath.[1] The relation may also be expressed[2] in the form:
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b^{n-1}\equiv 1\pmod{n}}
for all integers Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} that are relatively prime to Template:Tmath. They are infinite in number.[3]
They constitute the comparatively rare instances where the strict converse of Fermat's Little Theorem does not hold. This fact precludes the use of that theorem as an absolute test of primality.[4]
The Carmichael numbers form the subset K1 of the Knödel numbers.
The Carmichael numbers were named after the American mathematician Robert Carmichael by Nicolaas Beeger, in 1950. Øystein Ore had referred to them in 1948 as numbers with the "Fermat property", or "F numbers" for short.[5]
Overview
[edit]Fermat's little theorem states that if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} is a prime number, then for any integer Template:Tmath, the number Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b^p-b} is an integer multiple of Template:Tmath. Carmichael numbers are composite numbers which have the same property. Carmichael numbers are also called Fermat pseudoprimes or absolute Fermat pseudoprimes. A Carmichael number will pass a Fermat primality test to every base Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} relatively prime to the number, even though it is not actually prime. This makes tests based on Fermat's Little Theorem less effective than strong probable prime tests such as the Baillie–PSW primality test and the Miller–Rabin primality test.
However, no Carmichael number is either an Euler–Jacobi pseudoprime or a strong pseudoprime to every base relatively prime to it[6] so, in theory, either an Euler or a strong probable prime test could prove that a Carmichael number is, in fact, composite.
Arnault[7] gives a 397-digit Carmichael number Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} that is a strong pseudoprime to all prime bases less than 307:
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N = p \cdot (313(p - 1) + 1) \cdot (353(p - 1) + 1 )}
where
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p = }
is a 131-digit prime. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} is the smallest prime factor of Template:Tmath, so this Carmichael number is also a (not necessarily strong) pseudoprime to all bases less than Template:Tmath.
As numbers become larger, Carmichael numbers become increasingly rare. For example, there are 20138200 Carmichael numbers between 1 and 1021 (approximately one in 50 trillion (5×1013) numbers).[8]
Korselt's criterion
[edit]An alternative and equivalent definition of Carmichael numbers is given by Korselt's criterion.
- Theorem (A. Korselt 1899): A positive composite integer Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} is a Carmichael number if and only if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} is square-free, and for all prime divisors Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} of Template:Tmath, it is true that Template:Tmath.
It follows from this theorem that all Carmichael numbers are odd, since any even composite number that is square-free (and hence has only one prime factor of two) will have at least one odd prime factor, and thus Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p-1 \mid n-1} results in an even dividing an odd, a contradiction. (The oddness of Carmichael numbers also follows from the fact that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle -1} is a Fermat witness for any even composite number.) From the criterion it also follows that Carmichael numbers are cyclic.[9][10] Additionally, it follows that there are no Carmichael numbers with exactly two prime divisors.
Discovery
[edit]The first seven Carmichael numbers, from 561 to 8911, were all found by the Czech mathematician Václav Šimerka in 1885[11] (thus preceding not just Carmichael but also Korselt, although Šimerka did not find anything like Korselt's criterion).[12] His work, published in Czech scientific journal Časopis pro pěstování matematiky a fysiky, however, remained unnoticed.
Korselt was the first who observed the basic properties of Carmichael numbers, but he did not give any examples.
That 561 is a Carmichael number can be seen with Korselt's criterion. The first seven Carmichael numbers are Template:OEIS:
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle ~~561 = 3 \cdot 11 \cdot 17 \qquad (2 \mid ~~560;\quad 10 \mid ~~560;\quad 16 \mid ~~560)}
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1105 = 5 \cdot 13 \cdot 17 \qquad (4 \mid 1104;\quad 12 \mid 1104;\quad 16 \mid 1104)}
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1729 = 7 \cdot 13 \cdot 19 \qquad (6 \mid 1728;\quad 12 \mid 1728;\quad 18 \mid 1728)}
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2465 = 5 \cdot 17 \cdot 29 \qquad (4 \mid 2464;\quad 16 \mid 2464;\quad 28 \mid 2464)}
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2821 = 7 \cdot 13 \cdot 31 \qquad (6 \mid 2820;\quad 12 \mid 2820;\quad 30 \mid 2820)}
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 6601 = 7 \cdot 23 \cdot 41 \qquad (6 \mid 6600;\quad 22 \mid 6600;\quad 40 \mid 6600)}
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 8911 = 7 \cdot 19 \cdot 67 \qquad (6 \mid 8910;\quad 18 \mid 8910;\quad 66 \mid 8910).}
In 1910, Carmichael himself[13] also published the smallest such number, 561, and the numbers were later named after him.
Jack Chernick[14] proved a theorem in 1939 which can be used to construct a subset of Carmichael numbers. The number Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (6k + 1)(12k + 1)(18k + 1)} is a Carmichael number if its three factors are all prime. Whether this formula produces an infinite quantity of Carmichael numbers is an open question (though it is implied by Dickson's conjecture).
Paul Erdős heuristically argued there should be infinitely many Carmichael numbers. In 1994 W. R. (Red) Alford, Andrew Granville and Carl Pomerance used a bound on Olson's constant to show that there really do exist infinitely many Carmichael numbers. Specifically, they showed that for sufficiently large Template:Tmath, there are at least Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^{2/7}} Carmichael numbers between 1 and Template:Tmath.[3]
Thomas Wright proved that if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} are relatively prime, then there are infinitely many Carmichael numbers in the arithmetic progression Template:Tmath, where Template:Tmath.[15]
Löh and Niebuhr in 1992 found some very large Carmichael numbers, including one with 1101518 factors and over 16 million digits. This has been improved to 10333229505 prime factors and 295486761787 digits,[16] so the largest known Carmichael number is much greater than the largest known prime.
Properties
[edit]Factorizations
[edit]Carmichael numbers have at least three prime factors. The first Carmichael numbers with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k = 3, 4, 5, \ldots} prime factors are Template:OEIS:
| k | |
|---|---|
| 3 | Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 561 = 3 \cdot 11 \cdot 17\,} |
| 4 | Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 41041 = 7 \cdot 11 \cdot 13 \cdot 41\,} |
| 5 | Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 825265 = 5 \cdot 7 \cdot 17 \cdot 19 \cdot 73\,} |
| 6 | Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 321197185 = 5 \cdot 19 \cdot 23 \cdot 29 \cdot 37 \cdot 137\,} |
| 7 | Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 5394826801 = 7 \cdot 13 \cdot 17 \cdot 23 \cdot 31 \cdot 67 \cdot 73\,} |
| 8 | Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 232250619601 = 7 \cdot 11 \cdot 13 \cdot 17 \cdot 31 \cdot 37 \cdot 73 \cdot 163\,} |
| 9 | Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 9746347772161 = 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 31 \cdot 37 \cdot 41 \cdot 641\,} |
The first Carmichael numbers with 4 prime factors are Template:OEIS:
| i | |
|---|---|
| 1 | Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 41041 = 7 \cdot 11 \cdot 13 \cdot 41\,} |
| 2 | Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 62745 = 3 \cdot 5 \cdot 47 \cdot 89\,} |
| 3 | Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 63973 = 7 \cdot 13 \cdot 19 \cdot 37\,} |
| 4 | Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 75361 = 11 \cdot 13 \cdot 17 \cdot 31\,} |
| 5 | Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 101101 = 7 \cdot 11 \cdot 13 \cdot 101\,} |
| 6 | Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 126217 = 7 \cdot 13 \cdot 19 \cdot 73\,} |
| 7 | Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 172081 = 7 \cdot 13 \cdot 31 \cdot 61\,} |
| 8 | Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 188461 = 7 \cdot 13 \cdot 19 \cdot 109\,} |
| 9 | Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 278545 = 5 \cdot 17 \cdot 29 \cdot 113\,} |
| 10 | Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 340561 = 13 \cdot 17 \cdot 23 \cdot 67\,} |
The second Carmichael number (1105) can be expressed as the sum of two squares in more ways than any smaller number. The third Carmichael number (1729) is the Hardy-Ramanujan Number: the smallest number that can be expressed as the sum of two cubes (of positive numbers) in two different ways.
Distribution
[edit]Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C(X)} denote the number of Carmichael numbers less than or equal to Template:Tmath. The distribution of Carmichael numbers by powers of 10 Template:OEIS:[8]
| Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C(10^n)} | 0 | 0 | 1 | 7 | 16 | 43 | 105 | 255 | 646 | 1547 | 3605 | 8241 | 19279 | 44706 | 105212 | 246683 | 585355 | 1401644 | 3381806 | 8220777 | 20138200 |
In 1953, Knödel proved the upper bound:
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C(X) < X \exp\left({-k_1 \left( \log X \log \log X\right)^\frac{1}{2}}\right)}
for some constant Template:Tmath.
In 1956, Erdős improved the bound to
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C(X) < X \exp\left(\frac{-k_2 \log X \log \log \log X}{\log \log X}\right)}
for some constant Template:Tmath.[17] He further gave a heuristic argument suggesting that this upper bound should be close to the true growth rate of Template:Tmath.
In the other direction, Alford, Granville and Pomerance proved in 1994[3] that for sufficiently large X,
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C(X) > X^\frac{2}{7}.}
In 2005, this bound was further improved by Harman[18] to
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C(X) > X^{0.332}}
who subsequently improved the exponent to Template:Tmath.[19]
Regarding the asymptotic distribution of Carmichael numbers, there have been several conjectures. In 1956, Erdős[17] conjectured that there were Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X^{1-o(1)}} Carmichael numbers for X sufficiently large. In 1981, Pomerance[20] sharpened Erdős' heuristic arguments to conjecture that there are at least
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X \cdot L(X)^{-1 + o(1)} }
Carmichael numbers up to Template:Tmath, where Template:Tmath.
However, inside current computational ranges (such as the count of Carmichael numbers performed by GoutierTemplate:OEIS up to 1022), these conjectures are not yet borne out by the data; empirically, the exponent is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C(X) \approx X^{0.35}} for the highest available count (C(X) = 49679870 for X = 1022).
In 2021, Daniel Larsen proved an analogue of Bertrand's postulate for Carmichael numbers first conjectured by Alford, Granville, and Pomerance in 1994.[4][21] Using techniques developed by Yitang Zhang and James Maynard to establish results concerning small gaps between primes, his work yielded the much stronger statement that, for any Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \delta>0} and sufficiently large Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} in terms of Template:Tmath, there will always be at least
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \exp{\left(\frac{\log{x}}{(\log \log{x})^{2+\delta}}\right)} }
Carmichael numbers between Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} and
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x+\frac{x}{(\log{x})^{\frac{1}{2+\delta}}}.}
Generalizations
[edit]The notion of Carmichael number generalizes to a Carmichael ideal in any number field Template:Tmath. For any nonzero prime ideal Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathfrak p} in Template:Tmath, we have Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha^{{\rm N}(\mathfrak p)} \equiv \alpha \bmod {\mathfrak p}} for all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} in Template:Tmath, where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {\rm N}(\mathfrak p)} is the norm of the ideal Template:Tmath. (This generalizes Fermat's little theorem, that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m^p \equiv m \bmod p} for all integers Template:Tmath when Template:Tmath is prime.) Call a nonzero ideal Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathfrak a} in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {\mathcal O}_K} Carmichael if it is not a prime ideal and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha^{{\rm N}(\mathfrak a)} \equiv \alpha \bmod {\mathfrak a}} for all Template:Tmath, where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {\rm N}(\mathfrak a)} is the norm of the ideal Template:Tmath. When Template:Tmath is Template:Tmath, the ideal Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathfrak a} is principal, and if we let Template:Tmath be its positive generator then the ideal Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathfrak a = (a)} is Carmichael exactly when Template:Tmath is a Carmichael number in the usual sense.
When Template:Tmath is larger than the rationals it is easy to write down Carmichael ideals in Template:Tmath: for any prime number Template:Tmath that splits completely in Template:Tmath, the principal ideal Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p{\mathcal O}_K} is a Carmichael ideal. Since infinitely many prime numbers split completely in any number field, there are infinitely many Carmichael ideals in Template:Tmath. For example, if Template:Tmath is any prime number that is 1 mod 4, the ideal Template:Tmath in the Gaussian integers Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb Z[i]} is a Carmichael ideal.
Both prime and Carmichael numbers satisfy the following equality:
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gcd \left(\sum_{x=1}^{n-1} x^{n-1}, n\right) = 1.}
Lucas–Carmichael number
[edit]A positive composite integer Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} is a Lucas–Carmichael number if and only if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} is square-free, and for all prime divisors Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} of Template:Tmath, it is true that Template:Tmath. The first Lucas–Carmichael numbers are:
- 399, 935, 2015, 2915, 4991, 5719, 7055, 8855, 12719, 18095, 20705, 20999, 22847, 29315, 31535, 46079, 51359, 60059, 63503, 67199, 73535, 76751, 80189, 81719, 88559, 90287, ... Template:OEIS
Quasi–Carmichael number
[edit]Quasi–Carmichael numbers are squarefree composite numbers Template:Tmath with the property that for every prime factor Template:Tmath of Template:Tmath, Template:Tmath divides Template:Tmath positively with Template:Tmath being any integer besides 0. If Template:Tmath, these are Carmichael numbers, and if Template:Tmath, these are Lucas–Carmichael numbers. The first Quasi–Carmichael numbers are:
- 35, 77, 143, 165, 187, 209, 221, 231, 247, 273, 299, 323, 357, 391, 399, 437, 493, 527, 561, 589, 598, 713, 715, 899, 935, 943, 989, 1015, 1073, 1105, 1147, 1189, 1247, 1271, 1295, 1333, 1517, 1537, 1547, 1591, 1595, 1705, 1729, ... Template:OEIS
Knödel number
[edit]An n-Knödel number for a given positive integer n is a composite number m with the property that each Template:Tmath coprime to m satisfies Template:Tmath. The Template:Tmath case are Carmichael numbers.
Higher-order Carmichael numbers
[edit]Carmichael numbers can be generalized using concepts of abstract algebra.
The above definition states that a composite integer n is Carmichael precisely when the nth-power-raising function pn from the ring Zn of integers modulo n to itself is the identity function. The identity is the only Zn-algebra endomorphism on Zn so we can restate the definition as asking that pn be an algebra endomorphism of Zn. As above, pn satisfies the same property whenever n is prime.
The nth-power-raising function pn is also defined on any Zn-algebra A. A theorem states that n is prime if and only if all such functions pn are algebra endomorphisms.
In-between these two conditions lies the definition of Carmichael number of order m for any positive integer m as any composite number n such that pn is an endomorphism on every Zn-algebra that can be generated as Zn-module by m elements. Carmichael numbers of order 1 are just the ordinary Carmichael numbers.
An order-2 Carmichael number
[edit]According to Howe, 17 · 31 · 41 · 43 · 89 · 97 · 167 · 331 is an order 2 Carmichael number. This product is equal to 443372888629441.[22]
Properties
[edit]Korselt's criterion can be generalized to higher-order Carmichael numbers, as shown by Howe.
A heuristic argument, given in the same paper, appears to suggest that there are infinitely many Carmichael numbers of order m, for any m. However, not a single Carmichael number of order 3 or above is known.
Notes
[edit]- ↑ Riesel, Hans (1994). Prime Numbers and Computer Methods for Factorization. Progress in Mathematics. 126 (second ed.). Boston, MA: Birkhäuser. ISBN 978-0-8176-3743-9. Zbl 0821.11001.
- ↑ Crandall, Richard; Pomerance, Carl (2005). Prime Numbers: A Computational Perspective (second ed.). New York: Springer. pp. 133–134. ISBN 978-0387-25282-7.
- ↑ 3.0 3.1 3.2 W. R. Alford; Andrew Granville; Carl Pomerance (1994). "There are Infinitely Many Carmichael Numbers" (PDF). Annals of Mathematics. 140 (3): 703–722. doi:10.2307/2118576. JSTOR 2118576. Archived (PDF) from the original on 2005-03-04.
- ↑ 4.0 4.1 Cepelewicz, Jordana (13 October 2022). "Teenager Solves Stubborn Riddle About Prime Number Look-Alikes". Quanta Magazine. Retrieved 13 October 2022.
- ↑ Ore, Øystein (1948). Number Theory and Its History. New York: McGraw-Hill. pp. 331–332 – via Internet Archive.
- ↑ D. H. Lehmer (1976). "Strong Carmichael numbers". J. Austral. Math. Soc. 21 (4): 508–510. doi:10.1017/s1446788700019364. Lehmer proved that no Carmichael number is an Euler-Jacobi pseudoprime to every base relatively prime to it. He used the term strong pseudoprime, but the terminology has changed since then. Strong pseudoprimes are a subset of Euler-Jacobi pseudoprimes. Therefore, no Carmichael number is a strong pseudoprime to every base relatively prime to it.
- ↑ F. Arnault (August 1995). "Constructing Carmichael Numbers Which Are Strong Pseudoprimes to Several Bases". Journal of Symbolic Computation. 20 (2): 151–161. doi:10.1006/jsco.1995.1042.
- ↑ 8.0 8.1 Pinch, Richard (December 2007). Anne-Maria Ernvall-Hytönen (ed.). The Carmichael numbers up to 1021 (PDF). Proceedings of Conference on Algorithmic Number Theory. 46. Turku, Finland: Turku Centre for Computer Science. pp. 129–131. Retrieved 2017-06-26.
- ↑ Carmichael Multiples of Odd Cyclic Numbers "Any divisor of a Carmichael number must be an odd cyclic number"
- ↑ Proof sketch: If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} is square-free but not cyclic, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_i \mid p_j - 1} for two prime factors Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_i} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_j} of Template:Tmath. But if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} satisfies Korselt then Template:Tmath, so by transitivity of the "divides" relation Template:Tmath. But Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_i} is also a factor of Template:Tmath, a contradiction.
- ↑ Šimerka, Václav (1885). "Zbytky z arithmetické posloupnosti" [On the remainders of an arithmetic progression]. Časopis pro pěstování mathematiky a fysiky. 14 (5): 221–225. doi:10.21136/CPMF.1885.122245.
- ↑ Lemmermeyer, F. (2013). "Václav Šimerka: quadratic forms and factorization". LMS Journal of Computation and Mathematics. 16: 118–129. doi:10.1112/S1461157013000065.
- ↑ R. D. Carmichael (1910). "Note on a new number theory function". Bulletin of the American Mathematical Society. 16 (5): 232–238. doi:10.1090/s0002-9904-1910-01892-9.
- ↑ Chernick, J. (1939). "On Fermat's simple theorem" (PDF). Bull. Amer. Math. Soc. 45 (4): 269–274. doi:10.1090/S0002-9904-1939-06953-X.
- ↑ Thomas Wright (2013). "Infinitely many Carmichael Numbers in Arithmetic Progressions". Bull. London Math. Soc. 45 (5): 943–952. arXiv:1212.5850. doi:10.1112/blms/bdt013. S2CID 119126065.
- ↑ W.R. Alford; et al. (2014). "Constructing Carmichael numbers through improved subset-product algorithms". Math. Comp. 83 (286): 899–915. arXiv:1203.6664. doi:10.1090/S0025-5718-2013-02737-8. S2CID 35535110.
- ↑ 17.0 17.1 Erdős, P. (2022). "On pseudoprimes and Carmichael numbers" (PDF). Publ. Math. Debrecen. 4 (3–4): 201–206. doi:10.5486/PMD.1956.4.3-4.16. MR 0079031. S2CID 253789521 Check
|s2cid=value (help). Archived (PDF) from the original on 2011-06-11. - ↑ Glyn Harman (2005). "On the number of Carmichael numbers up to x". Bulletin of the London Mathematical Society. 37 (5): 641–650. doi:10.1112/S0024609305004686. S2CID 124405969.
- ↑ Harman, Glyn (2008). "Watt's mean value theorem and Carmichael numbers". International Journal of Number Theory. 4 (2): 241–248. doi:10.1142/S1793042108001316. MR 2404800.
- ↑ Pomerance, C. (1981). "On the distribution of pseudoprimes". Math. Comp. 37 (156): 587–593. doi:10.1090/s0025-5718-1981-0628717-0. JSTOR 2007448.
- ↑ Larsen, Daniel (20 July 2022). "Bertrand's Postulate for Carmichael Numbers". International Mathematics Research Notices. 2023 (15): 13072–13098. arXiv:2111.06963. doi:10.1093/imrn/rnac203.
- ↑ Everett W. Howe (October 2000). "Higher-order Carmichael numbers". Mathematics of Computation. 69 (232): 1711–1719. arXiv:math.NT/9812089. Bibcode:2000MaCom..69.1711H. doi:10.1090/s0025-5718-00-01225-4. JSTOR 2585091. S2CID 6102830.
References
[edit]- Carmichael, R. D. (1910). "Note on a new number theory function". Bulletin of the American Mathematical Society. 16 (5): 232–238. doi:10.1090/s0002-9904-1910-01892-9.
- Carmichael, R. D. (1912). "On composite numbers P which satisfy the Fermat congruence Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a^{P-1}\equiv 1\bmod P} ". American Mathematical Monthly. 19 (2): 22–27. doi:10.2307/2972687. JSTOR 2972687.
- Chernick, J. (1939). "On Fermat's simple theorem" (PDF). Bull. Amer. Math. Soc. 45 (4): 269–274. doi:10.1090/S0002-9904-1939-06953-X.
- Korselt, A. R. (1899). "Problème chinois". L'Intermédiaire des Mathématiciens. 6: 142–143.
- Löh, G.; Niebuhr, W. (1996). "A new algorithm for constructing large Carmichael numbers" (PDF). Math. Comp. 65 (214): 823–836. Bibcode:1996MaCom..65..823L. doi:10.1090/S0025-5718-96-00692-8. Archived (PDF) from the original on 2003-04-25.
- Ribenboim, P. (1989). The Book of Prime Number Records. Springer. ISBN 978-0-387-97042-4.
- Šimerka, V. (1885). "Zbytky z arithmetické posloupnosti (On the remainders of an arithmetic progression)". Časopis Pro Pěstování Matematiky a Fysiky. 14 (5): 221–225. doi:10.21136/CPMF.1885.122245.
External links
[edit]- Template:Springer
- Encyclopedia of Mathematics
- Table of Carmichael numbers
- Tables of Carmichael numbers with many prime factors
- Tables of Carmichael numbers below Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 10^{18}}
- Template:MathPages
- Weisstein, Eric W. "Carmichael Number". MathWorld.
- Final Answers Modular Arithmetic