Results and estimates on pseudopowers
HTML articles powered by AMS MathViewer
- by Eric Bach, Richard Lukes, Jeffrey Shallit and H. C. Williams PDF
- Math. Comp. 65 (1996), 1737-1747
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} (\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
- Charles Hopkins, Rings with minimal condition for left ideals, Ann. of Math. (2) 40 (1939), 712–730. MR 12, DOI 10.2307/1968951
- 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.
- Carter Bays and Richard H. Hudson, The segmented sieve of Eratosthenes and primes in arithmetic progressions to $10^{12}$, Nordisk Tidskr. Informationsbehandling (BIT) 17 (1977), no. 2, 121–127. MR 447090, DOI 10.1007/bf01932283
- H. M. Edwards, Riemann’s zeta function, Pure and Applied Mathematics, Vol. 58, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1974. MR 0466039
- 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.
- 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, DOI 10.1007/978-1-4757-2103-4
- James Kraft and Michael Rosen, Eisenstein reciprocity and $n$th-power residues, Amer. Math. Monthly 88 (1981), no. 4, 269–270. MR 610488, DOI 10.2307/2320551
- 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, DOI 10.1007/BF01390234
- Serge Lang, Algebraic number theory, Addison-Wesley Publishing Co., Inc., Reading, Mass.-London-Don Mills, Ont., 1970. MR 0282947
- D. H. Lehmer, Emma Lehmer, and Daniel Shanks, Integer sequences having prescribed quadratic character, Math. Comp. 24 (1970), 433–451. MR 271006, DOI 10.1090/S0025-5718-1970-0271006-X
- H. W. Lenstra Jr., On Artin’s conjecture and Euclid’s algorithm in global fields, Invent. Math. 42 (1977), 201–224. MR 480413, DOI 10.1007/BF01389788
- R. F. Lukes, C. D. Patterson, and H. C. Williams. Some results on pseudosquares. Math. Comp. 65 (1996), 361–372.
- 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.
- 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, DOI 10.1007/BF01199060
- Paul Pritchard, Fast compact prime number sieves (among others), J. Algorithms 4 (1983), no. 4, 332–344. MR 729229, DOI 10.1016/0196-6774(83)90014-7
- J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94. MR 137689
- A. Schinzel, On the congruence $a^{x}\equiv b$ $(\textrm {mod}\ p)$, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys. 8 (1960), 307–309 (English, with Russian summary). MR 125070
- A. Schinzel, A refinement of a theorem of Gerst on power residues, Acta Arith. 17 (1970), 161–168. MR 284417, DOI 10.4064/aa-17-2-161-168
- A. Schinzel, On power residues and exponential congruences, Acta Arith. 27 (1975), 397–420. MR 379432, DOI 10.4064/aa-27-1-397-420
- J. Barkley Rosser and Lowell Schoenfeld, Sharper bounds for the Chebyshev functions $\theta (x)$ and $\psi (x)$, Math. Comp. 29 (1975), 243–269. MR 457373, DOI 10.1090/S0025-5718-1975-0457373-7
- 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.
- Saunders MacLane, Steinitz field towers for modular fields, Trans. Amer. Math. Soc. 46 (1939), 23–45. MR 17, DOI 10.1090/S0002-9947-1939-0000017-3
- E. Trost. Zur Theorie der Potenzreste. Nieuw Arch. Wiskunde 18 (1934), 58–61.
- Samuel S. Wagstaff Jr., Pseudoprimes and a generalization of Artin’s conjecture, Acta Arith. 41 (1982), no. 2, 141–150. MR 674829, DOI 10.4064/aa-41-2-141-150
- 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.
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
- MR Author ID: 159555
- 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
- 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
- © Copyright 1996 by the authors
- 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