May 4, 2013 - Abstract. A composite positive integer n is said to be a weak Carmichael number if ... that Ï(n) | (nâ1) [48], where Ï(n) is the Eul...

0 downloads 5 Views 448KB Size

arXiv:1305.1867v1 [math.NT] 4 May 2013

Dedicated to the 100th anniversary of birth of Paul Erd˝ os Abstract. A composite positive integer n is said to be a weak Carmichael number if X (1) k n−1 ≡ ϕ(n) (mod n). gcd(k,n)=1 1≤k≤n−1

It is proved that a composite positive integer n is a weak Carmichael number if and only if p − 1 | n − 1 for every prime divisor p of n. This together with Korselt’s criterion yields the fact that every Carmichael number is also a weak Carmichael number. In this paper we mainly investigate arithmetic properties of weak Carmichael numbers. Motivated by the investigations of Carmichael numbers in the last hundred years, here we establish several related results, notions, examples and computatinoal searches for weak Carmichael numbers and numbers closely related to weak Carmichael numbers. Furthermore, using the software Mathematica 8, we present the table containing all non-prime powers weak Carmichael numbers less than 2 × 106 . Motivated by heuristic arguments, our computations and some old conjectures and results for Carmichael numbers, we propose several conjectures for weak Carmichael numbers and for some other classes of Carmichael like numbers. Finally, we consider weak Carmichael numbers in light of Fermat primality test. We believe that it can be of interest to involve certain particular classes of weak Carmichael numbers in some problems concerning Fermatlike primality tests and the generalized Riemann hypothesis.

1. Carmichael numbers, Lehmer numbers and Giuga numbers 1.1. Lehmer numbers, Carmichael numbers and the main result. Lehmer’s totient problem asks about the existence of a composite number such that ϕ(n) | (n − 1) [48], where ϕ(n) is the Euler totient function defined as the number of positive integers less than n which are relatively prime to n. These numbers are sometimes reffered to as Lehmer numbers. In 1932 D.H. Lehmer 2010 Mathematics Subject Classification. Primary 05A19; Secondary 11A51, 05A10, 11A07, 11A15, 11A25, 11A41, 11A05, 11B50. Keywords and phrases. Carmichael number, Lehmer number, Giuga’s conjecture, weak Carmichael number, Carmichael function λ(n), super Carmichael number, k-Lehmer number, Fermat primality test. 1

2

[48] showed that every Lehmer number n must be odd and square-free, and that the number of distinct prime factors of n must be greater than 6. However, no Lehmer numbers are known up to date, and computations by Pinch [61] show that any examples must be greater than 1030 . In 1977 Pomerance [64] showed that the number of Lehmer numbers n ≤ x is O(x1/2 (log x)3/4 ). In 2011 this bound is improved by Luca and Pomerance [50] to O(x1/2 (log x)1/2+o(1) ). Carmichael numbers are quite famous among specialists in number theory, as they are quite rare and very hard to test. Fermat little theorem says that if p is a prime and the integer a is not a multiple of p, then ap−1 ≡ 1(mod p). However, there are positive integers n that are composite but still satisfy the congruence an−1 ≡ 1(mod n) for all a coprime to n. Such “false primes” are called Carmichael numbers in honour of R.D. Carmichael, who demonstrated their existence in 1912 [18]. A Carmichael number n is a composite integer that is a base-a Fermat-pseudoprime for all a with gcd(a, n) = 1. These numbers present a major problem for Fermat-like primality tests. In [34] A. Granville wrote: “Carmichael numbers are nuisance, masquerading as primes like this, though computationally they only appear rarely. Unfortunately it was recently proved that there are infinitely many of them and that when we go out far enough they are not so rare as it first appears.” It is easy to see that every Carmichael number is odd, namely, if n ≥ 4 is even, then (n − 1)n−1 ≡ (−1)n−1 = −1 6≡ −1(modn). In 1899 A. Korselt [47] gave a complete characterization of Carmichael numbers which is often rely on the following equivalent definition. Definition 1.1 (Korselt’s criterion, 1899). A composite odd positive integer n is a Carmichael number if n is squarefree, and p − 1 | n − 1 for every prime p dividing n. Korselt did not find any Carmichael numbers, however. The smallest Carmichael number, 561(= 3 × 11 × 17), was found by Carmichael in 1910 [17]. Carmichael also gave a new characterization of these numbers as those composite n which satisfy λ(n) | n − 1, where λ(n), Carmichael lambda function, denotes the size of the largest cyclic subgroup of the group (Z/nZ)∗ of all reduced residues modulo n. In other words, λ(n) is the smallest positive integer m such that am ≡ 1(mod n) for all for all a coprime to n (Sloane’s sequence A002322). Since λ(n) | ϕ(n) for every positive integer n, every Lehmer number would also be a Carmichael number. Recall that various upper bound and lower bounds for λ(n) have been obtained in [28]. It is easily deduced from Korselt’s criterion that every Carmichael number is a product of at least three distinct primes (see e.g., [35]). It was unsolved problem for many years whether there are infinitely many Carmichael numbers. The question was resolved in 1994 by Alford, Granville and Pomerance [1] who proved, not only that the answer is yes, but that there are more than x2/7 Carmichael numbers up to x, once x is sufficiently large. In 2005 G. Harman [42] has improved the constant

3

2/7 to 0.33 (for a more general result see [43, Theorem 1.2]). However, there are a very wide gap between these estimates and the known upper bounds for C(x). Related upper bounds and the counting function for the Carmichael numbers were studied in 1956 by P. Erd˝os [26], in 1980 by C. Pomerance, J.L. Selfridge and Samuel S. Wagstaff [67] and in 1989 by C. Pomerance [66]. In the same paper Erd˝os proposed a popular method for the construction of Carmichael numbers (cf. [81] and for a recent application of this construction see [35] and [49]). Some other algorihms for constructing Carmichael numbers can be found in [2] and [49] where are constructed Carmichael numbers with millions of components. Recall also that in 1939, Chernick [19] gave a simple method to obtain Carmichael numbers with three prime factors considering the products of the form (6m + 1)(12m + 1)(18m + 1) with m ≥ 1. Notice also that the number of Carmichael numbers less than 10n is given in [72] as the Sloane’s sequence A055553. Quite recently, T. Wright [80] proved that for every pair of coprime positive integers a and d there are infinitely many Carmichael numbers m such that m ≡ a(mod d).

Remark 1.2. Quite recently, J.M. Grau and A.M. Oller-Marc´en [37, Definition 1] weakened Lehmer property by introducing the concept of k-Lehmer numbers. For given positive integer k, a k-Lehmer number is a composite integer n such that ϕ(n) | (n − 1)k . It is easy to see that every k-Lehmer number must be square-free. Hence, if we denote by Lk the set that each k-Lehmer number Lk := {n ∈ N : ϕ(n) | (n − 1)k },

then k-Lehmer numbers are the composite elements of Lk . Then Lk ⊆ Lk+1 for each k ∈ N, and define ∞ [ L∞ := Lk . k=1

Then it can be easily shown that [37, Proposition 3] L∞ := {n ∈ N : rad(ϕ(n)) | (n − 1)}.

This immediately shows that [37, Proposition 6] if n is a Carmichael number, then n also belongs to the set L∞ . This leads to the following characterization of Carmichael numbers which slightly modifies Korselt’s criterion. Proposition 1.3. ([37, Proposition 6]) A composite number n is a Carmichael number if and only if rad(ϕ(n)) | n − 1 and p − 1 | n − 1 for every prime divisor p of n. Obviously, the composite elements of L1 are precisely the Lehmer numbers and the Lehmer property asks whether L1 contains composite numbers or not. Nevertheless, for all k > 1, Lk always contains composite elements (cf. Sloane’s sequence A173703 in OEIS [72] which presents L2 ). For further radically weaking the Lehmer and Carmichael conditions see [55].

4

Remark 1.4. Carmichael numbers can be generalized using concepts of abstract algebra. Namely, in 2000 Everet W. Howe [29] defined a Carmichael number of order m to be a composite integer n such that nth power raising defines an endomorphism of every Z/nZ-algebra that can be generated as a Z/nZ-module by m elements. The author gave a simple criterion to determine whether a number is a Carmichael number of order m. In 2008 G.A. Steele [74] generalized Carmichael numbers to ideals in number rings and proved a generalization of Korselt’s criterion for these Carmichael ideals. Here, as always in P the sequel, gcd(k, n) denotes the greatest common divisor of k and n, and gcd(k,n)=1 · denotes the sum ranging over all integers k k∈P satisfying the prperty P and the condition gcd(k, n) = 1. Studying some variations on the “theme of Giuga”, in 1995 J.M. Borwein and E. Wong [15] established the following result. Theorem 1.5. ([15, Corollary 8]) A positive integer n ≥ 2 satisfies the congruence X (1.1) k n−1 ≡ ϕ(n) (mod n) gcd(k,n)=1 1≤k≤n−1

if and only if p − 1 | n − 1 for every prime divisor p of n. Remark 1.6. Theorem 1.5 was proved in [15] as a particular case of Theorem 11 in [15]. In the proof of this theorem the authors deal with congruences for the sum (1.1) modulo prime powers dividing n. In particular, in this proof it was used the Chinese remainder theorem to factor the sum (1.1) modulo n into product of s similar “restricted sums”, where s is a number of distinct prime factors of n. In Section 4 we give another proof of Theorem 1.5 (this is in fact proof of Theorem P 2.4). Our proof is based on some congruential properties of sums of powers gcd(k,n)=1 k n−1 (Lemmas 4.1–4.7) and Carlitz-von Staudt’s 1≤k≤n−1

result [16] for determining S2k (m)(mod m) (Lemma 4.8).

A direct consequence of Theorem 1.5 is the following simple characterization of Carmichael numbers. Corollary 1.7. (Corollary 2.8). A composite positive integer n is a Carmichael number if and only if the following conditions are satisfied. (i) n X is square-free and (ii) k n−1 ≡ ϕ(n) (mod n). gcd(k,n)=1 1≤k≤n−1

In this paper we mainly investigate arithmetic properties of composite positive integers satisfying the congruence (1.1). Such numbers are called weak Carmichael numbers. Motivated by the investigations of Carmichael numbers

5

in the last hundred years, here we establish several related results, notions, examples and computatioal searches for weak Carmichael numbers and numbers closely related to weak Carmichael numbers. 1.2. Bernoulli’s formula for the sum of powers P and von Staudt-Clausen’s theorem. The sum of powers of integers ni=1 ik is a well-studied problem in mathematics (see e.g., [11], [69]). Finding formulas for these sums has interested mathematicians for more than 300 years since the time of James Bernoulli (1665-1705). These lead to numerous recurrence relations. The first such well known recurrence relation was established by B. Pascal [60]. A related new reccurrence relation is quite recently established in [54, Corollary 1.9]. For a nice account of sums of powers see [24]. For simplicity, here as often in the sequel, for all integers k ≥ 1 and n ≥ 2 we denote Sk (n) :=

n−1 X i=1

ik = 1k + 2k + 3k + · · · + (n − 1)k .

The study of these sums led Jakob Bernoulli [10] to develop numbers later named in his honor. Namely, the celebrated Bernoulli’s formula (sometimes called Faulhaber’s formula) ([30] and [?]) gives the sum Sk (n) explicitly as (see e.g., [33] or [8]) k 1 X k + 1 k+1−i n Bi (1.2) Sk (n) = i k + 1 i=0 where Bi (i = 0, 1, 2, . . .) are Bernoulli numbers defined by the generating function ∞ X xi x Bi = x . i! e −1 i=0

1 , and Bi = 0 It is easy to find the values B0 = 1, B1 = − 12 , B2 = 61 , B4 = − 30 for odd i ≥ 3. Furthermore, (−1)i−1 B2i > 0 for all i ≥ 1. Recall that several identities involving Bernoulli numbers and Bernoulli polynomials can be found in [59] and [76]. The von Staudt-Clausen’s theorem is a result determining the fractional part of Bernoulli numbers, found in 1840 independently by K. von Staudt ([73]; see also [41, Theorem 118]) and T. Clausen [20]).

Theorem 1.8. (von Staudt-Clausen’s theorem). The denominator of Bernoulli number B2n with n = 1, 2, . . . is the product of all primes p such that p − 1 divides 2n. Remark 1.9. In literature, von Staudt-Clausen’s theorem is often formulated as: X 1 B2n + is an integer for each n = 1, 2, . . . , p p−1|2n p prime

6

or equivalently (see e.g., [75, page 153]): 0 (mod p) if p − 1 ∤ 2n pB2n ≡ −1 (mod p) if p − 1 | 2n,

where p is a prime and k a positive integer. We also point out that in the proof of Theorem 2.4 we use a particular case of a Carlitz-von Staudt’s result (see Remark 1.6) which can be easily deduced from the above form of von Staudt-Clausen’s theorem. 1.3. Giuga’s conjecture and Giuga numbers. Notice that if n is any prime, then by Fermat’s little theorem, Sn−1 (n) ≡ −1(mod n). In 1950 G. Giuga [32] proposed that the converse is also true via the following conjecture. Conjecture 1.10 (Giuga’s conjecture). A positive integer n ≥ 2 is a prime if and only if (1.3)

Sn−1 (n) :=

n−1 X i=1

in−1 ≡ −1

(mod n).

A counterexample to Giuga’s conjecture is called a Giuga number. It is easy to show that Sn−1 (n) ≡ −1 (mod n) if and only if for each prime divisor p of n, (p − 1) | (n/p − 1) and p | (n/p − 1) (see [32], [13, Theorem 1] or [68, p. 22]). Observe that both these conditions are equivalent to the condition that p2 (p − 1) | p(n − 1). Therefore, any Giuga number must be squarefree. Giuga [32] showed that there are no exceptions to the conjecture up to 101000 . In 1985 E. Bedocchi [9] improved this bound to n > 101700 . In 1996 D. Borwein, J.M. Borwein, P.B. Borwein and R. Girgensohn [13] raised the bound to n > 1013887 . In 2011 F. Luca, C. Pomerance and I. Shparlinski [51] proved that for any real number x, the number of counterexamples to Giuga’s conjecture G(x) := #{n < x : √n is composite and Sn−1 (n) ≡ −1 (mod n)} satisfies the estimate G(x) = O( x/(log x)2 ) as x → ∞ improving slightly on a previous result by V. Tipu [82]. Quite recently, J.M. Borwein, M. Skerritt and C. Maitland [14, Theorem 2.2] reported that any counterexample to Giuga’s primality conjecture is an odd square-free integer with at least 4771 prime factors and so must exceed 1019907 . Let ϕ(n) be the Euler totient function. Definition 1.11. A positive composite integer n is said to be a Giuga number if n−1 X (1.4) k ϕ(n) ≡ −1 (mod n). k=1

This definition was given by Giuga [32]. However, it is known (e.g., see [13, Theorem 1]) that a positive composite integer n is a Giuga number if and only if p2 (p − 1) divides n − p for every prime divisor p of n. Moreover, it is easy to

7

see that only square-free integers can be Giuga numbers. For more information about Giuga numbers see D. Borwein et al. [13], J.M. Borwein and E. Wong [15], and E. Wong [79, Chapter 2]. A weak Giuga number is a composite number n for which the sum X 1 1 − + n p p|n p prime

