A remark on primality testing and decimal expansions. (English) Zbl 1251.11089

Following ideas of F. Cohen and J. L. Selfridge (for the base \(a=2\)) [Math. Comput. 29, 79–81 (1975; Zbl 0296.10029)] the present paper shows that, for any integer positive base \(a\), there exist primes \(p\) such that changing any of the digits in the base \(a\) expansion of \(p\) the resulting number is composite. As a consequence a deterministic primality test need to read all the digits in the base \(a\) expansion of a positive integer candidate to decide if \(a\) is prime or not.
More generally the paper proves the following result (Theorem 1.2): Let \(K\) be a natural number. For all sufficiently large \(N\) a positive proportion of primes in the interval \([N, (1+1/K)N]\) verifies that all the numbers \(|kp\pm ja^i|\) are composite (\(a,j,k\in [1,K],\,\, i\in [1,K\log K])\).
Section 1 introduces the problem and Section 2 gives the proof of Theorem 1.2. Instead of using a fully covering set of congruences (as Cohen and Selfridge) this proof take a partially covering using some special primes and then applies upper bound sieves. Finally Section 3 discusses possible variants and generalizations of Theorem 1.2.


11Y11 Primality
11N36 Applications of sieve methods
11A07 Congruences; primitive roots; residue systems


Zbl 0296.10029
Full Text: DOI arXiv


[1] DOI: 10.1007/978-3-0348-8037-4
[2] DOI: 10.1090/S0002-9939-99-05502-1 · Zbl 0959.11043
[3] DOI: 10.2307/2690284
[4] DOI: 10.4064/aa125-2-4 · Zbl 1246.11155
[5] Murata, Number Theory pp 209– (2004)
[6] DOI: 10.1007/BF02403921 · JFM 48.0143.04
[7] Montgomery, Multiplicative Number Theory I. Classical Theory (2007) · Zbl 1142.11001
[8] Fileseta, J. Comb. Number Theory 2 pp 25– (2010)
[9] DOI: 10.4007/annals.2010.171.1591 · Zbl 1213.11025
[10] Erdos, Acta Arithm. 30 pp 257– (1976)
[11] Łuszczki, Funct. Approx. Comment. Math. 2 pp 115– (1976)
[12] Erdos, Summa Brasil. Math. 2 pp 113– (1950)
[13] Heath-Brown, Asian J. Math. 6 pp 535– (2002) · Zbl 1097.11050
[14] Crocker, Pacific J. Math. 36 pp 103– (1971) · Zbl 0215.34703
[15] DOI: 10.1090/S0025-5718-1975-0376583-0
[16] DOI: 10.4064/aa135-1-4 · Zbl 1180.11005
[17] DOI: 10.1006/jcss.2000.1725 · Zbl 1032.11058
[18] DOI: 10.4064/aa115-1-2 · Zbl 1096.11007
[19] DOI: 10.1016/j.tcs.2004.03.037 · Zbl 1098.68050
[20] DOI: 10.2178/bsl/1102022663 · Zbl 1095.03025
[21] DOI: 10.4064/aa148-1-4 · Zbl 1219.11150
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.