# Counting Quadratic Nonresidues in Shifted Subsets of the Set of Quadratic Nonresidues for Primesp

Authors: Rocío Meza-Moreno; Mario Pineda-Ruelas
Journal: International Journal of Mathematics and Mathematical Sciences
 (2015)

---

## Abstract

Letp
=
4
k
+
1 be a prime number and F
p the finite field with p elements. For x
∈
1
,
n, N
x will denote the set of quadratic nonresidues less than or equal to x. In this work we calculate the number of quadratic nonresidues in the shifted set N
(
p
-
1
)
/
2
+
a.


---

## Body

## 1. Introduction

Letp be an odd prime, F
p the finite field with p elements, and F
p
∗ the multiplicative group of F
p. We will write a
,
n to denote the set {
a
,
a
+
1
,
…
,
n
} and (
/
p
) to denote the Legendre symbol. Let R be the set of quadratic residues modulo p, including 0, and N
=
F
p
∖
R. The distribution of quadratic residues and nonresidues has been studied with great interest in the literature [1–3]. In [2] Perron finds the number of quadratic residues and nonresidues in the shifted sets R
+
a and N
+
a, where a
∈
F
p
∗, in particular, with a
=
1; his result gives the number of pairs of consecutive quadratic residues and of nonresidues. Perron also gives nonsquare matrices having two properties: each row has the same number of elements in common with every other row and the corresponding elements of every two rows have the same difference. According to Brauer [4], Paley [5] found these matrices and used them in the construction of Hadamard matrices. Following Perron, we can ask what happens to the number of quadratic residues when we shift some subset of R or N. Let R
x
=
{
r
∈
R
:
1
≤
r
≤
x
}. In [6] the authors study the number of quadratic residues in the shifted set R
(
p
-
1
)
/
2
+
a. Let N
x
=
{
n
∈
N
:
1
≤
n
≤
x
} and let p
=
4
k
+
1 be a prime number. In this work we use Perron’s results and elementary techniques to determine the number of quadratic nonresidues (and hence the number of residues) in the set N
(
p
-
1
)
/
2
+
a.Theorem 1 (O. Perron).
Letp
=
4
k
+
1 be a prime number and N the set of quadratic nonresidues modulo p.(1)
Ifa
∈
R and a
≠
0, then N
+
a
∩
R
=
N
+
a
∩
N
=
k.
(2)
Ifa
∈
N, then |
(
N
+
a
)
∩
R
|
=
k
+
1 and |
(
N
+
a
)
∩
N
|
=
k
-
1.Proof.
See [2].


## 2. Some Properties ofR

Ifp
≡
1
(
mod
⁡
4
) is a prime number, then a is a quadratic residue if and only if p
-
a is also a quadratic residue modulo p. We will call this property theelementary symmetry. The elementary symmetry implies that (1)
∑
n
=
1
p
-
1
/
2
n
p
=
0
.If we consider smaller intervals the elementary symmetry is lost, but we still have some useful properties. In general, ifp
=
2
k
+
1, then (2)
k
p
=
p
-
1
/
2
p
=
2
p
-
1
p
=
1
if
and
only
if
p
≡
1,3
mod
⁡
8
,
-
1
if
and
only
if
p
≡
5,7
mod
⁡
8
.In particular, ifp
=
4
k
+
1 we get the following.Corollary 2.
Ifp
≡
1
mod
⁡
4 is a prime number, then (3)
p
-
1
/
2
p
=
1
i
f
a
n
d
o
n
l
y
i
f
p
≡
1
mod
⁡
8
,
-
1
i
f
a
n
d
o
n
l
y
i
f
p
≡
5
mod
⁡
8
.Theorem 3.
Ifp
=
4
k
+
1 is a prime number, then (4)
1
p
-
1
/
2
-
n
p
=
2
p
2
n
+
1
p
.
2
p
-
1
/
2
+
n
p
=
2
p
2
n
-
1
p
.Proof.
The first assertion follows fromp
-
1
-
2
n
/
p
=
2
/
p
(
(
p
-
1
-
2
n
)
/
2
)
/
p and the elementary symmetry. The proof of the second assertion is similar to the one of the first assertion.According to the first assertion of the previous theorem we have that ifp
≡
1
(
mod
⁡
8
), then the numbers p
-
1
/
2
-
n and 2
n
+
1 are both quadratic residues or are both nonresidues modulo p. If p
≡
5
(
mod
⁡
8
), then one of these numbers is a residue and the other one is a nonresidue. This fact gives a correspondence between the numbers p
-
1
/
2
-
n and 2
n
+
1. We can give a similar interpretation to the second assertion.


