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
