Квадратичен остатък
от Уикипедия, свободната енциклопедия
Едно естествено число се нарича квадратичен остатък по модул
ако
[редактиране] Свойства
[редактиране] Квадратични остатъци по модул съставно число
Въпросът затова дали едно число е квадратичен остатък по модул за съставни
може да се сведе до частния случай за прости
, както твърди следната теорема:
Теорема: Нека и
са взаимнопрости, a
представлява разлагането на на прости множители. Конгруенцията
има решение тогава и само тогава, когато е е квадратичен остатък по модул
и е изпълнено поне едно от условията:
или
и
или
и
[редактиране] Квадратични остатъци по модул просто число
За частния случай на конгруенции по модул просто число е възприето следното обозначение:
Дефинция: Нека е просто число и
. Функцията със стойности:
ако
е квадратичен остатък по модул
и
в противен случай,
се нарича символ на Льожандър.
Могат да се докажат следните правила за смятане със символа на Льожандър:
- Критерий на Ойлер:
- Второ правило за допълнението:
- Квадратичен закон за реципрочност:
.
Забележка: Последното правило показва, че квадратичните остатъци по модул просто число са точно толкова колкото и неостатъците.