Lemma: Gaussian Lemma (Number Theory)

Let $p > 2$ be an odd prime number and let $n$ be an integer not divisible by $p$ ($p\not\mid n$). The Legendre symbol $\left(\frac np\right)$ can be calculated via the formula $$\left(\frac np\right)=(-1)^m,$$ where $m\ge 0$ is the number of congruence classes modulo $p$ represented by $\frac{p-1}2$ residues $$ n,2n,3n,\dots ,{\frac {p-1}{2}}n\mod p$$ which are $ > \frac{p}{2}$ (i.e. $\ge\frac{p+1}2$).

Proofs: 1

Proofs: 1 2


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

Github:
bookofproofs


References

Bibliography

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