{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T21:52:40Z","timestamp":1776721960173,"version":"3.51.2"},"reference-count":25,"publisher":"American Mathematical Society (AMS)","issue":"216","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n Let\n \n \n \n n<\/mml:mi>\n n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n be a positive integer. We say\n \n \n \n n<\/mml:mi>\n n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n looks like a power of<\/italic>\n 2 modulo a prime\n \n \n \n p<\/mml:mi>\n p<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n if there exists an integer\n \n \n \n \n \n e<\/mml:mi>\n p<\/mml:mi>\n <\/mml:msub>\n \n \u2265\n \n <\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n e_p \\geq 0<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n such that\n \n \n \n \n n<\/mml:mi>\n \n \u2261\n \n <\/mml:mo>\n \n 2<\/mml:mn>\n \n \n e<\/mml:mi>\n p<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:msup>\n (<\/mml:mo>\n mod<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n \n p<\/mml:mi>\n <\/mml:mrow>\n )<\/mml:mo>\n <\/mml:mrow>\n n \\equiv 2^{e_p} (\\operatorname {mod} {p})<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . First, we provide a simple proof of the fact that a positive integer which looks like a power of\n \n \n \n 2<\/mml:mn>\n 2<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n modulo all but finitely many primes is in fact a power of\n \n \n \n 2<\/mml:mn>\n 2<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . Next, we define an\n \n \n \n \n x<\/mml:mi>\n x<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n -pseudopower of the base\n \n \n \n 2<\/mml:mn>\n 2<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n <\/italic>\n to be a positive integer\n \n \n \n n<\/mml:mi>\n n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n that is not a power of\n \n \n \n 2<\/mml:mn>\n 2<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , but looks like a power of\n \n \n \n 2<\/mml:mn>\n 2<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n modulo all primes\n \n \n \n \n p<\/mml:mi>\n \n \u2264\n \n <\/mml:mo>\n x<\/mml:mi>\n <\/mml:mrow>\n p \\leq x<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . Let\n \n \n \n \n \n P<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n (<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n P_2 (x)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n denote the least such\n \n \n \n n<\/mml:mi>\n n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . We give an unconditional upper bound on\n \n \n \n \n \n P<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n (<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n P_2 (x)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , a conditional result (on ERH) that gives a lower bound, and a heuristic argument suggesting that\n \n \n \n \n \n P<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n (<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n P_2 (x)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is about\n \n \n \n \n exp<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n (<\/mml:mo>\n \n c<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n x<\/mml:mi>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n log<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \\exp ( c_2 x \/ \\log x)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n for a certain constant\n \n \n \n \n c<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n c_2<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . We compare our heuristic model with numerical data obtained by a sieve. Some results for bases other than\n \n \n \n 2<\/mml:mn>\n 2<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n are also given.\n <\/p>","DOI":"10.1090\/s0025-5718-96-00762-4","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T18:14:28Z","timestamp":1027707268000},"page":"1737-1747","source":"Crossref","is-referenced-by-count":10,"title":["Results and estimates on pseudopowers"],"prefix":"10.1090","volume":"65","author":[{"given":"Eric","family":"Bach","sequence":"first","affiliation":[]},{"given":"Richard","family":"Lukes","sequence":"additional","affiliation":[]},{"given":"Jeffrey","family":"Shallit","sequence":"additional","affiliation":[]},{"given":"H.","family":"Williams","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[1996]]},"reference":[{"key":"1","doi-asserted-by":"publisher","first-page":"712","DOI":"10.2307\/1968951","article-title":"Rings with minimal condition for left ideals","volume":"40","author":"Hopkins, Charles","year":"1939","journal-title":"Ann. of Math. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0003-486X","issn-type":"print"},{"key":"2","doi-asserted-by":"crossref","unstructured":"E. Bach and J. Sorenson. Explicit bounds for primes in residue classes. In Walter Gautschi, ed., Mathematics of Computation 1943\u20131993: A Half-Century of Computational Mathematics, Proc. Symp. Appl. Math. 48 (1994), 535\u2013539. Full version submitted to Math. Comp.","DOI":"10.1090\/psapm\/048\/1314886"},{"issue":"2","key":"3","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/bf01932283","article-title":"The segmented sieve of Eratosthenes and primes in arithmetic progressions to 10\u00b9\u00b2","volume":"17","author":"Bays, Carter","year":"1977","journal-title":"Nordisk Tidskr. Informationsbehandling (BIT)","ISSN":"https:\/\/id.crossref.org\/issn\/0901-246X","issn-type":"print"},{"key":"4","series-title":"Pure and Applied Mathematics, Vol. 58","volume-title":"Riemann's zeta function","author":"Edwards, H. M.","year":"1974"},{"key":"5","doi-asserted-by":"crossref","unstructured":"D. Hilbert. Die Theorie der algebraischen Zahlk\u00f6rper. Jahresbericht der Deutschen Mathematiker-Vereinigung 4 (1897), 175\u2013546. Reprinted in Gesammelte Abhandlungen, Vol. I, pp. 63\u2013363.","DOI":"10.1007\/978-3-642-50831-8_7"},{"key":"6","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2103-4","volume-title":"A classical introduction to modern number theory","volume":"84","author":"Ireland, Kenneth","year":"1990","ISBN":"https:\/\/id.crossref.org\/isbn\/038797329X","edition":"2"},{"issue":"4","key":"7","doi-asserted-by":"publisher","first-page":"269","DOI":"10.2307\/2320551","article-title":"Eisenstein reciprocity and \ud835\udc5bth-power residues","volume":"88","author":"Kraft, James","year":"1981","journal-title":"Amer. Math. Monthly","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9890","issn-type":"print"},{"issue":"3","key":"8","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/BF01390234","article-title":"A bound for the least prime ideal in the Chebotarev density theorem","volume":"54","author":"Lagarias, J. C.","year":"1979","journal-title":"Invent. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0020-9910","issn-type":"print"},{"key":"9","volume-title":"Algebraic number theory","author":"Lang, Serge","year":"1970"},{"key":"10","doi-asserted-by":"publisher","first-page":"433","DOI":"10.2307\/2004491","article-title":"Integer sequences having prescribed quadratic character","volume":"24","author":"Lehmer, D. H.","year":"1970","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"11","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/BF01389788","article-title":"On Artin\u2019s conjecture and Euclid\u2019s algorithm in global fields","volume":"42","author":"Lenstra, H. W., Jr.","year":"1977","journal-title":"Invent. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0020-9910","issn-type":"print"},{"key":"12","doi-asserted-by":"crossref","unstructured":"R. F. Lukes, C. D. Patterson, and H. C. Williams. Some results on pseudosquares. Math. Comp. 65 (1996), 361\u2013372.","DOI":"10.1090\/S0025-5718-96-00678-3"},{"key":"13","unstructured":"R. F. Lukes, C. D. Patterson, and H. C. Williams. Numerical sieving devices: their history and some applications. Nieuw Arch. Wisk. (4) 13 (1995), 113\u2013139."},{"issue":"6","key":"14","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/BF01199060","article-title":"A problem analogous to Artin\u2019s conjecture for primitive roots and its applications","volume":"57","author":"Murata, Leo","year":"1991","journal-title":"Arch. Math. (Basel)","ISSN":"https:\/\/id.crossref.org\/issn\/0003-889X","issn-type":"print"},{"issue":"4","key":"15","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1016\/0196-6774(83)90014-7","article-title":"Fast compact prime number sieves (among others)","volume":"4","author":"Pritchard, Paul","year":"1983","journal-title":"J. Algorithms","ISSN":"https:\/\/id.crossref.org\/issn\/0196-6774","issn-type":"print"},{"key":"16","first-page":"64","article-title":"Approximate formulas for some functions of prime numbers","volume":"6","author":"Rosser, J. Barkley","year":"1962","journal-title":"Illinois J. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0019-2082","issn-type":"print"},{"key":"17","first-page":"307","article-title":"On the congruence \ud835\udc4e^{\ud835\udc65}\u2261\ud835\udc4f (\ud835\udc5a\ud835\udc5c\ud835\udc51\ud835\udc5d)","volume":"8","author":"Schinzel, A.","year":"1960","journal-title":"Bull. Acad. Polon. Sci. S\\'{e}r. Sci. Math. Astronom. Phys.","ISSN":"https:\/\/id.crossref.org\/issn\/0001-4117","issn-type":"print"},{"key":"18","doi-asserted-by":"publisher","first-page":"161","DOI":"10.4064\/aa-17-2-161-168","article-title":"A refinement of a theorem of Gerst on power residues","volume":"17","author":"Schinzel, A.","year":"1970","journal-title":"Acta Arith.","ISSN":"https:\/\/id.crossref.org\/issn\/0065-1036","issn-type":"print"},{"key":"19","doi-asserted-by":"publisher","first-page":"397","DOI":"10.4064\/aa-27-1-397-420","article-title":"On power residues and exponential congruences","volume":"27","author":"Schinzel, A.","year":"1975","journal-title":"Acta Arith.","ISSN":"https:\/\/id.crossref.org\/issn\/0065-1036","issn-type":"print"},{"key":"20","doi-asserted-by":"publisher","first-page":"243","DOI":"10.2307\/2005479","article-title":"Sharper bounds for the Chebyshev functions \ud835\udf03(\ud835\udc65) and \ud835\udf13(\ud835\udc65)","volume":"29","author":"Rosser, J. Barkley","year":"1975","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"21","doi-asserted-by":"crossref","unstructured":"A. J. Stephens and H. C. Williams. An open architecture number sieve. In J. H. Loxton, editor, Number Theory and Cryptography, Vol. 154 of London Mathematical Society Lecture Note Series, pages 38\u201375. Cambridge University Press, 1990.","DOI":"10.1017\/CBO9781107325838.005"},{"key":"22","doi-asserted-by":"publisher","first-page":"23","DOI":"10.2307\/1989990","article-title":"Steinitz field towers for modular fields","volume":"46","author":"MacLane, Saunders","year":"1939","journal-title":"Trans. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9947","issn-type":"print"},{"key":"23","unstructured":"E. Trost. Zur Theorie der Potenzreste. Nieuw Arch. Wiskunde 18 (1934), 58\u201361."},{"issue":"2","key":"24","doi-asserted-by":"publisher","first-page":"141","DOI":"10.4064\/aa-41-2-141-150","article-title":"Pseudoprimes and a generalization of Artin\u2019s conjecture","volume":"41","author":"Wagstaff, Samuel S., Jr.","year":"1982","journal-title":"Acta Arith.","ISSN":"https:\/\/id.crossref.org\/issn\/0065-1036","issn-type":"print"},{"key":"25","doi-asserted-by":"crossref","unstructured":"H. C. Williams and J. O. Shallit. Factoring integers before computers. In Walter Gautschi, ed., Mathematics of Computation 1943\u20131993: A Half-Century of Computational Mathematics, Proc. Symp. Appl. Math. 48 (1994), 481\u2013531.","DOI":"10.1090\/psapm\/048\/1314885"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/1996-65-216\/S0025-5718-96-00762-4\/S0025-5718-96-00762-4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/1996-65-216\/S0025-5718-96-00762-4\/S0025-5718-96-00762-4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T21:17:50Z","timestamp":1776719870000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/1996-65-216\/S0025-5718-96-00762-4\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"references-count":25,"journal-issue":{"issue":"216","published-print":{"date-parts":[[1996,10]]}},"alternative-id":["S0025-5718-96-00762-4"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-96-00762-4","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[1996]]}}}