Welcome guest
You're not logged in.
251 users online, thereof 0 logged in

Calculating Legendre Symbols

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.

| | | | created: 2019-05-26 06:34:32 | modified: 2019-05-26 07:18:32 | by: bookofproofs | references: [1272]

(none)