is an integer. It is known that each Giuga number is a weak Giuga number and that n is a weak Giuga number if and only if p2 | n − p for every prime divisor p of n (see [13]). Up to date only thirteen weak Giuga numbers are known and all these numbers are even. The first few Giuga numbers are 30, 858, 1722, 66198, 2214408306, 24423128562, 432749205173838 (see sequence A007850 in [72]). Independently, in 1990 T. Agoh (published in 1995 [4]; see also [15] and Sloane’s sequence A046094 in [72]) proposed the following conjecture. Conjecture 1.12. (Agoh’s conjecture). A positive integer n ≥ 2 is a prime if and only if nBn−1 ≡ −1(mod n).

Remark 1.13. Notice that the denominator of the number nBn−1 can be greater than 1, but since by von Staudt-Clausen’s theorem (Theorem 1.8), the denominator of any Bernoulli number B2k is squarefree, it follows that the denominator of nBn−1 is invertible modulo n. In 1996 it was reported by T. Agoh [13] that his conjecture is equivalent to Giuga’s conjecture, hence the name Giuga-Agoh’s conjecture found in the litterature. Therefore, Proposition 1.14. Giuga’s conjecture and Agoh’s conjecture are equivalent. It was pointed out in [13] that this can be seen from the Bernoulli formula (1.2) after some analysis involving von Staudt-Clausen’s theorem. The equivalence of both conjectures is in details proved in 2002 by B.C. Kellner [45, Satz 3.1.3, Section 3.1, p. 97] (also see [46, Theorem 2.3]). In a recent manuscript [53, Subsection 2.1] the author of this article proposed several Giuga-Agoh’slike conjectures. Notice that von Staudt-Clausen’s theorem allows one to give the following equivalent reformulation of Korselt’s criterion involving the Bernoulii number Bn−1 is (see e.g., [67, Section 2, Remarks after Proposition 2], [78]). Definition 1.15. An odd composite positive integer n is a Carmichael number if and only if n is squarefree and n divides the denominator of the Bernoulli number Bn−1 . We present the following relationship between Giuga’s conjecture and Carmichael numbers. Proposition 1.16. (see e.g., [13, Theorem] or [36, Corollary 4]) A positive integer n is a counterexample to Giuga’s conjecture if and only if it is both a

8

Carmichael and a Giuga number. In other words, a positive integer n satisfies the congruence (1.5)

n−1 X i=1

in−1 ≡ −1

(mod n)

if and only if is n is both a Carmichael and a Giuga number. In 2011 J.M. Grau and A.M. Oller-Marc´en [36] established a new approach to Giuga’s conjecture as follows. Proposition 1.17. ([36, Corollary 3]) If a positive integer n is a counterexample to Giuga’s conjecture, then for each positive integer k (1.6)

n−1 X i=1

ik(n−1) ≡ −1

(mod n).

Remark 1.18. Proposition 1.17 leads to the generalization of Giuga’s ideas in the following way [36, Section 3]: Do there exist integers k such that the congruence (1.6) is satisfied by some composite integer n? Several open problems concerning Giuga’s conjecture can be found in J.M. Borwein and E. Wong [15, 8, E Open Problems]. Remark 1.19. Quite recently, J.M. Grau and A.M. Oller-Marc´en [38, Theorem 1] characterized, in terms of the prime divisors of n, the pairs (k, n) for which n divides Sk (n). More generally, in [38] it is investigated Sf (n) (b)(mod n) for different arithmetic functions f . 2. Weak Carmichael numbers 2.1. Sum of powers of coprime residues of n. The Euler totient function ϕ(n) is defined as equal to the number of positive integers less than n which are relatively prime to n. Each of these ϕ(n) integers is called a totative (or “totitive”) of n (see [69, Section 3.4, p. 242] where this notion is attributed to J.J. Sylvester). Let t(n) denote the set of all totatives of n, i.e., t(n) = {j ∈ N : 1 ≤ j < n, gcd(j, n) = 1}. Given any fixed nonnegative integer k, in 1850 A. Thacker (see [69, p. 242]) introduced the function ϕk (n) defined as X (2.1) ϕk (n) = tk t∈t(n)

where the summation ranges over all totatives t of n (in addition, we define ϕk (1) = 0 for all k). Notice that ϕ0 (n) = ϕ(n) and ϕk (n) = Sk (n) holds if and only if n = 1 or n is a prime number.

9

The following recurrence relation for the functions ϕk (n) was established in 1857 by J. Liouville (cf. [69, p. 243]): X nk ϕk (d) = Sk (n + 1) := 1k + 2k + · · · + nk d d|n P which for k = 0 reduces to Gauss’ formula d|n ϕ(d) = n. Furthermore, in 1985 P.S. Bruckman [12] established an explicitP Bernoulli’s-like formula for s the Dirichlet series of ϕk (n) defined as fk (s) = ∞ k=1 ϕk (n)/n (there ϕk (n) is called generalized Euler function). Quite recently, in [54, Corollary 1.9] the author of this article proved for all k ≥ 1 and n ≥ 2 the following recurrence relation involving the functions ϕk (n). 2k−1 X i 2k − 1 22k−1−i ni ϕ2k−1−i (n) = 0. (−1) i i=0 2.2. Weak Carmichael numbers. Inspired by the previous definitions, results, and considerations we give the following definition. Definition 2.1. A composite positive integer n is said to be a weak Carmichael number if X (2.2) k n−1 ≡ ϕ(n) (mod n), gcd(k,n)=1 1≤k≤n−1

where the summation ranges over all k such that 1 ≤ k ≤ n−1 and gcd(k, n) = 1. From the above definition we see that each Carmichael number is also a weak Carmichael number; hence the name. This together with the mentioned result that the set of Carmichael numbers is infinite implies the following fact. Proposition 2.2. There are infinitely many weak Carmichael numbers. The following characterization of weak Carmichael numbers may be useful for computational purposes. Proposition 2.3. Every weak Carmichael number is odd. Furthermore, an odd composite positive integer n is a weak Carmichael number if and only if ϕ(n)/2

(2.3)

2

X i=1

rin−1 ≡ ϕ(n) (mod n),

where r1 < r2 < · · · < rϕ(n) are all reduced residues modulo n. As noticed above, the results, definitions and conjectures in this article are mainly based on Theorem 1.5 (a result of Borwein and Wong [15, Corollary 8]) which in terms of weak Carmichael numbers can be reformulated as the following Korselt’s type criterion for characterizing weak Carmichael numbers.

10

Theorem 2.4. Let n = pe11 pe22 · · · pess be a composite integer, where p1 , p2 , . . . , ps are distinct odd primes and e1 , e2 , . . . , es are positive integers. Then n is a weak Carmichael number if and only pi − 1 | n − 1 for every i = 1, 2, . . . , s. Remark 2.5. Any integer greater than 1 and satisfying the congruence (2.2) is called in [15]) a generalized Carmichael number. Therefore, by Definition 2.1, the set of all generalized Carmichael numbers is a union of the set of weak Carmichael numbers and the set of all primes. The following result of E. Wong ([79, p. 17, Subsection 2.5.3] where weak Carmichael numbers are called pseudo-Carmichael numbers) is immediate by Euler totient theorem and it establish the fact that there are numerous weak Carmichael numbers that are not prime powers nor Carmichael numbers. Here, as always in the sequel, lcm(·) will denote the least common multiple function. Proposition 2.6. Let p1 , p2 , . . . , ps be distinct primes such that pi −1 6≡ 0( mod pj ) for each pair of indices i, j with 1 ≤ i 6= j ≤ s. For all j = 1, 2, . . . , s put ei = lcm 1≤j≤s ϕ(pj ). Then any number of the form p1k1 e1 p2k2 e2 · · · psks es with j6=i ki ≥ 1, is a weak Carmichael number. Conversely, if n is a weak Carmichael number with prime factors p1 , p2 , . . . , ps , then pi − 1 6≡ 0( mod pj ) for each pair of indices i, j with 1 ≤ i 6= j ≤ s.

Definition 2.7. Let n ≥ 3 be any odd positive integer with a prime factorization n = pe11 pe22 · · · pess . Then the function cw (n) of n is defined as (2.4)

cw (n) = lcm(p1 − 1, p2 − 1, . . . , ps − 1).

From the above definition, the definition of Carmichael function λ(n) and its property that p − 1 = λ(p) | λ(pe ) for any odd prime p and e ≥ 2, we immediately obtain the following result. Proposition 2.8. For each odd positive integer n, cw (n) | λ(n). Therefore, for such a n we have cw (n) ≤ λ(n).

Using Euler totient theorem, Theorem 2.4 easily yields the following result which gives a possibility for the construction of weak Carmichael numbers via Carmichael numbers.

Proposition 2.9. Let n = p1 p2 · · · ps be an arbitrary Carmichael number. For any fixed i ∈ {1,Q 2, . . . , s} let di be a smallest positive divisor of ϕ(cw (n/pi )) i with cw (n/pi ) := 1≤j≤l (pj −1), such that pdi i ≡ 1( mod cw (n/pi )). Then npmd i j6=i is a weak Carmichael number for every positive integer m. Examples 2.10. Consider the smallest Carmichael number 561 = 3 · 11 · 17. Then cw (561/3) = lcm(10, 16) = 80, cw (561/11) = lcm(2, 16) = 16 and cw (561/17) = lcm(2, 10) = 10, and d1 = 4, d2 = 8, and d3 = 4 are smallest integers for which 3d1 ≡ 1(mod 80), 11d2 ≡ 1(mod 16) and 17d3 ≡ 1(mod 10),

11

respectively. This by Proposition 2.9 shows that 34m+1 ·11·17, 3·118m+1 ·17 and 3 · 11 · 174m+1 are weak Carmichael numbers for every positive integer m (the smallest such a number 35 · 11 · 17 = 45441 occurs in Table 1 as a smallest weak Carmichael number described in Proposition 2.9). Similarly, regarding related values d1 for a smallest prime divisor of the next four Carmichael numbers 1105, 1729, 2465 and 2821 (see Table 1), we respectively obtain the following associated sequences for weak Carmichael numbers: 54m+1 ·13·17, 76m+1 ·13·19, 512m+1 · 17 · 29 and 74m+1 · 13 · 31 with m ≥ 1. Remark 2.11. As noticed above, in 1939, Chernick [19] gave a simple method to obtain Carmichael numbers with three prime factors. The distribution of primes with three prime factors has been studied in 1997 by R. Balasubramanian and S.V. Nagaraj [5], who showed that the number of such Carmichael numbers up to x is at most O(x5/(14+o(1)) ). If n = pqr is a Carmichael number then we have p −1 = da, q −1 = db and r −1 = dc where a, b and c are coprime and dabc | n − 1. The Chernick form n = pqr = (6m + 1)(12m + 1)(18m + 1) is a special case of the form n = pqr = (am + 1)(bm + 1)(cm + 1) with a < b < c, where a, b and c are relatively prime in pairs. Namely, the case a = 1, b = 2, c = 3, leading to d ≡ 0(mod 6). We see that most values (amb, c) will lead to a possible congruence for d modulo abc, whose smallest solution may be expected to be of the same order as abc. As shown in [19, the congruence (5)] in Ore’s book [58, Ch. 14], m = m0 + tabc with t = 1, 2, 3, . . ., where m0 is the solution to the linear congruence (2.5)

m0 (ab + ac + bc) ≡ −(a + b + c) (mod abc).

Thus, for given a, b, c it is easy to find all allowable values of m. All that remains is to test the three components for primality for each allowable m. In this way a “family” of Carmichael numbers is found corresponding to triplets (a, b, c). In [22, Section 5, Table 2] H. Dubner reported that the counts of (1, a, b) are about 64.4% of the corresponding Carmichael numbers with three prime factors less than 10n for a wide range of n. Moreover, the counts of (1, a, b) are about 2.2% of such Carmichael numbers. However, it is not yet known whether there are infinitely many Carmichael numbers of Chernick form, although this would folow from the more general conjecture of Dickson [21]. In 2002 H. Dubner [22] tabulated the counts of Carmichael numbers of Chernick form up to 10n for each n < 42. Up to 1012 and 1018 there are respectively 1000 and 35586 with three prime factors (see [22, Table 2]). Between these 1000 (resp. 35585) Carmichael numbers, 25 (resp. 783) numbers correspond to the Chernick form with related triplets (a, b, c) = (1, 2, 3) (see [22, Table 1]). Examples 2.12. Here we present a simple way for constructing weak Carmichael numbers with four prime factors using the Chernick form of product (6m +

12

1)(12m + 1)(18m + 1). Consider the extended Chernick product in the form l 36m +1 , (2.6) C(m; d, l) := (6m + 1)(12m + 1)(18m + 1) d with d | 36m and some l ≥ 1. Then under the assumptions that p = 6m + 1, q = 12m + 1 and r = 18m + 1 are primes, a routine calculation shows that C(m; d, l) is a weak Carmichael numbers with four prime factors if and only if w(m, d) := 36m/d + 1 is a prime different from p, q and r such that (36m/d + 1)l ≡ 1(mod6m). In particular, for a given m, possible values d = 1, 4, 9, 12, 18, 36 respectively give the following values for s: 36m + 1, 9m + 1, 4m + 1, 2m + 1, m + 1. For example, Chernick [19, p. 271] observed that the integers C(m) := (6m + 1)(12m + 1)(18m + 1) are Carmichael numbers for m ∈ {1, 6, 35, 45, 51, 55, 56, 100, 121}. For a fixed m ≥ 1, denote by Wm the set of all odd primes in the set {36m/d + 1 : d | 36}. Then W1 = {3, 5, 7}, W6 = {7, 13, 19, 37, 217}, W35 = {7, 13, 19}, W45 = {71}, W51 = {103}, W55 = Φ, W56 = {13, 2017}, W100 = {401} and W121 = {4357}. Then every w ∈ Wm for some m ∈ {1, 6, 35, 45, 51, 55, 56, 100, 121} arise a set of weak Carmichael numbers of the form C(m; d, l) given by (2.6), where l must satisfy the congruence w l ≡ 1(mod 6m). For example, assuming w = 13 ∈ W35 , we arrived to the set of weak Carmichael numbers of the form 211 · 421 · 631 · 13l with l such that 13l ≡ 1(mod 210). Using the fact that ϕ(210) = 48, we can easily verify that l0 = 4 is the smallest value of l satisfying the previous congruence. Consequently, each integer of the form 211 · 421 · 631 · 134u with u = 1, 2, . . . is a weak Carmichael number. Definition 2.13. A weak Carmichael number which can be obtained from certain Carmichael number in the manner described in Proposition 2.9 is called a Carmichael like number. Remark 2.14. From Table 1 we see that there exist many weak Carmichael numbers of the form n = p1 · · · pk−1 pfk with some k ∈ {3, 4} and f ≥ 2, which are not Carmichael numbers. For example, from Table 1 we see that 8625 = 3 · 53 · 23 is the smallest such number, and the smallest such numbers with four distinct prime factors is 54145 = 5 · 72 · 13 · 17. In terms of the function cw (n), Theorem 2.4 can be reformulated as follows. Theorem 2.4’. Let n = pe11 pe22 · · · pess be a composite integer, where p1 , p2 , . . . , ps are odd distinct primes and e1 , e2 , . . . , es are positive integers. Then n is a weak Carmichael number if and only cw (n) | n − 1. As an immediate consequence of Theorem 2.4, we establish a surprising result that summing all ϕ(n) congruences an−1 ≡ 1( mod n) over 1 ≤ a ≤ n−1 with gcd(a, n) = 1, we obtain the congruence which characterizes Carmichael numbers under the assumption that n is a square-free integer.

