TOPICS
Search

Pseudosquare


The pseudosquare L_p modulo the odd prime p is the least nonsquare positive integer that is congruent to 1 (mod 8) and for which the Legendre symbol (L_p/q)=1 for all odd primes q<=p. They were first considered by Kraitchik (1924, pp. 41-46), who computed all up to L_(47), and were named by Lehmer (1954). Hall (1933) showed that the values of L_p are unbounded as p->infty.

Pseudosquares arise in primality proving. Lukes et al. (1996) computed pseudosquares up to L_(271). The first few pseudosquares are 73, 241, 1009, 2641, 8089, ... (OEIS A002189). Note that the pseudosquares need not be unique so, for example, L_(59)=L_(61), L_(71)=L_(73), L_(83)=L_(89)=L_(97), and so on.


See also

Legendre Symbol, Square Number

Explore with Wolfram|Alpha

References

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.

Referenced on Wolfram|Alpha

Pseudosquare

Cite this as:

Weisstein, Eric W. "Pseudosquare." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Pseudosquare.html

Subject classifications