A096008 -id:A096008 - cp's OEIS frontend

A165909 a(n) is the sum of the quadratic residues of n.

0, 1, 1, 1, 5, 8, 7, 5, 12, 25, 22, 14, 39, 42, 30, 14, 68, 60, 76, 35, 70, 110, 92, 42, 125, 169, 126, 84, 203, 150, 186, 72, 165, 289, 175, 96, 333, 342, 208, 135, 410, 308, 430, 198, 225, 460, 423, 124, 490, 525, 408, 299, 689, 549, 385, 252, 532, 841, 767, 270

Offset: 1

Christopher Hunt Gribble, Sep 30 2009

nonn

The table below shows n, the number of nonzero quadratic residues (QRs) of n (A105612), the sum of the QRs of n and the nonzero QRs of n (A046071) for n = 1..10.
..n..num QNRs..sum QNRs.........QNRs
..1.........0.........0
..2.........1.........1.........1
..3.........1.........1.........1
..4.........1.........1.........1
..5.........2.........5.........1..4
..6.........3.........8.........1..3..4
..7.........3.........7.........1..2..4
..8.........2.........5.........1..4
..9.........3........12.........1..4..7
.10.........5........25.........1..4..5..6..9
When p is prime >= 5, a(p) is a multiple of p by a variant of Wolstenholme's theorem (see A076409 and A076410). Robert Israel remarks that we don't need Wolstenholme, just the fact that Sum_{x=1..p-1} x^2 = p*(2*p-1)*(p-1)/6. - Bernard Schott, Mar 13 2019

G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 4th ed., Oxford Univ. Press, 1960, pp. 88-90.

Alois P. Heinz, Table of n, a(n) for n = 1..10000 (first 1000 terms from C. H. Gribble)

Row sums of A046071 and of A096008.

Cf. A000290, A076409, A076410.

import Data.List (nub)
a165909 n = sum $ nub $ map (`mod` n) $
                        take (fromInteger n) $ tail a000290_list
-- Reinhard Zumkeller, Aug 01 2012