13

Theorem 2.15. Let n > 1 be a square-free positive integer. Then n is a Carmichael number if and only if X (2.7) k n−1 ≡ ϕ(n) (mod n), gcd(k,n)=1 1≤k≤n−1

Using the well known fact that every Carmichael number is square-free, as a consequence of Theorem 2.15, we obtain the following simple characterization of Carmichael numbers. Corollary 2.16. A composite positive integer n is a Carmichael number if and only if the following conditions are satisfied. (i) n X is square-free and (ii) k n−1 ≡ ϕ(n) (mod n). gcd(k,n)=1 1≤k≤n−1

Recall that the M¨obius µ-function is defined so that µ(1) = 1, µ(n) = (−1)s if n is a product of s distinct primes, and µ(n) = 0 if n is divisible by the square of a prime. Then the following consequence of Theorem 2.4 gives a characterization of weak Carmichael numbers that are not Carmichael numbers. Corollary 2.17. An integer n > 1 is a weak Carmichael number which is not a Carmichael number if and only if X k n−1 ≡ ϕ(n) + µ(n) (mod n). gcd(k,n)=1 1≤k≤n−1

Theorem 2.4 immediately gives the following result which was also observed in [15], and also directly proved in [38, Lemma 1]. Proposition 2.18. Every power pe of any odd prime p with e ≥ 2 is a weak Carmichael number. Corollary 2.19. If n is a weak Carmichael number, then every power ne of n with e = 2, 3, . . . is also a weak Carmichael number. In particular, such a power of any Carmichael number is also a weak Carmichael number. Theorem 2.4 and the well known fact that every Carmichael number has at least three distinct prime factors imply the following result. Corollary 2.20. Let n = pq be a product of distinct odd primes p and q. Then n is not a weak Carmichael number. Remark 2.21. Recall that in Section 3 we give a direct proof of Corollary 2.20. Proposition 2.18 shows that weak Carmichael numbers appear to be more numerous than the Carmichael numbers, which can be expressed as follows.

14

Corollary 2.22. Let C(x) and Cw (x) be the numbers of Carmichael numbers and weak Carmichael numbers in the interval [1, x], respectively. Then lim (Cw (x) − C(x)) = +∞.

x→∞

Remark 2.23. Obviously, Corollary 2.17 may be very significant for compuational search of Carmichael numbers. Namely, in order to examine whether a given non-square positive integer n is a Carmichael number, it is sufficient to verify only one congruence modulo n. However, for related faster compuations may be useful the following charaterization of Carmichael numbers which immediately follows from Corollary 2.17 and the fact that ϕ(p1 p2 . . . pk ) = (p1 − 1)(p2 − 2) · · · (pk − 1).

Corollary 2.24. Let n = p1 p2 · · · ps be a composite positive integer, where p1 , p2 , . . . , ps are distinct primes. Let li be residues of n − 1 modulo pi with i = 1, 2, . . . , s. Then n is a Carmichael number if and only if the following k congruences are satified: s X 1 Y li (2.8) k ≡− (pj − 1) (mod pi ), i = 1, 2, . . . , s. pi − 1 j=1 gcd(k,n)=1 1≤k≤l−1

Proposition 2.6 motivates the following definition. Definition 2.25. A weak Carmichael number n is called a primitive weak Carmichael number if n 6= mf for every weak Carmichael numbers m and all integers f ≥ 2. Remark 2.26. Clearly, each weak Carmichael number which is not a power of some integer is also a primitive weak Carmichael number. In particular, this is true for all Carmichael numbers. However, there are primitive weak Carmichael numbers which are powers of some integers. For example, Corollary 2.20 implies that every weak Carmichael number of the form p2 q 2 is a primitive weak Carmichael number. From Table 1 we read the following perfect squares of product of distinct primes: 225, 1225, 8281 and 14161. We also see from Table 1 that the numbers 2025 = 34 · 52 , 18225 = 36 · 52 are primitive weak Carmichael numbers, but 2025 is not a primitive weak Carmichael number (in view of the fact that its square root 45 is a weak Carmichael number). Table 1 also shows that there are primitive Carmichael numbers which are aquare of non-square integers (for example, 1071225 = (32 · 5 · 23)2 ). Furthermore, in view of Definition 2.25, Proposition 2.18 we have the following result. Corollary 2.27. If p is an odd prime, then pf is a primitive weak Carmichael number if and only if f is a prime. The facts that there are infinitely many Carmichael numbers and that every Carmichael number is a weak Carmichael number yield the following result.

15

Corollary 2.28. There are infinitely many primitive weak Carmichael numbers which are not prime powers. Applying the congruence (2.2), we find via Mathematica 8 the following table of weak Carmichael numbers up to 25000 and their factorizations. In this table Carmichael numbers are written in boldface, while prime powers are written in italic face. The notion of indices of weak Carmichael numbers which are less than 30000, given in Table 2, are described in Subsection 2.6. Table 1. Weak Carmichael numbers up to 25000

9 = 32 25 = 5 2 27 = 3 3 45 = 32 · 5 2 4 2 49 = 7 81 = 3 121 = 11 125 = 5 3 2 2 2 5 169 = 13 225 = 3 · 5 243 = 3 289 = 17 2 2 3 2 325 = 5 · 13 343 = 7 361 = 19 405 = 34 · 5 529 = 23 2 561 = 3 · 11 · 17 625 = 5 4 637 = 72 · 13 6 2 4 729 = 3 841 = 29 891 = 3 · 11 961 = 31 2 2 3 2 2 1105 = 5 · 13 · 17 1125 = 3 · 5 1225 = 5 · 7 1331 = 11 3 2 4 2 1369 = 37 1377 = 3 · 17 1681 = 41 1729 = 7 · 13 · 19 2 4 2 7 1849 = 43 2025 = 3 · 5 2187 = 3 2197 = 13 3 2 4 2209 = 47 2401 = 7 2465 = 5 · 17 · 29 2809 = 53 2 5 4 2821 = 7 · 13 · 31 3125 = 5 3321 = 3 · 41 3481 = 59 2 6 2 2 3645 = 3 · 5 3721 = 61 3751 = 11 · 31 3825 = 32 · 52 · 17 4225 = 52 · 132 4489 = 67 2 4913 = 17 3 4961 = 112 · 41 2 2 5 5041 = 71 5329 = 73 5589 = 3 · 23 5625 = 32 · 54 2 3 2 2 6241 = 79 6517 = 7 · 19 6525 = 3 · 5 · 29 6561 = 3 8 3 2 6601 = 7 · 23 · 41 6859 = 19 6889 = 83 7381 = 112 · 61 7921 = 89 2 8125 = 54 · 13 8281 = 72 · 132 8625 = 3 · 53 · 23 2 4 2 8911 = 7 · 19 · 67 9409 = 97 9801 = 3 · 11 10125 = 34 · 53 2 2 10201 = 101 10585 = 5 · 29 · 73 10609 = 103 10625 = 54 · 17 2 2 2 11449 = 107 11881 = 109 12025 = 5 · 13 · 37 12167 = 23 3 12769 = 113 2 13357 = 192 · 37 13833 = 32 · 29 · 53 14161 = 72 · 172 4 6 14641 = 11 15625 = 5 15841 = 7 · 31 · 73 15925 = 52 · 72 · 13 2 5 16129 = 127 16807 = 7 17161 = 131 2 18225 = 36 · 52 2 2 9 18769 = 137 19321 = 139 19683 = 3 21141 = 36 · 29 22201 = 149 2 22801 = 151 2 23409 = 32 · 5 · 232 23805 = 32 · 5 · 232 3 2 24389 = 29 24649 = 157

Remark 2.29. Table 1 shows that there are 102 weak Carmichael numbers less than 25000, and between them there are 9 Carmichael numbers, 57 odd prime powers, and 36 other composite numbers. Recall that in 2006 R.G.E. Pinch [63] reported that there are 1401644 Carmichael numbers up to 1018 (also see [62] for a search of total 105212 Carmichael numbers up to 1015 ). Notice that 1401644 ≈ 1.4 × (1018 )1/3 .

16

Table 2. Weak Carmichael numbers up to 2 × 106 that are not prime powers

458 = 32 · 5 2258 = 32 · 52 32548 = 52 · 13 4 4058 = 3 · 5 561320 = 3 · 11 · 17 63772 = 72 · 13 4 89120 = 3 · 11 1105768 = 5 · 13 · 17 11258 = 32 · 53 2 2 4 122524 = 5 · 7 137732 = 3 · 17 17291296 = 7 · 13 · 19 4 2 20258 = 3 · 5 24651792 = 5 · 17 · 29 28212160 = 7 · 13 · 31 332180 = 34 · 41 36458 = 36 · 5 3751300 = 112 · 31 2 2 2 2 3825128 = 3 · 5 · 17 422548 = 5 · 13 4961400 = 112 · 41 5 2 4 558944 = 3 · 23 56258 = 3 · 5 6517108 = 73 · 19 6525224 = 32 · 52 · 29 66015280 = 7 · 23 · 41 7381600 = 112 · 61 4 2 2 812548 = 5 · 13 828172 = 7 · 13 8625176 = 3 · 53 · 23 4 2 89117128 = 7 · 19 · 67 980120 = 3 · 11 101258 = 34 · 53 4 105858064 = 5 · 29 · 73 1062564 = 5 · 17 120251728 = 52 · 13 · 37 13357648 = 192 · 37 138332912 = 32 · 29 · 53 1416196 = 72 · 172 2 2 1584112960 = 7 · 31 · 73 15925288 = 5 · 7 · 13 182258 = 36 · 52 6 4 2 2114156 = 3 · 29 2340932 = 3 · 17 23805176 = 32 · 5 · 232 2 2 2 25425896 = 3 · 5 · 113 263531296 = 19 · 73 280331536 = 172 · 97 281258 = 32 · 55 2934125920 = 13 · 37 · 61 30625 = 54 · 72 4 8 31213 = 7 · 13 32805 = 3 · 5 33125 = 54 · 53 2 2 35425 = 5 · 13 · 109 35443 = 23 · 67 38637 = 36 · 53 3 41041 = 7 · 11 · 13 · 41 41125 = 5 · 7 · 47 45325 = 52 · 72 · 37 5 45441 = 3 · 11 · 17 46657 = 13 · 37 · 97 47081 = 232 · 89 47125 = 53 · 13 · 29 50625 = 3 4 · 5 4 52633 = 7 · 73 · 103 2 54145 = 5 · 7 · 13 · 17 54925 = 52 · 133 58621 = 312 · 61 2 4 60025 = 5 · 7 62745 = 3 · 5 · 47 · 89 63973 = 7 · 13 · 19 · 37 65025 = 32 · 52 · 172 65341 = 192 · 181 72171 = 38 · 11 74431 = 74 · 31 75361 = 11 · 13 · 17 · 31 78625 = 53 · 17 · 37 3 4 81289 = 13 · 37 83125 = 5 · 7 · 19 89425 = 52 · 72 · 73 6 3 3 91125 = 3 · 5 94501 = 11 · 71 98125 = 54 · 157 2 2 99541 = 13 · 19 · 31 99937 = 37 · 73 101101 = 7 · 11 · 13 · 101 4 2 2 2 105625 = 5 · 13 106641 = 3 · 17 · 41 107653 = 72 · 133 4 3 8 107811 = 3 · 11 111537 = 3 · 17 115921 = 13 · 37 · 241 116281 = 112 · 312 117325 = 52 · 13 · 192 123823 = 73 · 192 5 2 126217 = 7 · 13 · 19 · 73 128547 = 3 · 23 134113 = 73 · 17 · 23 136161 = 34 · 412 140625 = 32 · 56 142129 = 132 · 292 4 146461 = 7 · 61 162401 = 17 · 41 · 233 164025 = 3 8 · 5 2 3 172081 = 7 · 13 · 31 · 61 177331 = 7 · 11 · 47 180225 = 34 · 52 · 89 4 2 3 180625 = 5 · 17 187461 = 3 · 53 · 131 188461 = 7 · 13 · 19 · 109 2 2 2 4 189225 = 3 · 5 · 29 195625 = 5 · 313 203125 = 56 · 13 2 2 2 203401 = 11 · 41 203841 = 3 · 11 · 29 · 71 207025 = 52 · 72 · 132 2 2 211141 = 7 · 31 · 139 231601 = 31 · 241 232897 = 74 · 97 2 2 236321 = 29 · 281 239701 = 7 · 11 · 283 241129 = 73 · 19 · 37 251505 = 37 · 5 · 23 252601 = 41 · 61 · 101 253125 = 34 · 55 3 3 254221 = 11 · 191 261625 = 5 · 7 · 13 · 23 269001 = 38 · 41 4 2 278545 = 5 · 17 · 29 · 113 290521 = 7 · 11 294409 = 37 · 73 · 109 295245 = 310 · 5 306397 = 72 · 132 · 37 307051 = 472 · 139 309825 = 36 · 52 · 17 312481 = 132 · 432 314721 = 32 · 112 · 172 3 314821 = 13 · 61 · 397 319345 = 5 · 13 · 17 321201 = 32 · 89 · 401 2 2 334153 = 19 · 43 · 409 338031 = 3 · 23 · 71 340561 = 13 · 17 · 23 · 67 341341 = 7 · 112 · 13 · 31 354061 = 292 · 421 362551 = 74 · 151 378625 = 53 · 13 · 233 388125 = 33 · 54 · 23 397953 = 34 · 173

17

Table 2. (Continued) 54

· 72

