В этой статье вы узнаете всё о квадратичных вычетах по простому модулю и разложении числа в сумму двух квадратов.
Будем обозначать множество остатков по модулю \(p\) со сложением и умножением как \(\mathbb{F}_p\).
Будем считать, что арифметические операции в \(\mathbb{F}_p\) работают за константое время или что то же самое, мерять все в арифметических операциях(сложение, умножение, вычитание).
Здесь и далее \(p\) – простое число.
Определение. \(a \in \mathbb{F}_p\) называется квадратичным вычетом если существует такое \(z\), что \(z^2 \equiv a \pmod{p}\), а иначе невычетом.
Определение. Символом Лежандра числа \(a\) называется величина \(\begin{pmatrix} a\cr \hdashline p\cr \end{pmatrix}\), равная единице, если \(a\) является квадратичным вычетом по модулю \(p\), нулю если \(a \equiv 0\), и \(-1\) иначе.
Лемма. В \(\mathbb{F}_p\) поровну квадратичных вычетов и невычетов, а именно \(\frac{p - 1}{2}\).
Доказательство. Посмотрим на числа \(1^2, 2^2, \ldots, (p - 1)^2\). Заметим, что \(a^2 \equiv b^2\) равносильно тому что \(p \mid (a - b)(a + b)\), то есть либо \(a \equiv b\), либо \(a \equiv -b\). А это значит, что среди первых \(\frac{p - 1}{2}\) квадратов нет повторяющихся, а поскольку \(a^2 \equiv (p - a)^2\), то это все квадраты, что и требовалось.
Лемма. \(\begin{pmatrix} ab\cr \hdashline p\cr \end{pmatrix} = \begin{pmatrix} a\cr \hdashline p\cr \end{pmatrix} \begin{pmatrix} b\cr \hdashline p\cr \end{pmatrix}\).
Доказательство. Посмотрим что означает данное утверждение. Оно значит, что произведение двух вычетов является вычетом, произведение двух невычетов также является вычетом, а вот произведение вычета и невычета является невычетом.
Очевидно, что произведение двух вычетов является вычетом. \(a \equiv x^2, b \equiv y^2\), значит \(ab \equiv (xy)^2\).
Также понятно про произведение вычета и невычета. Если \(a \equiv x^2, ab \equiv y^2\), то \(b \equiv \left( \frac{y}{x} \right)^2\), где \(\frac{y}{x} = yx^{-1}\), а \(x^{-1}\) обратный остаток к \(x\).
Осталось доказать, что произведение двух невычетов является вычетом. Предположим противное. Пусть \(c \equiv ab\). Для каждого \(x\) существует единственный \(y\) такой, что \(xy \equiv c\). Поскольку \(c\) не является вычетом все числа можно так разбить на пары. Но в каждой паре есть хотя бы один невычет из первого пункта доказательства, но в одной из пар два невычета, значит их больше половины, противоречие.
Мы доказали очень важное свойство, которое называется мультипликативностью.
Лемма. \(\begin{pmatrix} a\cr \hdashline p\cr \end{pmatrix} = a^{\frac{p - 1}{2}}\).
Доказательство. Заметим, что если \(a \equiv x^2\), то \(a^{\frac{p - 1}{2}} \equiv x^{p - 1} \equiv 1\) по малой теореме Ферма, то есть для вычетов утверждение верно.
Можно было бы сказать, что многочлен \(x^{\frac{p - 1}{2}} - 1\) имеет не более \(\frac{p - 1}{2}\) корней, потому что \(\mathbb{F}_p\) – поле, но у этого факта есть более элементарное доказательство.
Проделаем тот же трюк, что и в доказательстве мультипликативности для двух невычетов. Тогда произведение всех чисел в парах с одной стороны равно \((p - 1)!\), так как каждое число встречается ровно один раз, а с другой стороны \(a^{\frac{p - 1}{2}}\), но по теореме Вильсона \((p - 1)! \equiv -1 \pmod{p}\).
Это знание, например, позволит нам определить когда \(-1\) является вычетом, и, даже, если очень постараться, понять то же самое про \(2\).
Лемма. \(-1\) является вычетом тогда и только тогда, когда \(p = 4k + 1\).
Доказательство. Примените формулу для символа Лежандра.
Лемма. \(\begin{pmatrix} 2\cr \hdashline p\cr \end{pmatrix} = (-1)^{\frac{p^2 - 1}{8}}\).
Доказательство. Пусть \(P = 2 \cdot 4 \cdot \ldots \cdot (p - 1)\). Тогда \(P \equiv 2^{\frac{p - 1}{2}} \left(\frac{p - 1}{2}\right)! \equiv \begin{pmatrix} 2\cr \hdashline p\cr \end{pmatrix} \left(\frac{p - 1}{2} \right)!\)
Сократим общие множители в сравнении и рассмотрим случаи.
Первый случай. \(p = 4k + 1\). Получаем сравнение \[\begin{equation*} (2k + 2) \cdot \ldots \cdot 4k \equiv \begin{pmatrix} 2\cr \hdashline p\cr \end{pmatrix} \cdot 1 \cdot 3 \cdot \ldots (2k - 1) \end{equation*}\]
Заметим, что \[\begin{equation*} (2k + 2) \cdot \ldots \cdot 4k \equiv (-1)^k \cdot 1 \cdot 4 \cdot \ldots \cdot (2k - 1) \end{equation*}\] Откуда \((-1)^k \equiv \begin{pmatrix} 2\cr \hdashline p\cr \end{pmatrix}\). Нетрудно проверить, что \(k\) и \(\frac{p^2 - 1}{8}\) имеют одинаковую четность, что и требовалось.
Второй случай. \(p = 4k + 3\). Второй случай аналогичен и достается читателю в качестве простого и приятного упражнения.
Символ Лежандра числа \(a\) можно найти за \(O(\log p)\), возведя его в степень \(\frac{p - 1}{2}\). А можно ли найти квадратный корень числа по модулю?
Для начала попробуем найти квадратный корень \(-1\), если \(p = 4k + 1\). Пусть \(a\) – невычет по модулю \(p\), то \(a^{\frac{p - 1}{2}} \equiv -1\), а значит \(a^{\frac{p - 1}{4}} \equiv a^k\) это искомый корень. Перед нами встаёт задача о нахождении невычета по модулю \(p\).
Лемма. Существует алгоритм, который находит невычет по модулю \(p\) за ожидаемое время \(O(\log p)\).
Доказательство. Будем брать случайное число от \(1\) до \(p - 1\) включительно и проверять является ли оно невычетом, вычисляя символ Лежандра за \(O(\log p)\). Поскольку невычетов ровно половина, вероятность того, что очередное число окажется невычетом равна \(\frac{1}{2}\), а значит ожидаемое число шагов равно \(2\).
Существование полиномиального, детерминированного и безусловного(не опирающегося на недоказанные факты) алгоритма является открытой проблемой. В предположении гипотезы Римана среди первых \(O(\log^2 p)\) чисел есть невычет.
Лемма. Если \(n\) является вычетом, то существует алгоритм, который за ожидаемое время \(O(\log p)\) находит такое \(a\), что \(a^2 - n\) является невычетом.
Доказательство. Если \(n\) вычет, то \(n = x^2\), а тогда \(a^2 - n = a^2 - x^2 = (a - x)(a + x)\). Воспользуемся мультипликативностью символа Лежандра, в предположении, что \(a + x\) не равно нулю по модулю \(p\).
\[\begin{equation*} \begin{pmatrix} a^2 - n\cr \hdashline p\cr \end{pmatrix} = \begin{pmatrix} (a - x)(a + x)\cr \hdashline p\cr \end{pmatrix} = \begin{pmatrix} a - x\cr \hdashline p\cr \end{pmatrix} \begin{pmatrix} a + x\cr \hdashline p\cr \end{pmatrix} = \frac{\begin{pmatrix} a - x\cr \hdashline p\cr \end{pmatrix}}{\begin{pmatrix} a + x\cr \hdashline p\cr \end{pmatrix}} = \begin{pmatrix} \dfrac{a - x}{a + x}\cr \hdashline p\cr \end{pmatrix} \end{equation*}\]
Обозначим \(f(a) = \dfrac{a - x}{a + x}\). Пусть \(f(a) \equiv f(b)\). Тогда \[\begin{equation*} \dfrac{a - x}{a + x} \equiv \dfrac{b - x}{b + x} \end{equation*}\] \[\begin{equation*} (a - x)(b + x) \equiv (a + x)(b - x) \end{equation*}\] \[\begin{equation*} ab - bx + ax - x^2 \equiv ab + bx - ax - x^2 \end{equation*}\] \[\begin{equation*} (a - b)x \equiv (b - a)x \end{equation*}\]
То есть \(f(a) \equiv f(b) \Longrightarrow a \equiv b\).
Поскольку \(\begin{pmatrix} a^2 - n\cr \hdashline p\cr \end{pmatrix} = \begin{pmatrix} f(a)\cr \hdashline p\cr \end{pmatrix}\), то вероятность того, что случайно выбранное \(a\) окажется подходящим равна вероятности того, что \(f(a)\) является невычетом. Но как было показано ранее, для разных аргументов \(f\) возвращает разные значения, а значит \(f\) равновероятно распределена между какими-то \(p - 1\) значениями.
Среди любых \(p - 1\) остатков хотя бы \(\frac{p - 1}{2} - 1\) невычетов. Можно понять это так, мы берем все остатки, и исключаем из них один, а изначально невычетов \(\frac{p - 1}{2}\). Таким образом вероятность того, что \(f(a)\) невычет не меньше \(\frac{p - 3}{2p - 2}\).
То есть если мы будем выбирать \(a\) случайно от 0 до \(p\) невключительно, то ожидаемое количество шагов при \(p > 3\) ограничено константой. Можно убедиться, что при \(p = 3\) мы сможем найти такое \(a\). Действительно, единственный вычет это \(1\), то есть \(n = 1\). Тогда подходящее \(a = 0\).
Лемма. Существует алгоритм, который для вычета \(n\) ищет такой \(z\), что \(z^2 \equiv n \pmod{p}\) за ожидаемое время \(O(\log p)\).
Доказательство. Найдём такое \(a\), что \(a^2 - n\) является невычетом за ожидаемое время \(O(\log p)\). Обозначим за \(\omega = \sqrt{a^2 - n}\). Строго говоря, посмотрим на все многочлены в \(\mathbb{F}_p\) от \(\omega\). и посмотрим на них по модулю \(\omega^2 - (a^2 - n)\). Получившееся множество \(\{ a + bw \mid a, b \leftarrow \mathbb{F}_p\}\) будем обозначать \(T = \mathbb{F}_p[w]/(w^2 - (a^2 - n))\).
Заметим, что числа из \(T\) можно складывать и умножать: \[(a + bw) + (c + dw) = (a + c) + (b + d)w, (a + bw)(c + dw) = (ac + bd(a^2 - n)) + (ad + bc)w\]
Понятно, что сложение и умножение обладает всеми необходимыми свойствами(коммутативность, дистрибутивность, ассоциативность)
В качестве упражнения читателю остается проверить, что \(T\) – поле. Из содержательных свойств надо проверить обратимость умножения.
Лемма. \((a + w)^{\frac{p + 1}{2}}\) является искомым \(z\), что в частности значит, что оно не имеет компоненту с \(w\).
Доказательство. Посмотрим на \((a + w)^{p + 1}\). Заметим, что \((a + w)^p = a^p + w^p\). Действительно, если раскрыть скобки по биному Ньютона, то все остальные члены будут делиться на \(p\). Также \(w^p = -w\), поскольку \(w^{p - 1} = (a^2 - n)^\frac{p - 1}{2} = -1\), в силу того, что \(a^2 - n\) невычет. Тогда
\[\begin{equation*} (a + w)^{p + 1} = (a^p + w^p)(a + w) = (a - w)(a + w) = a^2 - w^2 = a^2 - (a^2 - n) = n \end{equation*}\]
Поскольку читатель проверил, что \(T\) является полем, многочлен \(x^2 - n\) имеет в нем не более двух корней. Но мы знаем, что \(z\) и \(-z\) являются его корнями. В то же время \(\left((a + w)^\frac{p + 1}{2}\right)^2 - n = 0\), значит оно и есть искомое \(z\).
Итого мы доказали очень простой алгоритм для нахождения квадратного корня по модулю.
Наша цель, понять, для каких \(n\) существуют \(a, b\), такие, что \(a^2 + b^2 = n\), и как их оптимально искать.
Для начала попробуем решить задачу для простого \(p\). Сразу понятно, что если \(p = 4k + 3\), то разложить в сумму двух квадратов не удастся, можно даже доказать более сильное утверждение.
Лемма Жирара. Если \(a^2 + b^2 \equiv 0 \pmod{p}\), где \(p\) простое число вида \(4k + 3\), то \(p \mid a, b\).
Доказательство. \(a^2 \equiv -b^2 \pmod{p}\). Возьмём символ лежандра от обоих частей и воспользуемся мультипликативностью.
\[\begin{equation*} \begin{pmatrix} a^2\cr \hdashline p\cr \end{pmatrix} = \left[\begin{pmatrix} a^2\cr \hdashline p\cr \end{pmatrix} = \begin{pmatrix} -b^2\cr \hdashline p\cr \end{pmatrix}\right] = \begin{pmatrix} -1\cr \hdashline p\cr \end{pmatrix} \begin{pmatrix} b^2\cr \hdashline p\cr \end{pmatrix} = -1 \begin{pmatrix} b^2\cr \hdashline p\cr \end{pmatrix} \end{equation*}\]
Последнее равенство в силу того, что \(p = 4k + 3\). Но тогда \(\begin{pmatrix} a^2\cr \hdashline p\cr \end{pmatrix} = \begin{pmatrix} b^2\cr \hdashline p\cr \end{pmatrix} = 0\), что и требовалось.
Лемма. Любое простое \(p\) вида \(4k + 1\) представляется в виде суммы двух квадратов.
Попробуем конструктивно научиться искать разложение для \(p = 4k + 1\). Для начала поймем как “перемножать” такие разложения, это также поможет нам далее, когда мы перейдем в составному \(n\).
Пусть \(a^2 + b^2 = x, c^2 + d^2 = y\). Тогда \[\begin{equation*} a^2c^2 + a^2d^2 + b^2c^2 + b^2d^2 = xy \end{equation*}\] \[\begin{equation*} (ac)^2 + (ad)^2 + (bc)^2 + (bd)^2 = xy \end{equation*}\] \[\begin{equation*} (ac)^2 + (bd)^2 + 2abcd + (ad)^2 + (bc)^2 - 2abcd = xy \end{equation*}\] \[\begin{equation*} (ac + bd)^2 + (ad - bc)^2 = xy \end{equation*}\]
То же самое можно увидеть, если рассмотреть \(z = a + bi, w = c + di\), тогда \(\conj{z}w = (ac + bd) + (ad - bc)i\), а \(xy = |z|^2|w|^2 = |\conj{z}|^2|w|^2 = |\conj{z}w|^2|\).
То есть мы доказали, что если \(x, y\) представимы в виде суммы двух квадратов, то \(xy\) тоже представимо в виде суммы двух квадратов.
Попробуем представить число \(p\), пользуясь предыдущим знанием. Пусть для начала у нас есть разбиение числа \(mp\) для какого-то \(m\), то есть \(a^2 + b^2 = mp\).
Определение. Абсолютно наименьшим вычетом числа \(a\) по модулю \(m\) называется наименьшее по абсолютному значению \(b\) такое, что \(a \equiv b \pmod{m}\).
Пусть \(c, d\) абсолютно наименьшие вычеты чисел \(a, b\) по модулю \(m\). Тогда \(c^2 + d^2 = mk\) и \(k \leqslant \frac{m}{2}\).
Тогда мы можем представить \(m^2pk = (ac + bd)^2 + (ad - bc)^2\). Остается только заметить, что \(ad - bc\) и \(ac + bd\) делятся на \(m\). Действительно, \(ad - bc \equiv ab - ab \equiv 0 \pmod{m}\) и \(ac + bd \equiv a^2 + b^2 \equiv 0 \pmod{m}\). \[\begin{equation*} pk = \left( \dfrac{ad - bc}{m} \right)^2 + \left( \dfrac{ac + bd}{m} \right)^2 \end{equation*}\]
Если мы будем повторять эту процедуру, то на каждом шаге \(m\) будет уменьшаться хотя бы в два раза, а значит когда-то станет единицей, и мы получим требуемое разбиение.
Тем самым мы не только доказали лемму, но и нашли эффективный алгоритм нахождения такого разложения.
В качестве начального разбиения можно взять \(a = 1, b = z\), где \(z^2 \equiv -1 \pmod{p}\). Найти \(z\) можно за \(O(\log p)\). Далее мы делаем \(O(\log p)\) шагов, так как начальное \(m\) не превосходит \(p\), на каждом шаге делаем константное число операций.
Итого за \(O(\log p)\) времени и \(O(1)\) дополнительной памяти мы умеем искать разложение \(p\) в сумму двух квадратов.
Самое интересное происходит в случае составного \(n\). Оказывается верно следующее.
Рождественская теорема Ферма. Число \(n\) можно представить в виде суммы двух квадратов тогда и только тогда, когда каждое простое \(p\) вида \(4k + 3\) входит в разложение \(n\) в четной степени.
В одну сторону мы уже умеем доказывать и находить разбиение. Действительно \(2 = 1^2 + 1^2, p^2 = 0^2 + p^2\). Для простых вида \(4k + 1\) мы умеем находить разбиение, а ещё мы умеем перемножать два существующих.
Лемма. Для любого простого \(p\) вида \(4k + 3\) его степень вхождения в \(a^2 + b^2\) чётна.
Доказательство. Если \(a^2 + b^2\) не делится на \(p\), то утверждение очевидно. Иначе воспользуемся леммой Жирара, получим что \(p \mid a, b\). Тода \(p^2 \mid a^2 + b^2\) и \(\left( \frac{a}{p} \right)^2 + \left( \frac{b}{p} \right)^2 = \frac{a^2 + b^2}{p^2}\). Применяя то же самое рассуждение получаем требуемое.
Тем самым мы доказали рождественскую теорему Ферма и научились раскладывать числа в суммы двух квадратов.