By definition, the Legendre symbol indicates, if the congruence $x^2(p)\equiv a(p)$ is solvable for a given odd prime number $p$ and a given integer $a.$ It would be, therefore, very useful to have a universal way to calculate Legendre symbols.
We start the section with an observation. We have seen that the Legendre symbol is multiplicative. This means that if $p$ is an odd prime number, then the Legendre symbol $\left(\frac np\right)$ can be written as a product of Legendre symbols of the form $$\left(\frac {-1}p\right),\label{eq:E18679a}\tag{1}$$ $$\left(\frac {2}p\right),\text{or}\label{eq:E18679b}\tag{2}$$ $$\left(\frac {q}p\right),\label{eq:E18679c}\tag{3}$$ where in $(\ref{eq:E18679c}),$ $q$ denotes a prime number distinct from $p.$ Therefore, knowing the factorization of $n$, we can calculate the Legendre symbol $\left(\frac np\right),$ using the fact that $\left(\frac np\right)$ is multiplicative, if we know the values of $(\ref{eq:E18679a})$ to $(\ref{eq:E18679c}).$ In this section, we will, therefore, deal with these three kinds of Legendre symbols and provide explicit formulae for them. The most famous formula is for the case $(\ref{eq:E18679c}),$ and it is known as the quadratic reciprocity law. The other two cases are known $(\ref{eq:E18679a}),$ and $(\ref{eq:E18679b})$ as supplementary laws to the quadratic reciprocity law.
Explanations: 1
