A REMARK ON PRIMALITY TESTING AND DECIMAL EXPANSIONS

作者：Tao Terence^*

来源：Journal of the Australian Mathematical Society, 2011, 91(3): 405-413.

DOI：10.1017/S1446788712000043

• primality testing
• sieve theory
• covering congruences

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 +/-p(a) +/- q(b,), Proc. Amer. Math. Soc. 128 (2000), 997-1002], using some covering congruence ideas of Erdos. 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.

• 出版日期2011-12