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

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

$\mathrm{\exists }x:x^2\equiv a(\mathrm{mod}n).$

Свойства

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

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

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

$n=2^{{\alpha }_0}\prod _{i=1}^s{p}_i^{{\alpha }_i}$

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

$x^2\equiv a(\mathrm{mod}n)$

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

• ${\alpha }_0<2$ или
• ${\alpha }_0=2$ и $a\equiv 1(\mathrm{mod}4)$ или
• ${\alpha }_0>2$ и $a\equiv 1(\mathrm{mod}8).$

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

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

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

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

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

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

• $a\equiv b(\mathrm{mod}p)\Rightarrow \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\Rightarrow \left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}(\mathrm{mod}p)$

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

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

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

$2\nmid pq\Rightarrow \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$.

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