Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.14/118660
75 Visitors81 Hits1 Downloads
On pseudosquares and pseudopowers
Landman, Bruce; Nathanson, Melvyn B.; Nešetřil, Jaroslav; Nowakowski, Richard J.; Pomerance, Carl and Robertson, Aaron. Combinatorial number theory : proceedings of the 'Integers Conference 2007', Carrollton, Georgia, USA, October 24-27, 2007, p.171-184
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.