Für eine ungerade Primzahl ${\displaystyle {}p}$ und eine zu ${\displaystyle {}p}$ teilerfremde Zahl ${\displaystyle {}k\in \mathbb {Z} }$ definiert man das Legendre-Symbol, geschrieben ${\displaystyle {}\left({\frac {k}{p}}\right)}$ (sprich „${\displaystyle {}k}$ nach ${\displaystyle {}p}$“), durch

${\displaystyle \left({\frac {k}{p}}\right):={\begin{cases}1,{\text{ falls }}k{\text{ quadratischer Rest modulo }}p{\text{ ist}},\\-1,{\text{ falls }}k{\text{ kein quadratischer Rest modulo }}p{\text{ ist}}.\end{cases}}\,}$