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

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

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

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

Свойства[редактиране | edit source]

Квадратични остатъци по модул съставно число[редактиране | edit source]

Въпросът затова дали едно число е квадратичен остатък по модул 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}.

Квадратични остатъци по модул просто число[редактиране | edit source]

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

Дефинция: Нека 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.

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