Cipolla Pseudoprimes

Y. Hamahata^{1} and Y. Kokubun Department of Mathematics Tokyo University of Science Noda, Chiba, 278-8510 Japan

              hamahata yoshinori@ma.noda.tus.ac.jp

Abstract We consider the pseudoprimes that M. Cipolla constructed. We call such pseudoprimes Cipolla pseudoprimes. In this paper we find infinitely many Lucas and Lehmer pseudoprimes that are analogous to Cipolla pseudoprimes.

1 Introduction

Take an integer a > 1. A pseudoprime to base a is a composite number n such that a^{n−1} ≡ 1 ( mod n). In 1904, M. Cipolla [1] found infinitely many pseudoprimes to a given base a. To be more precise,

Theorem 1 (Cipolla [1], cf. Ribenboim [5]). Let p be a prime such that p does not divide a(a^{2} − 1). Put

n_{1} = \frac{a^{p} − 1}{a − 1}, n_{2} = \frac{a^{p} + 1}{a + 1}, n = n_{1}n_{2}.

Then n is a pseudoprime to base a.

In this paper we call such n a Cipolla pseudoprime. In the above theorem, if we set P = a + 1, Q = a, then n is written as n = U_{2p}/P, where U_{2p} is a term in the Lucas sequence with parameters P and Q. See the next section for Lucas sequences. From this observation, the following question arises. For given integers P, Q, are there infinitely many Lucas pseudoprimes with parameters P and Q of the form U_{2p}/P? Here Lucas pseudoprimes will be defined in the next section.

The purpose of the paper is to solve the above question affirmatively under a certain condition. As a corollary to our result, we derive the result of Lehmer [4]. We are also going to consider an analogous question for Lehmer sequences.

1Partially supported by Grant-in-Aid for Scientific Research (No. 18540050), Japan Society for the Promotion of Science.

2 Cipolla-Lucas pseudoprimes

In this section we consider Lucas pseudoprimes of special type.

Let P, Q be integers such that D := P^{2} − 4Q ≠ 0, and α, β the roots of the polynomial z^{2} − P z + Q. For a nonnegative integer n, put

U_{n} = \frac{α^{n} − β^{n}}{α − β} , V_{n} = α^{n} + β^{n}.

For example, we have U_{0} = 1, U_{1} = 1, U_{2} = P, V_{0} = 2, and V_{1} = P. One sees that (U_{n})_{n≥0} and (V_{n})_{n≥0} are integer sequences. We call the sequences (U_{n})_{n≥0}, (V_{n})_{n≥0} the Lucas sequences with parameters P and Q.

We exhibit some results needed afterwards. One can consult Ribenboim [5, 6] for the basic results. (I) For a nonnegative integer n, U_{2n} = U_{n}V_{n}. (II) (a) If P is odd and Q is even, then U_{n}, V_{n} (n ≥ 1) are odd.

(b) If P and Q are odd, then U_{n}, V_{n} (3 ∤ n) are odd. (III) (a) When U_{m} ≠ 1, U_{m}|U_{n} if and only if m|n.

(b) When V_{m} ≠ 1, V_{m}|V_{n} if and only if m|n and n/m is odd. (IV) For any odd prime p,

2^{p−1}U_{p} = ∑_{k=0}^{(p−1)/2} ( \begin{matrix}p \\ 2k + 1 \end{matrix} ) P^{p−(2k+1))}D^{k},  (1)

2^{p−1}V_{p} = ∑_{k=0}^{(p−1)/2} ( \begin{matrix}p \\ 2k \end{matrix} ) P^{(p−2k)}D^{k}.  (2)

U_{p} ≡ (\frac{D}{p}) (mod p), V_{p} ≡ P (mod p).

We recall Lucas pseudoprimes. A composite number n is a Lucas pseudoprime with parameters P and Q if

U_{n−(\frac{D}{n})} ≡ 0 (mod n)

holds. Here (\frac{D}{n}) is the Jacobi symbol.

Now let us define an analogue of Cipolla pseudoprimes for Lucas sequences.

Definition 2. A composite number n is called a Cipolla-Lucas pseudoprime with parameters P and Q if it is a Lucas pseudoprime with parameters P and Q and has the form U_{2p}/P for a certain prime number p.

Our first result is as follows.

Theorem 3. Let P be an odd number, and Q a nonzero integer such that gcd(P, Q) = 1. Assume that D = P^{2} − 4Q is square-free. Then there are infinitely many Cipolla-Lucas pseudoprimes with parameters P and Q.

Proof. Let p be an odd prime such that gcd(p, 3P D) = 1 and φ(D)|p − 1. Then we show that U_{2p}/P is a Lucas pseudoprime. From now on we prove the theorem step by step. Put m = U_{2p}/P.

First of all, we prove m|U_{m−(\frac{D}{m})}. Since p is odd, U_{p} ≡ (\frac{D}{p}) (mod p), V_{p} ≡ P (mod p). So that

U_{2p} = U_{p}V_{p} ≡ P (\frac{D}{p}) (mod p).

