Квадратичен остатък

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

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

Свойства

Квадратични остатъци по модул съставно число

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

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

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

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

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

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

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

Квадратични остатъци по модул просто число

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

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

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

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

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

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

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

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

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

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

$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}}}$

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

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