398125 = · 13 399001 = 31 · 61 · 211 401841 = 34 · 112 · 41 2 4 2 405121 = 41 · 241 405769 = 7 · 13 409825 = 52 · 132 · 97 2 410041 = 41 · 73 · 137 441013 = 53 · 157 442225 = 52 · 72 · 192 2 2 444925 = 5 · 13 · 37 449065 = 5 · 19 · 29 · 163 450241 = 112 · 612 453125 = 56 · 29 453871 = 114 · 31 455625 = 36 · 54 2 2 2 462241 = 13 · 31 · 37 468391 = 7 · 11 · 79 472361 = 412 · 281 2 2 488881 = 37 · 73 · 181 494209 = 19 · 37 499681 = 7 · 13 · 172 · 19 2 2 2 2 501025 = 5 · 7 · 409 505141 = 7 · 13 · 61 511525 = 52 · 7 · 37 · 79 512461 = 31 · 61 · 271 530881 = 13 · 97 · 421 531505 = 5 · 132 · 17 · 37 8 544563 = 3 · 83 552721 = 13 · 17 · 41 · 61 554625 = 32 · 53 · 17 · 29 2 2 2 561925 = 5 · 7 · 13 · 19 566401 = 11 · 31 · 151 578125 = 56 · 37 4 2 578641 = 7 · 241 595441 = 7 · 11 · 19 · 37 600281 = 114 · 41 604513 = 72 · 132 · 73 611893 = 472 · 277 613089 = 36 · 292 3 2 2 624169 = 7 · 13 · 19 652257 = 3 · 23 · 137 656601 = 3 · 11 · 101 · 197 658801 = 11 · 13 · 17 · 271 670033 = 7 · 13 · 37 · 199 690625 = 55 · 13 · 17 4 2 4 2 693889 = 7 · 17 695871 = 3 · 11 · 71 703125 = 32 · 57 713125 = 54 · 7 · 163 714025 = 52 · 134 717025 = 52 · 23 · 29 · 43 2 748657 = 7 · 13 · 19 · 433 750541 = 11 · 31 · 71 750925 = 52 · 72 · 613 6 2 3 765625 = 5 · 7 767625 = 3 · 5 · 23 · 89 777925 = 52 · 292 · 37 2 4 2 780325 = 5 · 7 · 13 784225 = 5 · 13 · 19 · 127 793117 = 133 · 192 793881 = 3 8 · 11 2 803551 = 72 · 232 · 31 808561 = 13 · 37 · 412 2 2 2 811073 = 59 · 233 815121 = 3 · 41 · 47 815425 = 52 · 132 · 193 8 3 820125 = 3 · 5 825265 = 5 · 7 · 17 · 19 · 73 838125 = 32 · 54 · 149 838201 = 7 · 13 · 61 · 151 852841 = 11 · 31 · 41 · 61 856087 = 432 · 463 856801 = 112 · 73 · 97 860625 = 34 · 54 · 17 877825 = 52 · 13 · 37 · 73 2 4 879217 = 53 · 313 893101 = 11 · 61 894691 = 72 · 19 · 312 2 2 943041 = 3 · 11 · 17 · 41 965497 = 13 · 29 · 197 968485 = 5 · 72 · 59 · 67 5 2 970785 = 3 · 5 · 17 · 47 979837 = 79 · 157 989901 = 34 · 112 · 101 997633 = 7 · 13 · 19 · 577 1002001 = 72 · 112 · 132 1024651 = 19 · 199 · 271 1030393 = 7 · 133 · 67 1033669 = 7 · 13 · 37 · 307 1050985 = 5 · 13 · 19 · 23 · 37 1063651 = 712 · 211 4 2 2 2 1071225 = 3 · 5 · 23 1080801 = 3 · 29 · 41 · 101 1082809 = 7 · 13 · 73 · 163 2 2 3 6 1105425 = 3 · 5 · 17 1140625 = 5 · 73 1152271 = 43 · 127 · 211 1154881 = 74 · 13 · 37 1165537 = 172 · 37 · 109 1185921 = 34 · 114 3 1193221 = 31 · 61 · 631 1207845 = 3 · 5 · 23 · 389 1214869 = 592 · 349 2 2 2 4 6 1221025 = 5 · 13 · 17 1265625 = 3 · 5 1269621 = 33 · 59 · 797 1299961 = 13 · 192 · 277 1321029 = 34 · 47 · 347 1335961 = 112 · 61 · 181 2 2 2 2 1355121 = 3 · 17 · 521 1357741 = 7 · 11 · 229 1358127 = 310 · 23 4 3 2 4 1373125 = 5 · 13 1399489 = 7 · 13 1401841 = 73 · 61 · 67 2 2 2 1413721 = 29 · 41 1416521 = 71 · 281 1439425 = 52 · 13 · 43 · 103 1443001 = 74 · 601 1461241 = 37 · 73 · 541 1468125 = 34 · 54 · 29 10 2 2 2 1476225 = 3 · 5 1498861 = 7 · 13 · 181 1500625 = 5 4 · 7 4 3 6 1506625 = 5 · 17 · 709 1529437 = 7 · 13 1540081 = 172 · 732 2 2 3 1555009 = 29 · 43 1566891 = 3 · 131 · 443 1569457 = 17 · 19 · 43 · 113 3 2 2 1610401 = 13 · 733 1615441 = 31 · 41 1615681 = 23 · 199 · 353 1653125 = 55 · 232 1658385 = 32 · 5 · 137 · 269 1677025 = 52 · 72 · 372 2 2 2 2 1710325 = 5 · 37 · 43 1741825 = 5 · 19 · 193 1742221 = 134 · 61 4 2 1755625 = 5 · 53 1773289 = 7 · 19 · 67 · 199 1815937 = 972 · 193 1857241 = 31 · 181 · 331 1896129 = 3 8 · 17 2 1909001 = 41 · 101 · 461 2 2 1923769 = 19 · 73 1935025 = 52 · 17 · 29 · 157 1953433 = 792 · 313

18

Remark 2.30. Here, as always in the sequel, the Carmichael number(s) and weak Carmichael number(s) will be often denoted by CN and W CN, respectively. A computation via Mathematica 8 shows that there are “numerous” weak Carmichael numbers that are neither Carmichael numbers nor prime powers. In particular, Table 2 shows that up to 106 there are 235 weak Carmichael numbers which are not prime powers, and between them there are 43 Carmichael numbers. Moreover, up to 2 × 106 there are 298 W CN which are not prime powers, and between them there are 55 CN. Remark 2.31. It is known [58, p. 338] that a Carmichael number can be a product of two other Carmichael numbers; for example, such a number is (7 · 13 · 19)(37 · 73 · 109) = 1729 · 294409 = 509033161. It can be of interest to consider a related problem extended to the set of W CN which are not prime powers (for example, 10125 = 45 × 225, 18225 = 45 × 405 and 50625 = 45 × 1125). Examples 2.32. Notice that it is easy to determine W CN with two distinct prime factors. In [15] the authors observed that such numbers are all integers of the form 32e 5f for any e, f ≥ 1, and more generally, given any two odd primes p < q with q − 1 6≡ 0(mod p), peϕ(q−1) q f ϕ(p−1) is a W CN. For arbitrary given positive integers e and f such that e ≥ f and e + f ≥ 3, denote by Cw (e, f ) the set of all W CN of the form n = pe q f for some distinct odd primes p and q. For any odd prime p let Cw (p; e, f ) denote the set of all primes q such that pe q f ∈ Cw (e, f ). Then by Theorem 2.4, n is in Cw (e, f ) if and only if p−1 | q f −1 and q−1 | pe −1, or equivalently with p−1 | q f −1 and q−1 | pe −1, respectively. In other words, for any given odd prime q, a prime p is in Cw (q; e, f ) if and only if p − 1 | q f − 1 and q − 1 | pe − 1. For example, when e = 1 and f = 2, the above two conditions easily reduced to the condition of finding all divisors d ≥ 2 of p + 1 such that the number q := d(p − 1) + 1 is a prime. Examining this condition for primes p ∈ {3, 5, 7, 11, 13, . . . , 997} (all 168 primes less than 1000), we find 452 WCN of the form p2 q. We have verified also that into prime factorizations of these 452 numbers does not occur only primes 107, 317, 433 and 857 less than 1000, while between other 164 these primes, each of the primes 13, 73, 193, 277, 313, 397, 421, 457, 541, 613, 673, 733, 757 and 787 occur only as a non-square factor q into WCN p2 q (for example, for the first such number 13, 52 · 13 is a W CN, and for the latest between them, 787, 2632 · 787 is a W CN). Since for a given p and divisors d1 = 2 and d2 = (p + 1)/2 of p + 1, we have the candidates q1 = 2p − 1 and q2 = (p2 + 1)/2 for q, respectively. In the first case, if 2p − 1 is also a prime, we obtain that n1 = p2 (2p − 1) is a WCN. In the second case, if (p2 + 1)/2 is a prime, then p2 (p2 + 1)/2 is a WCN. Notice that it was conjectured that there are infinitely many pairs (p, 2p + 1) such that both p and 2p + 1 are primes (such a prime p is called a

19

Sophie Germain prime; AOO5384 in OEIS). A computation shows that there are many pairs (p, 2p − 1) such that both numbers p and 2p − 1 are primes (up to 103 , 104 , 105 , 106 , 107 there are 153, 1206, 9686, 82374 and 711033 such pairs, respectively, while related numbers of Sophie Germain primes are 167, 1222, 9668, 82237 and 711154 respectively). Moreover, there are many triplets (p, 2p − 1, (p2 + 1)/2) such that the all numbers p, 2p − 1 and (p2 + 1)/2 are primes (up to 103 , 104 , 105 , 106 , 107 there are 30, 180, 1113, 8029 and 58294 such triplets, respectively.) Similarly, if e = 3 and f = 1, then the corresponding conditions are equivalent to finding all divisors d ≥ 2 of p2 + p + 1 such that the number q := d(p − 1) + 1 is a prime. For example, using this condition to the primes p ∈ {3, 5, 7, 11, 13}, we obtain the following three numbers in Cw (3, 1): 73 · 19 = 6517, 113 · 71 = 94501 and 113 · 191 = 254221. A determination of some elements of Cw (2, 2) consists in finding distinct odd primes p and q such that p − 1 | q 2 − 1 and q − 1 | p2 − 1. Using this for p ∈ {3, 5, 7, 11, 13}, we get the following numbers in Cw (2, 2): 32 · 52 = 225, 52 ·72 = 1225, 52 ·132 = 4225, 72 ·132 = 8281, 72 ·172 = 14161, 112 ·312 = 116281, 112 ·412 = 203401, 112 ·612 = 450241, 132 ·292 = 142129 and 132 ·432 = 312481. For arbitrary pair (e, f ) of integers e and f with 1 ≤ e ≤ f and e + f ≥ 3, let Pw (e, f ) be a set defined as a a set of all pairs (p, q) of distinct primes p ′ and q such that pe q f ∈ Cw (e, f ). Since pe − 1 | pe − 1 whenever e | e′ , it follows that for every such a pair (e, e′ ), Pw (e′ , f ) ⊆ Pw (e, f ) holds. We conjecture that the converse statement is also true, that is, we have Conjecture 2.33. If Pw (e′ , f ′ ) = Pw (e, f ) then f = f ′ and e | e′ , or e = e′ and f | f ′ . Furthermore, for the pair (e, f ) with 1 ≤ e ≤ f and e + f ≥ 3 let Qw (e, f ) be a set defined as Qw (e, f ) = {p : p is a prime and there is a prime q = 6 p such that pe q f is a W CN or q e pf is a W CN}.

Conjecture 2.34. For arbitrary given pair (e, f ) with 1 ≤ e ≤ f and e+f ≥ 3 the set Qw (e, f ) has a density 1 with respect to the set of all primes. Finally, for every pair (e, f ) with 1 ≤ e ≤ f and e + f ≥ 3, and any odd prime q let Qw (q; e, f ) be a set defined as

