## 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]

## 1.**Theorem**: Quadratic Reciprocity Law

## 2.**Theorem**: First Supplementary Law to the Quadratic Reciprocity Law

## 3.**Lemma**: Gaussian Lemma (Number Theory)

## 4.**Theorem**: Second Supplementary Law to the Quadratic Reciprocity Law

[1272] **Landau, Edmund**: “Vorlesungen über Zahlentheorie, Aus der Elementaren Zahlentheorie”, S. Hirzel, Leipzig, 1927

© 2018 Powered by BooOfProofs, All rights reserved.