Sep 16, 2011 - We prove that an odd number n is an Euler pseudoprime for exactly one half of the admissible bases if and only if n is a special Carmic...

0 downloads 13 Views 113KB Size

arXiv:1109.3596v1 [math.NT] 16 Sep 2011

Dedicated to the memory of Prof. John Lewis Selfridge Abstract. We prove that an odd number n is an Euler pseudoprime for exactly one half of the admissible bases if and only if n is a special Carmichael number, that is, a

n−1 2

≡ 1 mod n for every invertible a ∈ Zn .

1. Introduction Given a large odd number n without small factors, one can try to decide whether n is prime by randomly taking some a coprime with n and computing an−1 mod n. If this value is not 1, then n is certainly not prime, by Fermat’s little theorem. Otherwise we can only say that n is probably prime. Actually either n is prime or n is pseudoprime for the base a; the latter is equivalent to saying that a is a liar to Fermat’s primality test. Even if Fermat’s primality test is often correct, unfortunately it cannot be trustingly used as a Monte-Carlo primality test because there exist odd composite numbers that are pseudoprimes for all of the bases coprime with n. These numbers are called Carmichael numbers: they are much rarer than primes but they are still infinite, as proved by Alford, Granville and Pomerance in [1]. Instead of considering Fermat’s little theorem one could use Euler’s criterion: p−1 namely Euler proved that if p is an odd prime, then a 2 ≡ ( ap ) mod p for every a, where ( ap ) is the Legendre–Jacobi symbol. Thus the primality of a large odd number n−1

n can be tested by checking a 2 ≡ ( na ) mod n for some a coprime with n. If this relation is not satisfied then n is certainly not prime; otherwise n is probably prime and, as before, we have that either n is prime or n is an Euler pseudoprime for the base a; the latter is equivalent to saying that a is a liar to the Solovay–Strassen primality test. In order to confidently use this primality test in a Monte-Carlo method, it was very important to establish for how many bases an odd composite number can be an Euler pseudoprime. It has been reported to the author by Pomerance that Selfridge was probably the first one to realize that for every odd composite number n there is at least one x for which n is not an Euler pseudoprime for the base x, but he did not publish his discovery (see [3, §5], where Selfridge is credited). Anyway, a few years after Selfridge’s discovery, both Lehmer (see [5]) and Solovay–Strassen (see [8]), independently, proved the same result. In particular, Solovay and Strassen also noticed that the subset of bases in U (Zn ) := {a ∈ Zn | gcd(a, n) = 1} for which n is an Euler pseudoprime is actually a subgroup. As an easy consequence of this fact, they showed that no odd composite number can be an Euler pseudoprime for more than half of the admissible bases (that is, elements of the group U (Zn )): n a o n−1 mod n ≤ φ(n)/2. (1) a ∈ U (Zn ) | a 2 ≡ n 2010 Math classification: 11A15, 11A51, 11Y11. Key words: Euler pseudoprimes, liars, Carmichael numbers. September 19, 2011. 1

2

LORENZO DI BIAGIO

This remark paved the way for an efficient probabilistic primality test, named Solovay–Strassen after the two authors. During the subsequent years many papers about pseudoprimes, Euler pseudoprimes, strong pseudoprimes appeared: for example, an article by Pomerance, Selfridge and Wagstaff ([7]), where many properties are stated and many examples are given and an article by Monier ([6]), where a formula to count the number of liars is given. The purpose of this note is just to understand in which cases the bound in (1) is actually achieved. We will prove the following in an equivalent form as Proposition 3.4: Proposition 1.1. Let n be an odd composite number. Then n is an Euler pseudon−1 prime for exactly one half of the bases in U (Zn ) if and only if a 2 ≡ 1 mod n for every a ∈ U (Zn ). Acknowldegments. The author wishes to warmly thank Prof. C. Pomerance for his kindness and for many helpful discussions. 2. Preliminary lemmas Lemma 2.1. Let n > 2 be an odd number. Then, for any a ∈ Z, an−1 6≡ −1 mod n. αr 1 Proof. Let n = pα 1 · · · pr , pi distinct prime numbers. Without loss of generality we can suppose that gcd(a, n) = 1 and that v := v2 (p1 −1) ≤ v2 (pi −1) for all 1 ≤ i ≤ r (v2 being the dyadic valuation). By contradiction, suppose an−1 ≡ −1 mod n. 1 α Then, in particular, an−1 ≡ −1 mod pα 1 . Let g be a generator for U (Zp1 1 ) and let α1 α1 h(n−1) h ≡ −1 mod p1 , that is, h be such that g ≡ a mod p1 . Then g 1 φ(pα 1 ) 1 | h(n − 1) but φ(pα 1 ) ∤ h(n − 1). 2 α1 −1 1 Hence there exists k ∈ Z, k odd, such that φ(pα (p1 − 1 )k = 2h(n − 1), that is, p1 1)k = 2h(n − 1). It follows that v = v2 (p1 − 1) > v2 (n − 1); however this is not possible since pi ≡ 1 mod 2v for every 1 ≤ i ≤ r and thus n − 1 ≡ 0 mod 2v .

