Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-18T08:28:09.546Z Has data issue: false hasContentIssue false
  • English
  • Français

A REMARK ON PRIMALITY TESTING AND DECIMAL EXPANSIONS

Part of: Elliptic equations and systems

Published online by Cambridge University Press:  19 March 2012

TERENCE TAO
TERENCE TAO*
Affiliation:
Department of Mathematics, UCLA, Los Angeles, CA 90095-1555, USA (email: [email protected])
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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.

Keywords

primality testingsieve theorycovering congruences

MSC classification

Secondary: 35J10: Schrödinger operator
Type
Research Article
Information
Journal of the Australian Mathematical Society , Volume 91 , Issue 3 , December 2011 , pp. 405 - 413
Copyright
Copyright © Australian Mathematical Publishing Association Inc. 2012

References

[1]Allender, E., Saks, M. and Shparlinski, I. E., ‘A lower bound for primality’, J. Comput. System Sci. 62 (2001), 356–366.CrossRefGoogle Scholar
[2]Chen, Y.-G., Feng, R. and Templier, N., ‘Fermat numbers and integers of the form a k+a l+p α’, Acta Arith. 135 (2008), 51–61.CrossRefGoogle Scholar
[3]Cohen, F. and Selfridge, J. L., ‘Not every number is the sum or difference of two prime powers’, Math. Comput. 29 (1975), 79–81.CrossRefGoogle Scholar
[4]Crocker, R., ‘On the sum of a prime and two powers of two’, Pacific J. Math. 36 (1971), 103–107.CrossRefGoogle Scholar
[5]Erdős, P., ‘On integers of the form 2k+p and some related problems’, Summa Brasil. Math. 2 (1950), 113–123.Google Scholar
[6]Erdős, P. and Shorey, T. N., ‘On the greatest prime factor of 2p−1 for a prime p and other expressions’, Acta Arithm. 30 (1976), 257–265.CrossRefGoogle Scholar
[7]Fileseta, M., Kozek, M., Nicol, C. and Selfridge, J., ‘Composites that remain composite after changing a digit’, J. Comb. Number Theory 2 (2010), 25–36.Google Scholar
[8]Hardy, G. H. and Littlewood, J. E., ‘Some problems of “partitio numerorum” III: On the expression of a number as a sum of primes’, Acta Math. 44 (1923), 1–70.CrossRefGoogle Scholar
[9]Harman, G., ‘Primes with preassigned digits’, Acta Arith. 125 (2006), 179–185.CrossRefGoogle Scholar
[10]Heath-Brown, D. R. and Puchta, J.-C., ‘Integers represented as a sum of primes and powers of two’, Asian J. Math. 6 (2002), 535–565.CrossRefGoogle Scholar
[11]Łuszczki, Z., ‘On the prime factors of ∏ xn=1(a τ n+1)’, Funct. Approx. Comment. Math. 2 (1976), 115–120.Google Scholar
[12]Mauduit, C. and Rivat, J., ‘Sur un problème de Gelfond: la somme de chiffres des nombres premiers’, Ann. of Math. (2) 171 (2010), 1591–1646.CrossRefGoogle Scholar
[13]Montgomery, H. and Vaughan, R., Multiplicative Number Theory I. Classical Theory, Cambridge Studies in Advanced Mathematics, 97 (Cambridge University Press, Cambridge, 2007).Google Scholar
[14]Murata, L. and Pomerance, C., ‘On the largest prime factor of a Mersenne number’, in: Number Theory, CRM Proceedings Lecture Notes, 36 (American Mathematical Society, Providence, RI, 2004), pp. 209–218.CrossRefGoogle Scholar
[15]Orno, P.et al., ‘Problems’, Math. Mag. 52 (1979), 179–184.CrossRefGoogle Scholar
[16]Pan, H., ‘On the number of distinct prime factors of nj+a hk’, arXiv:0907.1940.Google Scholar
[17]Pan, H., ‘On the integers not of the form p+2a+2b’, Acta Arith. 148 (2011), 55–61.CrossRefGoogle Scholar
[18]Shparlinski, I., Cryptographic Applications of Analytic Number Theory (Birkhaüser, Basel, 2003).CrossRefGoogle Scholar
[19]Sloane, N. J. A., ‘The On-Line Encyclopedia of Integer Sequences’, published electronically atwww.research.att.com/∼njas/sequences/, 2007.Google Scholar
[20]Sun, Z. W., ‘On integers not of the form ±p a±q b’, Proc. Amer. Math. Soc. 128 (2000), 997–1002.CrossRefGoogle Scholar
[21]van der Dries, L. and Moschovakis, Y., ‘Is the Euclidean algorithm optimal among its peers?’, Bull. Symbolic Logic 10 (2004), 390–418.CrossRefGoogle Scholar
[22]Woods, A., ‘Subset sum “cubes” and the complexity of prime testing’, Theor. Comp. Sci. 322 (2004), 203–219.CrossRefGoogle Scholar
[23]Yuan, P., ‘Integers not of the form c(2a+2b)+pα’, Acta Arith. 115 (2004), 23–28.CrossRefGoogle Scholar