Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

   
 

 

Results and estimates on pseudopowers


Authors: Eric Bach, Richard Lukes, Jeffrey Shallit and H. C. Williams
Journal: Math. Comp. 65 (1996), 1737-1747
MSC (1991): Primary 11Y70; Secondary 11Y55, 11A15
DOI: https://doi.org/10.1090/S0025-5718-96-00762-4
MathSciNet review: 1355005
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let $n$ be a positive integer. We say $n$ looks like a power of 2 modulo a prime $p$ if there exists an integer $e_p \geq 0$ such that $n \equiv 2^{e_p}\break (\operatorname {mod}\ {p})$. First, we provide a simple proof of the fact that a positive integer which looks like a power of $2$ modulo all but finitely many primes is in fact a power of $2$. Next, we define an $x$-pseudopower of the base $2$ to be a positive integer $n$ that is not a power of $2$, but looks like a power of $2$ modulo all primes $p \leq x$. Let $P_2 (x)$ denote the least such $n$. We give an unconditional upper bound on $P_2 (x)$, a conditional result (on ERH) that gives a lower bound, and a heuristic argument suggesting that $P_2 (x)$ is about $\exp ( c_2 x / \log x)$ for a certain constant $c_2$. We compare our heuristic model with numerical data obtained by a sieve. Some results for bases other than $2$ are also given.