Since P = U_{2}, U_{2}|U_{2p}, and gcd(p, P) = 1, we have m ≡ (\frac{D}{p}) (mod p). We recall that P is

odd and gcd(p, 3) = 1. Hence U_{p} and V_{p} are odd. We see 2p|m − (\frac{D}{p}). From this, we have

U_{2p}|U_{m−(\frac{D}{p})}. Moreover we have m|U_{m−(\frac{D}{p})}. We prove (\frac{D}{p}) = (\frac{D}{m}). By (1) and (2),

2^{p−1}U_{p} ≡ pP^{p−1} (mod D),
2^{p−1}V_{p} ≡ P^{p} (mod D).

By φ(D)|p − 1, we have U_{p} ≡ p (mod D), V_{p} ≡ P (mod D). Hence U_{2p} ≡ pP (mod D). By gcd(P, D) = 1, it follows that m = U_{2p}/P ≡ p (modD). Observe that D ≡ 1 (mod4) because P is odd. Thus we have (\frac{D}{p}) = (\frac{D}{m}), which implies m|U_{m−(\frac{D}{m})}.

We next show that m is a composite number. Since p is odd and P = U_{2} = V_{1}, one has P ∤ U_{p} and P |V_{p}. Now assume that there exists an odd prime p satisfying V_{p} = ±P. Then one has V_{1}|V_{p} and V_{p}|V_{1}. This implies p = 1, which is absurd. Therefore m is a composite number.

Finally, we prove the infinitude of U_{2p}/P. By Dirichlet’s theorem on primes in arithmetic progression, there are infinitely many primes p such that φ(D)|p − 1. The number of primes p with gcd(p, 3P D) > 1 among them is finite. This proves the claim.

As a corollary to the last theorem, we can derive a known result. We call the Lucas sequence with parameters 1 and −1 the Fibonacci sequence. We write (F_{n})_{n≥0} for it. A composite number n is called a Fibonacci pseudoprime if

F_{n−(\frac{D}{n})} ≡ 0 (mod n)

is valid. Using the last theorem, we have

Corollary 4 (Lehmer [4]). There are infinitely many primes p such that F_{2p} is a Fibonacci pseudoprime.

Proof. Since P = 1 and Q = −1, U_{2p}/P becomes F_{2p}. In this case one has D = 5. Hence for any prime p > 5 with p ≡ 1 (mod 4), the two conditions gcd(p, 3P D) = 1 and φ(D)|p − 1 hold. This yields the result.

3 Cipolla-Lehmer pseudoprimes

In this section we consider Lehmer pseudoprimes. First, we review Lehmer sequences.

Let α, β be distinct roots of the polynomial f(z) = z^{2} − \sqrt{L}z + M, where L > 0 and M are rational integers, and K := L − 4M is the discriminant of f(z). For a nonnegative integer n, put

