# Comptes Rendus
Mathématique

Qing-Hu Hou, Hao Pan and Zhi-Wei Sun

A new theorem on quadratic residues modulo primes

Volume 360 (2022), p. 1065-1069

https://doi.org/10.5802/crmath.371

<figure><img src="image_1.png" /></figure>

This article is licensed under the
CREATIVE COMMONS ATTRIBUTION 4.0 INTERNATIONAL LICENSE.
http://creativecommons.org/licenses/by/4.0/

<figure><img src="image_2.png" /></figure>

Les Comptes Rendus. Mathématique sont membres du
Centre Mersenne pour l'édition scientifique ouverte
www.centre-mersenne.org

e-ISSN : 1778-3569
Number theory / Théorie des nombres

# A new theorem on quadratic residues modulo primes

Qing-Hu Hou$^a$, Hao Pan$^b$ and Zhi-Wei Sun$^{*,c}$

$^a$School of Mathematics, Tianjin University, Tianjin 300350, People's Republic of China

$^b$School of Applied Mathematics, Nanjing University of Finance and Economics, Nanjing 210046, People's Republic of China

$^c$Department of Mathematics, Nanjing University, Nanjing 210093, People's Republic of China

URL: http://maths.nju.edu.cn/~zwsun

E-mails: qh_hou@tju.edu.cn, haopan79@zoho.com, zwsun@nju.edu.cn

**Abstract.** Let $p > 3$ be a prime, and let $(\frac{1}{p})$ be the Legendre symbol. Let $b \in \mathbb{Z}$ and $\epsilon \in \{\pm 1\}$. We mainly prove that

$$ \left| \left\{ N_p(a, b) : 1 < a < p \text{ and } \left(\frac{a}{p}\right) = \epsilon \right\} \right| = \frac{3 - \left(\frac{-1}{p}\right)}{2}, $$

where $N_p(a, b)$ is the number of positive integers $x < p/2$ with $\{x^2 + b\}_p > \{ax^2 + b\}_p$, and $\{m\}_p$ with $m \in \mathbb{Z}$ is the least nonnegative residue of $m$ modulo $p$.

**2020 Mathematics Subject Classification.** 11A15, 11A07, 11R11.

**Funding.** The first, second and third authors are supported by the National Natural Science Foundation of China (grants 11771330, 12071208 and 11971222, respectively).

Manuscript received 8 March 2022, accepted 26 April 2022.

## 1. Introduction

The theory of quadratic residues modulo primes plays an important role in fundamental number theory.

Let $p$ be an odd prime and let $a \in \mathbb{Z}$ with $p \nmid a$. By Gauss' Lemma (cf. [4, p. 52]),

$$ \left(\frac{a}{p}\right) = (-1)^{\lfloor 1 \le k \le \frac{p-1}{2} : \{ka\}_p > \frac{p}{2} \rfloor}, $$

where $(\frac{1}{p})$ denotes the Legendre symbol, and we write $\{x\}_p$ for the least nonnegative residue of an integer $x$ modulo $p$.

<footnote>* Corresponding author.</footnote>
Let $n$ be any positive odd integer, and let $a \in \mathbb{Z}$ with $\gcd(a(1-a), n) = 1$. In 2020, Z.-W. Sun [6] proved the following new result:

$$(-1)^{|\{1 \le k \le \frac{n-1}{2}: \{ka\}_n > k\}|} = \left(\frac{2a(1-a)}{n}\right),$$

where $(\frac{n}{2})$ is the Jacobi symbol.

Let $p$ be an odd prime and let $a, b \in \mathbb{Z}$ with $a(1-a) \neq 0 \pmod{p}$. By [5, Lemma 2.7], we have

$$|\{x \in \{0, \dots, p-1\}: \{ax+b\}_p > x\}| = \frac{p-1}{2}.$$

In 2019 Z.-W. Sun [5] employed Galois theory to prove that

$$(-1)^{|\{1 \le i < j \le \frac{p-1}{2}: \{i^2\}_p > \{j^2\}_p\}|} = \begin{cases} 1 & \text{if } p \equiv 3 \pmod 8, \\ (-1)^{(h(-p)+1)/2} & \text{if } p \equiv 7 \pmod 8, \end{cases}$$

where $h(-p)$ is the class number of the imaginary quadratic field $\mathbb{Q}(\sqrt{-p})$.

Motivated by the above work, for an odd prime $p$ and integers $a$ and $b$, we introduce the notation

$$N_p(a, b) := \left| \left\{ 1 \le x \le \frac{p-1}{2} : \{x^2 + b\}_p > \{ax^2 + b\}_p \right\} \right|.$$

**Example 1.** We have $N_7(4, 0) = 2$ since

$$\{1^2\}_7 < \{4 \times 1^2\}_7, \{2^2\}_7 > \{4 \times 2^2\}_7 \text{ and } \{3^2\}_7 > \{4 \times 3^2\}_7.$$

