The pseudosquare
modulo the odd prime is the least nonsquare positive integer that is congruent
to 1 (mod 8) and for which the Legendre symbol for all odd primes . They were first considered by Kraitchik (1924, pp. 41-46),
who computed all up to ,
and were named by Lehmer (1954). Hall (1933) showed that the values of are unbounded as .
Pseudosquares arise in primality proving. Lukes et al. (1996) computed pseudosquares up to .
The first few pseudosquares are 73, 241, 1009, 2641, 8089, ... (OEIS A002189).
Note that the pseudosquares need not be unique so, for example, , , , and so on.
Bernstein, D. J. "Doubly Focused Enumeration of Locally Square Polynomial Values." Draft, Dec. 31, 2001. http://cr.yp.to/papers/focus.ps.Hall,
M. "Quadratic Residues in Factorization." Bull. Amer. Math. Soc.39,
758-763, 1933.Kraitchik, M. Recherches sue la théorie des
nombres. Paris: Gauthier-Villars, 1924.Lehmer, D. H. "A
Sieve Problem on 'Pseudo-Squares.' " Math. Tables Other Aids Comput.8,
241-242, 1954.Lehmer, D. H. and Lehmer, E.; and Shanks, D. "Integer
Sequences Having Prescribed Quadratic Character." Math. Comput.24,
433-451, 1970.Lukes, R. F.; Patterson, C. D.; and Williams,
H. C. "Some Results on Pseudosquares." Math. Comput.65,
361-372 and S25-S27, 1996.Schinzel, A. "On Pseudosquares."
In New
Trends in Probability and Statistics, Vol. 4: Analytic and Probabilistic Methods
in Number Theory (Ed. A. Laurinčikas, E. Manstavičius,
and V. Stakenas). Utrecht, Netherlands: VSP, pp. 213-220, 1997.Sloane,
N. J. A. Sequence A002189/M5039
in "The On-Line Encyclopedia of Integer Sequences."Stephens,
A. J. and Williams, H. C. "An Open Architecture Number Sieve."
It Number Theory and Cryptography (Sydney, 1989). Cambridge, England: Cambridge
University Press, pp. 38-75, 1990.Williams, H. C. and Shallit,
J. O. "Factoring Integers Before Computers." In Mathematics
of Computation 1943-1993 (Vancouver, 1993) (Ed. W. Gautschi). Providence,
RI: Amer. Math. Soc., pp. 481-531, 1994.
modulo the odd prime 
is the least nonsquare positive integer that is congruent
to 1 (mod 8) and for which the Legendre symbol 
for all odd primes 
. They were first considered by Kraitchik (1924, pp. 41-46),
who computed all up to 
,
and were named by Lehmer (1954). Hall (1933) showed that the values of 
are unbounded as 
.
.
The first few pseudosquares are 73, 241, 1009, 2641, 8089, ... (OEIS A002189).
Note that the pseudosquares need not be unique so, for example, 
, 
, 
, and so on.