## 3. Main Results

In this section we count the number of nonresidues in the setN
(
p
-
1
)
/
2
+
a. To do this we arrange the elements in N
+
a in pairs such that the first element of the pair is in the set N
(
p
-
1
)
/
2
+
a and the second one is not, and then we make use of Theorem 1.Lemma 4.
Ifp
=
4
k
+
1 is a prime number and n
=
n
i
+
a
∈
N
+
a is a quadratic nonresidue modulo p, then p
-
n
i is also a quadratic nonresidue and p
-
n
i
∈
N
+
a.We will call the pair of quadratic nonresidues inN
+
a given by (
n
i
+
a
,
p
-
n
i
) acorresponding pair of quadratic nonresidues. If the pair also satisfies n
i
+
a
<
p
-
n
i we will say that (
n
i
+
a
,
p
-
n
i
) is anordered corresponding pair of quadratic nonresidues.Note that asn
i runs in 1
≤
n
i
<
(
p
-
a
)
/
2 then 1
+
a
≤
n
i
+
a
<
p
-
a
/
2
+
a and the corresponding pair p
-
n
i satisfies p
-
a
/
2
+
a
<
p
-
n
i
≤
p
-
1. In particular, for a corresponding pair to be ordered the following condition must be met:(5)
n
i
<
p
-
a
2
.InN
+
a eventually appear some of the integers in 0
,
a, but if a
≤
(
p
-
1
)
/
2, these are not in N
(
p
-
1
)
/
2
+
a and so we have to take these numbers out of consideration. If n
j is the maximum nonresidue such that n
j
≤
(
p
-
a
)
/
2, n
j
+
a
∈
N and its corresponding pair satisfy p
-
n
j
>
(
p
-
1
)
/
2
+
a, then half of the nonresidues left in N
+
a are elements of N
(
p
-
1
)
/
2
+
a (the ones of the form n
i
+
a) and the other half are not (the corresponding pairs p
-
n
i). Therefore, by Theorem 1 we get the following.Theorem 5.
Letp
=
4
k
+
1 be a prime number, a
∈
1
,
(
p
-
1
)
/
2, (6)
n
j
=
max
⁡
n
i
∈
N
:
n
i
≤
p
-
a
2
,
n
i
+
a
∈
N
,
S
=
0,1
,
…
,
a
-
1
,
a
∩
N
+
a
=
i
∈
0
,
a
:
a
-
i
∈
Nand s
=
|
S
∩
N
|. Suppose n
j satisfies the condition(7)
p
-
n
j
>
p
-
1
2
+
a
.
Then the following assertions hold:(1)
Ifa
∈
R, then |
(
N
(
p
-
1
)
/
2
+
a
)
∩
N
|
=
(
k
-
s
)
/
2.
(2)
Ifa
∈
N, then |
(
N
(
p
-
1
)
/
2
+
a
)
∩
N
|
=
(
k
-
1
-
s
)
/
2.If(
p
-
a
)
/
2
∈
N, then in the previous theorem n
j
=
(
p
-
a
)
/
2 and when this happens n
j
+
a
=
p
-
n
j. In this case the theorem does not apply because we get the equality in condition (7). When a corresponding pair satisfies n
i
+
a
=
p
-
n
i we will call it anoverlap.An overlap only occurs whenn
j
=
(
p
-
a
)
/
2
∈
Z and n
j
∈
N. In this situation it is possible to count nonresidues in N
(
p
-
1
)
/
2
+
a using basically the same idea with a slight modification: we must take the overlap into account because n
j
+
a
=
p
-
n
j
∈
N
(
p
-
1
)
/
2
+
a. Thus, if an overlap occurs, we must take 1 off in the result of Theorem 5 before dividing by 2 and then we add 1.Condition (7) may also fail when the left side is smaller than the right side; this happens when there is at least one corresponding pair whose elements are both in the set N
(
p
-
1
)
/
2
+
a; thus in this case both of the pair elements must be taken into account. We call such pair aninner pair. The necessary modification to the result of Theorem 5 is clear: we add 1 for every existing inner pair.Summarizing, for a givena and a prime p
=
4
k
+
1, if o
a is the number of overlaps (there is at most 1 overlap) and p
a is the number of inner pairs, we get the following result.Theorem 6.
Letp
=
4
k
+
1 be a prime number and a
∈
1
,
(
p
-
1
)
/
2 and s as in Theorem 5. Then the following assertions hold: (1)
Ifa
∈
R, then |
(
N
p
-
1
/
2
+
a
)
∩
N
|
=
(
k
-
s
-
o
a
)
/
2
+
o
a
+
p
a.
(2)
Ifa
∈
N, then |
(
N
p
-
1
/
2
+
a
)
∩
N
|
=
(
k
-
1
-
s
-
o
a
)
/
2
+
o
a
+
p
a.For particular values ofa it is possible to give conditions on the prime p so that hypothesis of Theorem 5 holds; moreover, it is possible to determine if an overlap occurs and the number of inner pairs.


