Carmichael number: Difference between revisions

Latest revision as of 22:01, 15 January 2012

Definition

A composite number $n>1$ is termed an Carmichael number or absolute pseudoprime if it satisfies the following equivalent conditions:

The universal exponent (also called the Carmichael function) $\lambda (n)$ of $n$ divides $n-1$ .
For any natural number $a$ relatively prime to $n$ , $n$ divides $a^{n-1}-1$ .
$n$ is a Fermat pseudoprime to any base relatively prime to it.
$n$ is a square-free odd number greater than 1 and $p-1$ divides $n-1$ for every prime divisor $p$ of $n$ .

Occurrence

Initial examples

561, 1105, 1729, 2465, 2821, 6601, [SHOW MORE]

View list on OEIS

Note that Carmichael number is square-free and Carmichael number is odd, so each of these is the product of distinct odd primes. Further, because Carmichael number is not semiprime, there are at least three prime factors of each number. For the first few examples, we indicate the prime factors:

Carmichael number	Prime factors as list	3?	5?	7?	11?	13?	17?	19?	23?	29?	31?	Universal exponent (must divide number minus one)
561	3, 11, 17	Yes	No	No	Yes	No	Yes	No	No	No	No	80
1105	5, 13, 17	No	Yes	No	No	Yes	Yes	No	No	No	No	48
1729	7, 13, 19	No	No	Yes	No	Yes	No	Yes	No	No	No	36
2465	5, 17, 29	No	Yes	No	No	No	Yes	No	No	Yes	No	112
2821	7, 13, 31	No	No	Yes	No	Yes	No	No	No	No	Yes	60

@@ Line 3: / Line 3: @@
 ==Definition==
-A composite number <math>n > 1</math> is termed an '''absolute pseudoprime''' or ''Carmichael number''' if it satisfies the following condition:
+A composite number <math>n > 1</math> is termed an '''Carmichael number''' or '''absolute pseudoprime''' if it satisfies the following equivalent conditions:
-* The [[Liouville-lambda function]] of <math>n</math> divides <math>n - 1</math>.
+# The [[defining ingredient::universal exponent]] (also called the Carmichael function) <math>\lambda(n)</math> of <math>n</math> divides <math>n - 1</math>.
-* For any natural number <math>a</math> relatively prime to <math>n</math>, <math>n</math> divides <math>a^{n-1} - 1</math>.
+# For any natural number <math>a</math> relatively prime to <math>n</math>, <math>n</math> divides <math>a^{n-1} - 1</math>.
-* <math>n</math> is a [[Fermat pseudoprime]] to any base relatively prime to it.
+# <math>n</math> is a [[defining ingredient::Fermat pseudoprime]] to any base relatively prime to it.
+# <math>n</math> is a square-free odd number greater than 1 and <math>p - 1</math> divides <math>n - 1</math> for every prime divisor <math>p</math> of <math>n</math>.
+==Occurrence==
+===Initial examples===
+<section begin="list"/>[[561]], [[1105]], [[1729]], [[2465]], [[2821]], [[6601]], <toggledisplay>8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881, 512461</toggledisplay>[[Oeis:A002997|View list on OEIS]]<section end="list"/>
+Note that [[Carmichael number is square-free]] and [[Carmichael number is odd]], so each of these is the product of distinct odd primes. Further, because [[Carmichael number is not semiprime]], there are at least three prime factors of each number. For the first few examples, we indicate the prime factors:
+{| class="sortable" border="1"
+! Carmichael number !! Prime factors as list !! [[3]]? !! [[5]]?!! [[7]]? !! [[11]]? !! [[13]]? !! [[17]]? !! [[19]]? !! [[23]]? !! [[29]]? !! [[31]]? !! [[Universal exponent]] (must divide number minus one)
+|-
+| [[561]] || [[3]], [[11]], [[17]] || Yes || No || No || Yes || No || Yes || No || No || No || No || 80
+|-
+| [[1105]] || [[5]], [[13]], [[17]] || No || Yes || No || No || Yes || Yes || No || No || No || No || 48
+|-
+| [[1729]] || [[7]], [[13]], [[19]] || No || No || Yes || No || Yes || No || Yes || No || No || No || 36
+|-
+| [[2465]] || [[5]], [[17]], [[29]] || No || Yes || No || No || No || Yes || No || No || Yes || No ||112
+|-
+| [[2821]] || [[7]], [[13]], [[31]] || No || No || Yes || No || Yes || No || No || No || No || Yes || 60
+|}
+==Facts==
+* [[There are infinitely many Carmichael numbers]]
+* [[Carmichael number is odd]]
+* [[Carmichael number is square-free]]
+* [[Carmichael number is not semiprime]]