Qw (q; e, f ) = {p : p is a prime such that pe q f is a W CN or q e pf is a W CN}. Conjecture 2.35. The union [

1≤e≤f <∞

is an infinite set.

Qw (q; e, f )

20

Using arguments from Examples 2.32, we immediiately obtain the following result and its corollary. Proposition 2.36. Let p and q be two odd distinct primes such that p < q and q − 1 is not divisible by p. Let u and v be the smallest positive integers for which pu ≡ 1(mod q − 1) and q v ≡ 1(mod p − 1). Then pa q b is a W CN if and only if a and b are positive integers such that u | a and v | b.

Corollary 2.37. If n = pe q f is a weak Carmichael number, then n = pde q lf is also a weak Carmichael number for all positive integers d and l.

Corollary 2.38. Let p and q be odd primes such that p < q and q − 1 is not divisible by p. Then peϕ(q−1) q f ϕ(p−1) is a weak Carmichael number for arbitrary pair of positive integers e and f . Remark 2.39. For any e ≥ 2 and a fixed prime p ≥ 3, consider the set Cw (p; e, 1) of WCN of the form pe q. Then (cf. Example 2.32) n = pe q is in WCN for some odd prime q 6= p if and only if p − 1 | q − 1 and q − 1 | pe − 1, or equivalently, q = (p − 1)s + 1 for some divisor s ≥ 2 of (pe − 1)/(p − 1) = pe−1 + pe−2 + · · · + 1. If e is even, then assuming s = 2, that is, q = 2p − 1, it follows that 2p − 1 belongs to Cw (p; e, 1) if and only if 2p − 1 is a prime. By using a “usual” heuristic argument based on the Prime number theorem that the probability that an odd integer m is a prime is 2/ log m, it follows that the “expected number” of the elements of the set Cw (e, 1) with even e is at least X X 1 1 2 ≥2 = ∞. log(2p − 1) 2(p − 1) p odd prime p odd prime (Here it is used the well known fact that the sum of reciprocals of primes diverges). The situation is somewhat complicated when e ≥ 3 is odd. Then consider the Pe−1 set of all odd primes p such that p ≡ 1(mod e). Then i=0 pi ≡ 0(mod e), and take q = e(p − 1) + 1. Then the probability that q = (p − 1)e + 1 is a prime is Pe/(ϕ(e) log(e(p − 1) + 1). Using this and the well known fact that the series p odd prime 1/p diverges, we find that the “expected number” of the elements p≡1( mod e)

that belong to the set Cw (e, 1) with odd e ≥ 3 is X X e 1 1 e < = ∞. ϕ(e) p odd prime log(e(p − 1) + 1) ϕ(e) p odd prime e(p − 1) p≡1( mod e)

p≡1( mod e)

The above considerations suggest the conjecture that Cw (e, 1) is infinite set for all e ≥ 2. This conjecture by Corollary 2.37 implies the same conjecture for all sets Cw (e, l) with e ≥ 2 and l ≥ 2. In accordance to this, some additional computations and the conjecture that for any given integer s ≥ 3, there are infinitely many CN with exactly s prime factors (cf. a stronger Conjecture 1 in [35] which asserts that this number up to x is at least x1/s+os (1) ), we give the following generalized conjecture.

21

Conjecture 2.40. Let s ≥ 2 be an arbitrary integer, and let (e1 , e2 , . . . , es ) be any fixed s-tuple of integers e1 , e2 , . . . , es with e1 ≥ e2 ≥ · · · ≥ es ≥ 1 and P s i=1 ei ≥ 3. Then there are infinitely many weak Carmichael numbers n with a prime factorization n = pe11 pe22 · · · pess , where p1 , p2 , . . . , ps are distinct odd primes. Remark 2.41. A heuristic argument suggests that for a large odd positive integer n which is neither a CN nor a prime power, the “probability” that Pϕ(n) n−1 ≡ ϕ(n)( mod n) is equal to (n − 1)/2. Consequently, the number of i=1 ri W CN in the interval [1, n] is asymptotically equal to the double harmonic sum P[n/2] 2 k=1 1/k which is ∼ 2 log n as n → ∞. Furthermore, as noticed above, the number of CN in the interval [1, n] is greater than n2/7 for sufficiently large n. Moreover, under certain (widely-believed) assumptions about the distribution of primes in arithmetic progressions, it is shown in [1, Theorem] (see also [35]) that there are n1−o(1) Carmichael numbers up to n, as had been conjectured in 1956 by Erd˝os [26] (see also [70]). On the other hand, it is known that the number of prime powers with exponents ≥ 2 (the sequence A025475 in [72]) up to x (see e.g., [40, p. 27]) is given by O(x1/2 log x) (more precisely, this number is 2x1/2 log x). These considerations suggest the following conjecture. Conjecture 2.42. The numbers of Carmichael numbers and weak Carmichael numbers in the interval [1, n] are asymptotically equal as n → ∞. From Table 1 we see that 2465 and 2821 are (the first) twin Carmichael numbers, and 62745 and 63973 are also twin Carmichael numbers in the sense of the following definition.

Definition 2.43. Two Carmichael numbers are said to be twin Carmichael numbers if there is none weak Carmichael number between them. Accordingly to the Conjecture 2.42, we can propose the following “twin Carmichael numbers conjecture” which is an immediate consequence of Conjecture 2.42. Conjecture 2.44. There are infinitely many pairs of twin Carmichael numbers. Remark 2.45. We see from Table 2 that the pairs (656601, 658801) and (658801, 670033) are consecutive twin Carmichael numbers. Remark 2.46. As noticed in Subsection 1.1, Lehmer condition implies that a composite positive integer must be square-free. This also concerns to the Giuga’s condition defined by the congruence (1.3). Moreover, all CN and kLehmer numbers are square-free (see Remark 1.2). However, from Table 2 we see that there are numerous non-square-free composite W CN. Remark 2.47. We believe that the investigation of W CN and their distribution would be more complicated than those on CN, Lehmer numbers and Giuga

22

numbers. This also concerns to the k-Lehmer numbers presented in Remark 1.2 as well as to the Giuga’s-like numbers recently investigated in [39] and [51]. We see from Table 2 that the smallest W CN with three prime distinct factors is the CN 561, and the smallest WCN with four prime distinct factors is the CN 41041. Accordingly, we propose the following curious conjecture. Conjecture 2.48. Let k be an arbitrary integer ≥ 3. Then the smallest W CN with k prime distinct factors is a CN. Remark 2.49. Under the assumption of Conjecture 2.48, every W CN less than the smallest CN with six distinct prime factors 3211197185 = 5 × 19 × 23 × 29 × 37 × 137 has at most five distinct factors.

2.3. A compuational search of weak Carmichael numbers via the function Carmichael Lambda. As noticed above, Carmichael lambda function λ(n) denotes the size of the largest cyclic subgroup of the group (Z/nZ)∗ of all reduced residues modulo n. In other words, λ(n) is the smallest positive integer m such that am ≡ 1(mod n) for all a coprime to n (Sloane’s sequence A002322 [72]). This function was implemented in Mathematica 8 as the function “Carmichael Lambda”. For a fast computation of W CN we can use this function in view of the following fact which is immediate from Theorem 2.4 and the fact that for every odd integer n = pe11 pe22 · · · pess , we have λ(n) = lcm(λ(pe11 ), λ(pe22 ), . . . , λ(pess )) with λ(pei i ) = ϕ(pei i ) = piei −1 (pi − 1) for all i = 1, 2, . . . , s. Proposition 2.50. Let n = pe11 pe22 · · · pess be an odd composite integer, and let n′ = p1 p2 · · · ps . Then n is a weak Carmichael number if and only if (2.9)

λ(n′ ) | n − 1.

Proposition 2.50 suggests the following definition introduced by Erd˝os in 1948 [25]. Definition 2.51. A positive integer n > 1 such that gcd(n, ϕ(n)) = 1 is called a K-number. Erd˝os noticed that n > 1 is a K-number if and only if n is a square-free and it is divisible by none of the products pq of two distinct primes p and q with q ≡ 1(mod p). Moreover, Erd˝os [25, Theorem] proved that the number of Knumbers less than x is ∼ xe−γ /(log log log x), where γ is the Euler’s constant. Proposition 2.50 together with Euler totient theorem and the definition of Carmichael lambda function easily gives the following result. Proposition 2.52. Let n > 2 be a K-number. Then n is odd and ndλ(n) is a weak Carmichael number for each positive integer d. In particular, for such a n, ndϕ(n) is a weak Carmichael number for each positive integer d. Furthermore, if n = p1 p2 · · · ps , then λ(n) = lcm(p1 − 1, p2 − 1, . . . , ps − 1).

23

Clearly, every Carmichael number is a K-number, and hence Proposition 2.52 immediately yields the following result. Corollary 2.53. Let n be a Carmichael number. Then both ndλ(n) and ndϕ(n) are weak Carmichael numbers for arbitrary positive integer d. Remark 2.54. For a fast search of some special “types” of W CN it can be used the condition (2.9) to make suitable codes for these purposes. For any fixed k ≥ 2, let Wk denote the set of all W CN whose prime factorizations contain exactly k primes. Further, T for positive integers a, b, c, d with a < b and c < d take Wk (a, b) = Wk [a, b], and let Wk (a, b; c, d) be the set of all elements in Wk (a, b) whose greatest prime divisor belongs to the interval [c, d]. Clearly, Wk (a, b; c, b) is a set of all elements in Wk (a, b) whose greatest prime divisor is grater than equal to c. The cardinilities of sets Wk , Wk (a, b) and Wk (a, b; c, d) are denoted by Wk , Wk (a, b) and Wk (a, b; c, d), respectively. For such a set Wk (a, b; c, d) define Pk (a, b; c, d) = {p : p is a prime with p | n for some n ∈ Wk (a, b; c, d)}, and let pk (a, b; c, d) be a prime defined as pk (a, b; c, d) = max{p : p ∈ Wk (a, b; c, d)}, and let wk (a, b; c, d) be the smallest number in Wk (a, b; c, d) which is divisible by pk (a, b; c, d). If Ck denotes the set of all Carmichael numbers whose prime factorizations contain exactly k primes, then in the same manner as above, we define the sets Ck (a, b), Ck (a, b; c, d) and related numbers Ck (a, b) and Ck (a, b; c, d) associated to Ck . Also let C(a, b) be the number of all Carmichael numbers that belong to the interval [a, b], and let P (a, b) be the number of all odd prime powers that belong to the interval [a, b]. To save the space, the set CkP (b) will be denoted by Ck (1, b) and its cardinality by Ck (b). Also let C(b) = k≥3 Ck (b) be the number of Carmichael numbers which are less than b. Similarly, we define the set Wk′ (b) consisting of all W CN in Wk (1, b) which are not CN. The cardinality of Wk′ (b) is denoted here as Wk′ (b). Denote by W ′ (b) the number of up to b which are neither CN nor prime powers; that is, Pall W CN ′ ′ W (b) = k≥2 Wk (b).

Here we present a computational search of W CN that belong to W2 , i.e., of integers n = pe q f with primes 3 ≤ p < q and some positive integers e and f . In particular, our code in Mathematica 8 for determining different sets of the form W2 (a, b; c, d) gives results presented in Table 3 (recall that all non-prime powers weak Carmichael numbers less than 2 × 106 are presented in Table 2).

24

Table 3. Numbers W2 (a, b; c, d), p2 (a, b; c, d), w2 (a, b; c, d) (all written in Table 2 without “(a, b; c, d)”), P (a, b) and C(a, b) for n < 1012 (a, b; c, d) W2 p2 w2 P (a, b) C(a, b) 6 6 2 (1, 10 ; 1, 10 ) 107 463 856087 = 43 · 463 218 43 (106 , 2 · 106 ; 1, 2 · 106 ) 25 733 1610401 = 133 · 733 65 12 total 132 283 55 (2 · 106 , 107 ; 1, 103 ) 69 937 2632033 = 532 · 937 250 50 6 7 3 4 2 (2 · 10 , 10 ; 10 , 10 ) 5 1861 6924781 = 61 · 1861 (2 · 106 , 107 ; 104 , 107 ) 0 − total 74 250 50 (107 , 108 ; 1, 103 ) 120 997 27805333 = 1672 · 997 846 150 7 8 3 4 (10 , 10 ; 10 , 10 ) 43 81390625 = 56 · 5209 (107 , 108 ; 104 , 108 ) 0 total 163 846 150 (108 , 109 ; 1, 103 ) 156 2282 391 (108 , 109 ; 103 , 104 ) 109 (108 , 109 ; 104 , 109 ) 9 total 274 2282 391 (109 , 1010 ; 1, 103 ) 211 6391 901 (109 , 1010 ; 103 , 104 ) 112 (109 , 1010 ; 104 , 1010 ) 74 total 397 6391 901 (1010 , 1011 ; 1, 103 ) 247 18069 2058 (1010 , 1011 ; 103 , 104 ) 93 10 11 4 11 (10 , 10 ; 10 , 10 ) 253 total 593 18069 2058 (1011 , 1012 ; 1, 103 ) 266 51911 4636 11 12 3 4 (10 , 10 ; 10 , 10 ) 220 (1011 , 1012 ; 104 , 1012 ) 689 total 1175 51911 4636 12 total up to 10 2808 80032 8241

Let W3′ (N) be the number of all n = pa q b r c ∈ WCN \ CN up to N with odd primes p < q < r. Using this notation and the previous notations, counting related numbers in Table, we arrived to the following table.

25

Table 4. Numbers Ck (N) and Wk′ (N) with k = 2, 3, 4, 5 and N ∈ {103 , 104 , 105 , 106, 2 · 106 }. Pairs (N, k) Ck (N ) C(N ) Wk′ (N ) W ′ (N ) (103 , 2) 1 6 6 (104 , 2) 7 22 25 (105 , 2) 16 51 70 (106 , 2) 43 107 192 (2 · 106 , 2) 55 132 243 (103 , 3) 1 0 (104 , 3) 7 3 (105 , 3) 12 18 (106 , 3) 23 68 (2 · 106 , 3) 30 89 (104 , 4) 0 0 (105 , 4) 4 1 6 (10 , 4) 19 17 (2 · 106 , 4) 23 22 (105 , 4) 0 0 6 (10 , 5) 1 0 (2 · 106 , 5) 2 0 6 total up to N = 2 · 10 55 55 243 243

For a search of W3′ (N) with N ≤ 1012 , we use a characetrization of W CN given by Theorem 2.4. The three-component Carmichael number counts, C3 (N), presented in the second column of Table 5, are taken from the Granville and Pomerance paper [35]. These counts were calculated by R. Pinch, J. Chick, G. Davies and M. Williams (cf. [22, Table 2]).

26

N

Table 5. Numbers C3 (N) and W3′ (N) with N ∈ {103 , 104 , 105, 106 , 2 · 106 , 107, 108 , . . . , 1012 }.

C3 (N ) W3′ (N )

103 1 104 7 105 12 106 23 2 · 106 30 107 47 108 84 9 10 172 1010 335 1011 590 1012 1000 1013 1858 1014 3284 1015 6083 1016 10816 1017 19539 1018 35586 1019 65309 1020 120625

0 3 18 68 89 186 413 863 1590 2866 4291

n = pa q b r c ∈ W3′ (N ) n = pqr ∈ C3′ (N ) with a maximal r with a maximal r 561 = 3 · 11 · 17 6525 = 32 · 52 · 29 8911 = 7 · 19 · 67 25425 = 32 · 52 · 113 52633 = 7 · 73 · 103 2 2 750925 = 5 · 7 · 613 530881 = 13 · 97 · 421 1269621 = 33 · 59 · 797 1193221 = 31 · 61 · 631 8927425 = 52 · 132 · 2113 8134561 = 37 · 109 · 2017 52280425 = 52 · 409 · 5113 67902031 = 43 · 271 · 5827 954036721 = 112 · 192 · 21841 962442001 = 73 · 601 · 21937 4465266751 = 113 · 71 · 47251 8863329511 = 211 · 631 · 66571 79183494081 = 34 · 173 · 198977 74190097801 = 151 · 2551 · 192601 800903953125 = 34 · 56 · 632813 921323712961 = 673 · 2017 · 678721

Remark 2.55. Notice that prime factors of every W CN n = pa q b r c in the fourth column of Table 5 besides the number 6525 satisfy the equlity r − 1 = (pa q b −1)/2. Similarly, the prime factors p, q, r of CN 561, 8911, 8134561,67902031, 962442001, 8863329511, 74190097801 and 921323712961 in the last column of Table 5 satisfy the equality r − 1 = (pq − 1)/2. Remark 2.56. Let α = α(N) denote the real number such that C3 (N) = N α , and let β = β(N) be the real number such that W3′ (N) = N β . Then from data in Table 5 we find that α(106 ) = 0.227, α(109 ) = 0.248, α(1012 ) = 0.250, α(1015 ) = 0.252 α(1018 ) = 0.253, α(1021) = 0.255, β(106 ) = 0.305 β(109 ) = 0.326 and β(1012) = 0.303. 2.4. k-Lehmer numbers and weak Carmichael numbers. Quite recently, J.M. Grau and A.M. Oller-Marc´en [37, Definition 1] weakened Lehmer property by introducing the concept of k-Lehmer numbers. For given positive integer k, a k-Lehmer number is a composite integer n such that ϕ(n) | (n − 1)k . Hence, if we denote by Lk the set Lk := {n ∈ N : ϕ(n) | (n − 1)k },

27

then k-Lehmer numbers are the composite elements of Lk . Clearly, Lk ⊆ Lk+1 for each k ∈ N, and define ∞ [ Lk . L∞ := k=1

Then it can be easily shown that (see [37, Proposition 3]) L∞ := {n ∈ N : rad(ϕ(n)) | n − 1}.

This immediately shows that if n is a Carmichael number, then n also belongs to the set L∞ ([37, Proposition 6]). This leads to the following characterization of Carmichael numbers which slightly modifies Korselt’s criterion. Proposition 2.57. A composite number n is a Carmichael number if and only if rad(ϕ(n)) | n − 1 and p − 1 | n − 1 for every prime divisor p of n. Obviously, the composite elements of L1 are precisely the Lehmer numbers and the Lehmer property asks whether L1 contains composite numbers or not. Nevertheless, for all k > 1, Lk always contains composite elements (cf. Sloane’s sequence A173703 in OEIS [72] which presents L2 ). For further radically weakening the Lehmer and Carmichael conditions see [55]. As an immediate consequence of Proposition 2.57 and Theorem 2.4 we obtain the following characterization of Carmichael numbers. Corollary 2.58. A composite number n is a Carmichael number if and only if n is a weak Carmichael number and rad(ϕ(n)) | n − 1. 2.5. Super Carmichael numbers. The fact that there are infinitely many weak Carmichael numbers suggests the following definition. Definition 2.59. A weak Carmichael number n is said to be a super Carmichael number if X (2.10) k n−1 ≡ ϕ(n) (mod n2 ), gcd(k,n)=1 1≤k≤n−1

where the summation ranges over all k such that 1 ≤ k ≤ n−1 and gcd(k, n) = 1. The following characterization of super Carmichael numbers may be useful for computational purposes. Proposition 2.60. An odd composite positive integer n > 1 is a super Carmichael number if and only if ϕ(n)/2

(2.11)

2

X i=1

ϕ(n)/2

rin−1

+n

X i=1

rin−2 ≡ ϕ(n)

(mod n2 )

where r1 < r2 < · · · < rϕ(n) are all reduced residues modulo n.

28

Here, as always in the sequel, the super Carmichael number(s) will be often denoted by SCN. Remark 2.61. Using Proposition 2.18, some computations and a heuristic argument, we can assume that the probability that a prime power ps with an odd prime p and s ≥ 2, is a SCN is equal to 1/ps . Furthermore, applying (2.11), a computation in Mathematica 8 shows that none prime power ps less than 316 P with s ≥ 2 and p ≤ p847 = 6553 is a SCN. This together with the i s identity ∞ i=s+1 1/p = 1/(p (p − 1)) X 1 (2.12) Σ1 := = 8.91952 · 10−7 . s p p odd prime s≥2 and ps ≥316

On the other hand, a computation also gives

(2.13)

∞ ∞ X X X X 1 1 1 = < 0.00016 < Σ2 : = i p p(p − 1) k2 p prime p prime i=2 k=6552 p>6553

p>6553

= ζ(2) −

6551 X k=1

1 = 0.000152381. k2

Using (2.12), (2.13) and the fact that none prime power ps less than 316 with s ≥ 2 and p ≤ p847 = 6553 is a SCN, we find that the expected number of SCN that occur in the set of all prime powers of the form ps with s ≥ 2 is Σ1 + Σ2 < 0.001525. Using the above estimate, we can propose the following conjecture. Conjecture 2.62. Let p be any odd prime. Then none prime power pf with f ≥ 2 is a super Carmichael number. Notice that by using a result of I.Sh. Slavutskii [71], it is proved in Section 4 the following result. Proposition 2.63. Let p be an odd prime greater than 3. Then a prime power pf with f ≥ 2 is a super Carmichael number if and only if the numerator of the Bernoulli number B(p2f −p2f −1 −1)(p2f −p2f −1 −pf +1) is divisible by pf +1 . Remark 2.64. Using Table 2, a computation in Mathematica 8 shows that there are none SCN less than 2 × 106 . Notice that by using Harman’s result [42] given in Subsection 1.1, it follows that the “probability” that a sufficiently large positive integer n is a CN is greater than n0.33 /n = 1/n0.67 . Using this, some “little” computations and a heuristic argument, we can assume that the “probability” that a large number n is a SCN is greater than 1/(n · n0.67 ) = 1/n1.67 . It follows that the “expected number” of CN in a large interval [1, N]

29

is greater than N X 1 1.67 n n=1

which tends to ζ(1.67) = 2.11628 as N → ∞. However, as noticed above, under certain assumptions about the distribution of primes in arithmetic progressions, it is shown in [1, Theorem] that there are x1−o(1) Carmichael numbers up to x. For this subject, see also [7]. It was also given in [65] a heuristic argument that this number is x1−ε(x) , where ε(x) = (1 + o(1)) log log log x/(log log x). This argument is supported by counts of CN mostly done in 1975 by J.D. Swift [77], in 1990 by G. Jaeschke [44], by R. Pinch [62] in 1993 and R. Pinch [63] in 2006. Accordingly, using the previous arguments, we can assume that the “probability” that a large number n is a SCN is about 1/no(1) . It follows that the “expected number” of Carmichael numbers in a very large interval [1, N] is greater than N X 1 . k k=1 P∞ This together with the fact that k=1 1/k = +∞ motivates the following conjecture. Conjecture 2.65. There are infinitely many super Carmichael numbers. Remark 2.66. A heuristic argument and considerations given in Remark 2.64 suggest that a search for SCN would be have a “chance” only between SCN. In other words, SCN “probably” can occur only between CN. Hence, we propose the following conjecture. Conjecture 2.67. Every super Carmichael number is necessarily a Carmichael number. Remark 2.68. Because of Conjecture 2.67, we have omitted the word “weak” in the name “super Carmichael number” given in Definition 2.59. Remark 2.69. In order to examine whether given CN n is also a SCN, it is natural to proceed as follows. Take n = p1 p2 · · · ps , where p1 , p2 , . . . , ps are distinct odd primes. Then by the congruence (2.11) of Proposition 2.60, with ri defined in Proposition 2.60, it follows that n is a SCN if and only if ϕ(n)/2

(2.14)

cn := 2

X i=1

ϕ(n)/2

rin−1

+n

X i=1

rin−2 − ϕ(n) ≡

(mod n2 ).

Clearly, the congruence (2.14) holds if and only if (2.15)

cn ≡ 0 (mod p2i ) for each i = 1, 2, . . . , s.

Now taking n − 1 = qi ϕ(p2i ) + li = qi pi (pi − 1) + li and n − 2 = ti ϕ(pi ) + ui = ti (pi − 1) + ui with integers qi , ti ≥ 1 and 0 ≤ li , ui ≤ pi − 1 for all

30

i ∈ {1, 2, . . . , s}. Then by Euler totient theorem and (2.15) and the fact that ϕ(p2i ) = p2i − pi , the congruence (2.14) is satisfied if and only if (2.16) ϕ(n)/2 ϕ(n)/2 X X li riui pi ≡ 0 (mod p2i ) for each i = 1, 2, . . . , s. ri + n cn (pi ) := 2 i=1

i=1

Taking mi = max{li , ui } for all i = 1, 2, . . . , s, without loss of generality we can suppose that m1 ≤ m2 ≤ · · · ≤ ms . Then we firstly verify the congruence (2.16) for i = 1. If (2.16) is not satisfied modullo p21 , then we conclude that n is not a SCN. Otherwise, we continue the computation passing to p2 etc. Of course, we finish the computation to a first index i for which cn (pi ) 6≡ (mod p2i ). If it is obtained that cn (pi ) ≡ (mod p2i ) for each i = 1, 2, . . . , k, then we conclude that n is a SCN. 2.6. Weak Carmichael numbers and the Fermat primality test. Gauss [31] (Article 329 of Disquisitiones Arithmeticae, 1801), let. 329]) wrote: The problem of distinguishing prime numbers from composite numbers is one of the most fundamental and important in arithmetic. It has remained as a central question in our subject from ancient times to this day... On October 18th, 1640 Fermat wrote, in a letter to his confidante Frenicle, that the fact that n divides 2n − 2 whenever n is prime is not an isolated phenomenon. Indeed that, if n is prime then n divides an − a for all integers n; which implies that if n doesn’t divide an − a for some integer a then n is composite. As noticed above, as “false primes” Carmichael numbers are quite famous among specialists in number theory, as they are quite rare and very hard to test. Accordingly, these numbers present a major problem for Fermat-like primality tests. Here we give some remarks on Carmichael and weak Carmichael numbers closely related to the Fermat primality test. Fermat little theorem says that if p is a prime and the integer a is not a multiple of p, then (2.17)

ap−1 ≡ 1

(mod p).

If we want to test if p is prime, then we can pick random a’s in the interval and see if the congruence holds. If the congruence does not hold for a value of a then p is composite. If the congruence does hold for many values of a, then we can say that p is “probable prime”. It might be in our tests that we do not pick any value for a such that the congruence (2.17) fails. Any a such that an−1 ≡ 1(mod n) when n is composite is called a Fermat liar. In this case n is called Fermat pseudoprime to base a. If we do pick an integer a such that an−1 6≡ 1(mod n), then a is called a Fermat witness for the compositeness of n. Clearly, a Carmichael number n is a composite

31

integer that is Fermat-pseudoprime to base a for every a with gcd(a, n) = 1. On the other hand, it is known that for “many” (necessarily even) integers n the congruence an−1 ≡ 1(mod n) is satisfied only when a ≡ 1(mod n) (this is Sloane’s sequence A111305 of “unCarmichael numbers” [72]; cf. Sloane’s A039772 [72]). For any integer n > 1 let F (n) be the set defined as F (n) = {a ∈ Z/nZ : an−1 ≡ 1 (mod n)},

and let F (n) = #F (n), that is, F (n) is a number of residues a modulo n such that an−1 ≡ 1(mod n) (F (n) is Sloane’s sequence A063994). Therefore, F (n) = #{a ∈ Z/nZ : an−1 ≡ 1(mod n)},

that is, F (n) is a number of Fermat liars for n. Clearly, F (n) is a subgroup of the multiplicative group (Z/nZ)∗ . If n = p is a prime, then F (p) = p − 1 and F (p) = (Z/pZ)∗ , i.e., F (p) is the entire group of reduced residues modulo p. The following elegant and simple formula for F (n) was established by Monier [56, Lemma 1] and Baillie and Wagstaff [6] (also see [3]): Y (2.18) F (n) = gcd(p − 1, n − 1). p|n

We also define the sequence f (n) with n ≥ 2 as F (n) Y gcd(p − 1, n − 1) = , (2.19) f (n) = ϕ(n) (p − 1)pep −1 p|n Q ep where n = p|n p .

Remark 2.70. Recall that the index of every W CN up to 26353 n presented in Table 2 denotes a related value F (n) (for example, F (26353) = 1296). Of course, F (n) = n−1 if and only if n is a prime or a CN. At the other extreme, there are infinitely many numbers n for which F (n) = 1. In particular, (2.18) immediately implies that F (2p) = 1 for every prime p. It is possible to show (see [27]) that while these numbers n with F (n) = 1 have asymptotic density 0, they are much more common than primes. The normal and average size of F (n) for n composite were studied in 1986 [27]. By Lagrange theorem, F (n) | ϕ(n) for any n. It was proved in [27, p. 263] that F (n) = ϕ(n)/k for an integer k implies λ(n) | k(n − 1), where λ(n) is the Carmichael lambda function denoting a smallest positive integer such that aλ(n) ≡ 1(mod n) for all a with gcd(a, n) = 1. Moreover, it was proved in [27, Theorem 6.6] that if k is odd or 4 | k, then there are infinitely many n with F (n) = k. If k ≡ 2(mod 4), then the equation F (n) = k has infinitely many solutions n or no solutions n depending on whether k = p−1 for some prime p. In particular, the density of the range of F is 3/4. It was also observed in [27, p. 277] that the universal exponent L(n) for the group of reduced residues a modulo n for which an−1 ≡ 1(mod n), is equal to lcm{(p − 1, n − 1) : p | n}, and that L(n) = λ(n) if and only if F (n) = ϕ(n). Moreover, F (n) | ϕ(n) for all n ≥ 2.

32

Applying Theorem 2.4 to the formula (2.18), we immediately get the following result. Proposition 2.71. A composite positive integer n is a weak Carmichael number if and only if Y (2.20) F (n) = (p − 1) p|n

where the product is taken over all primes p such that p | n. Furthermore, a composite positive integer n is a Carmichael number if and only if F (n) = ϕ(n). The equality (2.19) immediately gives Y gcd(p − 1, n − 1) Y (p − 1) Y 1 f (n) = ≤ = , (p − 1)pep −1 (p − 1)pep −1 pep −1 p|n

p|n

p|n

whence we have the following result. Corollary 2.72. Let n > 1 be a positive integer. Then Y 1 , f (n) ≤ pep −1 p|n

where equality holds if and only if n is a weak Carmichael number. Of course, it can be of interest to consider the function f (n) restricted to the set of positive integers which are not CN. For this purpose, we will need the following definition. Definition 2.73. Let k ≥ 2 be a positive integer. An integer n = p1 p2 · · · ps > 1 with odd primes p1 , p2 , . . . , ps and s ≥ 2, is said to be an almost Carmichael number of order k if the following conditions are satisfied: (i) pj − 1 | k(n − 1) for a fixed j ∈ {1, 2, . . . , s}, (ii) n − 1 is divisible by m(pj − 1) for none m ∈ {1, . . . , k − 1} and (iii) pi − 1 | n − 1 for all i ∈ {1, 2, . . . , s} such that i 6= j.

Remark 2.74. A computation shows that there exist “numerous” almost Carmichael numbers of order 2. First notice that a product pq of two distinct odd primes p and q with p < q is an almost Carmichael number of order 2 if and only q = 2p − 1. Recall that such a p is a Sophie Germain-type prime. Namely, if both p and 2p + 1 are primes, then p is called a Sophie Germain prime, and it was conjectured that there are infinitely many Sophie Germain primes. Notice that this conjecture as well as the conjecture that there are infinitely many primes p such that 2p − 1 is also a prime, are particular cases of a more general Prime-k-tuples conjecture due to Dickson in 1904 (see e.g., [68, p. 250]). Furthermore, Mathematica 8 gives numerous “three-component” almost Carmichael numbers of order 2 in the set {n : n = qi qj qk and 2 ≤ i < j < k ≤ 1000}.

33

Proposition 2.71, Corollary 2.72 and the formula (2.19) easily yield the following result. Proposition 2.75. The following assertions about a composite positive integer n are true. (i) f (n) ≤ 1, and equality holds if and only if n is a Carmichael number. (ii) If n is not a Carmichael number, then f (n) ≤ 1/2 and equality holds if and only if n is an almost Carmichael number of order 2. (iii) If n is neither a Carmichael number nor an almost Carmichael number of order 2, then f (n) ≤ 1/3 and equality holds if and only if n is an almost Carmichael number of order 3 or n is a weak Carmichael number with the prime factorization n = 32 p2 · · · ps , where 3 < p2 < · · · < ps are odd primes. Remark 2.76. If n is a composite integer which is not CN, then by (ii) of Proposition 2.75 we have ϕ(n) n−1 (2.21) F (n) ≤ ≤ . 2 2 This shows that for such a n, at least half of the integers a in the interval [1, n − 1] are Fermat liars for n (the so-called false witnesses for n [27]). These facts lead to the folowing test: given a positive integer n, pick k different positive integers less than n and perform the Fermat primality test on n for each of these bases; if n is composite and it is not a Carmichael number, then the probability that n passes all k tests is less than 1/2k . Remark 2.77. Let WCN 3 denote the set of all W CN of the form n = 32 p2 · · · ps , where 3 < p2 < · · · < ps are odd primes. (cf. (iii) of Proposition 2.75). It is easy to see 45 = 32 · 5 is the only number in the set WCN 3 whose prime factorization contains only one prime greater than 3. From Table 2 we see that up to 2 · 106 there are still six numbers belonging to the set WCN 3 ; these numbers are 13833 = 32 · 29 · 53, 203841 = 32 · 11 · 29 · 71, 321201 = 32 · 89 · 401, 1080801 = 32 · 29 · 41 · 101 and 1658385 = 32 · 5 · 137 · 269. A computation shows that {9m : m = pq with p and q primes such that 3 < p < q < 105 }∩WCN 3 = Φ.

Furthermore, if qk denotes the kth prime, then the set {9m : m = qi qj qk and 2 ≤ i < j < k ≤ 1000} contains the following five numbers of the set WCN 3 which are greater than 2 · 106 : 8074881 = 32 · 17 · 89 · 593, 19678401 = 32 · 17 · 41 · 3137, 95682861 = 32 · 29 · 53 · 6917, 359512011 = 32 · 23 · 467 · 3719 and 1955610801 = 32 · 53 · 1433 · 2861. Remark 2.78. If n is a CN, then as noticed above F (n) = ϕ(n). Erd˝os and Pomerance [27, Section 6] conjectured that not only are there infinitely many CN, but that F (n) lim sup = 1. n n composite

34

Notice that by [27, the estimate (2.8)], we have that F (n)/n1−ε is unbounded on the composites for any ε > 0. On the other hand, by [27, Theorem 6.1], F (n) log2 n > 0. n n composite lim sup

A computation (cf. Remark 2.77) suggests the following conjecture. Conjecture 2.79. Let WCN 3 denote the set of all weak Carmichael numbers described in Remark 2.77. Then lim sup n∈WCN 3

1 F (n) = . n 3

3. Proofs of Propositions 2.3, 2.60, 2.63 and Corollary 2.20 Proof of Proposition 2.3. Clearly, ϕ(n) is even for each n ≥ 3, and the set Rn can be presented as (3.1)

Rn = {r1 , r2 , . . . , rϕ(n)/2 , n − r1 , n − r2 , . . . , n − rϕ(n)/2 }.

Using (3.1) we find that

(3.2)

X

gcd(k,n)=1 1≤k≤n−1

ϕ(n)

k

n−1

≡

X

ϕ(n)/2

rin−1

=

i=1

X i=1

(rin−1 + (n − ri )n−1 ).

If n is odd, the right hand side of (3.2) is ϕ(n)/2

≡

X

(rin−1 + (−ri )n−1 )

(mod n) = 0

(mod n).

i=1

Hence, every weak Carmichael number must be odd. Finally, if n is odd, using (3.2), we have (3.3) ϕ(n)/2 ϕ(n)/2 ϕ(n) X X X X n−1 n−1 n−1 n−1 rin−1 (mod n). (ri + (n − ri ) ) ≡ 2 ri = k = gcd(k,n)=1 1≤k≤n−1

i=1

i=1

This together with Definition 2.1 concludes the proof.

i=1

35

Proof of Proposition 2.60. Applying the binomial formula and using the assumption that n is an odd composite integer, we find that X

ϕ(n)

k

n−1

X

=

ϕ(n)/2

rin−1

=

i=1

gcd(k,n) 1≤k≤n−1

(rin−1 + (n − ri )n−1 )

i=1

ϕ(n)/2 ϕ(n)/2 X X n−1 n−2 n ri + − rin−1 1 i=1 i=1

ϕ(n)/2

X

≡

X

rin−1

i=1

ϕ(n)/2

ϕ(n)/2

=2

X

(mod n2 )

rin−1

X

+n

rin−2 ≡ ϕ(n) (mod n2 ).

i=1

i=1

This completes the proof.

Proof of Corollary 2.20. Given product n = pq with primes q < p, using Fermat little theorem, the sum on the left right hand side of (2.8) in Definition 2.2 is X

S(p, q) : =

k

pq−1

q−1 (j+1)p−1 X X

=

j=0 i=jp+1

gcd(k,pq)=1 1≤k≤pq−1

=

q−1 (j+1)p−1 X X

pq−1

i

j=0 i=jp+1

−q

(3.4)

X

=q

p−1 X

i=1

ipq−1 − q pq−1 (p−1)q+(q−1)

i

i=1

X i=1

spq−1

s≡0( mod q) 1≤s≤p−1

ipq−1

i=1

X

ipq−1

(mod p)

i=1

−q

(p−1)q+(q−1)

p−1 X

i(p−1)q+(q−1)

i=1

p−1

p−1

≡q

p−1 X

X

p−1

p−1

≡q

pq−1

ipq−1 −

iq−1 − q q−1

= q(1 − q

q−2

)

p−1 X

X

iq−1

(mod p)

i=1

iq−1

(mod p).

i=1

Let a be a generator of the multiplicative unit group of Z/pZ. Then since q − 1 < p − 1 it follows easily that the set {1q−1, 2q−1 , . . . , (p − 1)q−1} regarding modulo p conicides with the set Z∗p = {1, 2, . . . , p − 1} of all nonzero residues modulo p. This shows that (3.5)

p−1 X i=1

q−1

i

≡

p−1 X i=1

i

(mod p) =

(p − 1)p ≡ 0 (mod p). 2

36

Taking (2.16) into (2.15), we immediately get S(p, q) ≡ 0 (mod p).

(3.6) (3.7)

X

S(p, q) :=

gcd(k,pq)=1 1≤k≤pq−1

k pq−1 ≡ 0 (mod p).

Since ϕ(n) = (p − 1)(q − 1) ≡ 1 − q(mod p) from (2.18) we have X (3.8) k pq−1 − ϕ(pq) ≡ q − 1 (mod p), gcd(k,pq)=1 1≤k≤pq−1

In view of the fact that q < p, we conclude that the expression on the left hand side of (2.19) is not divisible by p. Theefore, n = pq is not a Carmichael number, and the proof is completed. Proof of Proposition 2.63. Using Euler totient theorem, we have (3.9)

X

kp

f −1

1≤k≤pf −1 (k,p)=1

≡

X

1≤k≤pf −1 (k,p)=1

1 k p2f −p2f −1 −pf +1

(mod p2f ).

By the congruence (6) in [71], it follows that if s in an even positive integer and t = (ϕ(p2f ) − 1)s then (3.10)

X

1≤k≤pf −1 (k,p)=1

1 k

p2f −p2f −1 −pf +1

≡ pf Bt

(mod p2f )

where (3.11) t = (ϕ(p2f ) − 1)(p2f − p2f −1 − pf + 1) = (p2f − p2f −1 − 1)(p2f − p2f −1 − pf + 1) Comparing (3.10) and (3.11) gives X f (3.12) k p −1 ≡ pf Bt

(mod p2f )

1≤k≤pf −1 (k,p)=1

with t given by (3.12). Notice that by von Staudt-Clausen’s theorem, the denominator Dt of Bernoulli number Bt = Nt /Dt is the product of all primes p such that p − 1 divides t. In particular, this shows that p k Dt . From this P f and the congruence (3.13) we conclude that 1≤k≤pf −1 k p −1 is divisible by p2f (k,p)=1

if and only if Nt is divisible by pf +1 .

37

4. Proof of Theorem 2.4 and Corollary 2.17 Proof of Theorem 2.4 is based on the following three auxiliary results. Lemma 4.1. Let pe be a power of an odd prime p, and let me be a positive integer such that m is not divisible by p − 1. Then X k m ≡ 0 (mod pe ). (4.1) 1≤k≤pe −1 gcd(k,p)=1

Proof. Let a be a primitive root modulo pe . Then am is not divisible by p. Moreover, it is easy to see that the set {aj : 1 ≤ j ≤ pe − 1 and gcd(j, p) = 1} reduced modulo pe coincides with the set of all residues modulo pe which are relatively prime to p. This shows that X X X k m (mod pe ), (ak)m ≡ km = am 1≤k≤ps −1 gcd(k,p)=1

1≤k≤pe −1 gcd(k,p)=1

1≤k≤pe −1 gcd(k,p)=1

whence it follows that (am − 1)

X

1≤k≤pe −1 gcd(k,p)=1

k m ≡ 0 (mod pe ).

This together with the assumption that am 6≡ 1(mod pe ) immediately yields the desired congruence (4.1). Lemma 4.2. Let n > 1 be a positive integer with a prime factorization n = pe11 pe22 · · · pess where s ≥ 2. Let R be a set of positive integers less than n and relatively prime to n. For any fixed i ∈ {1, 2, . . . , s} set R(pei i ) = {a ∈ N : 1 ≤ a ≤ pei i

and

gcd(a, pi ) = 1}.

For all pairs (i, j) with i ∈ {1, 2, . . . , s} and j ∈ R(pei i ) define the set Aij as Aij = {a ∈ R : a ≡ j(mod pei i )}.

Then for any i ∈ {1, 2, . . . , s} Y e n (4.2) |Aij | = ϕ ei = (pl l − pel l −1 ) f or all pi 1≤l≤s

j ∈ R(pei i ),

l6=i

where |S| denotes the cardinality of a finite set S. Proof. Clearly, it suffices to show that (4.2) is satisfied for i = 1. Then for any fixed j ∈ R(pe11 ) consider the set n Tj = {j + rpe11 : r = 0, 1, . . . , e1 − 1(= pe22 · · · pess − 1)}. p1 e1 n Since for each t ∈ Tj , j ≤ t ≤ j + p1 pe1 − 1 ≤ n − 1, it follows that the 1 set A1j actually consists of these elements in Tj that are relatively prime to n/pe11 . Notice that the set Tj reduced modulo n/pe11 coincides with the set

38

{0, 1, 2, . . . , n/pe11 − 1} of all residues modulo n/pe11 ; namely, if j + r1 pe11 ≡ j + r2 pe11 (mod n/pe11 ) with 0 ≤ r1 < r2 ≤ n/pe11 − 1, then n/pe11 | (r2 − r1 )pe11 , and so, n/pe11 | (r2 − r1 ) which is impossible because of 1 ≤ r2 − r1 ≤ n/pe11 − 1. This shows that the set A1j contains exactly ϕ(n/pe11 ) elements, which is equal to (pe22 − pe22 −1 ) · · · (pess − pess −1 ). This completes the proof. Lemma 4.3. Let n and e be positive integers and let p be a prime such that pe | n and p − 1 | n − 1. Then k n−1 ≡ k p

(4.3)

e−1 −1

(mod pe )

for every integer k that is not divisible by p. Proof. Take n = pe n′ with an integer n′ . Then from the assumption p−1 | n−1 it follows that n′ ≡ 1(mod (p − 1)), and therefore n − 1 = pe n′ − 1 ≡ pe−1 − 1 (mod pe−1 (p − 1)).

If k is not divisible by p, then from the above congruence, the fact that ϕ(pe ) = e−1 pe−1 (p − 1) and Euler totient theorem, we have k p −1 ≡ k n−1 ( mod pe ) which immediately implies (4.3). Lemma 4.4. Let n > 1 be a positive integer with a prime factorization n = pe11 pe22 · · · pess . For any fixed i ∈ {1, 2, . . . , s}, set R(pei i ) = {a ∈ N : 1 ≤ a ≤ pei i

and

gcd(a, pi ) = 1}.

Then for every i ∈ {1, 2, . . . , s} there holds X X n n−1 k n−1 (4.4) k ≡ ϕ ei pi ei gcd(k,n)=1

(mod pei i ).

k∈R(pi )

1≤k≤n−1

If in addition, pi − 1 | n − 1 for some i ∈ {1, 2, . . . , s}, then X X ei −1 n n−1 (4.5) k ≡ ϕ ei k pi −1 (mod pei i ). pi ei gcd(k,n)=1 k∈R(pi )

1≤k≤n−1

Proof. Consider the set R of all reduced residues modulo n that are relatively prime to n, i.e., R = {k : 1 ≤ k ≤ n − 1 and gcd(k, n) = 1}.

Let i ∈ {1, 2, . . . , m} be any fixed. For each j ∈ R(pei i ) take Aij = {a ∈ R : a ≡ j(mod pei i )}.

Then by Lemma 4.2, (4.6)

|Aij | = ϕ

n pei i

for all j ∈ R(pei i ).

39

Furthermore, using (4.3) and (4.1) of Lemma 4.1 with s = n − 1, we have X X X X k n−1 = k n−1 = k n−1 e

k∈R

gcd(k,n)=1 1≤k≤n−1

≡ϕ

j∈R(pi i ) k∈Aij

n pei i

X

k n−1

(mod pei i ).

e

k∈R(pi i )

The above congruence implies (4.4). Finally, if pi − 1 | n − 1 then substituting (4.3) of Lemma 4.3 with pei i instead of pe into (4.4) we immediately obtain (4.5). Lemma 4.5. Let n be a composite positive integer with the prime factorization n = pe11 · · · pess . For any fixed i ∈ {1, 2, . . . , s} take R(pei i ) = {a ∈ N : 1 ≤ a ≤ pei i

and

gcd(a, pi ) = 1}.

Then n is a weak Carmichael number if and only if for every i ∈ {1, 2, . . . , s} there holds X n e −1 n−1 (4.7) k + pi i ϕ ei ≡ 0 (mod pei i ). pi ei k∈R(pi )

Proof. Clearly, n = pe11 · · · pess is a weak Carmichael number if and only if (2.2) is satisfied modulo pei i for all i = 1, . . . , s which is by (4.3) of Lemma 4.3 (4.4) of Lemma 4.4 equivalent to the congruence X n (4.8) ϕ ei k n−1 ≡ ϕ(n) (mod pei i ). pi ei k∈R(pi )

Since ϕ(n) = (pei i − piei −1 )ϕ(n/pei i ) ≡ −pei i −1 ϕ(n/pei i )(mod pei i ), substituting this into (4.8), we immediately obtain (4.7). Lemma 4.6. Let p ≥ 3 be a a prime and let e ≥ 2 be a positive integer. Define R(pe ) = {a ∈ N : 1 ≤ a ≤ pe

and

gcd(a, p) = 1}.

Then (4.9)

X

k∈R(pe )

pe −1

k

pe−1 −1

≡

X

kp

e−1 −1

(mod pe ).

k=1

Proof. From the obvious inequality pe−1 − 1 ≥ e with p ≥ 3 and e ≥ 2 we see that every term in the sum on the right hand side of (4.9) that is divisible by p is also divisible by pe . This yields the desired congruence (4.9). The following congruence is known as a Carlitz-von Staudt’s result [16] in 1961 (for an easier proof see [57, Theorem 3]).

40

Lemma 4.7. Let p ≥ 3 be a a prime and let e and l be positive integers such that p − 1 does not divide l. Then X (4.10) k l ≡ 0 (mod pe ). k∈R(pe )

Proof. By a particular case of a result obtained in 1955 by H.J.A. Duparc and W. Peremans [23, Theorem 1] (cf. [71, Corollary 2] or [52, the congruence (58) in Section 8]), if r is a positive integer such that p − 1 does not divide r, then X 1 ≡ 0 (mod pe ). (4.11) r k e k∈R(p )

Letting r = ϕ(pe ) − l = pe − pe−1 − l in (4.11) and then applying Euler totient theorem modulo pe , we immediately obtain (4.10). Lemma 4.8. ([16], [57, Theorem 3]) Let l and m ≥ 2 be positive integers. Then m−1 X 0 P (mod (m−1)m ) if l is odd l 2 (4.12) Sl (m) := i ≡ − (p−1)|l,p|m mp (mod m) if l is even i=1

where the summation is taken over all primes p such that (p − 1) | l and p | m.

Proof of Theorem 2.4. First assume that n = pe11 pe22 · · · pess is a composite integer such that pi − 1 | n − 1 for all i = 1, 2, . . . , s. Then by Lemma 4.5 n is a weak Carmichael number if for every i ∈ {1, 2, . . . , s} there holds X (4.13) k n−1 + piei −1 ≡ 0 (mod pei i ). e

k∈R(pi i )

For any fixed i ∈ {1, 2, . . . , s} consider two cases: ei = 1 and ei ≥ 2. Case 1. ei = 1. Then since n − 1 ≡ 0(mod (p − 1)), using Fermat little theorem, we obtain (4.14)

X

pi −1

k

n−1

+

p1−1 i

=

X k=1

k∈R(pi )

k n−1 + 1 ≡ (pi − 1) + 1 ≡ 0 (mod pi ).

Therefore, (4.13) is satisfied. Case 2. ei ≥ 2. Then using (4.3) of Lemma 4.3 and (4.10) of Lemma 4.7, with the notations of Lemma 4.4, for any fixed i ∈ {1, 2, . . . , s} we have X X ei −1 k pi −1 (mod pei i ) k n−1 ≡ e

e

(4.15)

k∈R(pi i )

k∈R(pi i )

e

pi i −1

≡

X k=1

ei −1 −1

k pi

(mod pei i ).

41

Furthermore, by the second congruence of (4.12) of Lemma 4.8 (cf. [38, Lemma 1]), we immediately get e

pi i −1

(4.16)

X

ei −1 −1

k pi

≡−

k=1

pei i = −pei i −1 pi

(mod pei i ).

Comparing (4.15) and (4.16) immediately gives (4.13), and therefore, n is a weak Carmichael number. Conversely, suppose that n is a weak Carmichael number with a prime factorization n = pe11 · · · pess where p1 , . . . , ps are odd primes. Suppose that for some i ∈ {1, 2, . . . , s}, n − 1 is not divisible by pi − 1. Then by (4.10) of Lemma 4.7, we have X (4.17) k n−1 ≡ 0 (mod pe ). e

k∈R(pi i )

Substituting (4.17) in (4.7) of Lemma 4.5, we get n ei −1 (4.18) pi ϕ ei ≡ 0 (mod pei i ), pi or equivalently, (4.19)

ϕ

n pei i

≡ 0 (mod pi ).

The above congruence implies that pi |

Q

e −1

1≤j≤s j6=i

pi | pj − 1 for some j 6= i. We can choose such a pi to be maximal, i.e.,

pj j

(pj − 1). It follows that

pi = max {pt : n − 1 6≡ 0 (mod pt − 1)}. 1≤t≤s

Then, as it is proved previously, we must have pi | pj − 1 for some j 6= i. It follows that pi < pj , and hence, by the maximality of pi we conclude that pj − 1 | n − 1. Therefore, pi | n − 1, which is impossible because of pi | n. A contradiction, and hence n − 1 is divisible by pi − 1 for each i = 1, 2, . . . , s. This completes the proof of Theorem 2.4. Proof of Corollary 2.17. If n is a weak Carmichael number that is not Carmichael number, then µ(n) = 0, and hence the congrueence in Corollary 2.17 reduced to the congruence (2.2). Conversely, if n > 1 satisfies the congruence X (4.20) k n−1 ≡ ϕ(n) + µ(n) (mod n), gcd(k,n)=1 1≤k≤n−1

42

then consider two cases: 1) n is not square-free and 2) n is square-free. In the first case (4.20) becomes X (4.21) k n−1 ≡ ϕ(n) (mod n), gcd(k,n)=1 1≤k≤n−1

