A307767 -id:A307767 - cp's OEIS frontend

A307798 The "residue" pseudoprimes: odd composite numbers n such that q(n)^((n-1)/2) == 1 (mod n), where base q(n) is the smallest prime quadratic residue modulo n.

121, 561, 1105, 1541, 1729, 1905, 2465, 4033, 5611, 8321, 8481, 10585, 15709, 15841, 16297, 18705, 18721, 19345, 25761, 28009, 29341, 30121, 31697, 33153, 34945, 42799, 44173, 46657, 49141, 52633, 55969, 62745, 63973, 65077, 69781, 75361, 76627, 79381, 82513, 85489, 88573, 90241, 102311

Offset: 1

Thomas Ordowski, Apr 29 2019

nonn

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.

			3^((121-1)/2) == 1 (mod 121), 2^((561-1)/2) == 1 (mod 561), ...

Cf. A002997, A033181, A306530, A307767 (the "non-residue" pseudoprimes).

q[n_] := Module[{p = 2, pn = Prime[n]}, While[JacobiSymbol[p, pn] != 1, p = NextPrime[p]]; p]; aQ[n_] := CompositeQ[n] && PowerMod[q[n], (n - 1)/2, n] == 1; Select[Range[3, 110000, 2], aQ] (* Amiram Eldar, Apr 29 2019 *)

More terms from Amiram Eldar, Apr 29 2019

A307809 Smallest "non-residue" pseudoprime to base prime(n).

Original entry on oeis.org

3277, 3281, 121463, 491209, 11530801, 512330281, 15656266201

Offset: 1

Amiram Eldar and Thomas Ordowski, Apr 30 2019

a(n) is the smallest odd composite k, with q = A020649(k) = prime(n), such that q^((k-1)/2) == -1 (mod k).

a(8) <= 139309114031, a(9) <= 7947339136801, a(10) <= 72054898434289, a(11) <= 334152420730129, a(12) <= 17676352761153241, a(13) <= 172138573277896681. - Daniel Suteu, Apr 30 2019

Cf. A000229, A020649, A307767 (the "non-residue" pseudoprimes).

residueQ[n_, m_] := Module[{ans = 0}, Do[If[Mod[k^2, m] == n, ans = True; Break[]], {k, 0, Floor[m/2]}]; ans]; A020649[n_] := Module[{m = 0}, While[ residueQ[m, n], m++]; m]; a[n_] := Module[{p = Prime[n], k = 3}, While[PrimeQ[k] || PowerMod[p, (k-1)/2, k] != k-1 || A020649[k] != p , k+=2]; k]; Array[a, 6]

a(7) from Daniel Suteu, Apr 30 2019

A309284 a(n) is the smallest odd composite k such that prime(n)^((k-1)/2) == -1 (mod k) and b^((k-1)/2) == 1 (mod k) for every natural b < prime(n).

Original entry on oeis.org

3277, 5173601, 2329584217, 188985961, 5113747913401, 30990302851201, 2528509579568281, 5189206896360728641, 12155831039329417441

Offset: 1

Thomas Ordowski, Jul 21 2019

a(n) is an Euler pseudoprime to base 2, so it is also a Fermat pseudoprime to base 2.
This sequence is analogous to the sequence A000229 of primes.
Conjecture: the smallest quadratic non-residue modulo a(n) is prime(n), i.e., A020649(a(n)) = prime(n).
a(10) <= 41154189126635405260441. - Daniel Suteu, Jul 22 2019

Cf. A000229, A001567, A006970, A307767, A309285.

isok(n,k) = (k%2==1) && !isprime(k) && Mod(prime(n), k)^((k-1)/2) == Mod(-1, k) && !for(b=2, prime(n)-1, if(Mod(b, k)^((k-1)/2) != Mod(1, k), return(0)));
a(n) = for(k=9, oo, if(isok(n, k), return(k))); \\ Daniel Suteu, Jul 22 2019

According to the data, b^((a(n)-1)/2) == (b / a(n)) (mod a(n)) for every natural b <= prime(n), where (x / y) is the Jacobi symbol.

a(5)-a(9) from Amiram Eldar, Jul 21 2019

cp's OEIS Frontend

A307798 The "residue" pseudoprimes: odd composite numbers n such that q(n)^((n-1)/2) == 1 (mod n), where base q(n) is the smallest prime quadratic residue modulo n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A307809 Smallest "non-residue" pseudoprime to base prime(n).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Extensions

A309284 a(n) is the smallest odd composite k such that prime(n)^((k-1)/2) == -1 (mod k) and b^((k-1)/2) == 1 (mod k) for every natural b < prime(n).

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Formula

Extensions