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, who computed all up to L_47, and were named by Lehmer. Hall showed that the values of L_p are unbounded as p->∞. 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.

Legendre symbol | square number