За информацията в тази статия или раздел не са посочени източници. Въпросната информация може да е непълна, неточна или изцяло невярна. Имайте предвид, че това може да стане причина за изтриването на цялата статия или раздел.

Тази статия се нуждае от подобрение. Необходимо е: ДОРАЗРАБОТВАНЕ, КРИТИЧЕН ПРОЧИТ И ПРИВЕЖДАНЕ В ЕНЦИКЛОПЕДИЧЕН ВИД.. Ако желаете да помогнете на Уикипедия, използвайте опцията редактиране в горното меню над статията, за да нанесете нужните корекции.

Едно естествено число ${\displaystyle a\,}$ се нарича квадратичен остатък по модул ${\displaystyle n\,}$ ако

${\displaystyle \exists x:\quad x^{2}\equiv a{\pmod {n}}.}$

Въпросът затова дали едно число е квадратичен остатък по модул ${\displaystyle n\,}$ за съставни ${\displaystyle n\,}$ може да се сведе до частния случай за прости ${\displaystyle n\,}$, както твърди следната теорема:

Теорема: Нека ${\displaystyle a\,}$ и ${\displaystyle n\,}$ са взаимнопрости, a

${\displaystyle n=2^{\alpha _{0}}\prod _{i=1}^{s}p_{i}^{\alpha _{i}}}$

представлява разлагането на ${\displaystyle n\,}$ на прости множители. Конгруенцията

${\displaystyle x^{2}\equiv a{\pmod {n}}}$

има решение тогава и само тогава, когато е ${\displaystyle a\,}$ е квадратичен остатък по модул ${\displaystyle p_{i},i=1,2,...,s\,}$ и е изпълнено поне едно от условията:

• ${\displaystyle \alpha _{0}<2\,}$ или
• ${\displaystyle \alpha _{0}=2\,}$ и ${\displaystyle a\equiv 1{\pmod {4}}\quad }$ или
• ${\displaystyle \alpha _{0}>2\,}$ и ${\displaystyle a\equiv 1{\pmod {8}}.}$

За частния случай на конгруенции по модул просто число е възприето следното обозначение:

Дефинция: Нека ${\displaystyle p\,}$ е просто число и ${\displaystyle p\nmid a}$. Функцията със стойности:

• ${\displaystyle \left({\frac {a}{p}}\right)=1}$ ако ${\displaystyle a\,}$ е квадратичен остатък по модул ${\displaystyle p\,}$ и
• ${\displaystyle \left({\frac {a}{p}}\right)=-1}$ в противен случай,

се нарича символ на Льожандър.

Могат да се докажат следните правила за смятане със символа на Льожандър:

• ${\displaystyle a\equiv b{\pmod {p}}\quad \Rightarrow \quad \left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right)}$
• ${\displaystyle \left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right)=\left({\frac {ab}{p}}\right)}$
• Критерий на Ойлер:

${\displaystyle 2\nmid p\quad \Rightarrow \quad \left({\frac {a}{p}}\right)\equiv a^{\frac {p-1}{2}}{\pmod {p}}}$

• Второ правило за допълнението:

${\displaystyle \left({\frac {2}{p}}\right)\equiv (-1)^{\frac {p^{2}-1}{8}}{\pmod {p}}}$

• Квадратичен закон за реципрочност:

${\displaystyle 2\nmid pq\quad \Rightarrow \quad \left({\frac {p}{q}}\right)\left({\frac {q}{p}}\right)=(-1)^{{\frac {p-1}{2}}{\frac {q-1}{2}}}}$

• ${\displaystyle \sum _{a=1}^{p-1}\left({\frac {a}{p}}\right)=0}$.

Забележка: Последното правило показва, че квадратичните остатъци по модул просто число са точно толкова колкото и неостатъците.