Carmichael number: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Richard Pinch
mNo edit summary
 
(3 intermediate revisions by 2 users not shown)
Line 4: Line 4:
== Properties ==
== Properties ==


*Every Carmichael number is square-free and has at least three different prime factors
*Every Carmichael number is [[square-free integer|square-free]] and has at least three different prime factors
*For every Carmichael number ''c'' it holds that <math>c-1</math> is divisible by <math>p_n - 1</math> for every one of its prime factors <math>p_n</math>.
*For every Carmichael number ''c'' it holds that <math>c-1</math> is divisible by <math>p_n - 1</math> for every one of its prime factors <math>p_n</math>.
*Every absolute [[Euler pseudoprime]] is a Carmichael number.
*Every absolute [[Euler pseudoprime]] is a Carmichael number.
Line 11: Line 11:


[[J. Chernick]] found in 1939 a way to construct Carmichael numbers<ref>J. Chernick, "On Fermat's simple theorem", ''Bull. Amer. Math. Soc.'' '''45''' (1939) 269-274</ref>
[[J. Chernick]] found in 1939 a way to construct Carmichael numbers<ref>J. Chernick, "On Fermat's simple theorem", ''Bull. Amer. Math. Soc.'' '''45''' (1939) 269-274</ref>
<ref>[http://home.att.net/~numericana/answer/modular.htm#carmichael (2003-11-22) Generic Carmichael Numbers]</ref>. If, for a natural number ''n'', the three numbers <math>\scriptstyle 6n+1\ </math>, <math>\scriptstyle 12n+1\ </math> and <math>\scriptstyle 18n+1\ </math> are prime numbers, the product <math>\scriptstyle M_3(n) = (6n+1)\cdot (12n+1)\cdot (18n+1)</math> is a Carmichael number. Equivalent to this is that if <math>\scriptstyle m\ </math>, <math>\scriptstyle 2m-1\ </math> and <math>\scriptstyle 3m-2</math> are prime numbers, then the product <math>\scriptstyle m\cdot (2m-1)\cdot (3m-2)</math> is a Carmichael number.
<ref>[http://home.att.net/~numericana/answer/modular.htm#carmichael (2003-11-22) Generic Carmichael Numbers]</ref>. If, for a natural number ''n'', the three numbers <math>\scriptstyle 6n+1\ </math>, <math>\scriptstyle 12n+1\ </math> and <math>\scriptstyle 18n+1\ </math> are prime numbers, the product <math>\scriptstyle M_3(n) = (6n+1)\cdot (12n+1)\cdot (18n+1)</math> is a Carmichael number. This condition can only be satisfied if the number <math>n\ </math> ends with 0, 1, 5 or 6. An equivalent formulation of Chernick's construction is that if <math>\scriptstyle m\ </math>, <math>\scriptstyle 2m-1\ </math> and <math>\scriptstyle 3m-2</math> are prime numbers, then the product <math>\scriptstyle m\cdot (2m-1)\cdot (3m-2)</math> is a Carmichael number.


To construct Carmichael numbers with <math>\scriptstyle M_3(n) = (6n+1)\cdot (12n+1)\cdot (18n+1)</math>, you could only use numbers <math>n\ </math> which ends with 0, 1, 5 or 6.
This way to construct Carmichael numbers may be extended<ref>Paulo Ribenboim, ''The new book of prime number records'', Springer-Verlag (1996) ISBN 0-387-94457-5.  P.120</ref> to
 
This way to construct Carmichael numbers mey be extended<ref>Paulo Ribenboim, ''The new book of prime number records'', Springer-Verlag (1996) ISBN 0-387-94457-5.  P.120</ref> to


:<math>M_k(n)=(6n+1)(12n+1)\prod_{i=1}^{k-2}(9\cdot 2^i n+1) \, </math>  
:<math>M_k(n)=(6n+1)(12n+1)\prod_{i=1}^{k-2}(9\cdot 2^i n+1) \, </math>  
Line 24: Line 22:
Let ''C''(''X'') denote the number of Carmichael numbers less than or equal to ''X''.  Then for all sufficiently large ''X''
Let ''C''(''X'') denote the number of Carmichael numbers less than or equal to ''X''.  Then for all sufficiently large ''X''


:<math>X^{2/7} < C(X) < X \exp(-\log X \log\log\log X / \log\log X) . \,</math>
:<math>X^{0.332} < C(X) < X \exp(-\log X \log\log\log X / \log\log X) . \,</math>


The upper bound is due to Erdős(1956)<ref>Paul Erdős,  "On pseudoprimes and Carmichael numbers", ''Publ. Math. Debrecen'' '''4''' (1956) 201-206. MR '''18''' 18</ref> and Pomerance, Selfridge and Wagstaff (1980)<ref>C. Pomerance, J.L. Selfridge and S.S. Wagstaff jr, "The pseudoprimes to 25.10<sup>9</sup>", ''Math. Comp.'' '''35''' (1980) 1003-1026.  MR '''82g''':10030</ref> and the lower bound is due to Alford, Granville and Pomerance (1994)<ref>W. R. Alford, A. Granville, and C. Pomerance. "There are Infinitely Many Carmichael Numbers", ''Annals of Mathematics'' '''139''' (1994) 703-722. MR '''95k''':11114</ref>.  The asymptotic rate of growth of ''C''(''X'') is not known.<ref>Richard Guy, "Unsolved problems in Number Theory" (3rd ed), Springer-Verlag (2004) ISBN 0-387-20860-7.  Section A13</ref>
The upper bound is due to Erdős(1956)<ref>Paul Erdős,  "On pseudoprimes and Carmichael numbers", ''Publ. Math. Debrecen'' '''4''' (1956) 201-206. MR '''18''' 18</ref> and Pomerance, Selfridge and Wagstaff (1980)<ref>C. Pomerance, J.L. Selfridge and S.S. Wagstaff jr, "The pseudoprimes to 25.10<sup>9</sup>", ''Math. Comp.'' '''35''' (1980) 1003-1026.  MR '''82g''':10030</ref> and the lower bound is due to [[Glyn Harman]] (2005),<ref>{{cite journal |author=Glyn Harman |title=On the number of Carmichael numbers up to ''x'' |journal=Bulletin of the London Mathematical Society | volume=37 | year=2005 | pages=641–650 | doi=10.1112/S0024609305004686 | id=Zbl. 1108.11065 }}</ref> improving the earlier lower bound of <math>X^{2/7}</math> obtained by Alford, Granville and Pomerance (1994), which first established that there were infinitely many Carmichael numbers.<ref>{{cite journal | author=W. R. Alford, A. Granville, and C. Pomerance | title=There are Infinitely Many Carmichael Numbers | journal=Annals of Mathematics | volume=139 | number=3 | year=1994 | pages=703-722 | id=MR 95k:11114 Zbl 0816.11005 }}</ref>.  The asymptotic rate of growth of ''C''(''X'') is not known.<ref>{{cite book | author=Richard Guy | title=Unsolved problems in Number Theory | edition=3rd | publisher=Springer-Verlag | year=2004 | isbn=0-387-20860-7 }}.  Section A13</ref>


==References and notes==
==References and notes==
<references/>
<references/>[[Category:Suggestion Bot Tag]]

Latest revision as of 06:01, 25 July 2024

This article is developing and not approved.
Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
Code [?]
 
This editable Main Article is under development and subject to a disclaimer.

A Carmichael number is a composite number named after the mathematician Robert Daniel Carmichael. A Carmichael number divides for every integer . A Carmichael number c also satisfies the congruence , if . The first few Carmichael numbers are 561, 1105, 1729, 2465, 2821, 6601 and 8911. In 1994 Pomerance, Alford and Granville proved that there exist infinitely many Carmichael numbers.

Properties

  • Every Carmichael number is square-free and has at least three different prime factors
  • For every Carmichael number c it holds that is divisible by for every one of its prime factors .
  • Every absolute Euler pseudoprime is a Carmichael number.

Chernick's Carmichael numbers

J. Chernick found in 1939 a way to construct Carmichael numbers[1] [2]. If, for a natural number n, the three numbers , and are prime numbers, the product is a Carmichael number. This condition can only be satisfied if the number ends with 0, 1, 5 or 6. An equivalent formulation of Chernick's construction is that if , and are prime numbers, then the product is a Carmichael number.

This way to construct Carmichael numbers may be extended[3] to

with the condition that each of the factors is prime and that is divisible by .

Distribution of Carmichael numbers

Let C(X) denote the number of Carmichael numbers less than or equal to X. Then for all sufficiently large X

The upper bound is due to Erdős(1956)[4] and Pomerance, Selfridge and Wagstaff (1980)[5] and the lower bound is due to Glyn Harman (2005),[6] improving the earlier lower bound of obtained by Alford, Granville and Pomerance (1994), which first established that there were infinitely many Carmichael numbers.[7]. The asymptotic rate of growth of C(X) is not known.[8]

References and notes

  1. J. Chernick, "On Fermat's simple theorem", Bull. Amer. Math. Soc. 45 (1939) 269-274
  2. (2003-11-22) Generic Carmichael Numbers
  3. Paulo Ribenboim, The new book of prime number records, Springer-Verlag (1996) ISBN 0-387-94457-5. P.120
  4. Paul Erdős, "On pseudoprimes and Carmichael numbers", Publ. Math. Debrecen 4 (1956) 201-206. MR 18 18
  5. C. Pomerance, J.L. Selfridge and S.S. Wagstaff jr, "The pseudoprimes to 25.109", Math. Comp. 35 (1980) 1003-1026. MR 82g:10030
  6. Glyn Harman (2005). "On the number of Carmichael numbers up to x". Bulletin of the London Mathematical Society 37: 641–650. DOI:10.1112/S0024609305004686. Zbl. 1108.11065. Research Blogging.
  7. W. R. Alford, A. Granville, and C. Pomerance (1994). "There are Infinitely Many Carmichael Numbers". Annals of Mathematics 139: 703-722. MR 95k:11114 Zbl 0816.11005.
  8. Richard Guy (2004). Unsolved problems in Number Theory, 3rd. Springer-Verlag. ISBN 0-387-20860-7. . Section A13