Математика · объяснение и практика
Два остатка одновременно: совместимы ли условия
Совмещаем два условия на остатки, проверяем совместимость при общих делителях модулей и находим период полного набора решений.

В теме Теория чисел: углубление · Учебная карта
Главная мысль
Для x ≡ a по модулю m и x ≡ b по модулю n совместимость требует НОД(m,n), делящего b−a. При выполнении условия решения образуют один класс по модулю НОК(m,n). Взаимно простые модули гарантируют совместимость любых остатков.
Два расписания должны согласоваться на общей части
Если число имеет заданные остатки по двум модулям, то его разности с a и b кратны соответственно m и n. Общий делитель этих модулей делит обе разности и потому должен делить b−a. Например, остатки один по модулю шесть и два по модулю девять несовместимы: общий делитель три не делит их разность один.
Это условие также достаточно. Подставим x = a+mk во второе сравнение: получим mk ≡ b−a по модулю n. По критерию линейного сравнения оно разрешимо именно при указанной делимости. Таким образом, проверка общего делителя не просто отсекает некоторые плохие случаи, а полностью отвечает на вопрос о существовании совместного остатка.
Как найти один ответ и весь период
Рассмотрим x ≡ 2 по модулю шесть и x ≡ 5 по модулю девять. Подставим x = 2+6k. Получаем 6k ≡ 3 по модулю девять, после сокращения 2k ≡ 1 по модулю три. Подходит k ≡ 2 по модулю три. Поэтому x = 14+18t при любом целом t.
Период восемнадцать равен наименьшему общему кратному шести и девяти. Он сохраняет оба условия одновременно. Произведение модулей пятьдесят четыре тоже сохраняло бы остатки, но пропустило бы другие решения, если использовать только одну серию с таким шагом. Минимальный общий период зависит от общих делителей, а не всегда равен произведению.
Пример
Совместите x ≡ 1 по модулю четыре и x ≡ 3 по модулю пять.
Модули взаимно просты. Среди 1, 5, 9, 13, 17 по модулю двадцать подходит 13, поскольку его остаток по модулю пять равен трём. Все решения: x = 13+20k.
Что обещает китайская теорема
Для взаимно простых положительных модулей любой набор остатков определяет единственный класс по их произведению. Единственность относится к классу, а не к одному целому числу: прибавление периода даёт бесконечно много представителей. Если задача ограничивает промежуток, после нахождения класса отдельно выбирают находящиеся в нём числа.
При невзаимно простых модулях нельзя автоматически объявлять отсутствие решения или использовать произведение как полный единственный шаг. Сначала проверяют совместимость, затем используют НОК. В задачах о повторяющихся событиях также важно, что остатки описывают одну и ту же начальную шкалу отсчёта. Разные начала времени нужно привести к общей системе до применения арифметического критерия.
От чтения к действию
А теперь — вы
Частые вопросы
Общий делитель модулей всегда мешает?
Нет. Он требует согласования остатков: их разность должна делиться на этот общий делитель.
Ответ представляет только одно число?
Обычно это целый класс с общим периодом. Единственное число появляется после дополнительного ограничения диапазона или выбора стандартного представителя.
Углублённый разбор
Идемпотенты CRT независимо включают остатки
Китайская теорема об остатках задаёт не только способ собрать число. В кольце по произведению взаимно простых модулей существуют ненулевые проекторы, которые независимо сохраняют одну компоненту и обнуляют другую.
Перед началом: Классы вычетов; Китайская теорема.
Базисные классы ведут себя как переключатели
Пусть m,n>1 взаимно просты, M=mn. Выберем e₁, имеющий остатки(1,0), и e₂ с остатками(0,1) по модулям m,n. Их можно построить как n·n⁻¹modm и m·m⁻¹modn, понимая каждое выражение в кольце по M. По компонентам сразу видно e₁+e₂=1 и e₁e₂=0.
Кроме того, e₁²=e₁ и e₂²=e₂: повторное включение той же компоненты ничего не меняет. Такое равенство называется идемпотентностью. Любой класс x разлагается как xe₁+xe₂. Умножение на e₁ сохраняет первую компоненту x и стирает вторую, поэтому этот класс действует как алгебраический проектор.
Проекторы обнаруживают делители нуля
Оба проектора ненулевые, но их произведение нулевое. Следовательно, кольцо по составному произведению содержит делители нуля и не является полем. Сокращение в равенстве e₁e₂=0 по ненулевому e₁ не разрешено: ненулевой элемент здесь не обязательно обратим. Это структурный вывод, который нельзя получить одним подсчётом количества классов.
При простых m,n любой идемпотент имеет в каждой компоненте только 0 или 1, поскольку в поле y(y−1)=0. Получаются ровно четыре идемпотента. Для составных взаимно простых компонент их может быть больше: утверждение о четырёх требует простоты, хотя построение двух проекторов её не требует.
Разложение сохраняет арифметику компонент
Если x имеет компоненты(a,b), то x=ae₁+be₂ по модулю M. При умножении двух разложений перекрёстные члены исчезают из-за e₁e₂=0, а квадрат каждого проектора заменяется им самим. Поэтому арифметика распадается на две независимые операции меньших колец.
Разложение не даёт обычного равенства выбранных целых представителей: все тождества выполняются по модулю M. Проверять их нужно остатком разности. Например, сумма представителей проекторов может быть M+1, а не 1. Это не нарушение разложения единицы, а следствие выбора канонических представителей.
Все проекторы по модулю тридцать пять
Условие. Постройте два компонентных проектора для модулей 5 и 7, найдите все идемпотенты по модулю 35 и покажите, почему ненулевое сокращение здесь опасно.
- Для первой компоненты e₁=7·3=21, поскольку 7·3≡1 по модулю 5. Для второй e₂=5·3=15, поскольку 5·3≡1 по модулю 7.
- Имеем 21²−21=420,15²−15=210 и 21·15=315. Все три числа делятся на 35, а 21+15=36≡1.
- Поля по 5 и 7 допускают в идемпотенте только компоненты 0 или 1. Четыре комбинации дают классы 0,21,15,1.
- В частности, 21 и 15 ненулевые, но их произведение равно 0 по модулю 35. Сокращение на 21 ошибочно превратило бы это равенство в ложное 15=0.
Ответ. Проекторы 21 и 15; все идемпотенты:0,1,15,21.
Проверка. Перебор x=0,…,34 находит ровно эти четыре решения x²≡x. Также НОД(21,35)=7 иНОД(15,35)=5, поэтому оба ненулевых проектора необратимы.
Где легко ошибиться. Ненулевой проектор не является единицей кольца. Равенство произведения нулю не позволяет сократить его так же, как ненулевой множитель в поле.
Проверьте понимание
Вопросы к этой главе
Почему для двух простых модулей решений четыре?
В каждой полевой компоненте идемпотент выбирает одно из двух значений. Независимость компонент даёт 2·2 комбинации, каждая соответствует ровно одному классу по произведению.
Связаны ли проекторы с линейными проекциями?
Да: повторное применение оставляет результат неизменным. Здесь это оператор умножения в кольце, который выделяет компоненту системы остатков; геометрическая ортогональность не предполагается.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Victor Shoup: §2.4 и §4.3, Chinese remaindering
Вебом прочитаны условия попарной взаимной простоты, формула базисных eᵢ в теореме 4.6 и упражнения 4.14–4.15 об инкрементальном восстановлении. Идемпотенты и треугольная схема малых разрядов главы доказаны отдельно; оригинальная статья Гарнера по найденному PDF не прочитана из-за таймаута.
Смешанные разряды Гарнера
Систему взаимно простых остатков можно переводить в смешанную позиционную запись. Треугольные поправки Гарнера вычисляют малые разряды по отдельным модулям, отделяя их от сборки большого целого результата.
Перед началом: Модульная обратная; Попарно взаимно простые модули.
Веса разрядов образуют вложенную запись
Для модулей m₁,…,mₖищем запись x=c₁+m₁c₂+m₁m₂c₃+…с границами 0≤cᵢ<mᵢ. Первое сравнение сразу даёт c₁=r₁. После вычитания c₁ и деления на m₁ все остальные сравнения превращаются в условия на следующий хвост. Деление выполняется умножением на обратный класс, существующий благодаря взаимной простоте.
Такое представление единственно на диапазоне 0≤x<M, где M — произведение модулей. Действительно, сравнение по m₁ фиксирует первый разряд, затем остаток от обычного целого деления на m₁ фиксирует второй и так далее. Сам порядок модулей важен для разрядов, хотя восстановленный класс x от перестановки входных условий не меняется.
Попарные обратные делают проход треугольным
Заранее найдём inv[j,i]=mⱼ⁻¹по модулю mᵢ для всех j<i. Для вычисления cᵢ начинаем с t=rᵢ и последовательно выполняем t←(t−cⱼ)inv[j,i]modmᵢ при j=1,…,i−1. После каждого шага снят один внешний уровень вложенной записи. В конце t равен нужному разряду cᵢ.
Каждое промежуточное t можно хранить по небольшому модулю mᵢ. Само большое произведение M не нужно внутри треугольного прохода. При многократном восстановлении с фиксированными модулями таблица обратных переиспользуется. Подготовка и один проход имеют квадратичное число малых операций по количеству модулей; это не обещает превосходства над любым другим алгоритмом CRT.
Большое число появляется только на отдельном этапе
Готовые разряды собирают схемой Горнера: начинают с последнего cₖи последовательно умножают на предыдущий модуль и добавляют предыдущий разряд. Здесь размер числа растёт, поэтому отсутствие больших промежуточных произведений при вычислении разрядов не отменяет потребность в достаточной разрядности результата.
Если модули имеют общий делитель, попарная обратная может не существовать. Это не означает автоматической несовместимости исходной системы, но описанная схема уже неприменима: нужна обобщённая проверка совместимости. Также нельзя считать найденные cᵢ исходными остатками rᵢ: разряды относятся к вложенным хвостам, а не к самому x.
Три малых разряда
Условие. Восстановите 0≤x<385 по остаткам x≡4(mod5),x≡3(mod7),x≡9(mod11), используя смешанные разряды в порядке 5,7,11.
- Первый разряд c₁=4. По модулю 7 обратный к 5 равен 3, поэтому c₂=(3−4)·3≡4.
- Для третьего начинаем t=9. Обратный к 5 по модулю 11 равен 9: t=(9−4)·9≡1.
- Обратный к 7 по модулю 11 равен 8. Следующий треугольный шаг даёт c₃=(1−4)·8≡9.
- Собираем x=4+5·4+35·9=339. Разряды(4,4,9) лежат в своих диапазонах, результат меньше 385.
Ответ. Смешанные разряды(4,4,9), восстановленное x=339.
Проверка. Прямые деления дают 339mod5=4,339mod7=3,339mod11=9. Перебор 0,…,384 находит единственный такой класс, независимо от треугольного вычисления разрядов.
Где легко ошибиться. Промежуточный t нужно нормализовать по текущему mᵢ после каждого снятия уровня. Готовые разряды отличаются от исходных остатков и зависят от выбранного порядка модулей.
Проверьте понимание
Вопросы к этой главе
Почему можно заранее хранить попарные обратные?
Они зависят только от модулей, а не от конкретных остатков. Для серии задач с той же системой модулей таблица остаётся одной и той же.
Можно получить только один нужный разряд?
Разряд cᵢ зависит от всех предыдущих cⱼ, поэтому их всё равно нужно вычислить. Сборку полного большого x можно отложить, если потребителю достаточно самой смешанной записи.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Victor Shoup: §2.4 и §4.3, Chinese remaindering
Вебом прочитаны условия попарной взаимной простоты, формула базисных eᵢ в теореме 4.6 и упражнения 4.14–4.15 об инкрементальном восстановлении. Идемпотенты и треугольная схема малых разрядов главы доказаны отдельно; оригинальная статья Гарнера по найденному PDF не прочитана из-за таймаута.
NTT-свёртка: точные коэффициенты и граница однозначного восстановления
Преобразование по корням единицы можно выполнить целиком в конечном поле, без ошибок комплексного округления. Оно даёт свёртку коэффициентов по простому модулю. Чтобы назвать результат точным целым произведением, дополнительно нужны достаточная длина дополнения нулями и строгая граница величины коэффициентов.
Перед началом: Полиномиальное произведение и свёртка; Порядок элемента по простому модулю.
Корень нужного порядка обеспечивает обратимость
Выберем простой p и длину N, делящую p−1. Элемент ω должен иметь точный порядок N. Преобразование Â_k=Σ_(j=0)^(N−1)a_jω^(jk) вычисляется в поле F_p. Обратная формула использует ω⁻¹ и множитель N⁻¹ mod p. Простота p и делимость p−1 гарантируют, что N не обращается в нуль в поле.
Доказательство обратимости опирается на конечную геометрическую сумму Σ_kω^(k(j−l)): она равна N при j=l mod N и нулю иначе. Если выбрать элемент меньшего порядка, столбцы преобразования начнут совпадать. Поэтому одного равенства ωᴺ=1 недостаточно — требуется именно полный порядок.
Дополнение нулями отделяет линейную свёртку от циклической
Покомпонентное умножение преобразований и обратное преобразование дают циклическую свёртку длины N. Для обычного произведения массивов длин n и m требуется N≥n+m−1: тогда старшие коэффициенты не заворачиваются в младшие. В используемой лаборатории N выбирается минимальной подходящей степенью двойки для алгоритма radix-2.
Фиксированное поле имеет p=998244353=119·2²³+1 и первообразный корень 3. Для N=8 подходит ω=3^((p−1)/8)=372528824. Значение ω⁴=−1 и ω⁸=1 подтверждает точный порядок восемь. Конкретный учебный движок ограничивает длины входов и не пытается работать с произвольным размером, допустимым для всего поля.
Целое восстановление требует строгого запаса
Каждый коэффициент линейной свёртки содержит не более min(n,m) произведений. Поэтому B=min(n,m)·max|a_j|·max|b_j| является общей границей его модуля. Если 2B<p, единственный представитель в симметричном диапазоне восстанавливается из остатка: большие остатки трактуют как отрицательные числа после вычитания p.
Без этой границы NTT остаётся точным вычислением по модулю, но не однозначным восстановлением целого коэффициента. Числа c и c+p имеют один остаток. Лаборатория показывает модульные и восстановленные коэффициенты отдельно, а также длину и границу, чтобы смысл результата можно было проверить по исходным данным.
Шесть коэффициентов через преобразование длины восемь
Условие. Перемножьте A(x)=3−2x+x³ и B(x)=−1+4x−3x² с помощью лаборатории NTT. Обоснуйте длину и возможность точного знакового восстановления.
- Длины массивов равны четырём и трём, поэтому произведение имеет шесть коэффициентов. Минимальная степень двойки не меньше шести равна восьми.
- Вычисляем границу B=3·3·4=36. Строгое условие 72<998244353 выполнено с большим запасом, поэтому модульные результаты однозначно задают целые коэффициенты.
- После прямых преобразований, покомпонентного умножения и обратного преобразования первые шесть остатков равны p−3, 14, p−17, 5, 4, p−3. Последние два равны нулю.
- Знаковое восстановление даёт (−3,14,−17,5,4,−3). Значит, произведение равно −3+14x−17x²+5x³+4x⁴−3x⁵.
- Независимая школьная свёртка подтверждает каждую позицию. Например, кубический коэффициент равен (−2)(−3)+1·(−1)=5. При x=1 сумма коэффициентов −3+14−17+5+4−3=0 совпадает с A(1)B(1)=2·0=0.
Ответ. Коэффициенты произведения: (−3,14,−17,5,4,−3). Используется N=8 и доказанная граница |c_k|≤36<p/2.
Проверка. Полная школьная свёртка, нулевая сумма коэффициентов при x=1 и произведение значений при x=−1 независимо контролируют результат, не полагаясь на обратимость реализации NTT.
Где легко ошибиться. Не смешивайте точность арифметики по модулю с точностью целого восстановления. Без 2B<p один и тот же остаток может соответствовать нескольким допустимым целым значениям.
Точная целочисленная свёртка через NTT
Два непустых списка до 16 целых коэффициентов, каждый по модулю до 1000, от постоянного члена вверх. Простой модуль 998244353. Знаковое восстановление разрешено только при доказанной границе коэффициента строго меньше половины модуля. Это линейная свёртка с дополнением нулями.
Проверьте понимание
Вопросы к этой главе
Почему нельзя взять длину четыре?
Коэффициенты степеней четыре и пять завернутся в нулевую и первую позиции циклической свёртки. Получится другой объект, даже если все операции в поле выполнены без ошибок.
Почему лаборатория не выбирает длину шесть?
В ней реализовано двоичное разбиение radix-2, поэтому допустимы степени двойки. Длина восемь — минимальная такая длина, покрывающая шесть выходных коэффициентов.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- AtCoder Library: convolution
Прочитаны определение линейной свёртки по модулю, требование простого модуля и доступной степени двойки в m−1. Граница знакового целого восстановления, ортогональность и конкретные массивы выведены отдельно; обычная modular convolution не выдаётся за безусловное целое восстановление.
Рациональное восстановление по одному большому остатку
Модульный алгоритм иногда вычисляет остаток рационального ответа, а не целое число. Тогда представитель r сам по себе не является нужным числителем: он кодирует a·b⁻¹. Ограничения числителя и знаменателя позволяют найти исходную дробь расширенным алгоритмом Евклида, причём достаточно большой модуль даёт строгую гарантию единственности.
Перед началом: Расширенный алгоритм Евклида; Обратимый знаменатель и сокращённая дробь.
Вместо одного остатка ищем маленькую пару
Целый модуль m>1, остаток r и искомая сокращённая дробь a/b с b>0, gcd(b,m)=1, |a|≤A, b≤B.
Равенство a/b≡r по модулю m означает a≡rb, то есть a=sm+rb для некоторого целого s. Это условие линейно по двум неизвестным a,b, хотя искомый ответ рационален. Знаменатель должен быть обратим по модулю: без этого запись b⁻¹ не определена, даже если само сравнение a≡rb имеет решения.
Ограничения |a|≤A и 1≤b≤B являются частью задачи восстановления. Без них каждый остаток кодирует множество разных рациональных чисел. Результат приводят к несократимому виду с положительным знаменателем; для нулевого числителя нормальная форма 0/1. Одни и те же рациональные числа не следует считать разными ответами из-за общего множителя пары.
Почему строгого неравенства достаточно для единственности
Пусть две допустимые пары удовлетворяют a≡rb и a′≡rb′. Вычитание после перемножения даёт ab′−a′b≡0 по модулю m. Но абсолютная величина этой разности не больше 2AB. Если 2AB<m, единственное кратное m в таком диапазоне — ноль. Значит дроби равны; после нормировки совпадают и пары.
Это гарантия не более одного ответа, а не доказательство существования для произвольного r. При маленьком модуле разные дроби могут столкнуться. Даже равенство на границе недостаточно: при m=10,A=5,B=1 числа 5 и −5 оба дают остаток 5. Поэтому строгий знак нельзя заменять нестрогим на основании удачного отдельного примера.
Евклид одновременно уменьшает остаток и хранит знаменатель
Запустим расширенный Евклид для m и нормированного r. Каждая строка хранит остаток Rᵢ=Sᵢm+Tᵢr. Первый остаток, не превосходящий A, даёт кандидата Rᵢ/Tᵢ. Если исходная ограниченная дробь существует и 2AB<m, теорема восстановления гарантирует подходящий размер коэффициента Tᵢ. Знак пары исправляют вместе, затем сокращают.
В реализации всё равно проверяют полученные границы, ненулевой знаменатель, его обратимость и исходное сравнение. Неудачный кандидат не превращается в приблизительный ответ. Метод используется после точных модульных вычислений, где известны оценки размеров истинного результата; десятичное округление и восстановление дроби из измеренного вещественного значения — другая задача с иной моделью ошибки.
Положительный остаток скрывает отрицательную дробь
Условие. Модульное вычисление дало r=87 по модулю 1009. Известно |a|≤20, 1≤b≤25 и обратимость b. Восстановите сокращённую дробь a/b.
- Проверяем 2AB=2·20·25=1000<1009. Если подходящая дробь найдётся, она будет единственной в заданном прямоугольнике ограничений.
- Евклид даёт 1009=11·87+52, 87=52+35, 52=35+17. Последний остаток впервые не превосходит 20.
- Сопровождающие коэффициенты при 87 равны 1,−11,12,−23. Для последней строки имеем 17=2·1009−23·87, то есть кандидат 17/(−23).
- Нормируем знак: a/b=−17/23. Дробь сокращена, 23≤25 и gcd(23,1009)=1. Обратная проверка 87·23+17=2018=2·1009 выполняется точно.
Ответ. Единственная допустимая дробь равна −17/23. Сам положительный остаток 87 не передаёт знак исходной рациональной величины.
Проверка. Полный независимый перебор всех 25 знаменателей и 41 допустимого числителя оставляет одну сокращённую пару (−17,23). Умножение на обратный к 23 по модулю 1009 также возвращает остаток 87.
Где легко ошибиться. Проверка a≡rb не заменяет ограничений и обратимости знаменателя. Без них можно принять постороннюю дробь, которая случайно имеет тот же модульный образ.
Проверьте понимание
Вопросы к этой главе
Можно увеличить модуль, просто записав тот же r по большему m?
Нет. Остаток надо заново получить вычислением по новому модулю либо согласованно объединить дополнительные модульные результаты. Старое число 87 не содержит автоматически новой информации.
Если 2AB≥m, восстановление всегда невозможно?
Не обязательно. Конкретный набор может иметь один ответ, но приведённое доказательство единственности уже не действует. Тогда нужна отдельная проверка кандидатов или более сильная информация о результате.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Victor Shoup — A Computational Introduction, §4.6, теоремы 4.7–4.8
Ограниченное рациональное восстановление, строгий критерий единственности и остановка расширенного Евклида. Остаток, пределы и полный проверочный перебор главы выбраны независимо.
Подъём Гензеля для двух взаимно простых множителей
Разложение по маленькому простому модулю не обязано оставаться верным по его квадрату. Вместо нового поиска факторов можно исправить каждый множитель на величину, кратную p. После деления ошибки на p задача становится линейной над конечным полем, а взаимная простота обеспечивает обратимость нужной операции.
Перед началом: Деление многочленов и тождество Безу над полем; Покоэффициентное сравнение по целому модулю.
Ошибка произведения определяет линейную поправку
Монический целый многочлен f и два монических взаимно простых множителя g,h его редукции по простому p; один шаг до p².
Выберем целые представители g,h, для которых f−gh делится покоэффициентно на p, и положим E=(f−gh)/p. Ищем G=g+pu,H=h+pv. Раскрытие произведения даёт GH=gh+p(uh+vg)+p²uv. Поэтому достаточно решить uh+vg≡E по модулю p. Это равенство многочленов, а не проверка лишь в нескольких значениях x.
Чтобы сохранить моничность и степени, требуем deg u<deg g и deg v<deg h. При моническом f нужной степени deg E<deg g+deg h. Старшие коэффициенты факторов тогда не меняются. Без ограничений степеней можно перераспределять кратные g,h между поправками и получать разные записи одного исправленного произведения.
Безу выделяет поправки и доказывает единственность
Поскольку gcd(g,h)=1 над F_p, многочлен h обратим по модулю g. Найдём t с th≡1(mod g), затем u=остаток(tE при делении на g). После этого E−uh делится на g; его частное задаёт v по модулю p. Степенная граница на E и u обеспечивает нужную границу степени v.
Для единственности вычтем две пары решений. Тогда Δu·h+Δv·g=0 над полем. Сокращение по g показывает g|Δu, поскольку h обратим. Но deg Δu<deg g, значит Δu=0, а затем Δv=0. Здесь взаимная простота — действующее условие, а не формальная подпись перед алгоритмом.
Поднятые факторы ещё относятся к выбранному модулю
Проверка результата состоит из двух частей: G,H сокращаются к исходным g,h по p, а произведение совпадает с f по p². Это не равенство в Z[x]. Чтобы восстановить целочисленные факторы, нужны дальнейший подъём, оценки коэффициентов и отдельная проверка точного деления. Нельзя объявлять найденные остатки окончательной факторизацией над рациональными числами.
Если исходные факторы имеют общий делитель, поправка может отсутствовать или быть неоднозначной. Например, для g=h=x по модулю 5 и f=x²+5 требуется x(u+v)=1, что невозможно. Для f=x², напротив, пары x+5a и x−5a дают то же произведение по 25 при любом a. Одна удачная поправка в особом случае не восстанавливает общую теорему единственности.
Два квадратичных фактора поднимаются вместе
Условие. Для f=x⁴+16x³+3x²+2x+2 по модулю 5 даны g=x²+x+1 и h=x²+2. Найдите монические G,H тех же степеней по модулю 25.
- Произведение gh=x⁴+x³+3x²+2x+2, поэтому E=(f−gh)/5=3x³. Тождество (2x+4)h−(2x+2)g=6 даёт обратимость h по модулю g над F₅.
- По модулю g имеем x³≡1, значит E≡3. Умножение на 2x+4 даёт u≡x+2. Это уже представитель степени меньше двух.
- Из uh+vg≡E получаем v=2x+1 над F₅. Следовательно, G=g+5u=x²+6x+11, H=h+5v=x²+10x+7.
- Обычное произведение GH=x⁴+16x³+78x²+152x+77. Разность с f равна 75x²+150x+75=25·3(x+1)², поэтому требуемое покоэффициентное сравнение выполнено.
Ответ. По модулю 25 подходят G=x²+6x+11 и H=x²+10x+7. Поправки u=x+2,v=2x+1 единственны над F₅ при заданных степенях.
Проверка. Независимый перебор всех 5⁴ пар линейных поправок оставляет ровно одну допустимую четвёрку коэффициентов. Проверка только значений при пяти остатках x здесь была бы слабее проверки всех коэффициентов.
Где легко ошибиться. Нельзя проверять сравнение многочленов только подстановкой всех элементов F_p: разные многочлены могут задавать одну функцию. Сравнивайте коэффициенты после раскрытия произведения.
Проверьте понимание
Вопросы к этой главе
Почему нельзя поднять только g и оставить h неизменным?
Вообще ошибка E не обязана быть кратна h над полем. В примере ненулевая поправка v нужна: один член uh не совпадает со всем E. Совместная линейная задача распределяет ошибку между обоими факторами.
Нужно заново находить разложение f по модулю 25 полным перебором?
Нет. Исходная взаимно простая пара и тождество Безу задают единственную линейную поправку. Перебор 625 вариантов здесь используется лишь как независимый малый контроль, а не как основной способ.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Marc Moreno Maza, Western University — Hensel Lifting
Условия взаимной простоты, линейная поправка к факторизации и сохранение степеней. Покоэффициентный вывод и пара квадратичных факторов главы рассчитаны независимо.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как НОД определяет число решений линейного сравнения
Проверяем существование целых решений линейного сравнения через НОД, считаем классы по исходному модулю и восстанавливаем их после сокращения.
Открыть темуОбратный элемент по модулю: условие существования и проверка
Находим обратный множитель по модулю, проверяем условие взаимной простоты и отличаем обратный остаток от обычной дроби.
Открыть тему