residueQ[n_, k_] := Length[Select[Range[Floor[k/2]], PowerMod[#, 2, k] == n&, 1]] == 1;
a[n_] := Select[Range[n-1], residueQ[#, n]&] // Total;
Array[a, 60] (* Jean-François Alcover, Mar 13 2019 *)

a(n) = sum(k=0, n-1, k*issquare(Mod(k,n))); \\ Michel Marcus, Mar 13 2019

A366973 Smallest odd prime p such that n^((p+1)/2) == n (mod p).

Original entry on oeis.org

3, 3, 7, 3, 3, 5, 3, 3, 7, 3, 3, 5, 3, 3, 5, 3, 3, 13, 3, 3, 5, 3, 3, 7, 3, 3, 5, 3, 3, 5, 3, 3, 7, 3, 3, 5, 3, 3, 11, 3, 3, 5, 3, 3, 5, 3, 3, 11, 3, 3, 5, 3, 3, 7, 3, 3, 5, 3, 3, 5, 3, 3, 13, 3, 3, 5, 3, 3, 13, 3, 3, 5, 3, 3, 5, 3, 3, 7, 3, 3, 5, 3, 3, 17, 3, 3

Offset: 0

Thomas Ordowski, Oct 30 2023

nonn

a(n) is the smallest odd prime p for which the Legendre symbol (n / p) >= 0.
For any set S of odd primes, by Chinese Remainder Theorem, there is n such that n is a primitive root mod each prime p in S, and then n^((p-1)/2) != 1 (mod p). Since n is invertible mod p, n^((p-1)/2) != 1 (mod p) implies n^((p+1)/2) != n (mod p). So this sequence is unbounded. - Robert Israel, Oct 31 2023
From Charles L. Hohn, Sep 27 2024: (Start)
Smallest odd prime p for which n is a square mod p.
Smallest odd prime p for which n mod p is a member of row A096008(p). (End)

Robin Visser, Table of n, a(n) for n = 0..10000

Cf. A309316, A366930, A366982.

Cf. A096008.

f:= proc(n) local p;
  p:= 2;
  do
    p:= nextprime(p);
    if n &^ ((p+1)/2) - n mod p = 0 then return p fi
  od
end proc:
map(f, [$0..100]); # Robert Israel, Oct 30 2023

a[n_] := Module[{p = 3}, While[PowerMod[n, (p + 1)/2, p] != Mod[n, p], p = NextPrime[p]]; p]; Array[a, 100, 0] (* Amiram Eldar, Oct 30 2023 *)

a(n) = my(p=3); while(Mod(n, p)^((p+1)/2) != n, p=nextprime(p+1)); p; \\ Michel Marcus, Oct 30 2023

a(n) = for(i=2, oo, my(p=prime(i)); for(j=0, (p-1)/2, if(n%p==j^2%p, return(p)))) \\ Charles L. Hohn, Sep 27 2024

More terms from Amiram Eldar, Oct 30 2023

A373748 Triangle read by rows: T(n, k) is k if k is a quadratic residue modulo n, otherwise is -k and is a quadratic nonresidue modulo n. T(0, 0) = 0 by convention.

Original entry on oeis.org

0, 0, 1, 0, 1, 2, 0, 1, -2, 3, 0, 1, -2, -3, 4, 0, 1, -2, -3, 4, 5, 0, 1, -2, 3, 4, -5, 6, 0, 1, 2, -3, 4, -5, -6, 7, 0, 1, -2, -3, 4, -5, -6, -7, 8, 0, 1, -2, -3, 4, -5, -6, 7, -8, 9, 0, 1, -2, -3, 4, 5, 6, -7, -8, 9, 10, 0, 1, -2, 3, 4, 5, -6, -7, -8, 9, -10, 11, 0, 1, -2, -3, 4, -5, -6, -7, -8, 9, -10, -11, 12

Offset: 0

Peter Luschny, Jun 27 2024

			Triangle starts:
  [0] [0]
  [1] [0,  1]
  [2] [0,  1,  2]
  [3] [0,  1, -2,  3]
  [4] [0,  1, -2, -3,  4]
  [5] [0,  1, -2, -3,  4,  5]
  [6] [0,  1, -2,  3,  4, -5,  6]
  [7] [0,  1,  2, -3,  4, -5, -6,  7]
  [8] [0,  1, -2, -3,  4, -5, -6, -7,  8]
  [9] [0,  1, -2, -3,  4, -5, -6,  7, -8,  9]
 [10] [0,  1, -2, -3,  4,  5,  6, -7, -8,  9,  10]

Carl Friedrich Gauss, Vierter Abschnitt. Von den Congruenzen zweiten Grades. Quadratische Reste und Nichtreste. Art. 97, in "Untersuchungen über die höhere Arithmetik", Hrsg. H. Maser, Verlag von Julius Springer, Berlin, 1889.
Peter Luschny, SageMath: is_quadratic_residue.

Signed version of A002262.
Cf. A000004 (column 0), A001477 (main diagonal), A255644(n) + n (row sums).
Cf. A096008, A096013, A373749.

QR := (a, n) -> ifelse(n = 0, 1, NumberTheory:-QuadraticResidue(a, n)):
for n from 0 to 10 do seq(a*QR(a, n), a = 0..n) od;

qr[n_] := qr[n] = Join[Table[PowerMod[k, 2, n], {k, 0, Floor[n/2]}], {n}];
T[0, 0] := 0; T[n_, k_] := If[MemberQ[qr[n], k], k, -k];
Table[T[n, k], {n, 0, 11}, {k, 0, n}] // Flatten

def Trow(n):
    q = set(mod(a * a, n) for a in range(n // 2  + 1)).union({n})
    return [k if k in q else -k for k in range(n + 1)]
for n in range(11): print(Trow(n))

A010378 Squares mod 15.

Original entry on oeis.org

0, 1, 4, 6, 9, 10

Offset: 1

N. J. A. Sloane

Range of A070438; a(k) + a(7-k) = 10, 1 <= k <= 6. -Reinhard Zumkeller, Apr 24 2009

Cf. A010382, A010462, A010421. - Reinhard Zumkeller, Apr 24 2009

Row 15 of A096008.

[quadratic_residues(15)] # Zerinvary Lajos, May 24 2009

A047210 Largest square modulo n.

Original entry on oeis.org

0, 1, 1, 1, 4, 4, 4, 4, 7, 9, 9, 9, 12, 11, 10, 9, 16, 16, 17, 16, 18, 20, 18, 16, 24, 25, 25, 25, 28, 25, 28, 25, 31, 33, 30, 28, 36, 36, 36, 36, 40, 39, 41, 37, 40, 41, 42, 36, 46, 49, 49, 49, 52, 52, 49, 49, 55, 57, 57, 49, 60, 59, 58, 57, 64, 64, 65, 64, 64, 65, 64, 64, 72

Offset: 1

Henry Bottomley, Jun 08 2000

T. D. Noe, Table of n, a(n) for n=1..1000
Eric Weisstein's World of Mathematics, Quadratic Residue

Last elements of rows of A096008.

Table[r=Range[n]; Max[Mod[r^2, n]], {n, 100}] (* T. D. Noe, Dec 18 2008 *)
Table[r = Range[1 + n/2]; Max[Mod[r^2, n]], {n, 100}] (* Zak Seidov, Dec 18 2008 *)

residue(n,m)={local(r);r=0;for(i=0,floor(m/2),if(i^2%m==n,r=1));r}
A047210(n)={local(r,m);r=0;m=n;while(r==0,m=m-1;if(residue(m,n),r=1));m} (End)

A254328 Numbers k such that all x^2 mod k are squares (including 0 and 1).

Original entry on oeis.org

1, 2, 3, 4, 5, 8, 12, 16

Offset: 1

Joerg Arndt, Jan 28 2015

Are there any more terms > 16?
There are no more terms less than 10^12. Probably the sequence is finite. - Charles R Greathouse IV, Jan 29 2015
This is a subsequence of A303704, so it is full. - Jianing Song, Feb 14 2019

			Terms k <= 16 and the squares mod k:
1: [0]
2: [0, 1]
3: [0, 1, 1]
4: [0, 1, 0, 1]
5: [0, 1, 4, 4, 1]
8: [0, 1, 4, 1, 0, 1, 4, 1]
12: [0, 1, 4, 9, 4, 1, 0, 1, 4, 9, 4, 1]
16: [0, 1, 4, 9, 0, 9, 4, 1, 0, 1, 4, 9, 0, 9, 4, 1]
k = 10 is not a term: in the list of squares mod 10, [0, 1, 4, 9, 6, 5, 6, 9, 4, 1], the numbers 5 and 6 are not squares.

Dan Ismailescu and Yunkyu James Lee, Polynomially growing integer sequences all whose terms are composite, arXiv:2501.04851 [math.NT], 2025. (See the proof of Theorem 2.1.)

Cf. A065428, A254329, A096008, A303704.

f[n_] := Mod[Range[n]^2, n]; Select[Range@ 10000, AllTrue[f@ #, IntegerQ[Sqrt[#]] &] &] (* AllTrue function introduced in version 10; Michael De Vlieger, Jan 29 2015 *)

isok(n)=for(k=2,n-1,if(!issquare(lift(Mod(k,n)^2)),return(0)));return(1);
for(n=1,10^9,if(isok(n),print1(n,", ")));

is(n)=for(k=sqrtint(n)+1,n\2, if(!issquare(k^2%n), return(0))); 1
for(m=10,10^6,for(k=0,sqrtint(2*m),if(is(t=m^2-k^2),print(t))))
\\ Charles R Greathouse IV, Jan 29 2015

Keywords fini and full added by Jianing Song, Feb 14 2019

A373749 Triangle read by rows: T(n, k) = MOD(k^2, n) where MOD(a, n) = a if n = 0 and otherwise a - n*floor(a/n). (Quadratic residue.)

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 4, 4, 1, 0, 0, 1, 4, 3, 4, 1, 0, 0, 1, 4, 2, 2, 4, 1, 0, 0, 1, 4, 1, 0, 1, 4, 1, 0, 0, 1, 4, 0, 7, 7, 0, 4, 1, 0, 0, 1, 4, 9, 6, 5, 6, 9, 4, 1, 0, 0, 1, 4, 9, 5, 3, 3, 5, 9, 4, 1, 0, 0, 1, 4, 9, 4, 1, 0, 1, 4, 9, 4, 1, 0

Offset: 0

Peter Luschny, Jun 23 2024

The definition of the binary operation MOD in the name follows CMath (Graham et al.) and Bach & Shallit. This is important because some CAS unfortunately do not follow this definition and throw a 'division by zero' error if n = 0.

Row n reduced to a set is the set of the quadratic residues mod n.

			Triangle starts:
  [0] 0;
  [1] 0, 0;
  [2] 0, 1, 0;
  [3] 0, 1, 1, 0;
  [4] 0, 1, 0, 1, 0;
  [5] 0, 1, 4, 4, 1, 0;
  [6] 0, 1, 4, 3, 4, 1, 0;
  [7] 0, 1, 4, 2, 2, 4, 1, 0;
  [8] 0, 1, 4, 1, 0, 1, 4, 1, 0;
  [9] 0, 1, 4, 0, 7, 7, 0, 4, 1, 0;
 [10] 0, 1, 4, 9, 6, 5, 6, 9, 4, 1, 0;

Eric Bach and Jeffrey Shallit, Algorithmic Number Theory, p. 21.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, 2nd ed., pp. 81f.

Variants: A048152, A096008.

Cf. A048153 (row sums), A373750 (middle terms).

Mod(n, k) = k == 0 ? n : mod(n, k)
T(n, k) = Mod(k^2, n)
for n in 0:10
    [T(n, k) for k in 0:n] |> println
end

REM := (n, k) -> ifelse(k = 0, n, irem(n, k)):
T := n -> local k; seq(REM(k^2, n), k = 0..n):
seq(T(n), n = 0..12);

MOD[n_, k_] := If[k == 0, n, Mod[n, k]];
Table[MOD[k^2, n], {n, 0, 10}, {k, 0, n}]

def A373749(n, k): return mod(k^2, n)
for n in range(11): print([A373749(n, k) for k in range(n + 1)])

A010379 Squares mod 17.

Original entry on oeis.org

0, 1, 2, 4, 8, 9, 13, 15, 16

Offset: 1

N. J. A. Sloane

Row 17 of A096008.

Cf. A028730, A136805.

Union[PowerMod[Range[17], 2, 17]] (* Alonso del Arte, Dec 17 2019 *)

[quadratic_residues(17)] # Zerinvary Lajos, May 24 2009

(1 to 17).map(n => (n * n) % 17).toSet.toSeq.sorted // Alonso del Arte, Dec 17 2019

A010385 Squares mod 23.

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18

Offset: 1

N. J. A. Sloane

Row 23 of A096008. Row 9 of A063987. A028736 (complement), A278580.

Join[{0}, Select[Range[22], JacobiSymbol[#, 23] == 1&]] (* Jean-François Alcover, Oct 07 2018 *)

[quadratic_residues(23)] # Zerinvary Lajos, May 24 2009

A010392 Squares mod 31.

Original entry on oeis.org

0, 1, 2, 4, 5, 7, 8, 9, 10, 14, 16, 18, 19, 20, 25, 28

Offset: 1

N. J. A. Sloane

Row 31 of A096008.

Cf. A010423, A028744.

Union[PowerMod[Range[31], 2, 31]] (* Alonso del Arte, Dec 31 2019 *)

[quadratic_residues(31)] # Zerinvary Lajos, May 24 2009

(1 to 31).map(n => n * n % 31).toSet.toSeq.sorted // Alonso del Arte, Dec 31 2019

cp's OEIS Frontend

A165909 a(n) is the sum of the quadratic residues of n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

A366973 Smallest odd prime p such that n^((p+1)/2) == n (mod p).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Extensions

A373748 Triangle read by rows: T(n, k) is k if k is a quadratic residue modulo n, otherwise is -k and is a quadratic nonresidue modulo n. T(0, 0) = 0 by convention.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

SageMath

A010378 Squares mod 15.

Views

Author

Keywords

Comments

Crossrefs

Programs

Sage

A047210 Largest square modulo n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

A254328 Numbers k such that all x^2 mod k are squares (including 0 and 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Extensions

A373749 Triangle read by rows: T(n, k) = MOD(k^2, n) where MOD(a, n) = a if n = 0 and otherwise a - n*floor(a/n). (Quadratic residue.)

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

Julia

Maple

Mathematica

SageMath