Lemma 2.2. Let n be an odd composite number and let B := {a ∈ U (Zn ) | a ±1 mod n}. If |B| ≥ φ(n)/2, then n is a Carmichael number.

n−1 2

≡

Proof. If |B| = φ(n) the statement is trivial, therefore from now on we can suppose n−1 that |B| = φ(n)/2. Let B ′ := {a ∈ U (Zn ) | a 2 ≡ +1 mod n}. It is easily seen that two cases can occur: either B ′ = B, that is, B ′ has index 2 in U (Zn ), or C := B \ B ′ 6= ∅ is a coset of B ′ in U (Zn ), that is, B ′ has index 4. In the first n−1

case, for any h 6∈ B ′ we have h2 ∈ B ′ , that is, hn−1 = h2 2 ≡ 1 mod n. In the second case we can conclude by observing that again U (Zn )/B ′ has elements of order at most 2. Indeed C has order two in U (Zn )/B ′ , therefore if h 6∈ B, then h2 must be in B ′ or in C, but the latter is not possible because otherwise hn−1 = h2

n−1 2

≡ −1 mod n, contradicting Lemma 2.1.

Remark 2.3. Notice that in the proof of Lemma 2.2 the second case (C 6= ∅, B ′ has index 4) does not actually occur. In fact, since we have proved that n is a Carmichael number, we now know that n = p1 · · · pr with r ≥ 3, pi distinct primes (see, for example, [4, Proposition V.1.2, Proposition V.1.3]). For every 1 ≤ i ≤ r, let gi be a generator of U (Zpi ). Since C 6= ∅, there exists b ∈ U (Zn ) n−1 n−1 such that b 2 ≡ −1 mod n, that is, b 2 6≡ 1 mod pi for every i. In particular n−1 2

gi

6≡ 1 mod pi for every i. For every 1 ≤ i ≤ r, let xi be the solution mod n of the n−1 2

system X ≡ gi mod pi , X ≡ 1 mod n/pi . Notice that for every i, xi

6≡ ±1 mod n

EULER PSEUDOPRIMES FOR HALF OF THE BASES n−1 2

and that for any i 6= j, xi index ≥ 5.

3

n−1

6≡ xj 2 mod n. Therefore, since r ≥ 3, B ′ must have

Lemma 2.4. Let n > 2 be an odd number. Let n a o Pn := a ∈ U (Zn ) | =1 , n o n a = −1 . Nn := a ∈ U (Zn ) | n If n is not a perfect square then |Pn | = |Nn | = φ(n)/2. Proof. Notice that we need only to prove that if n is not a perfect square, then Nn 6= ∅, since in this case Nn is just a coset of the subgroup Pn in U (Zn ). Let αr 1 n = pα 1 · · · pr , pi distinct primes. Without loss of generality we can suppose that α1 is odd. Choose q ∈ U (Zp1 ) such that q is not a quadratic residue mod p1 . Let x be any solution of X ≡ q mod p1 X ≡ 1 mod p2 · · · pr Clearly gcd(x, n) = 1. Moreover αr x x α1 x = ··· = (−1)α1 = −1, n p1 pr that is, Nn 6= ∅.

3. special Carmichael numbers

Definition 3.1. Let n be an odd composite number. We say that n is a special n−1 Carmichael number if a 2 ≡ 1 mod n for all a ∈ U (Zn ). Following Korselt, we have the characterization below: Proposition 3.2. n is a special Carmichael number if and only if n is odd, squarefree and (p − 1) | n−1 2 for every prime p such that p | n. Proof. Just a minor modification of Korselt’s proof is needed (see, for example, [4, Proposition V.I.2]). Remark 3.3. It is clear that special Carmichael numbers are Carmichael numbers. As explained in [2, Exercise 3.24] the proof of the infinitude of Carmichael numbers (see [1]) actually implies that there are infinitely many special Carmichael numbers. The least example is the famous “taxicab” number 1729, dear to Hardy and Ramanujan. The first elements of the sequence of special Carmichael numbers are 1729, 2465, 15841, 41041, 46657, 75361, 162401, 172081, 399001, 449065, 488881, . . .. It is also clear from Proposition 3.2 that every special Carmichael number must be ≡ 1 mod 4. We are now ready to prove our main result. Proposition 3.4. Let n be an odd composite number. Then n is an Euler pseudoprime for exactly one half of the bases in U (Zn ) if and only if n is a special Carmichael number. Proof. If n is a special Carmichael number then, in particular, n is a Carmichael number and thus n is square-free. Therefore, by Lemma 2.4, n is an Euler pseudo prime for half of the bases in U (Zn ), namely for all a ∈ U (Zn ) such that na = 1. Conversely, suppose that n is an Euler pseudoprime for exactly one half of the n−1 bases in U (Zn ). Then by hypothesis a 2 ≡ ±1 mod n for at least one half of the admissible bases and therefore, in particular, n is a Carmichael number by Lemma 2.2, thus n = p1 · · · pr , pi distinct primes, r ≥ 3. By [2, Exercise 3.24] and Remark

