A063987 Irregular triangle in which n-th row gives quadratic residues modulo the n-th prime.

1, 1, 1, 4, 1, 2, 4, 1, 3, 4, 5, 9, 1, 3, 4, 9, 10, 12, 1, 2, 4, 8, 9, 13, 15, 16, 1, 4, 5, 6, 7, 9, 11, 16, 17, 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18, 1, 4, 5, 6, 7, 9, 13, 16, 20, 22, 23, 24, 25, 28, 1, 2, 4, 5, 7, 8, 9, 10, 14, 16, 18, 19, 20, 25, 28, 1, 3, 4, 7, 9, 10, 11, 12, 16, 21, 25

Offset: 1

Author

Suggested by Gary W. Adamson, Sep 18 2001

Keywords

• nonn
• tabf
• nice
• easy

Comments

For n >= 2, row lengths are (prime(n) - 1)/2. For example, since 17 is the 7th prime number, the length of row 7 is (17 - 1)/2 = 8. - Geoffrey Critzer, Apr 04 2015

Examples

			Modulo the 5th prime, 11, the (11 - 1)/2 = 5 quadratic residues are 1,3,4,5,9 and the 5 non-residues are 2, 6, 7, 8, 10.
The irregular triangle T(n, k) begins (p is prime(n)):
   n    p  \k 1 2 3 4  5  6  7  8  9 10 11 12 13 14
   1,   2:    1
   2,   3:    1
   3,   5:    1 4
   4,   7:    1 2 4
   5,  11:    1 3 4 5  9
   6:  13:    1 3 4 9 10 12
   7,  17:    1 2 4 8  9 13 15 16
   8,  19:    1 4 5 6  7  9 11 16 17
   9,  23:    1 2 3 4  6  8  9 12 13 16 18
  10,  29:    1 4 5 6  7  9 13 16 20 22 23 24 25 28
  ...  reformatted by _Wolfdieter Lang_, Mar 06 2016
		

References

• Albert H. Beiler, Recreations in the theory of numbers, New York, Dover, (2nd ed.) 1966. See Table 82 at p. 202.

Links

• T. D. Noe, Rows n = 1..100 of triangle, flattened
• C. F. 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.

Crossrefs

Cf. A063988, A010379 (6th row), A010381 (7th row), A010385 (8th row), A010391 (9th row), A010392 (10th row), A278580 (row 23), A230077.

Cf. A076409 (row sums).

Cf. A046071 (for all n), A048152 (for all n, with 0's).

Programs

Maple

with(numtheory): for n from 1 to 20 do for j from 1 to ithprime(n)-1 do if legendre(j, ithprime(n)) = 1 then printf(`%d,`,j) fi; od: od:
# Alternative:
QR := (a, n) -> NumberTheory:-QuadraticResidue(a, n):
for n from 1 to 10 do p := ithprime(n):
print(select(a -> 1 = QR(a, p), [seq(1..p-1)])) od:  # Peter Luschny, Jun 02 2024

Mathematica

row[n_] := (p = Prime[n]; Select[ Range[p - 1], JacobiSymbol[#, p] == 1 &]); Flatten[ Table[ row[n], {n, 1, 12}]] (* Jean-François Alcover, Dec 21 2011 *)

PARI

residue(n,m)=local(r);r=0;for(i=0,floor(m/2),if(i^2%m==n,r=1));r
isA063987(n,m)=residue(n,prime(m)) /* Michael B. Porter, May 07 2010 */

PARI

row(n) = my(p=prime(n)); select(x->issquare(Mod(x,p)), [1..p-1]); \\ Michel Marcus, Nov 07 2020

Python

from sympy import jacobi_symbol as J, prime
def a(n):
    p = prime(n)
    return [1] if n==1 else [i for i in range(1, p) if J(i, p)==1]
for n in range(1, 11): print(a(n)) # Indranil Ghosh, May 27 2017

SageMath

for p in prime_range(30): print(quadratic_residues(p)[1:])
# Peter Luschny, Jun 02 2024

Extensions

Edited by Wolfdieter Lang, Mar 06 2016