Let $p$ be a prime with $p \equiv 1 \pmod 4$. Then $q^2 \equiv -1 \pmod{p}$ for some integer $q$, hence for $a, x \in \mathbb{Z}$ we have $\{(qx)^2\}_p > \{a(qx)^2\}_p$ if and only if $\{x^2\}_p < \{ax^2\}_p$. Thus, for each $a = 2, \dots, p-1$ there are exactly $(p-1)/4$ positive integers $x < p/2$ such that $\{x^2\}_p > \{ax^2\}_p$. Therefore $N_p(a, 0) = (p-1)/4$ for all $a = 2, \dots, p-1$.

In this paper we establish the following novel theorem which was conjectured by the first and third authors [3] in 2018.

**Theorem 2.** Let $p > 3$ be a prime, and let $b$ be any integer. Set

$$S = \left\{ N_p(a, b) : 1 < a < p \text{ and } \left(\frac{a}{p}\right) = 1 \right\}$$

and

$$T = \left\{ N_p(a, b) : 1 < a < p \text{ and } \left(\frac{a}{p}\right) = -1 \right\}.$$

Then $|S| = |T| = 1$ if $p \equiv 1 \pmod 4$, and $|S| = |T| = 2$ if $p \equiv 3 \pmod 4$. Moreover, the set $S$ does not depend on the value of $b$.

**Example 3.** Let's adopt the notation in Theorem 2. For $p = 5$, we have $S = \{1\}$ for any $b \in \mathbb{Z}$, and the set $T$ depends on $b$ as illustrated by the following table:

$$\begin{array}{c|ccccc} b & 0 & 1 & 2 & 3 & 4 \\ \hline T & \{1\} & \{0\} & \{1\} & \{2\} & \{1\} \end{array}.$$

For $p = 7$, we have $S = \{1, 2\}$ for any $b \in \mathbb{Z}$, and the set $T$ depends on $b$ as illustrated by the following table:

$$\begin{array}{c|ccccccc} b & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline T & \{0,1\} & \{1,2\} & \{2,3\} & \{1,2\} & \{2,3\} & \{1,2\} & \{0,1\} \end{array}.$$
## 2. Proof of Theorem 2

**Lemma 4.** For any prime $p \equiv 3 \pmod 4$, we have

$$ \sum_{z=1}^{p-1} z \left(\frac{z}{p}\right) = -ph(-p), $$

where $h(-p)$ is the class number of the imaginary quadratic field $\mathbb{Q}(\sqrt{-p})$.

**Remark 5.** This is a known result of Dirichlet (cf. [1, Corollary 5.3.13]).

**Lemma 6.** For any prime $p \equiv 3 \pmod 4$ with $p > 3$, there are $x, y, z \in \{1, \dots, p-1\}$ such that

$$ \left(\frac{x}{p}\right) = \left(\frac{x+1}{p}\right) = 1, \quad -\left(\frac{y}{p}\right) = \left(\frac{y+1}{p}\right) = 1, \quad \text{and} \quad \left(\frac{z}{p}\right) = -\left(\frac{z+1}{p}\right) = 1. $$

**Proof.** By a known result (see, e.g., [2, pp. 64–65]), we have

$$ \left| \left\{ x \in \{1, \dots, p-2\} : \left(\frac{x}{p}\right) = \left(\frac{x+1}{p}\right) = 1 \right\} \right| = \frac{p-3}{4} > 0. $$

Hence

$$ \begin{aligned} \left| \left\{ y \in \{1, \dots, p-2\} : -\left(\frac{y}{p}\right) = \left(\frac{y+1}{p}\right) = 1 \right\} \right| &= \left| \left\{ y \in \{1, \dots, p-2\} : \left(\frac{y+1}{p}\right) = 1 \right\} \right| - \frac{p-3}{4} \\ &= \frac{p-1}{2} - 1 - \frac{p-3}{4} = \frac{p-3}{4} > 0 \end{aligned} $$

and

$$ \begin{aligned} \left| \left\{ z \in \{1, \dots, p-2\} : \left(\frac{z}{p}\right) = -\left(\frac{z+1}{p}\right) = 1 \right\} \right| &= \left| \left\{ z \in \{1, \dots, p-2\} : \left(\frac{z}{p}\right) = 1 \right\} \right| - \frac{p-3}{4} \\ &= \frac{p-1}{2} - \frac{p-3}{4} = \frac{p+1}{4} > 0. \end{aligned} $$

Now the desired result immediately follows.

□

**Proof of Theorem 2.** Let $a \in \{2, \dots, p-1\}$. For any $x \in \mathbb{Z}$, it is easy to see that

$$ \left\{ \frac{ax^2 + b}{p} \right\} + \left\{ \frac{(1-a)x^2}{p} \right\} - \left\{ \frac{x^2 + b}{p} \right\} = \begin{cases} 0 & \text{if } \{x^2 + b\}_p > \{ax^2 + b\}_p, \\ 1 & \text{if } \{x^2 + b\}_p < \{ax^2 + b\}_p, \end{cases} $$

where $\{\alpha\}$ denotes the fractional part of a real number $\alpha$. Thus

