a1 Department of Mathematics, UCLA, Los Angeles, CA 90095-1555, USA (email: email@example.com)
We show that for any fixed base a, a positive proportion of primes become composite after any one of their digits in the base a expansion is altered; the case where a=2 has already been established by Cohen and Selfridge [‘Not every number is the sum or difference of two prime powers’, Math. Comput. 29 (1975), 79–81] and Sun [‘On integers not of the form ±pa±qb’, Proc. Amer. Math. Soc. 128 (2000), 997–1002], using some covering congruence ideas of Erdős. Our method is slightly different, using a partially covering set of congruences followed by an application of the Selberg sieve upper bound. As a consequence, it is not always possible to test whether a number is prime from its base a expansion without reading all of its digits. We also present some slight generalisations of these results.
(Received February 22 2008)
(Accepted July 04 2008)
2010 Mathematics subject classification
Keywords and phrases
The author is supported by NSF grant CCF-0649473 and a grant from the MacArthur Foundation.
Communicated by I. E. Shparlinski