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

Едно естествено число $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$.

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