$$ \begin{aligned} N_p(a, b) &= \sum_{x=1}^{(p-1)/2} \left( 1 + \left\{ \frac{x^2+b}{p} \right\} - \left\{ \frac{ax^2+b}{p} \right\} - \left\{ \frac{(1-a)x^2}{p} \right\} \right) \\ &= \frac{p-1}{2} + \sum_{x=1}^{(p-1)/2} \left\{ \frac{x^2+b}{p} \right\} - \sum_{x=1}^{(p-1)/2} \left\{ \frac{ax^2+b}{p} \right\} - \sum_{x=1}^{(p-1)/2} \left\{ \frac{(1-a)x^2}{p} \right\} \\ &= \frac{p-1}{2} + \sum_{\substack{x=1 \\ (\frac{a}{p})=1}}^{p-1} \left\{ \frac{x+b}{p} \right\} - \sum_{\substack{y=1 \\ (\frac{y}{p})=(\frac{a}{p})}}^{p-1} \left\{ \frac{y+b}{p} \right\} - \sum_{z=1}^{p-1} \frac{z}{p}. \end{aligned} $$

Suppose that $(\frac{a}{p}) = \varepsilon$ with $\varepsilon \in \{\pm 1\}$. Then

$$ N_p(a, b) = \frac{p-1}{2} + \sum_{\substack{x=1 \\ (\frac{x}{p})=1}}^{p-1} \left\{ \frac{x+b}{p} \right\} - \sum_{\substack{y=1 \\ (\frac{y}{p})=\varepsilon}}^{p-1} \left\{ \frac{y+b}{p} \right\} - \sum_{\substack{z=1 \\ (\frac{z}{p})=\delta\varepsilon}}^{p-1} \frac{z}{p}, $$

where $\delta = (\frac{a(1-a)}{p})$.
If $\epsilon = 1$, then

$$N_p(a, b) = \frac{p-1}{2} - \frac{1}{p} \sum_{\substack{z=1 \\ (\frac{z}{p})=\delta}}^{p-1} z$$

does not depend on $b$.

If $p \equiv 1 \pmod 4$, then $(\frac{-1}{p}) = 1$ and hence

$$\sum_{\substack{z=1 \\ (\frac{z}{p})=1}}^{p-1} z = \sum_{\substack{z=1 \\ (\frac{p-z}{p})=1}}^{p-1} (p-z) = p \frac{p-1}{2} - \sum_{\substack{z=1 \\ (\frac{z}{p})=1}}^{p-1} z,$$

thus

$$\sum_{\substack{z=1 \\ (\frac{z}{p})=1}}^{p-1} z = p \frac{p-1}{4}$$

and

$$\sum_{\substack{z=1 \\ (\frac{z}{p})=-1}}^{p-1} z = \sum_{z=1}^{p-1} z - p \frac{p-1}{4} = p \frac{p-1}{4}.$$

So, if $p \equiv 1 \pmod 4$, then $|S| = |T| = 1$, and moreover

$$S = \left\{ \frac{p-1}{2} - \frac{p-1}{4} \right\} = \left\{ \frac{p-1}{4} \right\}.$$

Now assume that $p \equiv 3 \pmod 4$. We want to show that $|S| = |T| = 2$. By Lemma 4,

$$\sum_{z=1}^{p-1} z \left(\frac{z}{p}\right) = -ph(-p) \neq 0.$$

Thus

$$\sum_{\substack{z=1 \\ (\frac{z}{p})=1}}^{p-1} z = \sum_{z=1}^{p-1} z \frac{1+(\frac{z}{p})}{2} = p \frac{p-1}{4} - \frac{p}{2} h(-p)$$

and hence

$$\sum_{\substack{z=1 \\ (\frac{z}{p})=-1}}^{p-1} z = \sum_{z=1}^{p-1} z - \sum_{\substack{z=1 \\ (\frac{z}{p})=1}}^{p-1} z = p \frac{p-1}{4} + \frac{p}{2} h(-p).$$

By Lemma 6, for some $a \in \{2, \dots, p-2\}$ we have $(\frac{a-1}{p}) = (\frac{a}{p}) = 1$ and hence $(\frac{a(1-a)}{p}) = -1$. For $a' = p+1-a$, we have

$$(\frac{a'}{p}) = -1 \text{ and } (\frac{a'(1-a')}{p}) = (\frac{(1-a)a}{p}) = -1.$$

By Lemma 6, for some $a_*, b_* \in \{2, \dots, p-2\}$ we have

$$-(\frac{a_*-1}{p}) = (\frac{a_*}{p}) = 1 \text{ and } (\frac{b_*-1}{p}) = -(\frac{b_*}{p}) = 1.$$

Note that

$$(\frac{a_*(1-a_*)}{p}) = 1 = (\frac{b_*(1-b_*)}{p}).$$

Now we clearly have $|S| = |T| = 2$. Moreover,

$$S = \left\{ \frac{p-1}{2} - \left( \frac{p-1}{4} \pm \frac{h(-p)}{2} \right) \right\} = \left\{ \frac{p-1 \pm 2h(-p)}{4} \right\}.$$

The proof of Theorem 2 is now complete.

□