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

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

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

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

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

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

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

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

има решение тогава и само тогава, когато е е квадратичен остатък по модул и е изпълнено поне едно от условията:

  • или
  • и или
  • и

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

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

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

  • ако е квадратичен остатък по модул и
  • в противен случай,

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

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

  • Критерий на Ойлер:
  • Второ правило за допълнението:
  • Квадратичен закон за реципрочност:
  • .

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