On pseudosquares and pseudopowers

Introduced by Kraitchik and Lehmer, an x-pseudosquare is a positive integer n ≡ I (mod 8) that is a quadratic residue for each odd prime p ≤ 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 ≤ x. It is conjectured by Bach, Lukes, Shallit, and Williams that the least such number is at most exp(agXI log x) for a suitable constant ag. A bound of exp(agx log log xl 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.