Сравнения высших степеней

Сравнение второй степени по простому модулю

Пусть /(х) = ах² + Ьх + с, a, b, ceZ и peN.

Пусть а • р. Рассмотрим сравнение

ах² + Ьх + с = 0 (mod р) (2.234)

Умножим обе части сравнения (1) на 4а.

Получим

4о²х² + 4а Ьх + 4ас = 0 (mod р).

Выделим полный квадрат в правой части сравнения

4а²х² + 4аЬх + 4ас = ((2ах)² + 2 • 2ах • Ь + Ь²) + 4ас — Ь²

= (2ах + ЬУ + (4ас - Ь²). (2.235)

Тогда сравнение (1) равносильно сравнению

• (2ах + ЬУ + (4ас - Ь²) = 0 (mod р) (2.236)
• (2ах + b)² = b² - 4ас (mod р) (2.237)

Выполним замену переменных:

2ах + Ь = у, Ь² - 4ас = D. (2.238)

Тогда (2.234) равносильно

y²=D(modp). (2.239)

Но по условию р,следовательно, 2а^р. Значит, сравнение

2ах+=у (mod р)

имеет единственное решение относительно х, что устанавливает взаимно однозначное соответствие между решениями сравнения (2.234) и сравнения (2.239) относительно у.

Таким образом, сравнение (2.234) сводится к сравнению:

х² = a (mod р) (2.240)

Согласно китайской теореме об остатках сравнение х² = a (modp) имеет не более двух решений. Если это сравнение разрешимо и а'.р, то число решений равно двум, если класс вычетов х₀ (mod р) - решение, то и класс вычетов - х₀ (modp) также решение. Эти классы вычетов различны, поскольку если эти классы не различны, то справедливо х₀ = - х₀ (mod р) и х₀ -р, а значит а-р, что противоречит условию. То есть, х₀ (modp), - х₀ (mod р) действительно различные класса вычетов.

Вывод:

Если а= 0 (modp), то сравнение х² =а (modp) либо не имеет решений, либо имеет два различных решения.

Если а= 0 (mod р), то сравнение (2.234) имеет единственное решение х= 0 (modp). Возвращаясь к замене переменных имеем:

• 1. если D = b² — 4ac кратно p, то сравнение (2.234) имеет единственное решение;
• 2. если Dp, то сравнение (2.234) имеет либо два различных решения, либо не имеет решений.

Например, сравнение х² =-1 (mod 3) не имеет решений;

Сравнение х² = — 1 (mod 5) имеет два решения х= 2 (mod 5), х = 3 (mod 5).

Квадратичный вычет по модулю р

Число aeZ называется квадратичным вычетом по модулю р, если сравнение х² = a (mod р) имеет решение.

Если сравнение х² Ха (modp) не имеет решения, то число aeZ. называется квадратичным невычетом по модулю р.

Если два целых числа сравнимы между собой, то они либо квадратичные вычеты, либо квадратичные невычеты.

Теорема 2.58

Приведенная система вычетом по модулю р состоит из квадратичных вычетов, сравнимых с числами I², 2²,..., (^)² и квадратичных невычетов.

Лемма

Любая приведенная система вычетов по модулю р содержит X квадратичных невычетов.

p-і

Если ар и а г = l(mod р ), то а - квадратичный вычет. p-і

Если и выполнено условие а 2 = — l(modp),TO а - квадратичный невычет.