Математика · объяснение и практика
Остатки квадратов: как исключить невозможное равенство
Используем короткую таблицу остатков квадратов для доказательства невозможности равенства и не принимаем прохождение одного теста за доказательство существования.

В теме Теория чисел: углубление · Учебная карта
Главная мысль
Квадрат целого числа по модулю четыре имеет только остаток ноль или один. По модулю восемь возможны ноль, один и четыре. Если требуемое равенство даёт другой остаток, целых решений нет; здесь нулевой остаток включён в рассмотрение.
Почему достаточно нескольких представителей
Любое целое число сравнимо по модулю четыре с одним из 0, 1, 2, 3. Их квадраты дают остатки 0, 1, 0, 1. Прибавление кратного четырём к основанию не меняет остаток квадрата, поэтому таблица охватывает сразу все целые числа, в том числе отрицательные. Это не конечный перебор неизвестных решений, а проверка всех классов.
Из таблицы следует, что сумма двух квадратов может давать только 0, 1 или 2 по модулю четыре. Остаток три невозможен. Поэтому уравнение x²+y² = 4k+3 не имеет целых решений для любого целого k. Утверждение не зависит от размера числа справа: препятствие находится в его классе остатка, который сохраняется при точном равенстве.
Как более сильный модуль замечает новую невозможность
По модулю восемь квадрат имеет остаток 0, 1 либо 4. Для нечётного n = 2t+1 получаем n² = 4t(t+1)+1. Произведение соседних целых t(t+1) чётно, поэтому добавка кратна восьми и остаток всегда один. У чётного числа квадрат даёт ноль или четыре в зависимости от делимости основания на четыре.
Например, число 165 даёт остаток один по модулю четыре, поэтому первый тест не запрещает ему быть квадратом. Но по модулю восемь остаток равен пяти, что невозможно для квадрата. Более подробная таблица усилила проверку. Выбирать модуль полезно по структуре выражения, а не просто увеличивать его до неудобного размера без новой информации.
Пример
Может ли 27 быть суммой двух целых квадратов?
Число 27 даёт остаток три по модулю четыре. Сумма двух квадратов такого остатка не имеет, поэтому представление невозможно независимо от выбора положительных, отрицательных или нулевых оснований.
Разрешённый остаток ещё не строит решение
Число 185 оставляет один по модулю восемь, однако не является целым квадратом: оно лежит строго между 13² = 169 и 14² = 196. Прохождение теста означает только отсутствие найденного препятствия. Оно не подтверждает, что нужный целый корень существует. Необходимое условие нельзя незаметно превратить в достаточное.
При работе с квадратичными остатками разные справочники могут отдельно исключать нулевой класс из термина. В задачах на невозможность полезно прямо перечислить используемый набор и сохранить ноль, если основания могут быть кратны модулю. Иначе из таблицы исчезнет реальный допустимый случай. После модульного отсева оставшиеся кандидаты при необходимости проверяют другим аргументом или явным построением.
От чтения к действию
А теперь — вы
Частые вопросы
Отрицательные основания требуют новой таблицы?
Нет. Их квадраты совпадают с квадратами противоположных положительных чисел; кроме того, таблица классов уже охватывает все целые.
Остаток один по модулю восемь доказывает квадрат?
Нет. Это необходимый признак для нечётного квадрата, но многие неквадраты имеют такой же остаток.
Углублённый разбор
Квадратичная взаимность меняет числитель и простой модуль
Решение квадратного сравнения начинается с вопроса существования корня. Закон квадратичной взаимности позволяет ответить на него, последовательно уменьшая простые модули и учитывая знак перестановки. Это критерий для простого модуля, а не способ поднять уже известный корень на следующую степень простого.
Перед началом: Квадрат по модулю простого; Простое разложение целого.
Символ кодирует существование, но не сам корень
Для нечётного простого p символ (a|p) равен 0, если p делит a; равен 1, если ненулевой класс a является квадратом; иначе равен −1. В ненулевом случае значение 1 означает ровно два корня, противоположных по модулю p. Сам символ не указывает эти корни. Поэтому вычисление символа и построение решения — две разные алгоритмические задачи.
Символ мультипликативен по числителю: (ab|p)=(a|p)(b|p). Квадрат ненулевого множителя даёт 1, поэтому можно сокращать чётные показатели простого разложения числителя. Дополнительные законы задают (−1|p)=(−1)^((p−1)/2) и (2|p)=(−1)^((p²−1)/8). Они закрывают ветви, где обычная взаимность для двух различных нечётных простых неприменима.
Знак возникает только при двух простых вида 4k+3
Для различных нечётных простых p,q закон гласит (p|q)(q|p)=(−1)^(((p−1)/2)((q−1)/2)). Значит символы равны, если хотя бы один простой равен 1 по модулю 4, и противоположны, если оба равны 3. После обмена числитель сокращают по новому модулю, а затем снова раскладывают. В каждом таком переходе модуль уменьшается, что и делает процедуру полезной.
Простота знаменателя — существенная гипотеза. Для составного нечётного знаменателя определяют символ Якоби как произведение символов по простым делителям, но значение +1 уже не гарантирует квадратный корень. Например, (2|15)=1, хотя квадраты по модулю 3 не дают 2. Нельзя незаметно перенести достаточность символа Лежандра на этот другой объект.
Маленький конечный контроль проверяет большой вывод
На умеренном простом модуле ответ можно независимо подтвердить перечислением квадратов. Такой контроль не заменяет взаимность на больших числах, но обнаруживает потерянный знак и неверное сокращение. Полезно хранить всю цепочку символов: каждое равенство должно объясняться конкретным законом. Отрицательный итог немедленно запрещает корень; положительный позволяет отдельно запустить алгоритм извлечения квадратного корня.
Существование без поиска корня
Условие. Определите, имеет ли x²≡37 по модулю 101 решения, используя взаимность. Затем подтвердите ответ отдельной подстановкой.
- Оба числа 37 и 101 — различные нечётные простые, причём 37≡1 по модулю 4. Поэтому (37|101)=(101|37).
- Сокращаем 101 до 27 по модулю 37. По мультипликативности (27|37)=(3|37)³=(3|37).
- При обмене 3 и 37 знак снова положителен, поскольку 37≡1 по модулю 4. Значит (3|37)=(37|3)=(1|3)=1.
- Следовательно существуют два корня. Независимо 21²=441≡37 по модулю 101, а противоположный остаток равен 80. Их квадраты дают один требуемый класс.
Ответ. Символ равен 1; корни по модулю 101 равны 21 и 80.
Проверка. Полный независимый перебор 101 класса находит именно эти два остатка. Дополнительно перечисление квадратов по модулю 15 подтверждает контрпример для достаточности символа Якоби.
Где легко ошибиться. Не забывайте знак при обмене двух простых вида 4k+3 и не делайте вывод о существовании корня из символа Якоби +1 для составного модуля.
Проверьте понимание
Вопросы к этой главе
Зачем выделять случай нулевого числителя?
Он имеет один корень 0 по простому модулю и символ 0. Все рассуждения о двух противоположных ненулевых корнях и знаках ±1 относятся к числителю, взаимно простому с p.
Почему простоту 101 здесь можно считать проверенной?
Достаточно проверить простые делители не больше √101: 2,3,5,7. Ни один не делит 101. Число 37 проверяется делителями 2,3,5. Это отдельная предпосылка взаимности, а не её следствие.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- MIT18.781, Lecture9: Quadratic Reciprocity
Прочитаны определение символа Лежандра, мультипликативность, взаимность и дополнительные знаки для −1 и 2. Расчёт (37|101) и полный перебор квадратов выполнены самостоятельно.
Квадратный корень по простому модулю алгоритмом Тонелли — Шенкса
Критерий квадратичного вычета отвечает, существует ли корень по простому модулю, но не находит его. Алгоритм Тонелли — Шенкса исправляет приближённый корень, последовательно уменьшая двойную часть порядка ошибки. Каждая итерация сохраняет алгебраический инвариант и строго сокращает оставшийся показатель.
Перед началом: Группа ненулевых остатков простого поля; Порядок элемента и критерий Эйлера.
Нечётная и двойная части порядка выполняют разные роли
Пусть p нечётное простое, 0<a<p и a является квадратом. Запишем p−1=Q·2ˢ с нечётным Q. Выберем квадратичный невычет z. Начальное состояние: c=z^Q, r=a^((Q+1)/2), t=a^Q, M=S. Все значения берутся по модулю p.
Выполняется r²=at, а c имеет точный порядок 2ᴹ. Поскольку a — квадрат, порядок t делит 2^(M−1). Нечётная часть уже обработана степенями Q; остаётся устранить ошибку t в циклической двойной подгруппе. Случай a=0 проще и даёт корень нуль без этого алгоритма.
Исправление уменьшает порядок ошибки
Если t≠1, найдём наименьшее i>0, для которого t^(2ⁱ)=1. Имеем i<M. Положим b=c^(2^(M−i−1)), затем r←rb, t←tb², c←b², M←i. Инвариант r²=at сохраняется, потому что обе стороны умножились на b².
Элемент b² имеет порядок 2ⁱ и его степень 2^(i−1) равна −1. У прежнего t та же степень тоже равна −1 по минимальности i. Поэтому новый t имеет порядок, делящий 2^(i−1). Новый параметр M=i строго меньше прежнего. Это доказывает завершение по числу двоичных уровней, а не по перебору всех возможных корней.
Предпосылки и окончательная подстановка обязательны
До запуска проверяют простоту p и квадратичность a. Если a не является квадратом, рассуждение о меньшем порядке t перестаёт работать. Невычет z также должен быть подтверждён, например равенством z^((p−1)/2)=−1. Не всякое ненулевое основание создаёт требуемый c полного двойного порядка.
При t=1 получаем r²=a. Второй корень равен −r mod p; для ненулевого a они различны. Полнота следует из полевого разложения x²−r²=(x−r)(x+r): произведение равно нулю лишь при нулевом одном множителе. Для составного модуля это рассуждение и сам алгоритм без изменений неприменимы.
Две коррекции для квадратного корня по модулю сорок один
Условие. Решите x²≡5 mod 41 алгоритмом Тонелли — Шенкса, используя невычет z=3. Покажите обе коррекции и проверьте полный набор корней.
- Имеем 40=5·2³, поэтому Q=5, S=3. Проверки 5²⁰=1 и 3²⁰=40=−1 подтверждают вычет и невычет.
- Начальные значения: c=3⁵=38, r=5³=2, t=5⁵=9, M=3. Инвариант r²=4≡5·9 выполнен.
- Для t=9 получаем t²=40, t⁴=1, поэтому i=2. Берём b=38, обновляем r=35, t=40, c=9, M=2.
- Теперь i=1, потому что 40²=1. Берём b=9, после обновления r=28, t=1, c=40, M=1. Алгоритм завершён.
- Корни равны 28 и 41−28=13. Прямые квадраты 28²=784 и 13²=169 дают остаток пять; конечный перебор всех 41 классов подтверждает, что других корней нет.
Ответ. Полный набор корней: 13 и 28 по модулю 41. Параметр M уменьшился 3→2→1, а ошибка t стала единицей.
Проверка. В каждом состоянии проверено r²=5t mod 41. Независимая подстановка обоих окончательных корней и ограниченный перебор проверяют результат и полноту.
Где легко ошибиться. Не принимайте промежуточное r за корень до t=1. Инвариант содержит дополнительный множитель ошибки t, который может отличаться от единицы после нескольких корректных этапов.
Проверьте понимание
Вопросы к этой главе
Почему число 35 ещё не является корнем?
После первой коррекции t=40, поэтому r²=5·40≡36, а не пять. Нужно выполнить вторую коррекцию до исчезновения ошибки.
Зачем искать минимальный i?
Именно минимальность гарантирует t^(2^(i−1))=−1 и строгое уменьшение порядка после умножения на b². Произвольный показатель с возвратом к единице не даёт тот же доказанный прогресс.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Handbook of Applied Cryptography, §3.5: square roots modulo a prime
Прочитан алгоритм 3.34 и его предпосылки: простой модуль, вычет, выбор невычета и разложение p−1. Здесь используется эквивалентная форма Шенкса с переменным M; её инвариант, строгое уменьшение и пример p=41 проверены отдельно.
Символ Якоби равен единице, а квадратного корня нет
Символ Якоби можно вычислить быстро, даже не зная факторизацию нечётного модуля. Но положительный символ по составному модулю не гарантирует квадратного корня. Произведение двух отрицательных локальных ответов превращается в единицу и теряет информацию о том, на каких простых делителях возникло препятствие.
Перед началом: Символ Лежандра для простого модуля; Квадратичная взаимность.
Определение перемножает локальные символы
Для нечётного положительного n=∏p_i^(e_i) символ Якоби определяется как (a/n)=∏(a/p_i)^(e_i), где справа символы Лежандра. При простом n это прежний символ, но при составном его смысл слабее. Значение ноль равносильно НОД(a,n)>1; при взаимной простоте остаются знаки плюс и минус.
Если a является квадратом обратимого остатка по n, каждый локальный символ равен единице, поэтому и символ Якоби равен единице. Обратное неверно: знаки могут сократиться при перемножении, а чётная степень простого в n дополнительно стирает соответствующий знак. Значение минус один запрещает квадратный корень, но единица лишь не обнаруживает это препятствие.
Бинарное вычисление не требует факторизации
Алгоритм сначала уменьшает a по n и выделяет из a степени двойки. Множитель (2/n) равен единице при n≡1,7 mod 8 и минус единице при n≡3,5 mod 8; учитывается чётность числа выделенных двоек. Затем нечётный остаток меняют местами с n, добавляя минус, если оба равны трём по модулю четыре.
После перестановки берут новый числитель по новому знаменателю, как в алгоритме Евклида. Положительные знаменатели убывают, поэтому процесс завершится. Последний НОД определяет, нужно ли вернуть ноль. Полученный знак можно проверить через факторизацию в малом примере, однако для самого алгоритма эта факторизация не является входом.
Существование корня требует восстановить потерянную информацию
Чтобы решить x²≡a mod n, нужно проверять условия по каждому простому степенному множителю и согласовывать локальные корни. Один символ Якоби такую систему не кодирует. Даже наличие двух отрицательных локальных символов достаточно для положительного общего знака, хотя ни один из этих двух модулей не допускает корня.
При нулевом символе тоже нельзя делать общий вывод о разрешимости: необратимый квадрат может иметь общий делитель с модулем. Например, ноль всегда является квадратом нуля. Поэтому полезно разделять три задачи: вычисление знакового символа, проверку существования квадратного корня и построение всех корней.
Два минуса скрывают отсутствие квадратного корня
Условие. Вычислите символ Якоби (3/35) бинарными правилами. Затем решите, существует ли x²≡3 mod 35, и независимо проверьте локальные символы.
- Начинаем с нечётных 3 и 35. Оба равны трём по модулю четыре, поэтому взаимность даёт (3/35)=−(35/3)=−(2/3).
- Для знаменателя три правило двойки даёт (2/3)=−1. Поэтому общий символ равен плюс одному.
- Однако уже по модулю пять квадраты имеют остатки 0,1,4. Остатка три нет, следовательно, исходное сравнение по 35 неразрешимо.
- Факторизация 35=5·7 даёт (3/5)=−1 и (3/7)=−1. Их произведение равно единице и объясняет, какую информацию потерял общий символ.
- Полный перебор x=0,…,34 не находит корня. Он независимо подтверждает отсутствие решения, но для доказательства было достаточно короткого препятствия по модулю пять.
Ответ. Символ Якоби (3/35)=1, но квадратных корней числа три по модулю 35 нет.
Проверка. Бинарная взаимность, произведение локальных символов и прямое перечисление квадратов дают согласованные, но логически разные проверки: вычисление символа не подменяет разрешимость.
Где легко ошибиться. Не переносите равносильность «символ равен единице тогда и только тогда, когда есть корень» с простого модуля на составной.
Проверьте понимание
Вопросы к этой главе
Почему отрицательный символ всё же запрещает корень?
Квадрат обратимого элемента имеет локальный символ единица на каждом простом делителе, значит их произведение тоже единица. Значение минус один противоречит этому необходимому условию.
Нужна ли факторизация 35 для быстрого вычисления символа?
Нет. Взаимность и правило двойки вычисляют его напрямую. Факторизация здесь используется как независимая проверка и для объяснения неразрешимости корневой задачи.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Handbook of Applied Cryptography, §2.4: Jacobi symbol
Прочитаны определение 2.147, свойства 2.148 и алгоритм 2.149, включая оговорку о недостаточности положительного символа. Контрпример 3 по модулю 35 и все его локальные проверки рассчитаны отдельно.
Корнаккья: представление простого числа суммой двух квадратов
Таблица квадратов по небольшому модулю умеет запрещать представления, но не строит их. Для простого p, допускающего корень из −1, этот корень направляет алгоритм Евклида к двум небольшим координатам. Остановка у квадратного корня из p и точная проверка дополняющего квадрата дают само представление, а не только отсутствие препятствия.
Перед началом: Квадратные сравнения и простота модуля; Алгоритм Евклида и его коэффициенты Безу.
Корень из минус единицы кодирует направление решения
Простое p≡1(mod4) и уже найденный точный корень r²≡−1(mod p); рассматривается случай x²+y²=p.
Если p=x²+y² и y не делится на p, то (x·y⁻¹)²≡−1 по модулю p. Значит модульный корень хранит отношение координат, а не одну из координат непосредственно. Для простого p≡1(mod4) такие корни существуют. Их поиск является отдельным этапом; в этой главе корень задан и сначала проверяется точным возведением в квадрат.
Запустим обычный Евклид для p и представителя 0<r<p, сохраняя Rᵢ=Sᵢp+Tᵢr. В отличие от вычисления НОД, останавливаться следует не на единице: нужен первый остаток R со свойством R²<p. Использование целочисленного сравнения квадратов исключает ошибку округления порога √p.
Размер коэффициента превращает сравнение в равенство
Для первого остатка ниже √p предыдущий остаток больше √p. Стандартная оценка коэффициентов расширенного Евклида даёт 0<|T|≤p/R_пред<√p. Вместе с 0≤R<√p получаем 0<R²+T²<2p. При этом R≡Tr и r²≡−1, следовательно R²+T² делится на p. Единственная возможность в указанном строгом диапазоне — R²+T²=p.
Поэтому можно вообще не вычислять коэффициент T в основном проходе: после остановки положить q=p−R² и проверить, что q является точным целым квадратом. Сохранённый коэффициент Евклида даёт независимую проверку второго корня. Для простого входа и правильного корня проверка обязана пройти; её провал указывает на нарушение предпосылок или вычислительную ошибку.
Целочисленная проверка отделена от общей диофантовой задачи
Извлекать корень из q следует целочисленно: найти y=⌊√q⌋ и проверить y²=q. Близость вещественного результата к целому не является сертификатом. Итоговые координаты можно менять местами и независимо менять их знаки; это разные записи одного геометрического представления. Доказательство всех представлений или их количества не требуется для нахождения одного.
Для составного модуля этот ограниченный аргумент нельзя переносить автоматически, а у уравнения x²+dy²=m появляются дополнительные условия и ветви. Даже существование корня из −1 по составному модулю само по себе не обещает поведение именно этой простой версии. Проверка простоты p и проверка исходного модульного корня остаются явными предпосылками, а не скрытыми выводами успешной таблицы.
Три деления вместо поиска пары координат
Условие. Дано простое p=4093 и корень r=1059. Найдите неотрицательные x,y с x²+y²=4093, используя спуск до √p.
- Проверяем 1059²+1=1121482=274·4093. Корень из −1 действительно задан корректно. Для остановки сравниваем квадраты целых остатков с 4093.
- Деления: 4093=3·1059+916, 1059=916+143, 916=6·143+58. Остатки 1059,916,143 ещё имеют квадрат больше 4093; 58²=3364 уже меньше.
- Дополняющее число равно 4093−3364=729=27². Получаем пару (58,27) без перебора всех x,y.
- Расширенная обратная подстановка даёт 58=7·4093−27·1059. Значит коэффициент T=−27 независимо воспроизводит вторую координату; точное равенство квадратов проверяется напрямую.
Ответ. 4093=58²+27². Перестановка координат или смены знаков дают другие допустимые записи того же представления.
Проверка. Независимый перебор 0≤x≤63 с целочисленной проверкой 4093−x² на квадрат находит только неотрицательные пары (27,58) и (58,27). Он не использует корень 1059 и проверяет сам итог.
Где легко ошибиться. Не продолжайте Евклид до последнего ненулевого остатка: единица даёт НОД, а искомое представление возникает у первого пересечения порога √p.
Проверьте понимание
Вопросы к этой главе
Сам модульный корень 1059 является координатой решения?
Нет: его квадрат намного больше 4093. Он задаёт отношение координат по модулю, а короткие целые координаты появляются после спуска и точной проверки.
Почему нельзя округлить √729 приблизительно и закончить?
Для этого примера ответ очевиден, но общий алгоритм должен проверить квадрат полученного целого. Без такой проверки почти квадратное число могло бы породить ложное точное решение.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Victor Shoup — A Computational Introduction, §4.5, Effective Thue lemma
Остановка Евклида по размеру остатка и оценка коэффициента для построения двух квадратов. В главе дополняющий квадрат проверяется отдельно; пример 4093 не взят из конспекта.
Квадратичная сумма Гаусса и модуль sqrt(p)
Слагаемые квадратичной суммы имеют единичные модули, но разные направления. Они не складываются ни в число p, ни автоматически в ноль. После умножения на комплексно сопряжённую сумму квадратичная фаза раскладывается в произведение двух независимых координат, и конечная ортогональность даёт точный квадрат модуля.
Перед началом: Комплексное сопряжение и квадрат модуля суммы; Обратимые остатки и конечная геометрическая прогрессия.
Квадратичная фаза не является обычной геометрической прогрессией
Нечётное простое p, целое a не кратно p, комплексная экспонента с положительной фазой 2πi/p.
Пусть ζ=exp(2πi/p) и G(a;p)=Σₓζ^(ax²), где x пробегает все остатки. Переход от x к x+1 меняет показатель на a(2x+1), а не на постоянное число. Поэтому формулу для суммы последовательных степеней нельзя применять к G напрямую. Повторения квадратных остатков также важны: ноль возникает один раз, каждый ненулевой квадрат — дважды.
Зато линейная сумма Σᵥζ^(bv) равна p при b≡0 и нулю иначе. В ненулевом случае знаменатель геометрической прогрессии не нулевой, а её числитель исчезает. Это точное равенство комплексных чисел, а не предположение о статистически независимых направлениях. Оно станет полезным после изменения двойной суммы.
Разность двух квадратов раскрывает ортогональность
Квадрат модуля равен Σₓ,ᵧζ^[a(x²−y²)]. Сделаем замену u=x−y,v=x+y по модулю p. Она взаимно однозначна, поскольку 2 обратимо: x=(v+u)/2,y=(v−u)/2. Получаем |G|²=ΣᵤΣᵥζ^(auv). При u=0 внутренняя сумма p; при u≠0 коэффициент au ненулевой и внутренняя сумма исчезает.
Итак, |G|²=p, следовательно |G|=√p. Нечётность нужна для указанной замены, а ненулевой a — для обратимости au. Если a≡0, все слагаемые единичные и G=p, что не соответствует формуле √p. Каждая предпосылка участвует в вычислении, поэтому её нельзя опускать даже при красивом результате.
Модуль не определяет выбранный квадратный корень
Из |G|=√p не следует G=√p как комплексное равенство. Например, сопряжение меняет a на −a, сохраняя модуль. Замена a на квадратный множитель не меняет сумму после перенумерации x, но для неквадратного множителя положение суммы может измениться. Вычисление точной фазы требует дополнительного аргумента.
Для проверки модуля удобен другой путь: посчитать, сколько пар (x,y) дают каждую разность a(x²−y²). Такой целочисленный подсчёт превращает произведение G·conj(G) в линейную комбинацию степеней ζ. После использования 1+ζ+…+ζ^(p−1)=0 остаётся целое число. Машинное сложение синусов может служить иллюстрацией, но не заменяет этот сертификат.
Девятнадцать фаз и точное число пар
Условие. Найдите модуль G=Σₓ₌₀¹⁸exp(2πi·2x²/19). Проверьте ответ подсчётом коэффициентов в G·conj(G), не определяя фазу G.
- Число 19 — нечётное простое, a=2 ненулевой остаток. Ненулевые показатели 2x² образуют набор {2,3,8,10,12,13,14,15,18}, каждый с кратностью два; нулевой показатель имеет кратность один.
- По замене u=x−y,v=x+y произведение содержит сумму ζ^(2uv) по всем 19² парам. Для u=0 получаем 19, остальные внутренние суммы нулевые. Поэтому |G|²=19.
- Независимо считаем пары с данным показателем k. При k=0 условие 2uv=0 означает u=0 или v=0, всего 19+19−1=37 пар. При любом k≠0 каждый из 18 ненулевых u определяет ровно один v, всего 18 пар.
- Следовательно, G·conj(G)=37+18(ζ+…+ζ¹⁸)=37−18=19. Неотрицательный корень даёт |G|=√19; комплексное значение самой суммы этим расчётом ещё не выбрано.
Ответ. Точный модуль равен √19. Его квадрат равен 19, хотя в исходной сумме 19 слагаемых единичной длины.
Проверка. Полный перебор 361 пары исходных x,y даёт распределение [37,18,…,18] по остаткам показателя. Это проверяет коэффициенты без использования преобразованных координат u,v.
Где легко ошибиться. Не заменяйте утверждение о модуле утверждением о положительном вещественном значении суммы. Эти два вывода имеют разную силу.
Проверьте понимание
Вопросы к этой главе
Почему нулевой показатель в произведении встречается не 19, а 37 раз?
Нулевую разность дают не только одинаковые x=y, но и x=−y. Эти две прямые по 19 точек пересекаются лишь в начале, поэтому получается 37.
Что произойдёт при коэффициенте a=19 вместо 2?
Каждый показатель кратен 19, все экспоненты равны единице и сумма равна 19. Это явный контрпример попытке убрать предпосылку о ненулевом коэффициенте.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Jim Belk, Cornell — Gauss Sums
Квадратичные суммы и различие выбора знака от значения квадрата. Здесь используется прямой двойной подсчёт экспонент; параметры 19 и 2 и распределение 361 пары получены отдельно.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как неизменный остаток запрещает достижение игрового состояния
Ищем остаток, сохраняемый разрешёнными ходами, доказываем невозможность цели без перебора маршрутов и проверяем, чего одного инварианта ещё недостаточно установить.
Открыть темуКогда у ax + by = c существуют целые решения
Находим критерий целочисленной разрешимости линейного уравнения, строим полную параметрическую серию и отдельно отбираем неотрицательные решения.
Открыть тему