From: Bill Dubuque Subject: Carmichael Numbers: Korselt's Criterion [was: BuddhaSon number & Carmichael number] Date: 26 Mar 1999 08:14:31 -0500 Newsgroups: sci.math fredh@ix.netcom.com (Fred W. Helenius) wrote: | | "ªk¶³Äé³»" wrote: | > [...] | > n = q1^n1 q2^n2 ... qk^nk (qi prime) is a Carmichael number | > iff | > i) ni = 1, for all i=1,...,k | > ii) qi-1 | n-1, for all i=1,...,k | > iii) n=1 (mod 2) and k>=3 | | i) and ii) are called Korselt's Criterion. See below for more on Korselt's Criterion (including a proof). From: Bill Dubuque Date: Tue, 30 Dec 1997 06:23:42 -0500 DWW wrote: (convention: p always denotes a prime below) ! ! Is n Carmichael <=> n is composite, squarefree & p|n => p-1|n-1 ? Yes, in fact there is a generalization that counts Fermat liars: Let F(n) = { a in Z/n : a^(n-1) = 1 mod n }, n odd. ___ Then |F(n)| = | | gcd(n-1,p-1) [cf. Bach & Shallit, Algorithmic ] p|n [Number Theory, Exercise 9.25 p. 305] The criterion you state was discovered by Korselt in 1899, but he left open the question whether such numbers exist. It was not until 11 years later that Carmichael actually gave some examples while presenting his essentially equivalent criterion that y(n)|n-1 (and n is composite), where y(n) is the Carmichael lambda function, the (universal) exponent of the group of units in Z/n, i.e. the smallest integer e such that a^e = 1 mod n for all units a (i.e. those a with (a,n)=1). Actually this function was discovered much earlier by Gauss: it is implicit in Article 92 of Disq. Arith. Korselt's Criterion has an elementary proof: (<=) We are given a squarefree number n enjoying p|n => p-1|n-1 and we must show that n|a^n-a for all a. But a squarefree number divides another number iff each of its prime factors do. Hence we need only show that p|a^n-a for each prime p|n or, equivalently, that a != 0 => a^(n-1)=1 mod p, which, since p-1|n-1, follows from a != 0 => a^(p-1)=1 mod p (Fermat's little Theorem). (=>) Given that n|a^n-a for all integers a we must show (1) n is squarefree and (2) p|n => p-1|n-1. (1) If n is not squarefree it has a nontrivial divisor a^2; but then a^2|n|a^n-a yields the contradiction that a^2|a. (2) Let p|n and let a be a generator of the multiplicative group of Z/p, so a has order p-1. Now p|n|a(a^(n-1)-1) but not p|a, so a^(n-1)=1 mod p, hence n-1 must be divisible by p-1, the order of a mod p. QED For more on Carmichael numbers see the fine expository survey by Carl Pomerance: Carmichael Numbers, Nieuw Archief voor Wiskunde, 11 (1993) 199-209 (an elaboration of his April 22, 1992 Beeger Lecture during the 28th Nederlands Math. Congres in Delft). -Bill Dubuque