“Carmichael number”的意思、由来-开放百科全书

In number theory, a Carmichael number is a composite number

which satisfies the modular arithmetic congruence relation:

Overview

Fermat's little theorem states that if p is a prime number, then for any integer b, the number b^p − b is an integer multiple of p. Carmichael numbers are composite numbers which have this property. Carmichael numbers are also called Fermat pseudoprimes or absolute Fermat pseudoprimes. A Carmichael number will pass a Fermat primality test to every base 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

so, in theory, either an Euler or a strong probable prime test could prove that a Carmichael number is, in fact, composite.

gives a 397-digit Carmichael number

that is a strong pseudoprime to all prime bases less than 307:

is a 131-digit prime.

is the smallest prime factor of

, so this Carmichael number is also a (not necessarily strong) pseudoprime to all bases less than

As numbers become larger, Carmichael numbers become increasingly rare. For example, there are 20,138,200 Carmichael numbers between 1 and 10²¹ (approximately one in 50 trillion (5·10¹³) numbers).^[5]

Korselt's criterion

An alternative and equivalent definition of Carmichael numbers is given by Korselt's criterion.

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

results in an even dividing an odd, a contradiction. (The oddness of Carmichael numbers also follows from the fact that

is a Fermat witness for any even composite number.)

From the criterion it also follows that Carmichael numbers are cyclic.^[6]^[7] Additionally, it follows that there are no Carmichael numbers with exactly two prime factors.

Discovery

Korselt was the first who observed the basic properties of Carmichael numbers, but he did not give any examples. In 1910, Carmichael^[8] found the first and smallest such number, 561, which explains the name "Carmichael number".

That 561 is a Carmichael number can be seen with Korselt's criterion. Indeed,

is square-free and

and