D_{n} = \{ \begin{matrix}(α^{n} − β^{n})/(α − β) & if n is odd \\ (α^{n} − β^{n})/(α^{2} − β^{2}) & if n is even, \end{matrix}
E_{n} = \{ \begin{matrix}(α^{n} + β^{n})/(α + β) & if n is odd \\ α^{n} + β^{n} & if n is even. \end{matrix}

For example, we have D_{0} = 0, D_{1} = D_{2} = 1, E_{0} = 2, E_{1} = 1, and E_{2} = L − 2M. One sees that (D_{n})_{n≥0} and (E_{n})_{n≥0} are integer sequences. We call the sequences (D_{n})_{n≥0} and (E_{n})_{n≥0} the the Lehmer sequences with parameters L and M. It should be noticed that we modify the original definition of the Lehmer sequences in order to make them integer sequences.

We exhibit some results needed afterwards. One can consult Lehmer [3] for the basic results. (I) For a prime p, D_{2p} = D_{p}E_{p}. (II) D_{n} is even in the following cases only

(a) L = 4k, M = 2l + 1, n = 2h,

(b) L = 4k + 2, M = 2l + 1, n = 4h,

(c) L = 4k ± 1, M = 2l + 1, n = 3h. (III) E_{n} is even in the following cases only

(a) L = 4k, M = 2l + 1,

(b) L = 4k + 2, M = 2l + 1, n = 2h,

(c) L = 4k ± 1, M = 2l + 1, n = 3h. (IV) If m|n, then D_{m}|D_{n}. (V) For any odd prime p,

2^{p−1}D_{p} = ∑_{k=0}^{(p−1)/2} ( \begin{matrix}p \\ 2k + 1 \end{matrix} ) L^{(p−2k−1)/2}K^{k},  (3)

2^{p−1}E_{p} = ∑_{k=0}^{(p−1)/2} ( \begin{matrix}p \\ 2k \end{matrix} ) L^{(p−2k)/2}K^{k}.  (4)

D_{p} ≡ (\frac{K}{p} ) (mod p), E_{p} ≡ (\frac{L}{p}) (mod p).

Next, we review Lehmer pseudoprimes. A composite number n is called a Lehmer pseudoprime with parameters L and M if

D_{n−(\frac{KL}{n})} ≡ 0 (mod n)

holds. Here (\frac{KL}{n}) denotes the Jacobi symbol.

Any Cipolla pseudoprime is written as D_{2p} for some prime p. Hence we define Lehmer pseudoprimes related to Cipolla pseudoprimes as follows.

Definition 5. A composite number n is called a Cipolla-Lehmer pseudoprime with parameters L and M if it is a Lehmer pseudoprime with parameters L and M and has the form D_{2p} for a certain prime p

Our second result is as follows.

Theorem 6. Let L be a square-free odd number and M an integer such that gcd(L, M) = 1. Assume that K = L − 4M is square-free. Then there are infinitely many Cipolla-Lehmer pseudoprimes with parameters L and M.

Proof. The proof is similar to that of Theorem 3. Let p be an odd prime such that gcd(p, KL) = 1 and φ(KL)|p − 1. Then we prove that D_{2p} is a Lehmer pseudoprime. Put m = D_{2p}.

We first show m|D_{m−(\frac{KL}{m})}. Since p is odd, D_{p} ≡ (\frac{K}{p} ) (mod p), E_{p} ≡ (\frac{L}{p}) (mod p). Hence

m = D_{2p} = D_{p}E_{p} ≡ (\frac{KL}{p}) (mod p).

That is to say, p|m − (\frac{KL}{p}). Since L is odd, D_{p} and E_{p} are odd. Hence m is odd. We find

that m−(\frac{KL}{p}) is even. Thus 2p|m−(\frac{KL}{p}). Using this, we have D_{2p}|D_{m−(\frac{KL}{p})}, which shows

m|D_{m−(\frac{KL}{p})}. We must prove (\frac{KL}{p}) = (\frac{KL}{m}). Since K is odd, by (3) and (4),

2^{p−1}D_{p} ≡ pL^{\frac{p−1}{2}} + K^{\frac{p−1}{2}} (mod KL),
2^{p−1}E_{p} ≡ L^{\frac{p−1}{2}} + pK^{\frac{p−1}{2}} (mod KL).

Since φ(KL)|p − 1 and 2 ∤ KL hold, 2^{p−1} ≡ 1 (mod KL). Hence we have

m = D_{p}E_{p} ≡ p (K^{p−1} + L^{p−1}) (mod KL).

It should be noted that K^{p−1} + L^{p−1} ≡ 1 (mod KL). Indeed, because of gcd(K, L) = 1, the condition φ(K)φ(L)|p − 1 implies L^{p−1} ≡ 1 (mod K) and K^{p−1} ≡ 1 (mod L). For any prime divisor l of K, l|K^{p−1} + L^{p−1} − 1. Hence we have K^{p−1} + L^{p−1} − 1 ≡ 0 (mod K). In the same way, we have K^{p−1} + L^{p−1} − 1 ≡ 0 (mod L). Therefore our claim is proven. Using this observation, we obtain m ≡ p (mod KL). By the way, we see KL = L^{2} − 4ML ≡ L^{2} ≡ 1 (mod 4). Thus we conclude that (\frac{KL}{p}) = (\frac{KL}{m}). We get m|D_{m−(\frac{KL}{m})}.

Clearly m = D_{p}E_{p} is a composite number.

Finally we show the infinitude of D_{2p}. By Dirichlet’s theorem on primes in arithmetic progression, there are infinitely many primes p such that φ(KL)|p−1. The number of primes p with gcd(p, KL) > 1 among them is finite. This proves the claim.

References

[1] M. Cipolla, Sui numeri composti P, che verificanola congruenza di Fermat a^{P −1} ≡ 1 (mod P). Annali di Matematica 9 (1904), 139–160.

[2] N. Koblitz, A Course in Number Theory and Cryptography. Springer-Verlag, 1994.

[3] D. H. Lehmer, An extended theory of Lucas’ functions. Annals of Math. 31 (1930), 419–448.

[4] E. Lehmer, On the infinitude of Fibonacci pseudo-primes. Fibonacci Quart. 2 (1964), 229–230.

[5] P. Ribenboim, The Book of Prime Number Records. Springer-Verlag, 1989.

[6] P. Ribenboim, My Numbers, My Friends − Popular Lectures on Number Theory. Springer-Verlag, 2003.

[7] A. Rotkiewicz, Lucas pseudoprimes. Functiones et Approximatio XXVIII (2000), 97–104.

[8] A. Rotkiewicz, Arithmetic progressions formed by pseudoprimes. Acta Mathematica et Informatica Universitatis Ostraviensis 8 (2000) 61–74.

[9] J.-P. Serre, Cours d’arithmétique. Presses Universitaires de France, 1970.

2000 Mathematics Subject Classification: Primary 11A51; Secondary 11B39. Keywords: pseudoprime, Lucas sequence, Lucas pseudoprime, Lehmer sequence, Lehmer pseudoprime.

Received July 17 2007; revised version received August 1 2007. Published in Journal of Integer Sequences, August 14 2007.

Return to Journal of Integer Sequences home page.