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

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. C. Bays and R. H. Hudson. The segmented sieve of Eratosthenes and primes in arithmetic progressions to $10^{12}$. BIT 17 (1977), 121--127. MR 56:5405
  • 4. H. M. Edwards. Riemann's Zeta Function. Academic Press, New York, 1974. MR 57:5922
  • 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. K. Ireland and M. Rosen. A Classical Introduction to Modern Number Theory. Springer-Verlag, 2nd edition, 1990. MR 92e:11001
  • 7. J. Kraft and M. Rosen. Eisenstein reciprocity and $n$th power residues. Amer. Math. Monthly 88 (1981), 269--270. MR 82g:10008
  • 8. J. C. Lagarias, H. L. Montgomery, and A. M. Odlyzko. A bound for the least prime ideal in the Chebotarev density theorem. Inventiones Math. 54 (1979), 271--296. MR 81b:12013
  • 9. S. Lang. Algebraic Number Theory. Addison-Wesley, 1970. MR 44:181
  • 10. D. H. Lehmer, E. Lehmer, and D. Shanks. Integer sequences having prescribed quadratic character. Math. Comp. 24 (1970), 433--451. MR 42:5889
  • 11. H. W. Lenstra, Jr. On Artin's conjecture and Euclid's algorithm in global fields. Inventiones Math. 42 (1977), 201--224. MR 58:576
  • 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. L. Murata. A problem analogous to Artin's conjecture for primitive roots and its applications. Arch. Math. 57 (1991), 555--565. MR 93c:11071
  • 15. P. Pritchard. Fast compact prime number sieves (among others). J. Algorithms 4 (1983), 332--344. MR 85h:11080
  • 16. J. B. Rosser and L. Schoenfeld. Approximate formulas for some functions of prime numbers. Ill. J. Math. 6 (1962), 64--94. MR 25:1139
  • 17. A. Schinzel. On the congruence $a^x \equiv b$ (mod $p$). Bull. Acad. Polon. Sci. 8 (1960), 307--309. MR 23:A2377
  • 18. A. Schinzel. A refinement of a theorem of Gerst on power residues. Acta Arith. 17 (1970), 161--168. MR 44:1644
  • 19. A. Schinzel. On power residues and exponential congruences. Acta Arith. 27 (1975), 397--420. MR 52:337
  • 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. S. S. Wagstaff, Jr. Pseudoprimes and a generalization of Artin's conjecture. Acta Arith. 41 (1982), 141--150. MR 83m:10004
  • 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

American Mathematical Society