A020649 -id:A020649 - cp's OEIS frontend

A307767 The "non-residue" pseudoprimes: odd composite numbers n such that b(n)^((n-1)/2) == -1 (mod n), where base b(n) = A020649(n).

3277, 3281, 29341, 49141, 80581, 88357, 104653, 121463, 196093, 314821, 320167, 458989, 476971, 489997, 491209, 721801, 800605, 838861, 873181, 877099, 973241, 1004653, 1251949, 1268551, 1302451, 1325843, 1373653, 1397419, 1441091, 1507963, 1509709, 1530787, 1590751, 1678541, 1809697

Offset: 1

Thomas Ordowski, Apr 27 2019

nonn

As is well known, for an odd prime p, b(p) is the smallest quadratic non-residue b modulo p if and only if b(p) is the smallest base b such that b^((p-1)/2) == -1 (mod p). Note that b(n) is always a prime.
Conjecture: If 2^((n-1)/2) == -1 (mod n), then b(n) = 2, where b(n) as above. This is true for odd primes n; is it for odd composites n? If so, then all composite numbers n such that 2^((n-1)/2) == -1 (mod n) are in this sequence.
It seems that, for defined pseudoprimes n (similar to the odd primes p),
b(n) is the smallest base b such that b^((n-1)/2) == -1 (mod n), although this is not required by their definition.
Note: a "non-residue" pseudoprime n is a strong pseudoprime to base b(n); the Jacobi symbol (b(n)/n) = -1, where b(n) is the smallest non-residue modulo n; such a pseudoprime n is not a Proth number, so n = k*2^m + 1 with odd k > 2^m.
Problem: are there infinitely many such numbers?

			2^((3277-1)/2) == -1 (mod 3277), 3^((3281-1)/2) == -1 (mod 3281), ...

Cf. A001262, A006970, A020649, A047713, A053760, A244626, A307798 (the "residue" pseudoprimes), A307809.

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]; aQ[n_] := CompositeQ[n] && PowerMod[A020649[n], ((n - 1)/2), n] == n - 1; Select[Range[3, 110000, 2], aQ] (* Amiram Eldar, Apr 27 2019 *)

More terms from Amiram Eldar, Apr 27 2019

A053760 Smallest positive quadratic nonresidue modulo p, where p is the n-th prime.

Original entry on oeis.org

2, 2, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, 3, 2, 5, 2, 2, 2, 2, 7, 5, 3, 2, 3, 5, 2, 3, 2, 2, 3, 3, 2, 3, 2, 2, 3, 2, 2, 5, 2, 2, 2, 7, 5, 2, 3, 2, 3, 2, 2, 3, 7, 7, 2, 3, 5, 2, 3, 2, 3, 2, 2, 2, 11, 5, 2, 2, 5, 2, 2, 3, 7, 3, 2, 2, 5, 2, 2, 3, 7, 2, 2, 7, 5, 3, 2, 3, 5, 2, 3, 2, 13, 3, 2, 2, 5, 2, 3, 2, 2, 2, 2, 2

Offset: 1

Steven Finch, Apr 05 2000

nonn

Assuming the Generalized Riemann Hypothesis, Montgomery proved a(n) << (log p(n))^2, meaning that there is a constant c such that |a(n)| <= c*(log p(n))^2. - Jonathan Vos Post, Jan 06 2007
a(n) < 1 + sqrt(p), where p is the n-th prime (Theorem 3.9 in Niven, Zuckerman, and Montgomery). - Jonathan Sondow, May 13 2010
Treviño proves that a(n) < 1.1 p^(1/4) log p for n > 2 where p is the n-th prime. - Charles R Greathouse IV, Dec 06 2012
a(n) is always a prime, because if x*y is a nonresidue, then x or y must also be a nonresidue. - Jonathan Sondow, May 02 2013
a(n) is the smallest prime q such that the congruence x^2 == q (mod p) has no solution 0 < x < p, where p = prime(n). For n > 1, a(n) is the smallest base b such that b^((p-1)/2) == -1 (mod p), where odd p = prime(n). - Thomas Ordowski, Apr 24 2019

			The 5th prime is 11, and the positive quadratic residues mod 11 are 1^2 = 1, 2^2 = 4, 3^2 = 9, 4^2 = 5 and 5^2 = 3. Since 2 is missing, a(5) = 2.
The only positive quadratic redidue mod 2 is 1, so a(1)=2.

Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 94-98.
Hugh L. Montgomery, Topics in Multiplicative Number Theory, 3rd ed., Lecture Notes in Mathematics, Vol. 227 (1971), MR 49:2616.
Ivan Niven, Herbert S. Zuckerman, and Hugh L. Montgomery, An Introduction to the Theory Of Numbers, Fifth Edition, John Wiley and Sons, Inc., NY 1991, p. 147.
Paulo Ribenboim, The New Book of Prime Number Records, 3rd ed., Springer-Verlag 1996; Math. Rev. 96k:11112.

