(related to Proposition: Euler's Criterion For Quadratic Residues)

- By hypothesis, $p > 2$ is a prime number and $n\in\mathbb Z$ is a given integer.
- Case 0: Assume $p\mid n.$
- Then $n(p)\equiv 0(p).$
- Multiplying the congruences, we have $n^{\frac{p-1}{2}}(p)\equiv 0(p).$
- Therefore, the postulated formula for the Legendre symbol modulo $p$ is correct.

- Case 1: Now, assume $p\not\mid n,$ and $\left(\frac np\right)=1.$
- By definition of the Legendre symbol modulo $p$, the congruence $x^2(p)\equiv n(p)$ has a solution.
- According to the necessary condition for an integer to be prime, we have $$n^{\frac{p-1}{2}}(p)\equiv (x^2)^{\frac{p-1}{2}}(p)\equiv x^{p-1}(p)\equiv 1(p).$$
- Therefore, the postulated formula is again correct.

- Case 2: Now, assume $p\not\mid n,$ and $\left(\frac np\right)=-1.$
- According to counting the roots of a diophantine polynomial modulo $p$, the congruence $\left(x^{\frac{p-1}{2}}-1\right)(p)\equiv 0(p)\label{eq:E18698}\tag{1}$ has
*at most*$\frac{p-1}{2}$ solutions. - By case 1 and according to the number of quadratic residues in reduced residue systems modulo $p$, the congruence $(\ref{eq:E18698})$ has
*at least*$\frac{p-1}{2}$ solutions. - Therefore, the congruence $(\ref{eq:E18698})$ has
*exactly*the $\frac{p-1}{2}$ quadratic residues modulo $p$ as solutions in the reduced residue system modulo $p$. - The number $n$ as a quadratic nonresidue modulo $p$ solves therefore the congruence $\left(x^{\frac{p-1}{2}}+1\right)(p)\equiv 0(p).$
- Therefore, the postulated formula is again correct.∎

- According to counting the roots of a diophantine polynomial modulo $p$, the congruence $\left(x^{\frac{p-1}{2}}-1\right)(p)\equiv 0(p)\label{eq:E18698}\tag{1}$ has

**Landau, Edmund**: "Vorlesungen über Zahlentheorie, Aus der Elementaren Zahlentheorie", S. Hirzel, Leipzig, 1927