Prime divisors of palindromes
- PDF / 156,780 Bytes
- 10 Pages / 595 x 842 pts (A4) Page_size
- 64 Downloads / 198 Views
PRIME DIVISORS OF PALINDROMES William D. Banks (Columbia) and Igor E. Shparlinski (Sydney) [Communicated by: Andr´ as S´ ark¨ ozy ]
Abstract In this paper, we study some divisibility properties of palindromic numbers in a fixed base g ≥ 2. In particular, if PL denotes the set of palindromes with precisely L digits, we show that for any sufficiently large value of L there exists a palindrome n ∈ PL with at least (log log n)1+o(1) distinct prime divisors, and there exists a palindrome n ∈ PL with a prime factor of size at least (log n)2+o(1) .
1. Introduction For a fixed integer base g ≥ 2, consider the base g representation of an arbitrary natural number n ∈ N: n=
L−1
ak (n)g k ,
(1)
k=0
where ak (n) ∈ {0, 1, . . . , g − 1} for each k = 0, 1, . . . , L − 1, and the leading digit aL−1 (n) is nonzero. The integer n is said to be a palindrome if its digits satisfy the symmetry condition: ak (n) = aL−1−k (n),
k = 0, 1, . . . , L − 1.
It has recently been shown in [1] that almost all palindromes are composite. For any n ∈ N, the number L in (1) is called the length of n; let PL ⊂ N denote the set of all palindromes of length L. In this paper, as in [1], we estimate exponential sums of the form eq (cn), Sq (L; c) = n∈PL
where as usual eq (x) = exp(2πix/q) for all x ∈ R. Using these estimates, we show that for all sufficiently large values of L, there exists a palindrome n ∈ PL with at Mathematics subject classification number: 11A63, 11L07. Key words and phrases: palindromes, prime divisors. 0031-5303/2005/$20.00 c Akad´ emiai Kiad´ o, Budapest
Akad´ emiai Kiad´ o, Budapest Springer, Dordrecht
2
w. d. banks and i. e. shparlinski
least (log log n)1+o(1) distinct prime divisors, and there exists a palindrome n ∈ PL with a prime factor of size at least (log n)2+o(1) . Throughout the paper, all constants defined either explicitly or implicitly via the symbols O, Ω, and may depend on g but are absolute otherwise. We recall that the following statements are equivalent: A = O(B), B = Ω(A), A B, and B A. We also write A B to indicate that B A B. Acknowledgements. The authors wish to thank Florian Luca for some useful conversations. Most of this work was done during a visit by the authors to the Universidad de Cantabria; the hospitality and support of this institution are gratefully acknowledged. W. B. was supported in part by NSF grant DMS-0070628, and I. S. was supported in part by ARC grant DP0211459.
2. Preliminary results For every natural number q with gcd(q, g) = 1, we denote by tq the order of g in the multiplicative group modulo q. For arbitrary integers a, b, K with K ≥ 1 we consider the exponential sums Tq (a, b) =
tq
eq ag k + bg −k
and Tq (K; a, b) =
k=1
K
eq ag k + bg −k ,
k=1
where the inversion g −k is taken in the residue ring Zq . Lemma 1. Let S be a set of primes coprime to g, with gcd(tp1 , tp2 ) = 1 for all distinct p1 , p2 ∈ S. Then for the integer q = p∈S p one has Tp (a, b). Tq (a, b) = p∈S
Proof. Consider the Kloosterman sums χ(c) eq (ac + bc) Kχ (a, b;
Data Loading...
