|
| |
|
|
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).
|
|
4
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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)):
|
|
|
MATHEMATICA
|
Table[Table[Mod[a^2, p], {a, 1, (p - 1)/2}], {p,
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,tabf,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
