Квадратичные вычеты

(a) Пусть

Тогда или То есть имеем систему

Ясно, что она имеет различные решения для каждого которых Некоторым решениям на соответствуют разные Выдать одинаковые квадраты могут пары Посмотрим, в каких ситуациях эти пары совпадают между собой. Если то могут совпасть и и То есть пары склеиваются. Теперь рассмотрим Тогда получим, что должна быть квадратичным вычетом (для решения, в котором Значит, если то появятся ещё совпавшие пары, иначе их не появится. Тогда для ответ а для —

(b) Пусть — квадратичные вычеты. Тогда из мультипликативности символа Лежандра, домножив на — квадратичный невычет, мы получим все квадратичные невычеты Значит, по сравнению с предудыщим пунктом наша система превращается в следующую:

Тогда нас интересует число решений сравнения Пусть Тогда найдётся такое, что что преобразует сравнение в Если то решения два: Иначе поделим на и будем решать сравнение Теперь выражениие раскладывается на множители: где У него решение.

Тогда

то есть они восстанавливаются однозначно. Значит, аналогично прошлому пункту для решениия разбиваются на четвёрки во всех случаях, кроме но эти решения мы и так уже отбросили. нулём быть не может, поскольку всегда квадратичный вычет. Значит, все решений разбиваются на четверки и ответ Теперь пусть Здесь воспользуемся соображениями о том, что мы знаем число пар всех оставшихся видов: вычет-вычет, которых невычет-вычет, их и невычет-невычет, их Всего пар чисел (не считая так что на интересующие нас остаётся Тогда для ответ а для —