An old number theory problem
related to the Legendre symbol

Abstract: The main purpose of this paper is using a very simple elementary constructive method to study an old number theory problem related to the Legendre symbol modulo $p$, and completely solved it.
Keywords:   Prime; Legendre symbol; constructive method; quadratic residue.

Report issue for preceding element

2020 Mathematics Subject Classification: 11L40; 11N69.

Report issue for preceding element

1. Introduction

Report issue for preceding element

Let $p$ be an odd prime. For any integer $a$, the famous Legendre symbol modulo $p$ is define (see [1] and [2]) as

Report issue for preceding element

$$\left(\frac{a}{p}\right)=\left\{\begin{array}[]{ll}1&\textrm{ if $a$ a quadratic residue modulo $p$;}\\ -1&\textrm{ if $a$ is a quadratic non-residue modulo $p$;}\\ 0&\textrm{ if $a\equiv 0$ modulo $p$.}\end{array}\right.$$

This number theory function occupies a very important position in the study of elementary number theory and analytic number theory, so many theorists and scholars have studied its various properties, and a series of important results have been achieved. Perhaps the most significant result is its reciprocity formula. That is, for any two distinct odd primes $p$ and $q$, one has (see Theorem 9.8 in [1])

Report issue for preceding element

$$\left(\frac{q}{p}\right)\cdot\left(\frac{p}{q}\right)=(-1)^{\frac{(p-1)(q-1)}{4}}.$$

Some other properties of Legendre symbol can be found in references [3]–[6], and need not be listed here.

Report issue for preceding element

It is clear that

Report issue for preceding element

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

So in the reduced residue system modulo $p$, the number of the quadratic residues modulo $p$ and the number of the quadratic non-residues modulo $p$ half of each. If $p\equiv 1\bmod 4$, then note that $\left(\frac{-1}{p}\right)=1$, we have

Report issue for preceding element

$$\sum_{a=1}^{p-1}\left(\frac{a}{p}\right)=\sum_{a=1}^{\frac{p-1}{2}}\left(\frac{a}{p}\right)+\sum_{a=1}^{\frac{p-1}{2}}\left(\frac{p-a}{p}\right)=\sum_{a=1}^{\frac{p-1}{2}}\left(\frac{a}{p}\right)+\sum_{a=1}^{\frac{p-1}{2}}\left(\frac{-a}{p}\right)=2\sum_{a=1}^{\frac{p-1}{2}}\left(\frac{a}{p}\right).$$

So we have the identity

Report issue for preceding element

$$A(p)=\sum_{a=1}^{\frac{p-1}{2}}\left(\frac{a}{p}\right)=0.$$

That is to say, in the set $\{1,\ 2,\ \cdots,\ \frac{p-1}{2}\}$, the number of the quadratic residues modulo $p$ and the number of the quadratic non-residues modulo $p$ also half of each. But if $p\equiv 3\bmod 4$, then $\frac{p-1}{2}$ is an odd number and

Report issue for preceding element

$$A(p)=\sum_{a=1}^{\frac{p-1}{2}}\left(\frac{a}{p}\right)\neq 0.$$ (2)

About a century ago, J. Jacobi first conjecture that $A(p)>0$ and proved by L. Dirichlet [7] and [8] in connection with the theory of binary quadratic forms. The proofs are also given in the books of P. Bachmann [9] and E. Landau [10]. More proofs are due to Kai-Lai Chung [11], A. L. Whiteman [12] and L. Moser [13]. It is a shame that all known proofs are analytic. So, L. Moser in [13] said with emotion, “While a really elementary proof would be of great interest”.

Report issue for preceding element

Through analytic methods, i.e. Dirichlet’s class-number formula $h(p)=\frac{\sqrt{p}}{\pi}\cdot L(1,\chi_{2})$, where $\chi_{2}=\left(\frac{*}{p}\right)$, $h(p)$ denotes the class number of the imaginary quadratic field $\mathbf{Q}\left(\sqrt{-p}\right)$ (see [2], p. 295 or [14], p. 395 or [15], p. 50), one can easy to prove that $A(p)>0$. In fact, from B. C. Berndt’s work [16] (see Theorem 3.2) we have

Report issue for preceding element

$$\sum_{a=1}^{\frac{p-1}{2}}\left(\frac{a}{p}\right)=\frac{i\cdot\tau\left(\chi_{2}\right)}{\pi}\cdot\left(\left(\frac{2}{p}\right)-2\right)\cdot L\left(1,\chi_{2}\right)=\frac{\sqrt{p}}{\pi}\left(2-\left(\frac{2}{p}\right)\right)\cdot L(1,\chi_{2}),$$ (3)

where $\tau(\chi_{2})=i\cdot\sqrt{p}$.

Report issue for preceding element

Then combining Dirichlet’s class-number formula and (2) we have

Report issue for preceding element

$$\sum_{a=1}^{\frac{p-1}{2}}\left(\frac{a}{p}\right)=\left(2-\left(\frac{2}{p}\right)\right)\cdot h(p).$$

Since $2-\left(\frac{2}{p}\right)>0$ and $h(p)>0$, so $A(p)>0$.

Report issue for preceding element

That is, if $p\equiv 3\bmod 4$, then in the set $\{1,\ 2,\ \cdots,\frac{p-1}{2}\}$, the number of the quadratic residues modulo $p$ is greater than the number of the quadratic non-residues modulo $p$. R. K. Guy [17] (see problem F5) asked us:

Report issue for preceding element

Is there an elementary proof for $A(p)>0$?

Report issue for preceding element

In fact, the problem has been desired in the literature at least since 1927.

Report issue for preceding element

About this problem, it seems to have not solved at present, at least we have not found any elementary proof in the existing literature. In theory, this problem can be proven by using the elementary methods, but no one has been able to find one. Of course, it would be very meaningful to have a simple elementary method to prove this problem, just like the proof of the prime number theorem, the problem was already solved over a century ago by using the non-zero region of the Riemann zeta-function. It is precisely because A. Selberg [18] proved the prime number theorem using elementary methods that he was awarded the Fields Medal. Although A. Wiles [19] proved Fermat’s Last Theorem by using profound modular elliptic curves theory, I think it would be a remarkable achievement if someone could prove Fermat’s Last Theorem by using elementary methods. This is the way to make people feel that the problem and the proof method are aligned.

Report issue for preceding element

The main purpose of this paper is using a very simple elementary constructive method and the properties of the Legendre symbol to prove the following:

Report issue for preceding element

Theorem. For any odd prime $p$ with $p\equiv 3\bmod 4$, we have

Report issue for preceding element

$$A(p)=\sum_{a=1}^{\frac{p-1}{2}}\left(\frac{a}{p}\right)>0.$$

In fact, the proof of our theorem is purely elementary and has been desired in the literature at least since 1927.

Report issue for preceding element

3. Proof of the theorem

Report issue for preceding element

In this section, we provide a direct proof of the theorem. Of course, in the process of proving the theorem, we need to use some properties of the Legendre symbol, all them can be found in [1] or [2], and will not be repeated here. Now we always assume that $p=4m+3$. Let us distinguish between two situations to discuss:

Report issue for preceding element

Case 1. $\left(\frac{2}{p}\right)=-1$. In this case, note that $\left(\frac{2}{p}\right)=(-1)^{\frac{p^{2}-1}{8}}$ and $\left(\frac{-1}{p}\right)=-1$, we have $p=8k+3$. It is clear that $\left(\frac{(p-1)/2}{p}\right)=1$. Let $A=\{1,\ 2,\ 3,\ \cdots,\ 2k\}$ and $B=\{2k+1,\ 2k+2,2k+3,\ \cdots,\ 4k+1\}$. Note that for any odd number $r\in A$, $\left(\frac{r}{p}\right)=\left(\frac{(p-r)/2}{p}\right)$. Thus, the quadratic residue modulo $p$ or quadratic non-residue modulo $p$ occurs symmetrically in $A$ and $B$. Now if $8h+7\in A\bigcup B$, then $0\leq h\leq\frac{2k-3}{4}$. Note that $\left(\frac{2}{p}\right)=-1$, there must exist a pair quadratic residues modulo $p$: $8h+7$ and $\frac{p-8h-7}{2}=4(k-h)-2$ or $2(k-h)-1$ and $\frac{p-2(k-h)+1}{2}=3k+h+2$. So there are at least $2\left(\left[\frac{2k-3}{4}\right]+1\right)=2\left[\frac{2k+1}{4}\right]$ such quadratic residue modulo $p$.

Report issue for preceding element

If $8h+3\in A\bigcup B$, then $0\leq h\leq\frac{2k-1}{4}$. So one of $8h+3$ ( $\frac{p-8h-3}{2}=4(k-h)$) and $2(k-h)$ is a quadratic residue modulo $p$. So there are at least $\left[\frac{2k-1}{4}\right]+1=\left[\frac{2k+3}{4}\right]$ such quadratic residue modulo $p$.

Report issue for preceding element

If $8h+1\in A$, then $0\leq h\leq\frac{k-1}{4}$. In this case, one of $8h+1$ ( $\frac{p-8h-1}{2}=4(k-h)+1$) and $2(8h+1)$ is a quadratic residue modulo $p$. Note that $1$ and $\frac{p-1}{2}$ both are quadratic residues modulo $p$. So there are at least $\left[\frac{k-1}{4}\right]+2=\left[\frac{k+3}{4}\right]+1$ such quadratic residue modulo $p$.

Report issue for preceding element

If $8h+5\in A$, then $0\leq h\leq\frac{k-3}{4}$. In this case, one of $8h+5$ ( $\frac{p-8h-5}{2}=4(k-h)-1$) and $2(8h+5)$ is a quadratic residue modulo $p$. So there are at least $\left[\frac{k-3}{4}\right]+1=\left[\frac{k+1}{4}\right]$ such quadratic residue modulo $p$. Note that the quadratic residues constructed above are not repeated. So if $p=8k+3$, then in the set $\{1,\ 2,\ 3,\ \cdots,4k+1\}$, the number of the quadratic residues modulo $p$ is at least

Report issue for preceding element

$$2\left[\frac{2k+1}{4}\right]+\left[\frac{2k+3}{4}\right]+\left[\frac{k+3}{4}\right]+1+\left[\frac{k+1}{4}\right]=2k+1.$$

So in the case $p=8k+3$, we have

Report issue for preceding element

$$A(p)=\sum_{a=1}^{\frac{p-1}{2}}\left(\frac{a}{p}\right)>0.$$ (4)

Case 2. $\left(\frac{2}{p}\right)=1$. In this case, we have $p=8k+7$. For any $8h+3\in\{1,\ 2,\ 3,\ \cdots,\ 4k+3\}$, it is clear that one of $8h+3$ and $4(k-h)+2$ is a quadratic residue modulo $p$. If $8h+3\leq 2k+1$ is a quadratic residue modulo $p$, then $2(8h+3)$ is also a quadratic residue modulo $p$. If $4(k-h)+2$ is a quadratic residue modulo $p$, then $2(k-h)+1$ is also a quadratic residue modulo $p$. So in this case, there are at least

Report issue for preceding element

$$\left[\frac{k}{2}\right]+1+\left[\frac{k-1}{4}\right]+1=\left[\frac{k}{2}\right]+\left[\frac{k+3}{4}\right]+1$$

such quadratic residues in set $\{1,\ 2,\ 3,\ \cdots,\ 4k+3\}$.

Report issue for preceding element

For any $8h+7\in\{1,\ 2,\ 3,\cdots,\ 2k+1\}$ and $\frac{p-8h-7}{2}=4(k-h)$, it is clear that one of them is a quadratic residue modulo $p$. If $8h+7\leq 2k+1$ is a quadratic residue modulo $p$, then $2(8h+7)$ is also a quadratic residue modulo $p$. If $4(k-h)$ a quadratic residue modulo $p$, then $2(k-h)$ is also a a quadratic residue modulo $p$. Note that $8h+7\leq 2k+1$ implies $0\leq h\leq\left[\frac{k-3}{4}\right]$, there are a total of $\left[\frac{k-3}{4}\right]+1=\left[\frac{k+1}{4}\right]$ such integers. If $\left[\frac{k-2}{4}\right]\leq h\leq\left[\frac{k-1}{2}\right]$, then $2k+3\leq 8h+7\leq 4k+3$. In this way, there are at least $2\left[\frac{k+1}{4}\right]+\left[\frac{k-1}{2}\right]-\left[\frac{k-2}{4}\right]+1=\left[\frac{k+1}{2}\right]+\left[\frac{k+1}{4}\right]+1$ quadratic residue modulo $p$ in the set $\{1,\ 2,\ 3,\ \cdots,\ 4k+3\}$.

Report issue for preceding element

Similarly, if $8h+1\leq 2k+1$, then $0\leq h\leq\left[\frac{k}{4}\right]$; If $8h+5\leq 2k+1$, then $0\leq h\leq\left[\frac{k-2}{4}\right]$. Note that the quadratic residues constructed above are not repeated. So in the set $\{1,2,3,\cdots,4k+2,4k+3\}$, there are at least

Report issue for preceding element

$$\left[\frac{k}{2}\right]+\left[\frac{k+3}{4}\right]+1+\left[\frac{k+1}{2}\right]+\left[\frac{k+1}{4}\right]+1+\left[\frac{k}{4}\right]+1+\left[\frac{k+2}{4}\right]$$ (5)

$$= \left[\frac{k}{2}\right]+\left[\frac{k+1}{2}\right]+\left[\frac{k}{4}\right]+\left[\frac{k+1}{4}\right]+\left[\frac{k+2}{4}\right]+\left[\frac{k+3}{4}\right]+3$$

$$= k+k+3=2k+3$$

quadratic residue modulo $p$.

Report issue for preceding element

So if $p=8k+7$, then from (4) we also have

Report issue for preceding element

$$A(p)=\sum_{a=1}^{\frac{p-1}{2}}\left(\frac{a}{p}\right)>0.$$ (6)

It is clear that $p\equiv 3\bmod 4$ if and only if $p=8k+3$ or $p=8k+7$.

Report issue for preceding element

Combining (3) and (5) we complete the proof of our theorem.

Report issue for preceding element

Acknowledgements: The author would like to express his sincere gratitude to Professor Gong Ke for his comments and suggestions.

Report issue for preceding element