Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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
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?)


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: http://dx.doi.org/10.1090/S0025-5718-96-00762-4
PII: S 0025-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