Proof

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.
  ∎

Thank you to the contributors under CC BY-SA 4.0!

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