Carmichael number: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Olier Raby
mNo edit summary
 
(10 intermediate revisions by 2 users not shown)
Line 1: Line 1:
{{subpages}}
{{subpages}}
A '''Carmichael number''' is a composite number named after the mathematician [[Robert Daniel Carmichael]]. A Carmichael number <math>\scriptstyle c\ </math> satisfies for every integer <math>\scriptstyle a\ </math> that <math>\scriptstyle a^c - a\ </math> is divisible by <math>\scriptstyle c\ </math>. A Carmichael number ''c'' also satisfies the congruence <math>\scriptstyle a^{c-1} \equiv 1 \pmod c</math>, if <math>\scriptstyle \operatorname{gcd}(a,c) = 1</math>. 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.
A '''Carmichael number''' is a composite number named after the mathematician [[Robert Daniel Carmichael]]. A Carmichael number <math>\scriptstyle c\ </math> divides <math>\scriptstyle a^c - a\ </math> for every integer <math>\scriptstyle a\ </math>. A Carmichael number ''c'' also satisfies the [[modular arithmetic|congruence]] <math>\scriptstyle a^{c-1} \equiv 1 \pmod c</math>, if <math>\scriptstyle \operatorname{gcd}(a,c) = 1</math>. 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 ==
== 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 Carmichael number is an [[Euler pseudoprime]].
*Every absolute [[Euler pseudoprime]] is a Carmichael number.
*Every absolute Euler pseudoprime is a Carmichael number.


== Chernick's Carmichael numbers ==
== Chernick's Carmichael numbers ==


[[J. Chernick]] found in 1939 a way to construct Carmichael numbers<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.
[[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. 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 could expand to <math>M_k(n)=(6n+1)(12n+1)\prod_{i=1}^{k-2}(9\cdot 2^in+1)</math> with the restiction, that for <math>(36\cdot 2^jm + 1)</math> the variable <math>m\ </math> is divisible bei <math>2^j\ </math>
:<math>M_k(n)=(6n+1)(12n+1)\prod_{i=1}^{k-2}(9\cdot 2^i n+1) \, </math>  


==References and notes==
with the condition that each of the factors is prime and that <math>n\ </math> is divisible by <math>2^{k-4}</math>.
<references/>
 
==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''
 
:<math>X^{0.332} < C(X) < X \exp(-\log X \log\log\log X / \log\log X) . \,</math>


== Further reading ==
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>
* [[Richard E. Crandall]] and [[Carl Pomerance]]. Prime Numbers: A Computational Perspective. Springer-Verlag, 2001. ISBN 0-387-25282-7
* [[Paolo Ribenboim]]. The New Book of Prime Number Records. Springer-Verlag, 1996, ISBN 0-387-94457-5


== Links ==
==References and notes==
*[http://de.wikibooks.org/wiki/Pseudoprimzahlen:_Tabelle_Carmichael-Zahlen List of Carmichael numbers between 561 and 2,301,745,249]
<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 [?]
 
https://en.citizendium.org/wiki/index.php?title=Carmichael_number&printable=yes
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
Retrieved from "https://citizendium.org/wiki/index.php?title=Carmichael_number&oldid=966113"