login
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.)
11
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.
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
KEYWORD
sign,tabl,easy
AUTHOR
Peter Luschny, May 28 2024
STATUS
approved