Математика · объяснение и практика
Как НОД определяет число решений линейного сравнения
Проверяем существование целых решений линейного сравнения через НОД, считаем классы по исходному модулю и восстанавливаем их после сокращения.

В теме Теория чисел: углубление · Учебная карта
Главная мысль
Сравнение ax ≡ b по модулю m разрешимо тогда и только тогда, когда d = НОД(a,m) делит b. При разрешимости оно имеет ровно d разных классов решений по исходному модулю; после сокращения получают один класс по модулю m/d.
Почему общий делитель должен делить правую часть
Сравнение можно переписать как ax−my = b для некоторого целого y. Любой общий делитель a и m делит левую часть и потому обязан делить b. Например, 6x ≡ 8 по модулю пятнадцать невозможно: НОД(6,15) равен трём, а восемь на три не делится. Этот короткий тест позволяет остановиться до перебора всех остатков.
Если условие выполнено, делят a, b и m на d. Если уменьшенный модуль m/d равен единице и условие совместности выполнено, подходит каждое целое x: отдельный обратный элемент искать не требуется. При m/d ≥ 2 у новых коэффициента и модуля НОД равен единице, поэтому коэффициент имеет обратный элемент. Полученное сравнение решается однозначно по уменьшенному модулю. Условие существования и шаг нахождения конкретного остатка — разные действия: верное значение НОД ещё не сообщает сам ответ.
Как одна короткая серия даёт несколько классов
Решим 6x ≡ 9 по модулю пятнадцать. Общая часть равна трём и делит девять. После деления получаем 2x ≡ 3 по модулю пять. Обратный к двойке равен трём, поэтому x ≡ 9 ≡ 4 по модулю пять. Все целые решения имеют вид x = 4+5k.
В пределах от нуля до четырнадцати эта серия даёт 4, 9 и 14. Они различны по исходному модулю пятнадцать, но совпадают по уменьшенному модулю пять. Поэтому фраза «одно решение» требует уточнения, по какому модулю рассматриваются классы. Целых чисел, подходящих к сравнению, при наличии решения бесконечно много; конечным является число различных остатков.
Пример
Сколько классов по модулю двенадцать имеет 8x ≡ 4?
НОД(8,12) равен четырём и делит правую часть. Значит, классов четыре. После сокращения 2x ≡ 1 по модулю три получаем x ≡ 2 по модулю три, то есть остатки 2, 5, 8 и 11 по модулю двенадцать.
Проверка решения и крайние коэффициенты
Каждый найденный остаток проверяют по исходному сравнению, особенно если промежуточный модуль менялся. Достаточно убедиться, что ax−b кратно исходному m. Проверка только сокращённого равенства без правильного изменения модуля может скрыть ошибку. Разность между соседними классами при восстановлении равна m/d, а не произвольному удобному шагу.
При a = 0 задача превращается в проверку делимости b на m. Если делимость есть, подходит любой целый x и все m классов; если нет, решений нет. Общее правило с d = m согласуется с этим результатом, но прямое рассмотрение делает смысл яснее. Модуль остаётся положительным целым, а дробные значения x не относятся к этому виду задачи.
От чтения к действию
А теперь — вы
Частые вопросы
Есть решение, если НОД не равен единице?
Да, если он делит правую часть. Тогда будет несколько разных классов по исходному модулю.
Почему нельзя назвать количество всех целых решений числом d?
При наличии одного решения обычно есть бесконечная серия целых представителей. Число d относится к различным классам остатков по исходному модулю.
Углублённый разбор
Восстановление ограниченной рациональной дроби по модульному остатку
Модульный остаток может кодировать небольшую рациональную дробь. Ограничения числителя и знаменателя превращают множество возможных дробей в единственный кандидат, если модуль достаточно велик.
Перед началом: Модульная обратная; Расширенный Евклид.
Остаток дроби требует обратимого знаменателя
Ищем несократимую дробь n/d с целым n, положительным d, |n|≤N и d≤D. Её модульное значение r означает n≡rd по модулю m. Дополнительно требуется НОД(d,m)=1, чтобы это сравнение действительно задавало r=n·d⁻¹. Само целое r не следует читать как обыкновенную дробь r/m.
Ограничения нужны заранее. Без них добавление кратного m к числителю создаёт бесконечно много различных рациональных чисел с тем же остатком. Положительность знаменателя и несократимость убирают неоднозначность записи одного рационального значения, а не неоднозначность между разными значениями.
Две малые дроби не могут различаться на кратное большого модуля
Пусть две допустимые пары дают тот же r. Тогда n₁d₂−n₂d₁ делится на m. По ограничениям его модуль не превосходит 2ND. Если 2ND<m, единственное возможное кратное m в этом диапазоне равно нулю. Значит n₁/d₁=n₂/d₂. Для несократимой записи с положительным знаменателем совпадают и обе пары.
Это утверждение гарантирует не более одного ответа, но не его существование. Если поиск не дал подходящего знаменателя либо кандидат нарушил границу, нужно сообщить отсутствие реконструкции в указанном прямоугольнике. Увеличение границ без увеличения модуля может уничтожить гарантию, хотя конкретный пример иногда всё ещё имеет один ответ.
Поиск кандидата отделяют от окончательного сертификата
При малом D можно перебрать знаменатели: для каждого d найти наименьший по абсолютной величине представитель rd и проверить границу N. Для больших задач используют коэффициенты расширенного Евклида: его остатки имеют вид sm+tr, поэтому пара остаток/коэффициент t даёт кандидата на n/d после нормализации знака.
Независимо от способа поиска готовую дробь проверяют подстановкой nd⁻¹≡r, ограничениями, взаимной простотой и несократимостью. Условие 2ND<m затем служит отдельным сертификатом единственности. Нахождение одного красивого малого отношения без этих проверок не восстанавливает скрытое точное число обоснованно.
Малый числитель после модульного вычисления
Условие. По модулю 101 получен остаток 13. Восстановите несократимую дробь n/d при |n|≤3,1≤d≤8, НОД(d,101)=1.
- Граница 2ND=2·3·8=48<101 гарантирует не более одной допустимой дроби.
- Расширенный Евклид даёт 101=7·13+10 и 13=10+3. Следовательно 3=8·13−101, то есть кандидат n=3,d=8.
- Пара несократима, знаменатель положителен и взаимно прост с 101, обе размерные границы выполнены.
- Обратный к 8 по модулю 101 равен 38:8·38=304≡1. Поэтому 3·38=114≡13, что подтверждает искомый остаток.
Ответ. Единственная допустимая дробь равна 3/8.
Проверка. Для знаменателей 1,…,8 наименьшие абсолютные остатки 13d равны 13,26,39,−49,−36,−23,−10,3. Только последний попадает в диапазон[−3,3], независимо подтверждая полноту поиска.
Где легко ошибиться. Не путайте единственность с существованием. Условие 2ND<m исключает два разных ответа, но не обещает, что произвольный остаток вообще кодирует дробь в данных границах.
Проверьте понимание
Вопросы к этой главе
Обязательно использовать простой модуль?
Нет. Достаточны обратимость выбранного знаменателя и условие на размер модуля. Простой модуль лишь упрощает проверку обратимости ненулевого знаменателя.
Можно сократить пару после поиска?
Да, но нужно заново проверить модульное представление знаменателя. Удобнее сразу выводить несократимую пару с положительным знаменателем и отдельно проверять исходное сравнение.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Victor Shoup: §4.6, Rational reconstruction
Вебом прочитаны условия и доказательство теоремы 4.8, формулировка 4.9 о расширенном Евклиде. В главе собственные ограничения, остаток и полный перебор знаменателей; примеры источника не переносились.
Восстановление допустимого модуля по наблюдаемым остаткам
Если известны результаты взятия остатков, неизвестный модуль обязан делить все соответствующие разности. НОД этих разностей даёт конечный набор кандидатов, а требование канонического остатка отсекает слишком маленькие модули.
Перед началом: Делимость; Канонический остаток.
Перенесите наблюдения в делимость
Пусть наблюдаются равенства nᵢmodm=rᵢ, где m≥2 неизвестно, а каждый rᵢ заявлен обычным неотрицательным остатком. Тогда m делит eᵢ=nᵢ−rᵢ. Если хотя бы одна разность ненулевая, любой допустимый модуль является положительным делителем G=НОД(|e₁|,…,|eₖ|).
Обратно, каждый делитель m числа G удовлетворяет всем сравнениям nᵢ≡rᵢ. Но для исходных равенств с каноническим остатком дополнительно нужны 0≤rᵢ<m. Поэтому при неотрицательных rᵢ остаётся условие m>maxrᵢ. Забыв его, мы восстановили бы только модульные сравнения, а не реальные наблюдения операции остатка.
Три результата отличаются принципиально
Если G=1, модулей m≥2 нет. Если G>1, перечисляют его делители и применяют порог по остаткам; ответ всё ещё может оказаться пустым. Наибольший делитель G не обязан быть единственным ответом. Нельзя выбирать его просто потому, что он использует всю найденную делимость.
Если все eᵢ=0, принимаем G=0. Тогда делимость не ограничивает m: каждое наблюдение утверждает, что исходное число уже совпало с остатком. При неотрицательных rᵢ подходит любой m≥2, превышающий все rᵢ. Это бесконечный набор, и попытка перечислить делители нуля не является корректной ветвью алгоритма.
Новые наблюдения сужают множество, но не всегда до одной точки
Добавление строки заменяет G наНОД(G,|e_new|) и может поднять нижний порог maxrᵢ. Значит множество допустимых модулей только уменьшается. Если новая разность кратна прежнему G и остаток невелик, наблюдение вообще не добавляет информации. Повторение похожих данных не обеспечивает идентифицируемость.
Каждый оставшийся кандидат нужно подставить в первоначальные операции, а не только проверить делимость вычисленного НОД. Такая подстановка также обнаружит ошибку ввода отрицательного остатка или перепутанную арифметическую операцию. Метод даёт логически допустимые модули для точных наблюдений и не включает модель шумных измерений.
Два умножения с неизвестным модулем
Условие. Одна система сообщает, что 8·3 при делении на m даёт канонический остаток 4, а 8·5 — остаток 0. Найдите все целые m≥2.
- Разности равны 24−4=20 и 40−0=40. Поэтому m должен делить НОД(20,40)=20.
- Делители 20, не меньшие 2:2,4,5,10,20. Первое наблюдение требует 4<m, поэтому 2 и 4 исключаются.
- Остаются 5,10,20. Для каждого 24 имеет остаток 4, а 40 делится без остатка.
- Иных модулей нет: каждый возможный уже обязан быть делителем 20 и пройти порог. Однозначно восстановить модуль по этим двум наблюдениям нельзя.
Ответ. Допустимые модули:5,10,20.
Проверка. Независимый перебор m от 2 до 40 возвращает ровно 5,10,20. Модули больше 20 исключены положительной разностью 20, которую они должны делить.
Где легко ошибиться. Равенство остатка требует r<m. Кандидат m=4 удовлетворяет сравнению 24≡4, но реальный канонический остаток 24mod4 равен 0, поэтому наблюдение он не объясняет.
Проверьте понимание
Вопросы к этой главе
Можно сразу назвать НОД найденным модулем?
Нет. НОД является верхним кандидатом, а его подходящие делители также могут объяснять данные. Для единственности нужны дополнительные ограничения или наблюдения.
Нулевой остаток делает модуль единственным?
Нет. Он сообщает делимость исходного числа. Даже несколько таких наблюдений обычно оставляют все подходящие делители их НОД, а не единственный модуль.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Victor Shoup: §2.2, Definitions and basic properties of congruences
Прочитано определение сравнения через делимость разности. Обратная задача с неизвестным модулем, ограничение канонического остатка и классификация нулевого НОД выведены в главе самостоятельно.
Полига—Хеллмана восстанавливает дискретный логарифм по разрядам порядка
Трудность дискретного логарифма зависит от разложения порядка группы. Если порядок состоит из небольших простых множителей, показатель можно узнавать по нескольким разрядам, а затем собрать китайской теоремой. В каждом разряде решается логарифм в одной маленькой группе простого порядка; большой показатель целиком не перебирается.
Перед началом: Порядок элемента и возведение в степень в конечной группе; Китайская теорема для взаимно простых модулей.
Показатель имеет независимые компоненты
Известная циклическая группа с основанием g точного порядка N, известной факторизацией N и целью h в подгруппе основания.
Запишем N=∏qᵉ по различным простым q. Нужно узнать x по модулю каждой полной степени qᵉ. Возведение g и h в степень N/qᵉ переводит задачу в подгруппу точного порядка qᵉ: равенство h=gˣ сохраняется, но показатель теперь различим лишь по этому меньшему модулю. Простые степени попарно взаимно просты, поэтому их ответы однозначно собираются по модулю N.
Точность порядка существенна. Если вместо порядка основания взять произвольное кратное, полученные малые основания могут иметь меньший порядок, и таблица разрядов перестанет быть однозначной. Принадлежность h подгруппе тоже является предпосылкой: в общей конечной группе она не следует из одной обратимости цели. В примере основание порождает всю мультипликативную группу поля.
Одна таблица узнаёт каждый разряд
Для выбранного q положим γ=g^(N/q), элемент порядка q. Пусть первые j разрядов уже дали s=d₀+d₁q+…+d_(j−1)q^(j−1). Тогда x−s делится на qʲ. Возведём h·g^(−s) в степень N/q^(j+1): старшие разряды исчезнут, и останется γ^dⱼ. Достаточно сравнить результат с таблицей 1,γ,…,γ^(q−1).
После нахождения цифры обновляем s прибавлением dⱼqʲ. Важен именно текущий s: если не удалить ранее найденные разряды из цели, следующая степень не выделит одну новую цифру. Нулевые цифры сохраняют место в записи и не означают, что обработку можно прекратить. Для каждой простой степени строится свой набор цифр.
Факторизация определяет выигрыш и его предел
Малые логарифмы порядка q можно решать перебором или большими и малыми шагами. Если у N есть крупный простой множитель, соответствующая подзадача остаётся трудной: алгоритм не делает любой дискретный логарифм дешёвым. Стоимость факторизации порядка и получение его точного значения также нельзя считать бесплатными вне заданной учебной модели.
Здесь выбираем представитель 0≤x<N, поэтому для h=1 ответ x=0. В источниках встречается соглашение с наименьшим положительным показателем, которое для единицы возвращает N. Это один и тот же класс, но разные нормированные ответы. После сборки всегда проверяют исходное gˣ=h, а не только набор сравнений на x.
Пять двоичных цифр и одна троичная
Условие. В группе ненулевых остатков по модулю 97 найдите 0≤x<96 с 5ˣ=84. Используйте 96=2⁵·3 и извлечение разрядов.
- Порядок 5 равен 96: 5⁹⁶=1, но 5⁴⁸=96 и 5³²=35 не равны единице. Для двоичных цифр γ=96, таблица имеет значения 1 и 96.
- Последовательно вычисляем (84·5^(−s))^(96/2^(j+1)). При j=0,1,2,3,4 получаем 96,1,1,96,1. Цифры равны 1,0,0,1,0; промежуточные s равны 0,1,1,1,9, а итог x≡9 по модулю 32.
- Для q=3 основание γ=5³²=35. Таблица цифр 0,1,2 равна 1,35,61. Поскольку 84³²=35, получаем x≡1 по модулю 3.
- Пишем x=9+32k. Условие по модулю 3 даёт 2k≡1, то есть k≡2. Поэтому x=73 в нужном диапазоне; прямое возведение подтверждает 5⁷³≡84.
Ответ. Искомый показатель x=73; его компоненты равны 9 по модулю 32 и 1 по модулю 3.
Проверка. Независимый полный список 96 степеней основания содержит все ненулевые остатки ровно по одному разу, и 84 стоит на позиции 73. Он проверяет порядок, принадлежность цели и уникальность итогового представителя.
Где легко ошибиться. Не извлекайте следующую цифру из исходной h без удаления уже найденного s. Малое основание γ узнаёт только один очищенный разряд.
Проверьте понимание
Вопросы к этой главе
Почему после двоичного остатка 9 ответ не может быть просто 9?
Он ещё должен удовлетворять компоненте по модулю 3. Число 9 даёт ноль, а требуется один. Среди 9,41,73 именно 73 выполняет оба условия.
Можно применить метод, когда порядок основания — большое простое число?
Формально остаётся одна компонента с одной цифрой, но её таблица имеет размер этого простого числа. Основного выигрыша от разложения тогда нет; потребуется иной алгоритм малого логарифма.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Andrew Sutherland, MIT18.783 — Lecture9, Pohlig–Hellman
Разложение логарифма по взаимно простым компонентам порядка и сведение к простым степеням. В главе используется неотрицательное соглашение для показателя.
- Burton Rosenberg, University of Miami — Pohlig–Hellman
Последовательное удаление уже найденных цифр и таблица степеней элемента простого порядка. Все остатки примера в F₉₇ пересчитаны отдельно.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Когда в сравнении по модулю можно сократить множитель
Сокращаем множитель в сравнении по модулю с проверкой НОД и понимаем, почему обычное деление обеих сторон может потерять классы решений.
Открыть темуДва остатка одновременно: совместимы ли условия
Совмещаем два условия на остатки, проверяем совместимость при общих делителях модулей и находим период полного набора решений.
Открыть тему