Results and estimates on pseudopowers |
| |
Authors: | Eric Bach Richard Lukes Jeffrey Shallit H C Williams |
| |
Institution: | Computer Sciences Department, University of Wisconsin, 1210 W. Dayton, Madison, Wisconsin 53706 ; Department of Computer Science, University of Manitoba, Winnipeg, Manitoba R3T 2N2, Canada ; Department of Computer Science, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada ; Department of Computer Science, University of Manitoba, Winnipeg, Manitoba R3T 2N2, Canada |
| |
Abstract: | Let be a positive integer. We say looks like a power of 2 modulo a prime if there exists an integer such that . First, we provide a simple proof of the fact that a positive integer which looks like a power of modulo all but finitely many primes is in fact a power of . Next, we define an -pseudopower of the base to be a positive integer that is not a power of , but looks like a power of modulo all primes . Let denote the least such . We give an unconditional upper bound on , a conditional result (on ERH) that gives a lower bound, and a heuristic argument suggesting that is about for a certain constant . We compare our heuristic model with numerical data obtained by a sieve. Some results for bases other than are also given. |
| |
Keywords: | Pseudopowers |
|
| 点击此处可从《Mathematics of Computation》浏览原始摘要信息 |
| 点击此处可从《Mathematics of Computation》下载免费的PDF全文 |
|