whence using Theorem 2.4 we conclude that n is a weak Carmichael number. In the second case, we have µ(n) = ±1, and then (4.20) becomes X (4.22) k n−1 ≡ ϕ(n) ± 1 (mod n). gcd(k,n)=1 1≤k≤n−1

In view of Corollary 2.16, the above congruence shows that n is not a weak Carmichael number. Then by Theorem 2.4 there exists a prime factor p of n such that p − 1 does not divide n − 1. Asuume that n = pe n′ with n′ such that p does not divide n. Then applying (4.4) and Fermat little theorem, we find that X X n n−1 k n−1 (mod p) k ≡ϕ e p gcd(k,n)=1 k∈R(pe ) (4.23) 1≤k≤n−1 n n e ≡ ϕ e |R(p )| = ϕ e ϕ(pe ) = ϕ(n) (mod p). p p Substituting the congruence (4.23) into (4.22) reduced modulo p, we obtain 0 ≡ ±1(mod p). A contradiction, and hence, n is a weak Carmichael number which is not a Carmichael number. This concludes the proof. References [1] W.R. Alford, A. Granville and C. Pomerance, There are infinitely many Carmichael numbers, Ann. of Math. 139 (1994), 703–722. [2] W.R. Alford, J. Grantham, S. Hayman and A. Shallue, Constructing Carmichael numbers through improved subset-product algorihms, to appear in Math. Comp.; preprint arXiv:1203.6664v1 [math.NT], March 2012. [3] W.R. Alford, A. Granville and C. Pomerance, On the difficulty of finding reliable witnesses, Algorithmic number theory (Ithaca, NY, 1994), Lecture Notes in Comput. Sci. vol. 877, Springer, Berlin, 1994, 1994, pp. 1–16. [4] T. Agoh, On Giuga’s conjecture, Manuscripta Math. 87 (1995), 501–510. [5] R. Balasubramanian and S.V. Nagaraj, Density of Carmichael numbers with three prime factors, Math. Comp. 66 (1997), 1705–1708. [6] R. Baillie and S.S. Wagstaff, Jr., Lucas pseudoprimes, Math. Comp. 35 (1980), 1391– 1417. [7] W.D. Banks and C. Pomerance, On Carmichael numbers in arithmetic progressions, J. Aust. Math. Soc. 88 (2010), 313–321. [8] A.F. Beardon, Sums of powers of integers, Amer. Math. Monthly 103 (1996), 201–213. [9] E. Bedocchi, Nota ad una congettura sui numeri primi, Riv. Mat. Univ. Parma 11 (1985), 229–236. [10] J. Bernoulli, Ars Conjectandi, Basel, 1713.