References [Enhancements On Off] (What's this?)

  • 1. N. C. Ankeny and C. A. Rogers. A conjecture of Chowla. Ann. Math. 53 (1951), 541--550. MR 12:804h
  • 2. E. Bach and J. Sorenson. Explicit bounds for primes in residue classes. In Walter Gautschi, ed., Mathematics of Computation 1943--1993: A Half-Century of Computational Mathematics, Proc. Symp. Appl. Math. 48 (1994), 535--539. Full version submitted to Math. Comp. CMP 95:07
  • 3. Carter Bays and Richard H. Hudson, The segmented sieve of Eratosthenes and primes in arithmetic progressions to 10¹², Nordisk Tidskr. Informationsbehandling (BIT) 17 (1977), no. 2, 121–127. MR 0447090
  • 4. H. M. Edwards, Riemann’s zeta function, Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York-London, 1974. Pure and Applied Mathematics, Vol. 58. MR 0466039
  • 5. D. Hilbert. Die Theorie der algebraischen Zahlkörper. Jahresbericht der Deutschen Mathematiker-Vereinigung 4 (1897), 175--546. Reprinted in Gesammelte Abhandlungen, Vol. I, pp. 63--363.
  • 6. Kenneth Ireland and Michael Rosen, A classical introduction to modern number theory, 2nd ed., Graduate Texts in Mathematics, vol. 84, Springer-Verlag, New York, 1990. MR 1070716
  • 7. James Kraft and Michael Rosen, Eisenstein reciprocity and 𝑛th-power residues, Amer. Math. Monthly 88 (1981), no. 4, 269–270. MR 610488, https://doi.org/10.2307/2320551
  • 8. J. C. Lagarias, H. L. Montgomery, and A. M. Odlyzko, A bound for the least prime ideal in the Chebotarev density theorem, Invent. Math. 54 (1979), no. 3, 271–296. MR 553223, https://doi.org/10.1007/BF01390234
  • 9. Serge Lang, Algebraic number theory, Addison-Wesley Publishing Co., Inc., Reading, Mass.-London-Don Mills, Ont., 1970. MR 0282947
  • 10. D. H. Lehmer, Emma Lehmer, and Daniel Shanks, Integer sequences having prescribed quadratic character, Math. Comp. 24 (1970), 433–451. MR 0271006, https://doi.org/10.1090/S0025-5718-1970-0271006-X
  • 11. H. W. Lenstra Jr., On Artin’s conjecture and Euclid’s algorithm in global fields, Invent. Math. 42 (1977), 201–224. MR 0480413, https://doi.org/10.1007/BF01389788
  • 12. R. F. Lukes, C. D. Patterson, and H. C. Williams. Some results on pseudosquares. Math. Comp. 65 (1996), 361--372. CMP 96:03
  • 13. 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--139. CMP 95:14
  • 14. Leo Murata, A problem analogous to Artin’s conjecture for primitive roots and its applications, Arch. Math. (Basel) 57 (1991), no. 6, 555–565. MR 1135410, https://doi.org/10.1007/BF01199060
  • 15. Paul Pritchard, Fast compact prime number sieves (among others), J. Algorithms 4 (1983), no. 4, 332–344. MR 729229, https://doi.org/10.1016/0196-6774(83)90014-7
  • 16. J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94. MR 0137689
  • 17. A. Schinzel, On the congruence 𝑎^{𝑥}≡𝑏 (𝑚𝑜𝑑𝑝), Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys. 8 (1960), 307–309 (English, with Russian summary). MR 0125070
  • 18. A. Schinzel, A refinement of a theorem of Gerst on power residues, Acta Arith. 17 (1970), 161–168. MR 0284417
  • 19. A. Schinzel, On power residues and exponential congruences, Acta Arith. 27 (1975), 397–420. Collection of articles in memory of Juriĭ Vladimirovič Linnik. MR 0379432
  • 20. L. Schoenfeld. Sharper bounds for the Chebyshev functions $\theta (x)$ and $\psi (x)$. II. Math. Comp. 30 (1976), 337--360. Corrigenda in Math. Comp. 30 (1976), 900. MR 56:15581b; MR 56:15581c
  • 21. 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--75. Cambridge University Press, 1990. CMP 90:13
  • 22. H. Tôyama. A note on the different of the composed field. Kodai Math. Sem. Report 7 (1955), 43--44. MR 17:714
  • 23. E. Trost. Zur Theorie der Potenzreste. Nieuw Arch. Wiskunde 18 (1934), 58--61.
  • 24. Samuel S. Wagstaff Jr., Pseudoprimes and a generalization of Artin’s conjecture, Acta Arith. 41 (1982), no. 2, 141–150. MR 674829
  • 25. H. C. Williams and J. O. Shallit. Factoring integers before computers. In Walter Gautschi, ed., Mathematics of Computation 1943--1993: A Half-Century of Computational Mathematics, Proc. Symp. Appl. Math. 48 (1994), 481--531. CMP 95:07

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 11Y70, 11Y55, 11A15

Retrieve articles in all journals with MSC (1991): 11Y70, 11Y55, 11A15


Additional Information

Eric Bach
Affiliation: Computer Sciences Department, University of Wisconsin, 1210 W. Dayton, Madison, Wisconsin 53706
Email: bach@cs.wisc.edu

Richard Lukes
Affiliation: Department of Computer Science, University of Manitoba, Winnipeg, Manitoba R3T 2N2, Canada
Email: rflukes@cs.umanitoba.ca

Jeffrey Shallit
Affiliation: Department of Computer Science, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada
Email: shallit@graceland.uwaterloo.ca

H. C. Williams
Affiliation: Department of Computer Science, University of Manitoba, Winnipeg, Manitoba R3T 2N2, Canada
Email: hugh_williams@csmail.cs.umanitoba.ca

DOI: https://doi.org/10.1090/S0025-5718-96-00762-4
Keywords: Pseudopowers
Received by editor(s): February 27, 1995
Received by editor(s) in revised form: September 11, 1995
Additional Notes: The research of the first and third authors was supported in part by NSF Grant DCR 92-08639. The research of the first author was also supported by a Foreign Researcher Award from NSERC. The research of the third author was also supported by a grant from NSERC and the Wisconsin Alumni Research Foundation. The research of the second and fourth authors was supported in part by NSERC Grant A7649
Article copyright: © Copyright 1996 by the authors