Дополнительное образование

сравнения по модулю

Здравствуйте! Возник следующий вопрос:Существует ли теорема, которая помогает установить D, которые при данном p имеют решения:(Знак тройного равенства - сравения по модулю)То есть мы имеем некое p, и необходимо определить некие закономерности распределения D, то есть какими D быть не могут. Конечно, очевидно, что можно сделать p+1/2 возведений в квадрат и найти все возможные значения p. Но в условиях решения необходимой мне задачи данный способ является очень затратным (т.к. p может быть очень большим)Насколько данные закономерности каким-то образом относятся к Эйлеру(связано с теорией дивизоров квадратичных целых). Но в книге внятной информации(по-крайней мере понятной для меня) нет. Если да, скиньте ссылку или назовите название книги, где эжти закономерности установлены?Пример применения данной задачи(взят почти наугад для неких параметров в моей задаче):Доказать, не используя 16 последовательных проверок по модулю, что x^2+9 никогда не кратно 31.Немного обобщенный вариант данной задачи:Доказать, что x^2+102 не кратно никакому p,меньшему 102, и большему 3.(Для p=2 и p=3 задача имеет решение)Заранее спасибо за помощь =)
Роман Варакута
Роман Варакута
4 627
Такие D, что сравнение x² ≡ D (mod p) разрешимо называются квадратичными вычетами. Соответственно, D является квадратичным невычетом, когда сравнение неразрешимо. Символ Лежандра (D/p) = 1, когда D — квадратичный вычет по модулю p (здесь p — простое) , и (D/p) = −1, когда D — невычет; наконец, (D/p) = 0, когда p | D. Имеется несколько полезных равенств (для простых p, q):

(x/p) · (y/p) = (xy/p) (мультипликативность) ;
(x/p) ≡ x^((p–1)/2) (mod p) (критерий Эйлера) ;
(p/q) · (q/p) = (–1)^((p–1)/2 · (q–1)/2) (квадратичный закон взаимности) ;
(–1/p) = (–1)^((p–1)/2) (1-е дополнение к закону взаимности) ;
(2/p) = (–1)^((p²–1)/8) (2-е дополнение к закону взаимности) .

Для вычисления символов Лежандра используются эти равенства и символ Якоби (x/n), где n = p1 p2 … pk — произведение нечётных простых, определямый аналогично (символ Якоби также удовлетворяет закону взаимности) .

Например,

(–9/31) = (22/31) = (2/31) · (11/31) = (–1)^((31²–1)/8) · (11/31) = (11/31) =
= (–1)^((11–1)/2·(31–1)/2)·(31/11) = –(31/11) = –(9/11) = –1,

поскольку 9 — квадрат.

Мораль такова: применяя закон взаимности («переворачивая» символы) и дополнения, можно постепенно уменьшать числа в символах, пока не получится квадрат (как в примере) , либо одно из дополнений к закону.

PS. Доказательства в письме.
Камила Зарипова
Камила Зарипова
23 672
Лучший ответ
это 38
Сергей Резниченко
Сергей Резниченко
2 768
дочитав до 3 - ей строчки почувствовала приступ головной боли.
Инна Чернышева
Инна Чернышева
1 852

Похожие вопросы