43

[11] C.B. Boyer, Pascal’s formula for the sums of powers of the integers, Scripta Math. 9 (1943), 237–244. [12] P.S. Bruckman, Problem, Amer. Math. Monthly 92 (1985), p. 434. [13] D. Borwein, J.M. Borwein, P.B. Borwein and R. Girgensohn, Giuga’s conjecture on primality, Amer. Math. Monthly 103 (1996), 40–50. [14] J.M. Borwein, M. Skerritt and C. Maitland, Computation of an improved lower bound to Giuga’s primality conjecture, preprint 2013, http://www.carma.newcastle.edu.au/jon/. [15] J.M. Borwein and E. Wong, A survey of results relating to Giuga’s conjecture on primality, Proceedings of the 25th Anniversary Conference of the Centre de R´echerches Math´ematiques, CECM Preprint Series, 95-035:1–23, 1995; available at http://discerver.carma.newcastle.edu.au/101/. [16] L. Carlitz, The Staudt-Clausen theorem, Math. Mag. 34 (1960/1961), 131–146. [17] R.D. Carmichael, Note on a new number theory function, Bull. Amer. Math. Soc. 16 (1910), No. 5, 232–238. [18] R.D. Carmichael, On composite numbers P which satisfy the Fermat congruence aP −1 ≡ 1(mod P ), Amer. Math. Monthly 19 (1912), 22–27. [19] J. Chernick, On Fermat’s simple theorem, Bull. Amer. Math. Soc. 45 (1939), 269–274. [20] T. Clausen, Lehrsatz aus einer Abhandlung u ¨ber die Bernoullischen Zahlen, Astron. Nach. 17 (1840), 351–352. [21] L.E. Dickson, A new extension of Dirichlet’s theorem on prime numbers, Messenger of Mathematics 33 (1904), 155–161. [22] H. Dubner, Carmichael numbers of the form (6m + 1)(12m + 1)(18m + 1), J. Integer Seq. 5 (2002), Article 02.2.1. [23] H.J.A. Duparc and W. Peremans, On theorems of Wolstenholme and Leudesdorf, Koninkl. Nederl. Akademie Van Wetenschappen-Amsterdam. Reprinted from Proceedings knaw Series A, 58 (1955), No. 4 and Indag. Math. 17 (1955), 459–465. [24] A.W.F. Edwards, A quick route to sums of powers, Amer. Math. Monthly 93 (1986), 451–455. [25] P. Erd˝ os, Some asymptotic formulas in number theory, J. Indian Math. Soc. (N.S.) 12 (1948), 75–78. [26] P. Erd˝ os, On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen 4 (1956), 201–206. [27] P. Erd˝ os and C. Pomerance, On the numbers of false witnesses for a composite number, Math. Comp. 46 (1986), 259–279. [28] P. Erd˝ os, C. Pomerance and E. Schmutz, Carmichael’s lambda function, Acta Arith. 58 (1991), 363–385. [29] Everet W. Howe, Higher-order Carmichael numbers, Math. Comp. 69 (2000), 1711– 1719. [30] J. Faulhaber, Academia Algebrae, Darinnen die miraculosische Inventiones zu den h¨ ochsten Cossen weiters continuirt und profitiert werden, Augspurg, bey Johann Ulrich Sch¨ onigs, 1631. [31] C. F. Gauss, Disquisitiones Arithmeticae, Fleischer, Leipzig, 1801 (translated into English by A. C. Clarke, New Haven, CT: Yale University Press, 1966.) [32] G. Giuga, Su una presumibile propriet` a caratteristica dei numeri primi, Ist. Lombardo Sci. Lett. Rend. A 83 (1950), 511–528. [33] R.L. Graham, D.E. Knuth and O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley Publishing Company, 1989. [34] A. Granville, It is easy to determine whether a given integer is prime, Bull. Amer. Math. Soc. 42, (2004), No. 1, 3–38.

