A373223 Gauss's triangle read by rows: T(n, k) = KP(n, k) * KP(k, n) where KP(n, k) = KroneckerSymbol(prime(n), prime(k)). (Law of Quadratic Reciprocity.)

0, 1, 0, 1, 1, 0, 1, -1, 1, 0, 1, -1, 1, -1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, -1, 1, -1, -1, 1, 1, 0, 1, -1, 1, -1, -1, 1, 1, -1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0

Offset

1

Comments

Gauss gave no fewer than six proofs of the 'theorema aureum' as he called the law of quadratic reciprocity, and two more were found in his estate. Meanwhile, every self-respecting mathematician has added another proof, Lemmermeyer currently lists 345 proofs. A discussion on MathOverflow of the question of which is the best proof can serve as an entertaining introduction to the topic.

Although it is essentially a theoretical result, it has also found applications in cryptosystems (Goldwassser-Micali, Cocks, Paillier encryption). To date, no high-speed algorithm has been found for calculating the values of this sequence.

References

Carolus Fridericus Gauss, Disquisitiones arithmeticae, 1801 (written in 1798).

Franz Lemmermeyer, Reciprocity Laws. From Euler to Eisenstein, Springer 2000.

Links

Table of n, a(n) for n=1..91.

Pete L. Clark, Quadratic Reciprocity I.

Carl Friedrich Gauss, Untersuchungen über höhere Arithmetik, Springer 1889.

Franz Lemmermeyer, Proofs of the Quadratic Reciprocity Law.

MathOverflow, What's the 'best' proof of quadratic reciprocity?.

Formula

Let p, q be distinct odd primes. The law of quadratic reciprocity states that L(p/q)*L(q/p) = (-1)^(((p-1)/2)*((q-1)/2)), where L(p/q) is the Legendre symbol. The Legendre symbol is defined for an odd prime p and an integer a not divisible by p; it is 1 or -1 depending on whether a is a quadratic residue modulo p or not. The Kronecker symbol and the Legendre symbol coincide in these cases. Additionally T(p, p) = K(p, p) = 0 for all primes p and T(2, p) = T(p, 2) = K(2, p) * K(p, 2) = 1 for p > 2 where K(p, q) is the Kronecker symbol.

Example

The triangle is the lower triangular array (including the main diagonal) of the square array:
.
   |sum|n-1| p | 2,  3, 5,  7, 11,13,17, 19, 23,29, 31,37,41, 43, 47,53, ...
  --------------------------------------------------------------------------
   | 0 | 0 | 2 | 0,  1, 1,  1,  1, 1, 1,  1,  1, 1,  1, 1, 1,  1,  1, 1, ...
   | 1 | 1 | 3 | 1,  0, 1, -1, -1, 1, 1, -1, -1, 1, -1, 1, 1, -1, -1, 1, ...
  *| 2 | 2 | 5 | 1,  1, 0,  1,  1, 1, 1,  1,  1, 1,  1, 1, 1,  1,  1, 1, ...
   | 1 | 3 | 7 | 1, -1, 1,  0, -1, 1, 1, -1, -1, 1, -1, 1, 1, -1, -1, 1, ...
   | 0 | 4 |11 | 1, -1, 1, -1,  0, 1, 1, -1, -1, 1, -1, 1, 1, -1, -1, 1, ...
  *| 5 | 5 |13 | 1,  1, 1,  1,  1, 0, 1,  1,  1, 1,  1, 1, 1,  1,  1, 1, ...
  *| 6 | 6 |17 | 1,  1, 1,  1,  1, 1, 0,  1,  1, 1,  1, 1, 1,  1,  1, 1, ...
   | 1 | 7 |19 | 1, -1, 1, -1, -1, 1, 1,  0, -1, 1, -1, 1, 1, -1, -1, 1, ...
   | 0 | 8 |23 | 1, -1, 1, -1, -1, 1, 1, -1,  0, 1, -1, 1, 1, -1, -1, 1, ...
  *| 9 | 9 |29 | 1,  1, 1,  1,  1, 1, 1,  1,  1, 0,  1, 1, 1,  1,  1, 1, ...
   | 0 |10 |31 | 1, -1, 1, -1, -1, 1, 1, -1, -1, 1,  0, 1, 1, -1, -1, 1, ...
  *|11 |11 |37 | 1,  1, 1,  1,  1, 1, 1,  1,  1, 1,  1, 0, 1,  1,  1, 1, ...
  *|12 |12 |41 | 1,  1, 1,  1,  1, 1, 1,  1,  1, 1,  1, 1, 0,  1,  1, 1, ...
   | 1 |13 |43 | 1, -1, 1, -1, -1, 1, 1, -1, -1, 1, -1, 1, 1,  0, -1, 1, ...
   | 0 |14 |47 | 1, -1, 1, -1, -1, 1, 1, -1, -1, 1, -1, 1, 1, -1,  0, 1, ...
  *|15 |15 |53 | 1,  1, 1,  1,  1, 1, 1,  1,  1, 1,  1, 1, 1,  1,  1, 0, ...
.
 '*' marks a Pythagorean prime (A002144). If we index the primes starting at 0 then 0, 1 and the indices of the Pythagorean primes are equal to the row sums.

Maple

KP := (n, k) -> NumberTheory:-KroneckerSymbol(ithprime(n), ithprime(k)):
T := (n, k) -> KP(n, k) * KP(k, n): seq(seq(T(n, k), k = 1..n), n = 1..11);
# Alternative (by quadratic reciprocity):
A373223 := proc(n, k) local p, q;
if n = k then return 0 fi; if n = 1 or k = 1 then return 1 fi;
p := ithprime(n); q := ithprime(k); (-1)^(((p - 1)/2)*((q - 1)/2)) end:
seq(lprint(seq(A373223(n, k), k = 1..n)), n = 1..11);

Mathematica

KP[n_, k_] := KroneckerSymbol[Prime[n], Prime[k]];
Table[KP[n, k] * KP[k, n], {n, 1, 11}, {k, 1, 11}] // MatrixForm

Prog

(SageMath)
def T(n, k):
    if n == k: return 0
    if n == 1 or k == 1: return 1
    p = nth_prime(n); q = nth_prime(k)
    return (-1)^(((p - 1)/2)*((q - 1)/2))
for n in range(1, 12): print([n], [T(n, k) for k in range(1, n + 1)])
(PARI)
KP(p, q) = kronecker(p, q);
T(n, k) =  my(p=prime(n), q=prime(k)); KP(p, q) * KP(q, p);
matrix(7, 7, n, k, T(n, k)) \\ Michel Marcus, May 30 2024

Crossrefs

Family: A217831 (Euclid's triangle), A372726 (Legendre's triangle), A372877 (Jacobi's triangle), A372728 (Kronecker's triangle).

Cf. A373224 (row sums), A373225, A372728, A002144.

Sequence in context: A022924 A295893 A157412 * A023532 A226520 A268921

Adjacent sequences: A373220 A373221 A373222 * A373224 A373225 A373226

Keyword

sign,tabl,easy

Author

Peter Luschny, May 28 2024

Status

approved