4

LORENZO DI BIAGIO n−1

n−1

2.3, either a 2 ≡ 1 mod n for every a ∈ U (Zn ) or a 2 ≡ 1 mod n for exactly one n−1 half of the admissible bases (while a 2 6≡ ±1 mod n for the other half). We must rule out the latter case. n−1 By hypothesis and by Lemma 2.4, na = 1 for all a ∈ U (Zn ) such that a 2 ≡ n−1 1 mod n, while na = −1 for all a ∈ U (Zn ) such that a 2 6≡ 1 mod n. We will now n−1 exhibit x ∈ U (Zn ) such that x 2 6≡ 1 but nx = 1, a contradiction. n−1 Let b ∈ U (Zn ) such that b 2 6≡ 1. In particular, there exists a prime factor p n−1 of n, say p1 , such that b 2 6≡ 1 mod p1 . Let g be a generator of U (Zp1 ), so that n−1 g 2 6≡ 1 mod p1 . Let g ′ be a generator of U (Zp2 ). Let x be the unique solution mod n of the system X ≡ g mod p1 X ≡ g ′ mod p2 X ≡ 1 mod p3 · · · pr n−1

6 1 mod n and We see immediately that x 2 ≡ r x Y x = = (−1)(−1) = 1. n pi i=1

Remark 3.5. As Pomerance kindly pointed out to the author, Proposition 3.4 can also be proved by a careful consideration of all the cases in Monier’s formula for the number of liars to the Solovay–Strassen test (see [6, Proposition 3] and [3]). Actually Monier, in [6], also observes that odd composite numbers achieving the bound in (1) are Carmichael numbers, but he does not make calculations explicit and misses to give a complete characterization (although he was probably aware of the gist of Proposition 3.4). It is also worth remarking that Monier, in [6], additionally gives a formula for the number of liars to the Miller–Rabin test. This formula can be used to give a complete characterization of odd composite numbers n achieving the bound φ(n)/4 for strong pseudoprimes: see [6] and [9, Equation 1.5 and §5]. References [1] W. R. Alford, Andrew Granville, and Carl Pomerance. There are infinitely many Carmichael numbers. Ann. of Math. (2), 139(3):703–722, 1994. [2] Richard Crandall and Carl Pomerance. Prime numbers. A computational perspective. Springer, New York, second edition, 2005. [3] Paul Erd˝ os and Carl Pomerance. On the number of false witnesses for a composite number. In Number theory (New York, 1984–1985), volume 1240 of Lecture Notes in Math., pages 97–100. Springer, Berlin, 1987. [4] Neal Koblitz. A course in number theory and cryptography, volume 114 of Graduate Texts in Mathematics. Springer-Verlag, New York, second edition, 1994. [5] D. H. Lehmer. Strong Carmichael numbers. J. Austral. Math. Soc. Ser. A, 21(4):508–510, 1976. [6] Louis Monier. Evaluation and comparison of two efficient probabilistic primality testing algorithms. Theoret. Comput. Sci., 12(1):97–108, 1980. [7] Carl Pomerance, J. L. Selfridge, and Samuel S. Wagstaff, Jr. The pseudoprimes to 25 · 109 . Math. Comp., 35(151):1003–1026, 1980. [8] R. Solovay and V. Strassen. A fast Monte-Carlo test for primality. SIAM J. Comput., 6(1):84– 85, 1977. [9] Zhenxiang Zhang and Min Tang. Finding strong pseudoprimes to several bases. II. Math. Comp., 72(244):2085–2097 (electronic), 2003. ` degli Studi “Roma Tre”- Largo S. Leonardo Dipartimento di Matematica, Universita Murialdo 1, 00146, Roma, Italy E-mail address, 1: [email protected] E-mail address, 2: [email protected]