Legendrův symbol

Značený \(\displaystyle \left(\frac{a}{p}\right)\), funkce z teorie čísel, která umožňuje rozhodnout, zda dané celé číslo \(a\) je či není kvadratickým reziduem modulo lichého prvočísla \(p\). Předpokládáme přitom, že \(p\) nedělí \(a\) (tj. čísla \(\displaystyle a\) a \(\displaystyle p\) jsou nesoudělná, což znamená, že jejich největší společný dělitel je 1).

Definice zní: \(\displaystyle \left(\frac{a}{p}\right)\) = 1, pokud existují celá čísla \(m\) a \(n\), že \[ m^2 \;=\; a + np, \] tedy pokud se \(a\) stává čtvercem v aritmetice modulo \(p\). V opačném případě platí \[ \left(\frac{a}{p}\right)\;=\;-1. \] Takto definovanou hodnotu nazýváme Legendrův symbol.

Pokud navíc \(p\) dělí \(a\), obvykle se Legendreův symbol definuje jako 0, tj. \(\left(\tfrac{a}{p}\right) = 0\). Díky Legendrovu symbolu můžeme efektivně testovat, zda má rovnice \[ x^2 \equiv a \pmod{p} \] řešení, tedy zda je \(a\) kvadratickým reziduem modulo \(p\).