cp's OEIS Frontend

This sequence is analogous to A000229, but for least prime quadratic residue modulo p.

Note that a(n) is the least odd number m > prime(n) such that prime(n)^((m-1)/2) == 1 (mod m) and q^((m-1)/2) == -1 (mod m) for every prime q < prime(n). Such m is always an odd prime.

As is well known, for an odd prime p, a prime q is a quadratic residue modulo p if and only if q^((p-1)/2) == 1 (mod p). Hence the above definition of these pseudoprimes.

Such pseudoprimes n which are both "residue" and "non-residue", obviously to different bases q(n) and b(n), are particularly interesting: 29341, 49141, 1251949, 1373653, 2284453, ... These five numbers are in A244626.

Note that the absolute Euler pseudoprimes are odd composite numbers n such that b^((n-1)/2) == 1 (mod n) for every base b that is a quadratic residue modulo n and coprime to n. There are no odd composite numbers n such that b^((n-1)/2) == -1 (mod n) for every base b that is a quadratic non-residue modulo n and coprime to n. The absolute Euler-Jacobi pseudoprimes do not exist.

For n > 0, a(n) = n if and only if 2n+1 is prime.

If a(n) < n, then 2n+1 is composite.

Theorem: a(n) > n if and only if 2n+1 is an absolute Euler pseudoprime.

Conjecture: if 2n+1 is an absolute Euler pseudoprime, then a(n) = phi(2n+1).