Movatterモバイル変換

[0]ホーム
URL:

Jump to content
WikipediaThe Free Encyclopedia
Search

Carmichael number

From Wikipedia, the free encyclopedia
Composite number in number theory

Innumber theory, aCarmichael number is acomposite number⁠n{\displaystyle n}⁠ which inmodular arithmetic satisfies thecongruence relation:

bn≡b(modn){\displaystyle b^{n}\equiv b{\pmod {n}}}

for all integers⁠b{\displaystyle b}⁠.[1] The relation may also be expressed[2] in the form:

bn−1≡1(modn){\displaystyle b^{n-1}\equiv 1{\pmod {n}}}

for all integersb{\displaystyle b} that arerelatively prime to⁠n{\displaystyle n}⁠. They areinfinite in number.[3]

Robert Daniel Carmichael

They constitute the comparatively rare instances where the strict converse ofFermat's Little Theorem does not hold. This fact precludes the use of that theorem as an absolute test ofprimality.[4]

The Carmichael numbers form the subsetK1 of theKnödel numbers.

The Carmichael numbers were named after the American mathematicianRobert Carmichael byNicolaas 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 ifp{\displaystyle p} is aprime number, then for anyinteger⁠b{\displaystyle b}⁠, the numberbp−b{\displaystyle b^{p}-b} is an integer multiple of⁠p{\displaystyle p}⁠. Carmichael numbers are composite numbers which have the same property. Carmichael numbers are also calledFermat pseudoprimes orabsolute Fermat pseudoprimes. A Carmichael number will pass aFermat primality test to every baseb{\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 thanstrong probable prime tests such as theBaillie–PSW primality test and theMiller–Rabin primality test.

However, no Carmichael number is either anEuler–Jacobi pseudoprime or astrong 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 numberN{\displaystyle N} that is astrong pseudoprime to allprime bases less than 307:

N=p⋅(313(p−1)+1)⋅(353(p−1)+1){\displaystyle N=p\cdot (313(p-1)+1)\cdot (353(p-1)+1)}

where

p={\displaystyle p=} 2 9674495668 6855105501 5417464290 5332730771 9917998530 4335099507 5531276838 7531717701 9959423859 6428121188 0336647542 1834556249 3168782883

is a 131-digit prime.p{\displaystyle p} is the smallest prime factor of⁠N{\displaystyle N}⁠, so this Carmichael number is also a (not necessarily strong) pseudoprime to all bases less than⁠p{\displaystyle p}⁠.

As numbers become larger, Carmichael numbers become increasingly rare. For example, there are 20,138,200 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 byKorselt's criterion.

Theorem (A. Korselt 1899): A positive composite integern{\displaystyle n} is a Carmichael number if and only ifn{\displaystyle n} issquare-free, and for allprime divisorsp{\displaystyle p} of⁠n{\displaystyle n}⁠, it is true that⁠p−1∣n−1{\displaystyle p-1\mid n-1}⁠.

It follows from this theorem that all Carmichael numbers areodd, since anyeven composite number that is square-free (and hence has only one prime factor of two) will have at least one odd prime factor, and thusp−1∣n−1{\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−1{\displaystyle -1} is aFermat witness for any even composite number.)From the criterion it also follows that Carmichael numbers arecyclic.[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 mathematicianVá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.

Václav Šimerka listed the first seven Carmichael numbers

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. Indeed,561=3⋅11⋅17{\displaystyle 561=3\cdot 11\cdot 17} is square-free and⁠2∣560{\displaystyle 2\mid 560}⁠,10∣560{\displaystyle 10\mid 560} and⁠16∣560{\displaystyle 16\mid 560}⁠.The next six Carmichael numbers are (sequenceA002997 in theOEIS):

1105=5⋅13⋅17(4∣1104;12∣1104;16∣1104){\displaystyle 1105=5\cdot 13\cdot 17\qquad (4\mid 1104;\quad 12\mid 1104;\quad 16\mid 1104)}
1729=7⋅13⋅19(6∣1728;12∣1728;18∣1728){\displaystyle 1729=7\cdot 13\cdot 19\qquad (6\mid 1728;\quad 12\mid 1728;\quad 18\mid 1728)}
2465=5⋅17⋅29(4∣2464;16∣2464;28∣2464){\displaystyle 2465=5\cdot 17\cdot 29\qquad (4\mid 2464;\quad 16\mid 2464;\quad 28\mid 2464)}
2821=7⋅13⋅31(6∣2820;12∣2820;30∣2820){\displaystyle 2821=7\cdot 13\cdot 31\qquad (6\mid 2820;\quad 12\mid 2820;\quad 30\mid 2820)}
6601=7⋅23⋅41(6∣6600;22∣6600;40∣6600){\displaystyle 6601=7\cdot 23\cdot 41\qquad (6\mid 6600;\quad 22\mid 6600;\quad 40\mid 6600)}
8911=7⋅19⋅67(6∣8910;18∣8910;66∣8910).{\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 asubset of Carmichael numbers. The number(6k+1)(12k+1)(18k+1){\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 byDickson's conjecture).

Paul Erdős heuristically argued there should be infinitely many Carmichael numbers. In 1994W. R. (Red) Alford,Andrew Granville andCarl Pomerance used a bound onOlson's constant to show that there really do exist infinitely many Carmichael numbers. Specifically, they showed that for sufficiently largen{\displaystyle n}, there are at leastn2/7{\displaystyle n^{2/7}} Carmichael numbers between 1 and⁠n{\displaystyle n}⁠.[3]

Thomas Wright proved that ifa{\displaystyle a} andm{\displaystyle m} are relatively prime,then there are infinitely many Carmichael numbers in thearithmetic progression⁠a+k⋅m{\displaystyle a+k\cdot m}⁠,where⁠k=1,2,…{\displaystyle k=1,2,\ldots }⁠.[15]

Löh and Niebuhr in 1992 found some very large Carmichael numbers, including one with 1,101,518 factors and over 16 million digits.This has been improved to 10,333,229,505 prime factors and 295,486,761,787 digits,[16] so the largest known Carmichael number is much greater than thelargest known prime.

Properties

[edit]

Factorizations

[edit]

Carmichael numbers have at least three prime factors. The first Carmichael numbers withk=3,4,5,…{\displaystyle k=3,4,5,\ldots } prime factors are (sequenceA006931 in theOEIS):

k 
3561=3⋅11⋅17{\displaystyle 561=3\cdot 11\cdot 17\,}
441041=7⋅11⋅13⋅41{\displaystyle 41041=7\cdot 11\cdot 13\cdot 41\,}
5825265=5⋅7⋅17⋅19⋅73{\displaystyle 825265=5\cdot 7\cdot 17\cdot 19\cdot 73\,}
6321197185=5⋅19⋅23⋅29⋅37⋅137{\displaystyle 321197185=5\cdot 19\cdot 23\cdot 29\cdot 37\cdot 137\,}
75394826801=7⋅13⋅17⋅23⋅31⋅67⋅73{\displaystyle 5394826801=7\cdot 13\cdot 17\cdot 23\cdot 31\cdot 67\cdot 73\,}
8232250619601=7⋅11⋅13⋅17⋅31⋅37⋅73⋅163{\displaystyle 232250619601=7\cdot 11\cdot 13\cdot 17\cdot 31\cdot 37\cdot 73\cdot 163\,}
99746347772161=7⋅11⋅13⋅17⋅19⋅31⋅37⋅41⋅641{\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 (sequenceA074379 in theOEIS):

i 
141041=7⋅11⋅13⋅41{\displaystyle 41041=7\cdot 11\cdot 13\cdot 41\,}
262745=3⋅5⋅47⋅89{\displaystyle 62745=3\cdot 5\cdot 47\cdot 89\,}
363973=7⋅13⋅19⋅37{\displaystyle 63973=7\cdot 13\cdot 19\cdot 37\,}
475361=11⋅13⋅17⋅31{\displaystyle 75361=11\cdot 13\cdot 17\cdot 31\,}
5101101=7⋅11⋅13⋅101{\displaystyle 101101=7\cdot 11\cdot 13\cdot 101\,}
6126217=7⋅13⋅19⋅73{\displaystyle 126217=7\cdot 13\cdot 19\cdot 73\,}
7172081=7⋅13⋅31⋅61{\displaystyle 172081=7\cdot 13\cdot 31\cdot 61\,}
8188461=7⋅13⋅19⋅109{\displaystyle 188461=7\cdot 13\cdot 19\cdot 109\,}
9278545=5⋅17⋅29⋅113{\displaystyle 278545=5\cdot 17\cdot 29\cdot 113\,}
10340561=13⋅17⋅23⋅67{\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 theHardy-Ramanujan Number: the smallest number that can be expressed as thesum of two cubes (of positive numbers) in two different ways.

Distribution

[edit]

LetC(X){\displaystyle C(X)} denote the number of Carmichael numbers less than or equal to⁠X{\displaystyle X}⁠. The distribution of Carmichael numbers by powers of 10 (sequenceA055553 in theOEIS):[8]

n{\displaystyle n}123456789101112131415161718192021
C(10n){\displaystyle C(10^{n})}00171643105255646154736058241192794470610521224668358535514016443381806822077720138200

In 1953,Knödel proved theupper bound:

C(X)<Xexp⁡(−k1(log⁡Xlog⁡log⁡X)12){\displaystyle C(X)<X\exp \left({-k_{1}\left(\log X\log \log X\right)^{\frac {1}{2}}}\right)}

for some constant⁠k1{\displaystyle k_{1}}⁠.

In 1956, Erdős improved the bound to

C(X)<Xexp⁡(−k2log⁡Xlog⁡log⁡log⁡Xlog⁡log⁡X){\displaystyle C(X)<X\exp \left({\frac {-k_{2}\log X\log \log \log X}{\log \log X}}\right)}

for some constant⁠k2{\displaystyle k_{2}}⁠.[17] He further gave aheuristic argument suggesting that this upper bound should be close to the true growth rate of⁠C(X){\displaystyle C(X)}⁠.

In the other direction,Alford,Granville andPomerance proved in 1994[3] that forsufficiently largeX,

C(X)>X27.{\displaystyle C(X)>X^{\frac {2}{7}}.}

In 2005, this bound was further improved byHarman[18] to

C(X)>X0.332{\displaystyle C(X)>X^{0.332}}

who subsequently improved the exponent to⁠0.7039⋅0.4736=0.33336704>1/3{\displaystyle 0.7039\cdot 0.4736=0.33336704>1/3}⁠.[19]

Regarding the asymptotic distribution of Carmichael numbers, there have been several conjectures. In 1956, Erdős[17] conjectured that there wereX1−o(1){\displaystyle X^{1-o(1)}} Carmichael numbers forX sufficiently large. In 1981, Pomerance[20] sharpened Erdős' heuristic arguments to conjecture that there are at least

X⋅L(X)−1+o(1){\displaystyle X\cdot L(X)^{-1+o(1)}}

Carmichael numbers up to⁠X{\displaystyle X}⁠, where⁠L(x)=exp⁡(log⁡xlog⁡log⁡log⁡xlog⁡log⁡x){\displaystyle L(x)=\exp {\left({\frac {\log x\log \log \log x}{\log \log x}}\right)}}⁠.

However, inside current computational ranges (such as the count of Carmichael numbers performed by Goutier(sequenceA055553 in theOEIS) up to 1022), these conjectures are not yet borne out by the data; empirically, the exponent isC(X)≈X0.35{\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 ofBertrand's postulate for Carmichael numbers first conjectured by Alford, Granville, and Pomerance in 1994.[4][21] Using techniques developed byYitang Zhang andJames Maynard to establish results concerningsmall gaps between primes, his work yielded the much stronger statement that, for anyδ>0{\displaystyle \delta >0} and sufficiently largex{\displaystyle x} in terms ofδ{\displaystyle \delta }, there will always be at least

exp⁡(log⁡x(log⁡log⁡x)2+δ){\displaystyle \exp {\left({\frac {\log {x}}{(\log \log {x})^{2+\delta }}}\right)}}

Carmichael numbers betweenx{\displaystyle x} and

x+x(log⁡x)12+δ.{\displaystyle x+{\frac {x}{(\log {x})^{\frac {1}{2+\delta }}}}.}

Generalizations

[edit]

The notion of Carmichael number generalizes to a Carmichael ideal in anynumber field⁠K{\displaystyle K}⁠. For any nonzeroprime idealp{\displaystyle {\mathfrak {p}}} in⁠OK{\displaystyle {\mathcal {O}}_{K}}⁠, we haveαN(p)≡αmodp{\displaystyle \alpha ^{{\rm {N}}({\mathfrak {p}})}\equiv \alpha {\bmod {\mathfrak {p}}}} for allα{\displaystyle \alpha } in⁠OK{\displaystyle {\mathcal {O}}_{K}}⁠, whereN(p){\displaystyle {\rm {N}}({\mathfrak {p}})} is the norm of theideal⁠p{\displaystyle {\mathfrak {p}}}⁠. (This generalizes Fermat's little theorem, thatmp≡mmodp{\displaystyle m^{p}\equiv m{\bmod {p}}} for all integers⁠m{\displaystyle m}⁠ when⁠p{\displaystyle p}⁠ is prime.) Call a nonzero ideala{\displaystyle {\mathfrak {a}}} inOK{\displaystyle {\mathcal {O}}_{K}} Carmichael if it is not a prime ideal andαN(a)≡αmoda{\displaystyle \alpha ^{{\rm {N}}({\mathfrak {a}})}\equiv \alpha {\bmod {\mathfrak {a}}}} for all⁠α∈OK{\displaystyle \alpha \in {\mathcal {O}}_{K}}⁠, whereN(a){\displaystyle {\rm {N}}({\mathfrak {a}})} is the norm of the ideal⁠a{\displaystyle {\mathfrak {a}}}⁠. When⁠K{\displaystyle K}⁠ is⁠Q{\displaystyle \mathbf {Q} }⁠, the ideala{\displaystyle {\mathfrak {a}}} isprincipal, and if we let⁠a{\displaystyle a}⁠ be its positive generator then the ideala=(a){\displaystyle {\mathfrak {a}}=(a)} is Carmichael exactly when⁠a{\displaystyle a}⁠ is a Carmichael number in the usual sense.

When⁠K{\displaystyle K}⁠ is larger than therationals it is easy to write down Carmichael ideals in⁠OK{\displaystyle {\mathcal {O}}_{K}}⁠: for any prime number⁠p{\displaystyle p}⁠ that splits completely in⁠K{\displaystyle K}⁠, the principal idealpOK{\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⁠OK{\displaystyle {\mathcal {O}}_{K}}⁠. For example, if⁠p{\displaystyle p}⁠ is any prime number that is 1 mod 4, the ideal⁠(p){\displaystyle (p)}⁠ in theGaussian integersZ[i]{\displaystyle \mathbb {Z} [i]} is a Carmichael ideal.

Both prime and Carmichael numbers satisfy the following equality:

gcd(∑x=1n−1xn−1,n)=1.{\displaystyle \gcd \left(\sum _{x=1}^{n-1}x^{n-1},n\right)=1.}

Lucas–Carmichael number

[edit]
Main article:Lucas–Carmichael number

A positive composite integern{\displaystyle n} is a Lucas–Carmichael number if and only ifn{\displaystyle n} issquare-free, and for allprime divisorsp{\displaystyle p} of⁠n{\displaystyle n}⁠, it is true that⁠p+1∣n+1{\displaystyle p+1\mid n+1}⁠. 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, ... (sequenceA006972 in theOEIS)

Quasi–Carmichael number

[edit]

Quasi–Carmichael numbers are squarefree composite numbers⁠n{\displaystyle n}⁠ with the property that for every prime factor⁠p{\displaystyle p}⁠ of⁠n{\displaystyle n}⁠,⁠p+b{\displaystyle p+b}⁠ divides⁠n+b{\displaystyle n+b}⁠ positively with⁠b{\displaystyle b}⁠ being any integer besides 0. If⁠b=−1{\displaystyle b=-1}⁠, these are Carmichael numbers, and if⁠b=1{\displaystyle b=1}⁠, 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, ... (sequenceA257750 in theOEIS)

Knödel number

[edit]
Main article:Knödel number

Ann-Knödel number for a givenpositive integern is acomposite numberm with the property that each⁠i<m{\displaystyle i<m}⁠coprime tom satisfies⁠im−n≡1(modm){\displaystyle i^{m-n}\equiv 1{\pmod {m}}}⁠. The⁠n=1{\displaystyle n=1}⁠ case are Carmichael numbers.

Higher-order Carmichael numbers

[edit]

Carmichael numbers can be generalized using concepts ofabstract algebra.

The above definition states that a composite integern is Carmichaelprecisely when thenth-power-raising functionpn from theringZn of integers modulon to itself is the identity function. The identity is the onlyZn-algebraendomorphism onZn so we can restate the definition as asking thatpn be an algebra endomorphism ofZn.As above,pn satisfies the same property whenevern is prime.

Thenth-power-raising functionpn is also defined on anyZn-algebraA. A theorem states thatn is prime if and only if all such functionspn are algebra endomorphisms.

In-between these two conditions lies the definition ofCarmichael number of order m for any positive integerm as any composite numbern such thatpn is an endomorphism on everyZn-algebra that can be generated asZn-module bym 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 443,372,888,629,441.[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 orderm, for anym. However, not a single Carmichael number of order 3 or above is known.

Notes

[edit]
  1. ^Riesel, Hans (1994).Prime Numbers and Computer Methods for Factorization. Progress in Mathematics. Vol. 126 (second ed.). Boston, MA: Birkhäuser.ISBN 978-0-8176-3743-9.Zbl 0821.11001.
  2. ^Crandall, Richard;Pomerance, Carl (2005).Prime Numbers: A Computational Perspective (second ed.). New York: Springer. pp. 133–134.ISBN 978-0387-25282-7.
  3. ^abcW. 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. ^abCepelewicz, Jordana (13 October 2022)."Teenager Solves Stubborn Riddle About Prime Number Look-Alikes".Quanta Magazine. Retrieved13 October 2022.
  5. ^Ore, Øystein (1948).Number Theory and Its History. New York: McGraw-Hill. pp. 331–332 – viaInternet Archive.
  6. ^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 termstrong 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.
  7. ^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. ^abPinch, Richard (December 2007). Anne-Maria Ernvall-Hytönen (ed.).The Carmichael numbers up to 1021(PDF). Proceedings of Conference on Algorithmic Number Theory. Vol. 46. Turku, Finland: Turku Centre for Computer Science. pp. 129–131. Retrieved2017-06-26.
  9. ^Carmichael Multiples of Odd Cyclic Numbers "Any divisor of a Carmichael number must be an odd cyclic number"
  10. ^Proof sketch: Ifn{\displaystyle n} is square-free but not cyclic,pi∣pj−1{\displaystyle p_{i}\mid p_{j}-1} for two prime factorspi{\displaystyle p_{i}} andpj{\displaystyle p_{j}} ofn{\displaystyle n}. But ifn{\displaystyle n} satisfies Korselt then⁠pj−1∣n−1{\displaystyle p_{j}-1\mid n-1}⁠, so by transitivity of the "divides" relation⁠pi∣n−1{\displaystyle p_{i}\mid n-1}⁠. Butpi{\displaystyle p_{i}} is also a factor of⁠n{\displaystyle n}⁠, a contradiction.
  11. ^Š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.
  12. ^Lemmermeyer, F. (2013)."Václav Šimerka: quadratic forms and factorization".LMS Journal of Computation and Mathematics.16:118–129.doi:10.1112/S1461157013000065.
  13. ^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.
  14. ^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.
  15. ^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.
  16. ^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. ^abErdő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.Archived(PDF) from the original on 2011-06-11.
  18. ^Glyn Harman (2005). "On the number of Carmichael numbers up tox".Bulletin of the London Mathematical Society.37 (5):641–650.doi:10.1112/S0024609305004686.S2CID 124405969.
  19. ^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.
  20. ^Pomerance, C. (1981)."On the distribution of pseudoprimes".Math. Comp.37 (156):587–593.doi:10.1090/s0025-5718-1981-0628717-0.JSTOR 2007448.
  21. ^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.
  22. ^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]

External links

[edit]
Classes ofnatural numbers
Powers and related numbers
Of the forma × 2b ± 1
Other polynomial numbers
Recursively defined numbers
Possessing a specific set of other numbers
Expressible via specific sums
2-dimensional
centered
non-centered
3-dimensional
centered
non-centered
pyramidal
4-dimensional
non-centered
Combinatorial numbers
Divisor functions
Prime omega functions
Euler's totient function
Aliquot sequences
Primorial
Otherprime factor ordivisor related numbers
Numeral system-dependent numbers
Arithmetic functions
anddynamics
Digit sum
Digit product
Coding-related
Other
P-adic numbers-related
Digit-composition related
Digit-permutation related
Divisor-related
Other
Generated via asieve
Sorting related
Graphemics related
Retrieved from "https://en.wikipedia.org/w/index.php?title=Carmichael_number&oldid=1328580842"
Categories:
Hidden categories:
[8]ページ先頭
©2009-2026 Movatter.jp