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

Author

Wolfdieter Lang, Oct 25 2013

Keywords

• nonn
• tabf
• easy

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

Examples

			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.
		

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

Crossrefs

Cf. A000040, A002144, A063987.

Programs

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 *)

Formula

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