T. D. Noe, Table of n, a(n) for n = 1..10000
Robert Baillie and Samuel S. Wagstaff, Lucas pseudoprimes, Mathematics of Computation, Vol. 35, No. 152 (1980), pp. 1391-1417, Math. Rev. 81j:10005, alternative link.
Paul Erdős, Remarks on number theory. I., Mat. Lapok, Vol. 12 (1961), pp. 10-17; Math. Rev. 26 #2410.
Steven R. Finch, Quadratic Residues [Broken link]
Steven R. Finch, Quadratic Residues [From the Wayback machine]
Keith Matthews, Finding n(p), the least quadratic non-residue (mod p)
Enrique Treviño, The least k-th power non-residue, Journal of Number Theory, Vol. 149 (2015),pp. 201-224, alternative link.
Eric Weisstein's World of Mathematics, Quadratic Nonresidue.

Cf. A000229, A020649, A098990.

Table[ p = Prime[n]; First[ Select[ Range[p], JacobiSymbol[#, p] != 1 &]], {n, 1, 100}] (* Jonathan Sondow, Mar 03 2013 *)

residue(n,m)={local(r);r=0;for(i=0,floor(m/2),if(i^2%m==n,r=1));r}
A053760(n)={local(r,m);r=0;m=0;while(r==0,m=m+1;if(!residue(m,prime(n)),r=1));m} \\ Michael B. Porter, May 02 2010

qnr(p)=my(m);while(1,if(!issquare(Mod(m++,p)),return(m)))
a(n)=if(n>1,qnr(prime(n)),2) \\ Charles R Greathouse IV, Feb 27 2013

a(n) = A020649(prime(n)) for n > 1. - Thomas Ordowski, Apr 24 2019

Asymptotic mean: lim_{n->oo} (1/n) * Sum_{k=1..n} a(k) = A098990 (Erdős, 1961). - Amiram Eldar, Oct 29 2020

More terms from James Sellers, Apr 08 2000

A000229 a(n) is the least number m such that the n-th prime is the least quadratic nonresidue modulo m.

Original entry on oeis.org

3, 7, 23, 71, 311, 479, 1559, 5711, 10559, 18191, 31391, 422231, 701399, 366791, 3818929, 9257329, 22000801, 36415991, 48473881, 175244281, 120293879, 427733329, 131486759, 3389934071, 2929911599, 7979490791, 36504256799, 23616331489, 89206899239, 121560956039

Offset: 1

N. J. A. Sloane

Note that a(n) is always a prime q > prime(n).
For n > 1, a(n) = prime(k), where k is the smallest number such that A053760(k) = prime(n).
One could make a case for setting a(1) = 2, but a(1) = 3 seems more in keeping with the spirit of the sequence.
a(n) is the smallest odd prime q such that prime(n)^((q-1)/2) == -1 (mod q) and b^((q-1)/2) == 1 (mod q) for every natural base b < prime(n). - Thomas Ordowski, May 02 2019

			a(2) = 7 because the second prime is 3 and 3 is the least quadratic nonresidue modulo 7, 14, 17, 31, 34, ... and 7 is the least of these.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, Table of n, a(n) for n = 1..38 (from the web page of Tomás Oliveira e Silva)
H. J. Godwin, On the least quadratic non-residue, Proc. Camb. Phil. Soc., 61 (3) (1965), 671-672.
A. J. Hanson, G. Ortiz, A. Sabry and Y.-T. Tai, Discrete Quantum Theories, arXiv preprint arXiv:1305.3292 [quant-ph], 2013.
A. J. Hanson, G. Ortiz, A. Sabry, Y.-T. Tai, Discrete quantum theories, (a different version). (To appear in J. Phys. A: Math. Theor., 2014).
Tomás Oliveira e Silva, Least primitive root of prime numbers
Hans Salié, Uber die kleinste Primzahl, die eine gegebene Primzahl als kleinsten positiven quadratischen Nichtrest hat, Math. Nachr. 29 (1965) 113-114.
Yu-Tsung Tai, Discrete Quantum Theories and Computing, Ph.D. thesis, Indiana University (2019).

Cf. A020649, A025021, A053760, A307809. For records see A133435.

Differs from A002223, A045535 at 12th term.

leastNonRes[p_] := For[q = 2, True, q = NextPrime[q], If[JacobiSymbol[q, p] != 1, Return[q]]]; a[1] = 3; a[n_] := For[pn = Prime[n]; k = 1, True, k++, an = Prime[k]; If[pn == leastNonRes[an], Print[n, " ", an];  Return[an]]]; Array[a, 20] (* Jean-François Alcover, Nov 28 2015 *)

Definition corrected by Melvin J. Knight (MELVIN.KNIGHT(AT)ITT.COM), Dec 08 2006

Name edited by Thomas Ordowski, May 02 2019

A334819 Largest quadratic nonresidue modulo n (with n >= 3).

Original entry on oeis.org

2, 3, 3, 5, 6, 7, 8, 8, 10, 11, 11, 13, 14, 15, 14, 17, 18, 19, 20, 21, 22, 23, 23, 24, 26, 27, 27, 29, 30, 31, 32, 31, 34, 35, 35, 37, 38, 39, 38, 41, 42, 43, 44, 45, 46, 47, 48, 48, 50, 51, 51, 53, 54, 55, 56, 56, 58, 59, 59, 61, 62, 63, 63, 65, 66, 67

Offset: 3

Peter Schorn, May 12 2020

The largest nonnegative integer less than n which is not a square modulo n.

If p is a prime congruent 3 modulo 4 then a(p) = p-1 since -1 is not a quadratic residue for such primes.

			The squares modulo 3 are 0 and 1. Therefore a(3) = 2. The nonsquares modulo 4 are 2 and 3 which makes a(4) = 3. Modulo 5 we have 0, 1 and 4 as squares giving a(5) = 3. 0, 1 and 4 are also the squares modulo 6 resulting in a(6) = 5. Since 10007 is a prime of the form 4*k + 3, a(10007) = 10006.

Robert Israel, Table of n, a(n) for n = 3..10000

Cf. A020649, A047210 (the largest square modulo n), A192450 (a(n)=n-1).

f:= proc(n) local k;
  for k from n-1 by -1 do if numtheory:-msqrt(k,n)=FAIL then return k fi
  od
end proc:
map(f, [$3..100]); # Robert Israel, May 14 2020

a[n_] := Module[{r}, For[r = n-1, r >= 1, r--, If[!IntegerQ[Sqrt[Mod[r, n]] ], Return[r]]]];
a /@ Range[3, 100] (* Jean-François Alcover, Aug 15 2020 *)

a(n) = forstep(r = n - 1, 1, -1, if(!issquare(Mod(r, n)), return(r)))

A248972 a(n) is the smallest b such that b^((p-1)/2) == -1 (mod p) where p = A080076(n) is the n-th Proth prime.

Original entry on oeis.org

2, 2, 2, 3, 3, 5, 3, 5, 7, 3, 3, 3, 5, 3, 5, 7, 3, 5, 3, 3, 3, 5, 13, 3, 3, 3, 5, 3, 5, 7, 5, 13, 3, 3, 13, 3, 11, 5, 3, 3, 3, 11, 3, 11, 3, 3, 5, 3, 7, 3, 3, 5, 3, 5, 11, 3, 3, 5, 11, 3, 7, 5, 5, 3, 5, 3, 5, 3, 3, 3, 5, 3, 3, 3, 19, 3, 3, 3, 7, 7, 3, 3, 11, 5, 3, 3, 5, 3, 11, 5, 3, 7

Offset: 1

M. F. Hasler, Oct 18 2014

nonn

Proth's theorem asserts that p=1+k*2^m (with odd k < 2^m) is prime if there exists b such that b^((p-1)/2) == -1 (mod n). This sequence lists the smallest b which certifies primality of A080076(n) via this relation.

For n > 3, a(n) is an odd prime. - Thomas Ordowski, Apr 23 2019

Cf. A080076.

A subsequence of A020649 and of A053760.

A248972(n)=my(N=A080076[n]);for(a=0,9e9,Mod(a,N)^(N\2)==-1&&return(a))
A080076=[];forprime(p=1,99999,isproth(p)&&(A080076=concat(A080076,p))&&print1(A248972(#A080076)","))
isproth(x)={ !bittest(x--, 0) & (x>>valuation(x, 2))^2 < x }

a(n) = A020649(A080076(n)) = A053760(k), where prime(k) = A080076(n). - Thomas Ordowski, Apr 23 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

A307767 The "non-residue" pseudoprimes: odd composite numbers n such that b(n)^((n-1)/2) == -1 (mod n), where base b(n) = A020649(n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A053760 Smallest positive quadratic nonresidue modulo p, where p is the n-th prime.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A000229 a(n) is the least number m such that the n-th prime is the least quadratic nonresidue modulo m.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Extensions

A334819 Largest quadratic nonresidue modulo n (with n >= 3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A248972 a(n) is the smallest b such that b^((p-1)/2) == -1 (mod p) where p = A080076(n) is the n-th Proth prime.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Formula

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