On Pseudosquares and Pseudopowers
| dc.creator | Pomerance, Carl | |
| dc.creator | Shparlinski, Igor E. | |
| dc.date | 2007-12-07 | |
| dc.date | 2007-12-17 | |
| dc.date.accessioned | 2026-07-07T08:49:12Z | |
| dc.date.available | 2026-07-07T08:49:12Z | |
| dc.description | Introduced by Kraitchik and Lehmer, an $x$-pseudosquare is a positive integer $n\equiv1\pmod 8$ that is a quadratic residue for each odd prime $p\le x$, yet is not a square. We use bounds of character sums to prove that pseudosquares are equidistributed in fairly short intervals. An $x$-pseudopower to base $g$ is a positive integer which is not a power of $g$ yet is so modulo $p$ for all primes $p\le x$. It is conjectured by Bach, Lukes, Shallit, and Williams that the least such number is at most $\exp(a_g x/\log x)$ for a suitable constant $a_g$. A bound of $\exp(a_g x\log\log x/\log x)$ is proved conditionally on the Riemann Hypothesis for Dedekind zeta functions, thus improving on a recent conditional exponential bound of Konyagin and the present authors. We also give a GRH-conditional equidistribution result for pseudopowers that is analogous to our unconditional result for pseudosquares. | |
| dc.identifier | https://arxiv.org/abs/0712.1081 | |
| dc.identifier | http://arxiv.org/abs/0712.1081 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/144215 | |
| dc.subject | Number Theory | |
| dc.subject | 11A15, 11L40 | |
| dc.title | On Pseudosquares and Pseudopowers | |
| dc.type | text |