Квадратичные
вычеты и корни по простому модулю
В этой статье вы узнаете всё о квадратичных вычетах по простому
модулю и разложении числа в сумму двух квадратов.
Будем обозначать множество остатков по модулю со сложением и умножением как .
Будем считать, что арифметические операции в работают за константое время
или что то же самое, мерять все в арифметических операциях(сложение,
умножение, вычитание).
Вычеты, символ Лежандра
Здесь и далее – простое
число.
Определение. называется квадратичным вычетом если
существует такое , что , а иначе
невычетом.
Определение. Символом Лежандра числа называется величина , равная единице, если является квадратичным вычетом по модулю
, нулю если , и иначе.
Лемма. В поровну квадратичных вычетов
и невычетов, а именно .
Доказательство. Посмотрим на числа . Заметим, что
равносильно тому что
, то есть либо
, либо . А это значит, что среди
первых квадратов
нет повторяющихся, а поскольку , то это все квадраты, что и требовалось.
Лемма. .
Доказательство. Посмотрим что означает данное
утверждение. Оно значит, что произведение двух вычетов является вычетом,
произведение двух невычетов также является вычетом, а вот произведение
вычета и невычета является невычетом.
Очевидно, что произведение двух вычетов является вычетом. , значит .
Также понятно про произведение вычета и невычета. Если , то ,
где , а обратный остаток к .
Осталось доказать, что произведение двух невычетов является вычетом.
Предположим противное. Пусть . Для каждого
существует единственный такой,
что . Поскольку не является вычетом все числа можно так
разбить на пары. Но в каждой паре есть хотя бы один невычет из первого
пункта доказательства, но в одной из пар два невычета, значит их больше
половины, противоречие.
Мы доказали очень важное свойство, которое называется
мультипликативностью.
Лемма. .
Доказательство. Заметим, что если , то по малой теореме Ферма, то есть для вычетов утверждение
верно.
Можно было бы сказать, что многочлен имеет не более
корней, потому что
– поле, но у этого
факта есть более элементарное доказательство.
Проделаем тот же трюк, что и в доказательстве мультипликативности для
двух невычетов. Тогда произведение всех чисел в парах с одной стороны
равно , так как каждое
число встречается ровно один раз, а с другой стороны , но по теореме
Вильсона .
Это знание, например, позволит нам определить когда является вычетом, и, даже, если очень
постараться, понять то же самое про .
Лемма.
является вычетом тогда и только тогда, когда .
Доказательство. Примените формулу для символа
Лежандра.
Лемма. .
Доказательство. Пусть . Тогда
Сократим общие множители в сравнении и рассмотрим случаи.
Первый случай. . Получаем сравнение
Заметим, что Откуда .
Нетрудно проверить, что и имеют одинаковую
четность, что и требовалось.
Второй случай. . Второй случай аналогичен и достается читателю в качестве
простого и приятного упражнения.
Нахождение квадратного
корня по модулю
Символ Лежандра числа можно
найти за , возведя его в
степень . А можно ли
найти квадратный корень числа по модулю?
Для начала попробуем найти квадратный корень , если . Пусть – невычет
по модулю , то , а значит
это
искомый корень. Перед нами встаёт задача о нахождении невычета по модулю
.
Лемма. Существует алгоритм, который находит невычет
по модулю за ожидаемое время
.
Доказательство. Будем брать случайное число от до включительно и проверять является ли оно невычетом, вычисляя
символ Лежандра за .
Поскольку невычетов ровно половина, вероятность того, что очередное
число окажется невычетом равна , а значит ожидаемое число
шагов равно .
Существование полиномиального, детерминированного и безусловного(не
опирающегося на недоказанные факты) алгоритма является открытой
проблемой. В предположении гипотезы Римана среди первых чисел есть невычет.
Лемма. Если
является вычетом, то существует алгоритм, который за ожидаемое время
находит такое , что является невычетом.
Доказательство. Если вычет, то , а тогда . Воспользуемся мультипликативностью символа
Лежандра, в предположении, что не равно нулю по модулю .
Обозначим . Пусть . Тогда
То есть .
Поскольку , то вероятность того, что случайно выбранное
окажется подходящим равна
вероятности того, что является
невычетом. Но как было показано ранее, для разных аргументов возвращает разные значения, а значит
равновероятно распределена между
какими-то значениями.
Среди любых остатков хотя
бы невычетов.
Можно понять это так, мы берем все остатки, и исключаем из них один, а
изначально невычетов . Таким образом вероятность того, что невычет не меньше .
То есть если мы будем выбирать
случайно от 0 до невключительно,
то ожидаемое количество шагов при ограничено константой. Можно убедиться, что при мы сможем найти такое . Действительно, единственный вычет это
, то есть . Тогда подходящее .
Лемма. Существует алгоритм, который для вычета ищет такой , что за ожидаемое время .
Доказательство. Найдём такое , что является невычетом за ожидаемое время . Обозначим за . Строго говоря,
посмотрим на все многочлены в от . и посмотрим на них по модулю
. Получившееся
множество будем обозначать .
Заметим, что числа из можно
складывать и умножать:
Понятно, что сложение и умножение обладает всеми необходимыми
свойствами(коммутативность, дистрибутивность, ассоциативность)
В качестве упражнения читателю остается проверить, что – поле. Из содержательных свойств надо
проверить обратимость умножения.
Лемма. является искомым , что в частности значит, что оно не
имеет компоненту с .
Доказательство. Посмотрим на . Заметим, что . Действительно,
если раскрыть скобки по биному Ньютона, то все остальные члены будут
делиться на . Также , поскольку , в силу того, что невычет. Тогда
Поскольку читатель проверил, что является полем, многочлен имеет в нем не более двух корней.
Но мы знаем, что и являются его корнями. В то же время
, значит оно и есть искомое .
Итого мы доказали очень простой алгоритм для нахождения квадратного
корня по модулю.
- Найти такое , что является невычетом методом проб и
ошибок
- Возвести в степень
быстрым возведением
в степень, где ,
это и будет результатом.
Разложение в сумму двух
квадратов
Наша цель, понять, для каких
существуют , такие, что , и как их оптимально
искать.
Для начала попробуем решить задачу для простого . Сразу понятно, что если , то разложить в сумму двух
квадратов не удастся, можно даже доказать более сильное утверждение.
Лемма Жирара. Если , где простое число вида , то .
Доказательство. . Возьмём символ лежандра от обоих частей и
воспользуемся мультипликативностью.
Последнее равенство в силу того, что . Но тогда , что и требовалось.
Лемма. Любое простое вида представляется в виде суммы двух квадратов.
Попробуем конструктивно научиться искать разложение для . Для начала поймем как
“перемножать” такие разложения, это также поможет нам далее, когда мы
перейдем в составному .
Пусть . Тогда
То же самое можно увидеть, если рассмотреть , тогда , а
.
То есть мы доказали, что если представимы в виде суммы двух квадратов, то тоже представимо в виде суммы двух
квадратов.
Попробуем представить число ,
пользуясь предыдущим знанием. Пусть для начала у нас есть разбиение
числа для какого-то , то есть .
Определение. Абсолютно наименьшим вычетом
числа по модулю называется наименьшее по абсолютному
значению такое, что .
Пусть абсолютно
наименьшие вычеты чисел
по модулю . Тогда и .
Тогда мы можем представить . Остается только заметить, что и делятся на .
Действительно, и .
Если мы будем повторять эту процедуру, то на каждом шаге будет уменьшаться хотя бы в два раза, а
значит когда-то станет единицей, и мы получим требуемое разбиение.
Тем самым мы не только доказали лемму, но и нашли эффективный
алгоритм нахождения такого разложения.
Анализ алгоритма
В качестве начального разбиения можно взять , где . Найти можно за . Далее мы делаем шагов, так как начальное не превосходит , на каждом шаге делаем константное
число операций.
Итого за времени и
дополнительной памяти мы умеем
искать разложение в сумму двух
квадратов.
Составное
Самое интересное происходит в случае составного . Оказывается верно следующее.
Рождественская теорема Ферма. Число можно представить в виде суммы двух
квадратов тогда и только тогда, когда каждое простое вида входит в разложение в
четной степени.
В одну сторону мы уже умеем доказывать и находить разбиение.
Действительно . Для простых вида мы умеем находить разбиение, а ещё мы умеем перемножать два
существующих.
Лемма. Для любого простого вида его степень вхождения в чётна.
Доказательство. Если не делится на , то
утверждение очевидно. Иначе воспользуемся леммой Жирара, получим что
. Тода и . Применяя то же самое
рассуждение получаем требуемое.
Тем самым мы доказали рождественскую теорему Ферма и научились
раскладывать числа в суммы двух квадратов.