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
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
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
Comments