A287840 Numbers that generate Carmichael numbers using Erdős's method.

36, 48, 60, 72, 80, 108, 112, 120, 144, 180, 198, 216, 224, 240, 252, 288, 300, 324, 336, 360, 396, 420, 432, 468, 480, 504, 528, 540, 560, 576, 594, 600, 612, 630, 648, 660, 672, 720, 756, 768, 780, 792, 810, 828, 840, 864, 900, 936, 960, 972, 990, 1008

Offset: 1

Author

Amiram Eldar, Sep 01 2017

Keywords

• nonn

Comments

Erdős showed in 1956 how to construct Carmichael numbers from a given number n (typically with many divisors). Given a number n, let P be the set of primes p such that (p-1)|n but p is not a factor of n. Let c be a product of a subset of P with at least 3 elements. If c == 1 (mod n) then c is a Carmichael number.

Numbers with only one generated Carmichael number: 48, 80, 224, 252, 324, 468, 528, 560, 594, 780, 972, 1104, 1232, 1368, 1536, 1848, 2024, ...

Examples

			The set of primes for n = 36 is P={5, 7, 13, 19, 37}. Two subsets, {7, 13, 19} and {7, 13, 19, 37} have c == 1 (mod n): c = 7*13*19 = 1729 and c = 7*13*19*37 = 63973. 36 is the first number that generates Carmichael numbers thus a(1)=36.
		

Links

• Paul Erdős, On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen 4 (1956), pp. 201-206.
• Andrew Granville, Primality testing and Carmichael numbers, Notices of the American Mathematical Society, Vol. 39 No. 6 (1992), pp. 696-700.
• Andrew Granville and Carl Pomerance, Two contradictory conjectures concerning Carmichael numbers, Mathematics of Computation, Vol. 71, No. 238 (2002), pp. 883-908.

Crossrefs

Cf. A002997.

Programs

Mathematica

a = {}; Do[p = Select[Divisors[n] + 1, PrimeQ]; pr = Times @@ p; pr = pr/GCD[n, pr]; ps = Divisors[pr]; c = 0; Do[p1 = FactorInteger[ps[[j]]][[;; , 1]]; If[Length[p1] < 3, Continue[]]; c1 = Times @@ p1; If[Mod[c1, n] == 1, c++], {j, 1, Length[ps]}]; If[c > 0, AppendTo[a, n]], {n, 1, 1000}]; a