These first seven Carmichael numbers, from 561 to 8911, were all found by the Czech mathematician Václav Šimerka in 1885^[9] (thus preceding not just Carmichael but also Korselt, although Šimerka did not find anything like Korselt's criterion).^[10] His work, however, remained unnoticed.

J. Chernick^[11] proved a theorem in 1939 which can be used to construct a subset of Carmichael numbers. The number

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

Löh and Niebuhr in 1992 found some very large Carmichael numbers, including one with 1,101,518 factors and over 16 million digits.

Properties

Factorizations

Carmichael numbers have at least three positive prime factors. For some fixed R, there are infinitely many Carmichael numbers with exactly R factors; in fact, there are infinitely many such R.^[13]

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

Let

denote the number of Carmichael numbers less than or equal to

. The distribution of Carmichael numbers by powers of 10 {{OEIS|id=A055553}}:^[5]

for some constant

. He further gave a heuristic argument suggesting that this upper bound should be close to the true growth rate of

. The table below gives approximate minimal values for the constant k in the Erdős bound for

as n grows:

In the other direction, Alford, Granville and Pomerance proved in 1994^[12] that for sufficiently large X,

Regarding the asymptotic distribution of Carmichael numbers, there have been several conjectures. In 1956, Erdős^[14] conjectured that there were

Carmichael numbers for X sufficiently large. In 1981, Pomerance^[17] sharpened Erdős' heuristic arguments to conjecture that there are

Carmichael numbers up to X. However, inside current computational ranges (such as the counts of Carmichael numbers performed by Pinch^[5] up to 10²¹), these conjectures are not yet borne out by the data.

Generalizations

The notion of Carmichael number generalizes to a Carmichael ideal in any number field K. For any nonzero prime ideal

, we have

for all

, where

is the norm of the ideal

. (This generalizes Fermat's little theorem, that

for all integers m when p is prime.) Call a nonzero ideal

Carmichael if it is not a prime ideal and

for all

, where

is the norm of the ideal

. When K is

, the ideal

is principal, and if we let a be its positive generator then the ideal

is Carmichael exactly when a is a Carmichael number in the usual sense.

When K is larger than the rationals it is easy to write down Carmichael ideals in

: for any prime number p that splits completely in K, the principal ideal

is a Carmichael ideal. Since infinitely many prime numbers split completely in any number field, there are infinitely many Carmichael ideals in

. For example, if p is any prime number that is 1 mod 4, the ideal (p) in the Gaussian integers Z[i] is a Carmichael ideal.

Higher-order Carmichael numbers

precisely when the nth-power-raising function p_n from the ring Z_n of integers modulo n to itself is the identity function. The identity is the only Z_n-algebra endomorphism on Z_n so we can restate the definition as asking that p_n be an algebra endomorphism of Z_n.

The nth-power-raising function p_n is also defined on any Z_n-algebra A. A theorem states that n is prime if and only if all such functions p_n 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 p_n is an endomorphism on every Z_n-algebra that can be generated as Z_n-module by m elements. Carmichael numbers of order 1 are just the ordinary Carmichael numbers.

An order 2 Carmichael number

According to Howe, 17 · 31 · 41 · 43 · 89 · 97 · 167 · 331 is an order 2 Carmichael number. This product is equal to 443,372,888,629,441.^[18]

Properties

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

1. ^{{cite book | last=Riesel | first=Hans | title=Prime Numbers and Computer Methods for Factorization | publisher=Birkhäuser | location=Boston, MA | edition=second | year=1994 | isbn=978-0-8176-3743-9 | zbl=0821.11001 | series=Progress in Mathematics | volume=126 |author-link=Hans Riesel }}
2. ^{{cite book |last1=Crandall|first1=Richard |last2=Pomerance |first2=Carl |date=2005 |title=Prime Numbers: A Computational Perspective |edition=second |location=New York |publisher=Springer |page=133 |isbn=978-0387-25282-7 |author-link1=Richard Crandall |author-link2=Carl Pomerance }}
3. ^{{cite journal |author=D. H. Lehmer |author-link=Derrick Henry Lehmer |title=Strong Carmichael numbers |journal=J. Austral. Math. Soc. |date=1976 |volume=21 |issue=4 |pages=508–510 |url=http://journals.cambridge.org/article_S1446788700019364 |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.
4. ^{{cite journal|title=Constructing Carmichael Numbers Which Are Strong Pseudoprimes to Several Bases|journal=Journal of Symbolic Computation|date=August 1995|volume=20|issue=2|pages=151–161|author=F. Arnault|url=http://www.sciencedirect.com/science/article/pii/S0747717185710425|doi=10.1006/jsco.1995.1042}}
5. ^¹²{{cite conference |url=http://tucs.fi/publications/attachment.php?fname=G46.pdf |title=The Carmichael numbers up to 10²¹ |last=Pinch |first=Richard |date=December 2007 |editor=Anne-Maria Ernvall-Hytönen |volume=46 |publisher=Turku Centre for Computer Science |pages=129–131 |location=Turku, Finland |conference=Proceedings of Conference on Algorithmic Number Theory |access-date=2017-06-26}}
6. ^Carmichael Multiples of Odd Cyclic Numbers "Any divisor of a Carmichael number must be an odd cyclic number"
7. ^Proof sketch: If

is square-free but not cyclic,

for two prime factors

and

. But if

satisfies Korselt then

, so by transitivity of the "divides" relation

. But

is also a factor of

, a contradiction.
8. ^{{cite journal |author=R. D. Carmichael|title=Note on a new number theory function |journal=Bulletin of the American Mathematical Society |volume=16 |issue=5|year=1910 |pages=232–238 |url=http://www.ams.org/journals/bull/1910-16-05/home.html |doi=10.1090/s0002-9904-1910-01892-9}}
9. ^{{cite journal |author=V. Šimerka|title=Zbytky z arithmetické posloupnosti (On the remainders of an arithmetic progression) |journal=Časopis Pro Pěstování Matematiky a Fysiky |volume=14 |issue=5|year=1885 |pages=221–225 |url=http://dml.cz/handle/10338.dmlcz/122245}}
10. ^{{cite journal |last1=Lemmermeyer |first1=F. |title=Václav Šimerka: quadratic forms and factorization |journal=LMS Journal of Computation and Mathematics |date=2013 |volume=16 |pages=118–129 |doi=10.1112/S1461157013000065 |doi-access=free}}
11. ^{{cite journal |author=Chernick, J. |title=On Fermat's simple theorem |journal=Bull. Amer. Math. Soc. |volume=45 |issue=4 |year=1939 |pages=269–274 |doi=10.1090/S0002-9904-1939-06953-X |url=http://www.ams.org/journals/bull/1939-45-04/S0002-9904-1939-06953-X/S0002-9904-1939-06953-X.pdf}}
12. ^¹{{cite journal |author=W. R. Alford |author2=Andrew Granville |author3=Carl Pomerance |title=There are Infinitely Many Carmichael Numbers |journal=Annals of Mathematics |volume=139 |issue=3 |year=1994 |pages=703–722 |doi=10.2307/2118576 |url=http://www.math.dartmouth.edu/~carlp/PDF/paper95.pdf|jstor=2118576 }}
13. ^{{cite journal |last=Wright |first=Thomas|date=2016-06-01 |title=Factors of Carmichael numbers and a weak k-tuples conjecture |url=http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=10298704 |journal=Journal of the Australian Mathematical Society |volume=100 |issue=3 |pages=421–429 |doi=10.1017/S1446788715000427|access-date=2016-08-13}}
14. ^¹{{cite journal |author=Erdős, P. |year=1956 |title=On pseudoprimes and Carmichael numbers |journal=Publ. Math. Debrecen |volume=4 |pages=201–206 |url=http://www.renyi.hu/~p_erdos/1956-10.pdf |mr=79031 }}
15. ^{{cite journal |author=Glyn Harman |title=On the number of Carmichael numbers up to x |journal=Bulletin of the London Mathematical Society |volume=37 |issue=5 |year=2005 |pages=641–650 |doi=10.1112/S0024609305004686}}
16. ^{{cite journal |last=Harman |first=Glyn |date=2008 |title=Watt's mean value theorem and Carmichael numbers |doi=10.1142/S1793042108001316 |mr=2404800 |journal=International Journal of Number Theory |volume=4 |issue=2 |pages=241–248 }}
17. ^{{cite journal |author=Pomerance, C. |year=1981 |title=On the distribution of pseudoprimes |journal=Math. Comp. |volume=37 |issue=156 |pages=587–593|jstor=2007448 |doi=10.1090/s0025-5718-1981-0628717-0}}
18. ^{{cite journal |author = Everett W. Howe |title=Higher-order Carmichael numbers |journal=Mathematics of Computation |date=October 2000 |volume=69 |issue=232 |pages=1711–1719 |arxiv=math.NT/9812089 |jstor=2585091 |doi=10.1090/s0025-5718-00-01225-4}}

Overview

Korselt's criterion

Discovery

Properties

Factorizations

Distribution

Generalizations

Higher-order Carmichael numbers

An order 2 Carmichael number

Properties

Notes

References

External links