44

[35] A. Granville and C. Pomerance, Two contradictory conjectures concerning Carmichael numbers, Math. Comp. 71 (2001), 883–908. [36] J.M. Grau and A.M. Oller-Marc´en, Generalizing Giuga’s conjecture; preprint arXiv:1103.3483v1 [math.NT], March 2011. [37] J.M. Grau and A.M. Oller-Marc´en, On k-Lehmer numbers, Integers 12 (2012), No. A37, 9 pages. Pn [38] J.M. Grau and A.M. Oller-Marc´en, About the congruence k=1 k f (n) ≡ 0(mod n), submitted. [39] J.M. Grau, F. Luca and A.M. Oller-Marc´en, On a variant of Giuga numbers, Acta Math. Sin. (Engl. Ser.) 28, No. 4 (2012), 653–660; preprint arXiv:1103.3428v1 [math.NT], March 2011. [40] G.H. Hardy, Ramanujan: Twelve Lectures on Subject Suggested by His Life and Works, 3rd ed., Chelsea, 1999. [41] G.H. Hardy and E.M. Wright, An Introduction to the Theory of Numbers, Clarendon Press, Oxford, 1979. [42] G. Harman, On the number of Carmichael numbers up to x, Bull. London Math. Soc. 37 (2005), 641–650. [43] G. Harman, Watt’s mean value theorem and Carmichael numbers, Int J. Number Theory 4 (2008), 241–248. [44] G. Jaeschke, The Carmichael numbers up to 1012 , Math. Comp. 55 (1990), 383–389. ¨ [45] B.C. Kellner, ‘Uber irregul¨ are Paare h¨ oherer Ordnungen’, http://www.bernoulli.org/ebk/irrpairord.pdf, 2002. [46] B.C. Kellner, The equivalence of Giuga’s and Agoh’s conjectures; preprint arXiv:math/0409259v1 [math.NT], 2004. [47] A. Korselt, Probl`eme chinois, L’interm´ediaire des mathematiciens 6 (1899), 142–143. [48] D.H. Lehmer, On Euler’s totient function, Bull. Amer. Math. Soc. 38 (1932), No. 10, 745–751. [49] G. L¨ oh and G. Niebuhr, A new algorithm for constructing large Carmichael numbers, Math. Comp. 65 (1996), 823–836. [50] F. Luca and C. Pomerance, On composite integers n for which ϕ(n) | n − 1, Bol. Soc. Mat. Mexicana 17 (2011), 13–21. [51] F. Luca, C. Pomerance and I. Shparlinski, On Giuga numbers, Int. J. Mod. Math. 4 (2009), 13–18. [52] R. Meˇstrovi´c, Wolstenholme’s theorem: Its Generalizations and Extensions in the last hundred and fifty years (1862–2012); preprint arXiv: 0911.4433v3 [math.NT], December 2011. [53] R. Meˇstrovi´c, A congruence modulo n3 involving two consecutive sums of powers and its applications; prprint arXiv: 1211.15470 [math.NT], November 2012. [54] R. Meˇstrovi´c, Some identities in commutative rings with unity and their applications applications, 11 pages, submitted in Bull. Korean Math. Soc. [55] N. Mcnew, Radically weakening the Lehmer and Carmichael conditions; preprint arXiv:1210.2001v1 [math.NT], October 2012. [56] L. Monier, Evaluation and comparison of two efficient probabilistic primality testing algorithms, Theoret. Comput. Sci. 12, No. 1 (1980), 97–108. [57] P. Moree, A top hat for Moser’s four mathemagical rabbits, Amer. Math. Monthly 118 (2011), 364–370. [58] O. Ore, Number Theory and its History, McGraw-Hill New York, 1948. [59] H. Pan and Z.-W. Sun, New identities involving Bernoulli and Euler polynomials, J. Combin. Theory Ser. A 113 (2006), 156–175.

45

[60] B. Pascal, Sommation des puissances num´erique , in Oeuvres complet`e s, vol. III, Jean Mesnard, ed., Descl´ee-Brouwer, Paris, 1964, 341–367; English translation by A. Knoebel, R. Laubenbacher, J. Lodder, and D. Pengelley, Sums of numerical powers, in Mathematical Masterpieces: Further Chronicles by the Explorers, Springer-Verlag, New York, 2007, 32–37. [61] R.G.E. Pinch, A note on Lehmers totient problem, Poster presented in ANTS VII, http://www.math.tu.-berlin.de/kant/ants/Poster/PinchPoster3.pdf, 2006. [62] R.G.E. Pinch, The Carmichael numbers up to 1015 Math. Comp. 61 (1993), 381–391 (Lehmer memorial issue). [63] R.G.E. Pinch, The Carmichael numbers up to 1018 ; preprint arXiv:math/0604376v1 [math.NT], 2006; www.chalcedon.demon.co.uk/rgep/carpsp.html [64] C. Pomerance, On composite n for which φ(n) | n − 1, Pacific J. Math. 69 (1977), 177–186. [65] C. Pomerance, On the distribution of pseudoprimes, Math. Comp. 37 (1981), 587–593. [66] C. Pomerance, Two methods in elementary number theory, Number Theory and Applications (Banff, 1988; R.A. Mollin, ed.) NATO Adv. Sci. Ser. C 265 (1989), 135–161. [67] C. Pomerance, J.L. Selfridge and Samuel S. Wagstaff, The pseudoprimes to 25 · 109 , Math. Comp. 35, No. 151 (1980), 1003–1026. [68] P. Ribenboim, 13 The Little Book of Bigger Primes, second edition, Springer-Verlag, New York, 2004. [69] J. S´ andor and B. Crstici, Handbook of Number Theory II, Kluwer Academic Publishers, Dordrecht, 2004. [70] D. Shanks, Solved and unsolved problems in number theory, 3rd ed., Chelsea, New York, 1985. [71] I.Sh. Slavutskii, Leudesdorf’s theorem and Bernoulli numbers, Arch. Math. (Brno) 35 (1999), 299–303. [72] N.J. Sloane, The On-Line Encyclopedia of Integer Sequences. [73] K.G.C. von Staudt, Beweis eines Lehrsatzes die Bernoulli’schen Zahlen betreffend, J. Reine Angew. Math. 21 (1840), 372–374. [74] G.A. Steele, Carmichael numbers in number rings, J. Number Theory 128 (2008), No. 4, 910–917. [75] Z.-H. Sun, Congruences for Bernoulli numbers and Bernoulli polynomials, Discrete Math. 163 (1997), 153–163. [76] Z.-W. Sun and H. Pan, Identities concerning Bernoulli and Euler polynomials, Acta Arith. 125 (2006), 21–39. [77] J.D. Swift, Review 13[9] - table of Carmichael numbers to 109 , Math. Comp. 29 (1975), 338–339. [78] E.W. Weinstein, Carmichael number, http://mathworld.wolfram.com/CarmichaelNumber.html. [79] E. Wong, Computations on Normal Families of Primes, MSc Thesis, Simon Fraser University, 1997; available at http://discerver.carma.newcastle.edu.au/view/year/1997.html. [80] T. Wright, Infinitely many Carmichael numbers in arithmetic progressions, to appear in Bull. London Math. Soc.; preprint arXiv:1212.5850v1 [math.NT], December 2012. [81] M.Z. Zhang, A method for finding large Carmichael numbers, Sichuan Daxue Xuebao 29 (1992), no. 4, 472–479. [82] V. Tipu, A note on Giuga’s conjecture, Canad. Math. Bull. 50 (2007), 158–160.

46

Maritime Faculty, University of Montenegro, Dobrota 36, 85330 Kotor, Montenegro E-mail address: [email protected]