## 4. Examples

In this section we use particular values ofa to exemplify the results of the previous section.Proposition 7.
Letp
=
4
k
+
1 be a prime number. (1)
Ifp
≡
1
mod
⁡
8, then |
(
N
(
p
-
1
)
/
2
+
1
)
∩
N
|
=
k
/
2.
(2)
Ifp
≡
5
mod
⁡
8, then |
(
N
(
p
-
1
)
/
2
+
1
)
∩
N
|
=
(
k
+
1
)
/
2.Proof.
Fora
=
1, we get S
=
∅ so that s
=
0 and an overlap can occur only if (
p
-
1
)
/
2
∈
N. From Corollary 2 this happens if and only if 2
/
p
=
-
1. By Theorem 6 the result follows.From the previous proposition, we get the number of pairs of consecutive quadratic residues in the interval1
,
(
p
-
1
)
/
2 for a prime number p
=
4
k
+
1.Corollary 8.
Letp
=
4
k
+
1 be a prime number. The number of pairs of consecutive quadratic residues in 1
,
(
p
-
1
)
/
2 is (1)
(
k
-
2
)
/
2 if p
≡
1
(
mod
⁡
8
),
(2)
(
k
-
1
)
/
2 if p
≡
5
(
mod
⁡
8
).Proposition 9.
Letp
=
4
k
+
1 be a prime number. (1)
If2
/
p
=
1, then |
(
N
(
p
-
1
)
/
2
+
2
)
∩
N
|
=
k
/
2.
(2)
If2
/
p
=
3
/
p
=
-
1, then |
(
N
(
p
-
1
)
/
2
+
2
)
∩
N
|
=
(
k
-
1
)
/
2.
(3)
If2
/
p
=
-
1 and 3
/
p
=
1, then |
(
N
(
p
-
1
)
/
2
+
2
)
∩
N
|
=
(
k
+
1
)
/
2.Proof.
For this value ofa there is no overlap; thus o
a
=
0. For the first assertion, if 2
/
p
=
1 then S
=
∅, so s
=
0, and there are no inner pairs. From Theorem 6 it follows that there are (
k
-
s
)
/
2
=
k
/
2 nonresidues in N
(
p
-
1
)
/
2
+
2. The second and third assertions follow from the fact that if n
i
=
(
p
-
2
)
/
2
=
p
-
1
/
2
-
1 and n
i
+
2
=
p
-
1
/
2
+
1 are both nonresidues, then there is an inner pair given by (
n
i
+
2
,
p
-
n
i
), which occurs if and only if 2
/
p
=
-
1 and 3
/
p
=
1.Proposition 10.
Letp
=
4
k
+
1 be a prime number. (1)
If2
/
p
=
1, then |
(
N
(
p
-
1
)
/
2
+
3
)
∩
N
|
=
k
/
2.
(2)
If2
/
p
=
3
/
p
=
-
1 and 5
/
p
=
1 or 2
/
p
=
5
/
p
=
-
1 and 3
/
p
=
1, then |
(
N
(
p
-
1
)
/
2
+
3
)
∩
N
|
=
(
k
+
1
)
/
2.
(3)
If2
/
p
=
3
/
p
=
5
/
p
=
-
1, then |
(
N
(
p
-
1
)
/
2
+
3
)
∩
N
|
=
(
k
-
1
)
/
2.
(4)
If2
/
p
=
-
1 and 3
/
p
=
5
/
p
=
1, then |
(
N
(
p
-
1
)
/
2
+
3
)
∩
N
|
=
(
k
+
3
)
/
2.Proof.
Note thats
=
0 in every case. If (
p
-
3
)
/
2
∈
N, then there is an overlap, which happens if 2
/
p
≠
3
/
p. On the other hand, if n
i
=
p
-
1
/
2
-
2 and n
i
+
3
=
p
-
1
/
2
+
1 are both nonresidues, we get the inner pair (
n
i
+
3
,
p
-
n
i
). This occurs when 2
/
p
=
-
1 and 5
/
p
=
1. Analyzing each case and making use of Theorem 6 the result follows.Proposition 11.
Letp
=
4
k
+
1 be a prime number. (1)
If2
/
p
=
5
/
p
=
1 or 2
/
p
=
3
/
p
=
1, then |
(
N
(
p
-
1
)
/
2
+
4
)
∩
N
|
=
k
/
2.
(2)
If2
/
p
=
7
/
p
=
-
1 and 3
/
p
=
-
1
or
5
/
p
=
-
1, then (8)
N
p
-
1
/
2
+
4
∩
N
=
k
-
1
2
.
(3)
If2
/
p
=
-
1
,
7
/
p
=
1 and 3
/
p
=
-
1
or
5
/
p
=
-
1, then (9)
N
p
-
1
/
2
+
4
∩
N
=
k
+
1
2
.
(4)
If2
/
p
=
7
/
p
=
-
1 and 3
/
p
=
5
/
p
=
1, then (10)
N
p
-
1
/
2
+
4
∩
N
=
k
+
1
2
.
(5)
If2
/
p
=
1 and 3
/
p
=
5
/
p
=
-
1, then |
(
N
(
p
-
1
)
/
2
+
4
)
∩
N
|
=
(
k
+
2
)
/
2.
(6)
If2
/
p
=
-
1 and 3
/
p
=
5
/
p
=
7
/
p
=
1, then (11)
N
p
-
1
/
2
+
4
∩
N
=
k
+
3
2
.Proof.
Sincea
=
4 is even, then there is no overlap; thus o
a
=
0. But if n
i
=
(
p
-
4
)
/
2
=
(
p
-
1
)
/
2
-
2 and n
i
+
4 are both nonresidues, we get the inner pair (
n
i
+
4
,
p
-
n
i
). This happens if and only if 2
/
p
≠
5
/
p and 2
/
p
≠
3
/
p. If also n
i
=
(
p
-
4
)
/
2
-
1
=
p
-
1
/
2
-
3 and n
i
+
4 are both nonresidues, again (
n
i
+
4
,
p
-
n
i
) is an inner pair, which occurs if and only if 2
/
p
≠
7
/
p and 2
/
p
=
-
1. Finally, the set S has a nonresidue only if 2
∈
N. Therefore, in the first case one has s
=
0 and p
a
=
0; in the second case, s
=
1 and p
a
=
0; in the third and fourth cases, s
=
1 and p
a
=
1; in the fifth case, s
=
0 and p
a
=
1; and in the sixth case, s
=
1 and p
a
=
2. The result follows using Theorem 6.In order to count the number of nonresidues inN
(
p
-
1
)
/
2
+
a for a
=
p
-
b and b
∈
1
,
(
p
-
1
)
/
2 we use the same idea; that is, we consider corresponding pairs (
n
i
+
a
,
p
-
n
i
) of nonresidues; only this time the nonresidues in the set S are of interest and if an overlap occurs it must not be counted. Also, in this case, it is possible to have pairs whose elements are neither in N
(
p
-
1
)
/
2
+
a, so they must not be counted. We call such a pair anouter pair. Letting o
a be the number of overlaps and p
a the number of outer pairs, we get the following result.Theorem 12.
Letp
=
4
k
+
1 be a prime and a
=
p
-
b, where b
∈
1
,
(
p
-
1
)
/
2.(1)
Ifa
∈
R, then |
(
N
p
-
1
/
2
+
a
)
∩
N
|
=
(
k
-
s
-
o
a
)
/
2
-
p
a
+
s.
(2)
Ifa
∈
N, then |
(
N
p
-
1
/
2
+
a
)
∩
N
|
=
(
k
-
1
-
s
-
o
a
)
/
2
-
p
a
+
s.
s is as it is in Theorem 5.It can be shown that the number of overlaps is the same fora and for p
-
a and that the number of inner pairs for a equals the number of outer pairs for p
-
a; thus we get the following.Corollary 13.
Ifp
=
4
k
+
1 is a prime number and a
∈
1
,
(
p
-
1
)
/
2, then there is m
∈
Z such that if a
∈
R, then (12)
N
p
-
1
/
2
+
a
∩
N
=
k
+
m
2
,
N
p
-
1
/
2
+
p
-
a
∩
N
=
k
-
m
2
,and if a
∈
N, then (13)
N
p
-
1
/
2
+
a
∩
N
=
k
-
1
+
m
2
,
N
p
-
1
/
2
+
p
-
a
∩
N
=
k
-
1
-
m
2
,where m
=
2
p
a
+
o
a
-
s and s is as it is in Theorem 5.As a consequence of the previous corollary, we easily get the number of quadratic nonresidues in the setN
(
p
-
1
)
/
2
+
(
p
-
a
) for a
=
1,2
,
3,4 using Propositions 7, 9, 10, and 11. In Tables 1–4 we show these results along with the number of quadratic nonresidues in the set N
(
p
-
1
)
/
2
+
a.Table 1
N
p
-
1
/
2
+
1
∩
N
N
p
-
1
/
2
+
p
-
1
∩
N
p (mod 8)
k
+
1
2
k
-
1
2
5
k
2
k
2
1Table 2
N
p
-
1
/
2
+
2
∩
N
N
(
p
-
1
)
/
2
+
p
-
2
∩
N
p (mod 24)
k
2
k
2
1,17
k
-
1
2
k
-
1
2
5
k
+
1
2
k
-
3
2
13Table 3
N
(
p
-
1
)
/
2
+
3
∩
N
p (mod 120)
N
p
-
1
/
2
+
p
-
3
∩
N
p (mod 120)
k
-
1
2
53,77
k
-
1
2
13,37,53,77
k
2
1,17,41,49,73,89,97,113
k
2
1,49,73,97
k
+
1
2
13,29,37,101
k
-
2
2
17,41,89,113
k
+
3
2
61,109
k
-
3
2
29,61,101,109Table 4
N
(
p
-
1
)
/
2
+
4
∩
N
N
p
-
1
/
2
+
p
-
4
∩
N
p (mod 840)
k
-
1
2
k
+
1
2
13, 101, 157, 173, 269, 293, 341, 397, 437, 461, 493, 509, 517, 629, 677, 733, 773, 797
k
2
k
2
1, 41, 73, 89, 97, 121, 169, 193, 209, 241, 281, 289, 313, 337, 361, 401, 409, 433, 449, 457, 481, 521, 529, 569, 577, 601, 641, 649, 673, 689, 697, 761, 769, 793, 809, 817
k
+
1
2
k
-
1
2
29, 37, 53, 61, 149, 181, 197, 221, 229, 253, 277, 317, 349, 373, 389, 533, 557, 613, 653, 661, 701, 757, 821, 829
k
+
2
2
k
-
2
2
17, 113, 137, 233, 257, 353, 377, 473, 593, 617, 713, 737
k
+
3
2
k
-
3
2
109, 421, 541, 589, 709, 781



---

*Source: 163092-2015-04-30.xml*