A230077 Table a(n,m) giving in row n all k from {1, 2, ..., prime(n)-1} for which the Legendre symbol (k/prime(n)) = +1, for odd prime(n).

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

Offset

2,3

Comments

The length of row n is r(n) = (prime(n) - 1)/2, with prime(n) = A000040(n), n >= 2.

If k from {1, 2, ..., p-1} appears in row n then the Legendre symbol (k/prime(n)) = +1 otherwise it is -1.

The Legendre symbol (k/p), p an odd prime and gcd(k,p) = 1, is +1 if there exists an integer x with x^2 == k (mod p) and -1 otherwise. It is sufficient to consider k from {1, 2, ..., p-1} (gcd(0,p) = p, not 1) because (k/p) = ((k + l*p)/p) for integer l. Because (p - x)^2 == x^2 (mod p), it is also sufficient to consider only x^2 from {1^2, 2^2, ..., ((p-1)/2)^2} which are pairwise incongruent modulo p. See the Hardy-Wright reference. p. 68-69.

For odd primes p one has for the Legendre symbol ((p-1)/p) = (-1/p) = (-1)^(r(n)) (see above for the row length r(n), and theorem 82, p. 69 of Hardy-Wright), and this is +1 for prime p == 1 (mod 4) and -1 for p == 3 (mod 4). Therefore k = p-1 appears in row n iff p = prime(n) is from A002144 = 5, 13, 17, 29, 37, 41,...

For n>=4 (prime(n)>=7) at least one of the integers 2, 3, or 6 appears in every row. - Geoffrey Critzer, May 01 2015

References

G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. Fifth ed., Clarendon Press, 2003.

Links

Alois P. Heinz, Rows n = 2..100, flattened

Formula

a(n,m) = m^2 (mod prime(n)), n >= 2, where prime(n) = A000040(n), m = 1, 2, ..., (prime(n) - 1)/2.

Example

The irregular table a(n,m) begins (here p(n)=prime(n)):
n, p(n)\m 1 2 3  4  5  6   7   8   9  10  11  12  13  14  15
2,   3:   1
3,   5:   1 4
4,   7:   1 4 2
5,  11:   1 4 9  5  3
6,  13:   1 4 9  3 12 10
7,  17:   1 4 9 16  8  2  15  13
8,  19:   1 4 9 16  6 17  11   7   5
9,  23:   1 4 9 16  2 13   3  18  12   8   6
10, 29:   1 4 9 16 25  7  20   6  23  13   5  28  24  22
11, 31    1 4 9 16 25  5  18   2  19   7  28  20  14  10   8
...
Row n=12, p(n)=37: 1, 4, 9, 16, 25, 36, 12, 27, 7, 26, 10, 33, 21, 11, 3, 34, 30, 28.
Row n=13, p(n)=41: 1, 4, 9, 16, 25, 36, 8, 23, 40, 18, 39, 21, 5, 32, 20, 10, 2, 37, 33, 31.
(2/p) = +1 for n=4, p(4) = 7; p(7) = 17, p(9) = 23, p(11) = 31, p(13) = 41, ... This leads to A001132 (primes 1 or 7 (mod 8)).
4 = 5 - 1 appears in row n=3 for p(3)=5 because 5 is from A002144. 10 cannot appear in row 5 for p(5)=11 because 11 == 3 (mod 4), hence 11 is not in A002144.

Maple

T:= n-> (p-> seq(irem(m^2, p), m=1..(p-1)/2))(ithprime(n)):
seq(T(n), n=2..12);  # Alois P. Heinz, May 07 2015

Mathematica

Table[Table[Mod[a^2, p], {a, 1, (p - 1)/2}], {p,
Prime[Range[2, 20]]}] // Grid (* Geoffrey Critzer, Apr 30 2015 *)

Crossrefs

Cf. A000040, A002144, A063987.

Sequence in context: A002193 A020807 A188582 * A055190 A155781 A161772

Adjacent sequences: A230074 A230075 A230076 * A230078 A230079 A230080

Keyword

nonn,tabf,easy

Author

Wolfdieter Lang, Oct 25 2013

Status

approved