Обратимые остатки, сравнения, квадратичные вычеты, проверка простоты и уравнения в целых числах. Разобранные задачи и практика.
Задачи модуля
НОД показывает, когда деление в остатках допустимо, а когда сокращение меняет модуль и число классов. Начнём с сохранения общих делителей в алгоритме Евклида и перейдём к условию существования обратного элемента.
Затем решим линейное сравнение и совместим два условия, в том числе с невзаимно простыми модулями. Инструменты проверяют НОД и два сравнения; обратный элемент и все классы линейного сравнения нужно дополнительно подтвердить подстановкой.
Разные задачи используют разные свойства целых чисел: существование обратного элемента, структуру группы остатков, делимость коэффициентов и приближение иррациональных чисел. Метод выбирают по условию, а найденный ответ проверяют в исходном сравнении или уравнении.
Проверять существование обратного элемента по условию взаимной простоты.
Определять разрешимость и число классов линейного сравнения.
Согласовывать два остатка и записывать все решения с периодом НОК модулей.
Отличать конструкцию решения, свидетельство составности и сертификат простоты.
Арифметика сравнений
Линейное сравнение без обратного коэффициента
Отсутствие обратного элемента у коэффициента не означает отсутствия решения. Сначала проверяют общий делитель коэффициента и модуля; он одновременно определяет совместность и число классов ответа.
Перед началом: НОД; Сравнения по модулю.
Преобразуйте сравнение в целое равенство
Сравнение ax≡b по модулю m означает ax−my=b для некоторого целого y. Любая левая часть делится на d=НОД(a,m), поэтому d обязан делить b. Обратно, тождество Безу позволяет построить решение при выполнении этого условия. Это критерий существования, который работает до попытки искать обратный элемент. Модуль считаем положительным; особый случай m=1 содержит единственный класс остатков.
Сокращение меняет модуль
Если d делит b, делим a,b,m на d. Новый коэффициент a/d уже взаимно прост с m/d, поэтому имеет обратный элемент. Решение сокращённого сравнения задаётся одним классом x₀ по модулю m/d. В исходном модуле он распадается на d различных классов x₀+k(m/d), где k=0,…,d−1. Делить только коэффициенты, сохраняя старый модуль, нельзя: это теряет часть решений или создаёт неверное условие.
Посчитайте классы и проверьте представителя
Достаточно подставить общий вид ответа и показать, что соседние представители различаются на период m/d, но не совпадают по модулю m до полного цикла из d шагов. Так доказываются и правильность, и полнота списка. Для малого модуля независимый контроль даёт перебор всех остатков. В больших задачах полезно сохранить также коэффициенты Безу, чтобы обратимость сокращённого коэффициента можно было проверить одним умножением.
Период m/d можно увидеть непосредственно: при замене x на x+m/d левая часть увеличивается на a·m/d, кратное m, поскольку a делится на d. Это подтверждает повторяемость найденного класса без вычисления обратного элемента. Но для полноты ещё нужно доказать, что меньшая разность любых двух решений кратна этому периоду. Такое утверждение следует после сокращения из взаимной простоты a/d и m/d, а не только из предъявления нескольких примеров.
Два решения вместо одного
Условие. Решите 14x≡8 по модулю 30.
НОД(14,30)=2 делит 8, поэтому решения существуют.
Сокращаем до 7x≡4 по модулю 15.
Обратный к 7 равен 13, потому что 7·13=91≡1. Значит x≡52≡7 по модулю 15.
В модуле 30 получаем два класса: 7 и 22.
Ответ. x≡7 или x≡22 по модулю 30.
Проверка. 14·7=98 и 14·22=308 оба дают остаток 8; полный перебор тридцати остатков не добавляет решений.
Где легко ошибиться. Сокращение сравнения на общий делитель одновременно уменьшает модуль. Обычное деление равенства без этого шага неверно.
Проверьте понимание
Вопросы к этой главе
Что если НОД не делит правую часть?
Решений нет, потому что разность ax−my всегда кратна этому НОД.
Почему решений ровно d?
Один класс по меньшему модулю m/d имеет ровно d различных представителей среди m исходных остатков.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
§2.3, теорема 2.5: критерий НОД и класс по сокращённому модулю. Проверены релевантные определения и условия, а не прочитан весь учебник. Условия задач и расчёты главы подготовлены отдельно.
Обобщённая КТО: совместность при общих делителях
Два модульных условия могут быть совместны и без взаимной простоты модулей. Но общая часть модулей должна требовать один и тот же остаток, а период ответа становится наименьшим общим кратным.
Перед началом: Линейные сравнения; Наименьшее общее кратное.
Сравните требования на общей части
Пусть x≡a по модулю m и x≡b по модулю n. Любое решение даёт a−b, кратное d=НОД(m,n). Это необходимое условие совместности. Оно также достаточно. При взаимно простых модулях d=1 условие выполняется автоматически, что и даёт привычную формулировку китайской теоремы об остатках. При общих делителях проверку нельзя пропускать даже при очень маленьких остатках.
Одна подстановка сводит задачу к сравнению
Запишите x=a+mt. Тогда mt≡b−a по модулю n. После деления на d получается сравнение с обратимым коэффициентом m/d по модулю n/d. Решив его для t, восстанавливают x. Период изменения t равен n/d, поэтому период x равен mn/d, то есть НОК(m,n). Именно этот период, а не произведение модулей, описывает один полный класс совместных решений.
Разделите существование и единственность класса
Совместная система имеет бесконечно много целых решений, но ровно один класс по модулю НОК. Если два решения x и y удовлетворяют обоим условиям, их разность кратна и m, и n, следовательно, кратна НОК. Это доказывает полноту найденного класса независимо от способа вычисления. При объединении многих сравнений их можно сливать попарно, на каждом шаге сохраняя текущий остаток, модуль и свидетельство совместности.
В примере совместимость проверяется также по модулю шесть: оба остатка 5 и 11 дают один остаток 5. Если они различались бы на общей части, никакой выбор большого x не исправил бы противоречие. Это полезно в задачах восстановления по нескольким измерениям: сначала проверяют согласованность общих периодов, затем ищут конкретное число. Большой восстановленный представитель не является доказательством единственности без указания итогового модуля.
Общие делители не мешают
Условие. Решите x≡5 по модулю 12 и x≡11 по модулю 18.
НОД(12,18)=6; разность 11−5=6 кратна 6.
Подставляем x=5+12t: 12t≡6 по модулю 18.
После сокращения 2t≡1 по модулю 3, поэтому t≡2 по модулю 3.
Получаем x=29+36k; период 36 равен НОК(12,18).
Ответ. x≡29 по модулю 36.
Проверка. 29 даёт остатки 5 и 11; среди 0,…,35 других совместных остатков нет. Замена второго остатка на 10 сделала бы систему несовместной.
Где легко ошибиться. Произведение модулей при невзаимной простоте является лишним большим периодом и может скрыть несколько повторяющихся представителей одного класса.
Проверьте понимание
Вопросы к этой главе
Почему проверяется разность остатков?
Обе записи одного x при вычитании выражают эту разность как целую комбинацию модулей, кратную их НОД.
Можно ли менять порядок слияния?
Да, математический набор решений одинаков. Но на каждом промежуточном шаге нужно правильно обновлять модуль до НОК.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
§§2.3–2.4: линейные сравнения и китайская теорема; совместность общих делителей выведена через линейное сравнение. Проверены релевантные определения и условия, а не прочитан весь учебник. Условия задач и расчёты главы подготовлены отдельно.
Порядок элемента: период короче функции Эйлера
Теорема Эйлера даёт общий показатель, но конкретный элемент может возвращаться к единице раньше. Точный порядок позволяет сокращать огромные степени и одновременно проверять полноту найденного периода.
Перед началом: Умножение остатков; Функция Эйлера.
Период существует только у обратимого элемента
Для НОД(a,m)=1 степени a образуют конечную циклическую подгруппу обратимых остатков. Наименьшее положительное d с aᵈ≡1 называется порядком. Любой показатель возврата к единице кратен d: деление показателя с остатком сводит доказательство к минимальности d. Если a не обратим, возвращения к единице может вообще не быть. Тогда применение функции Эйлера без проверки НОД не имеет основания.
Сокращайте кандидата по простым делителям
Порядок делит число элементов группы, поэтому можно начать с φ(m). Если кандидат D разложен на простые множители, проверяют a^(D/p). При результате 1 кандидат уменьшают в p раз и продолжают. Если проверка не прошла, соответствующее сокращение невозможно. Такой процесс требует модульного возведения в степень, а не построения самого огромного целого числа. Для доказательства точности d достаточно aᵈ=1 и неравенств a^(d/p)≠1 для всех простых p, делящих d.
Точный порядок нужен для корректного сокращения
После нахождения d показатель k заменяют остатком k mod d. Это не означает, что само основание можно заменить произвольным числом с тем же порядком: разные циклические подгруппы и фазы дают разные остатки. Для малого модуля список последовательных степеней служит независимой проверкой. В криптографических задачах важен размер группы, но здесь вычисляется только арифметический период заданного элемента; стойкость какой-либо системы из такого примера не следует.
При отрицательном показателе сначала нужен обратный элемент, а затем тот же период. Для необратимого основания отрицательная степень вообще не определена в группе остатков. Поэтому выражение «сократить любой показатель» относится к целым показателям только после фиксации групповой области и допустимости обратного элемента.
Большой показатель в маленькой группе
Условие. Найдите порядок 3 по модулю 13 и остаток 3²⁰²⁶.
3²=9, 3³=27≡1 по модулю 13.
3≠1, а делители 3 только 1 и 3, поэтому точный порядок равен 3.
2026=3·675+1; показатель сокращается до 1.
Следовательно, 3²⁰²⁶≡3. Проверка быстрым модульным возведением не требует вычисления числа 3²⁰²⁶ целиком.
Ответ. Порядок 3; остаток большой степени равен 3.
Проверка. Цикл степеней равен 1,3,9,1. Он имеет длину 3, хотя φ(13)=12.
Где легко ошибиться. Теорема Эйлера требует взаимной простоты основания и модуля; без неё сокращение по φ(m) может дать неверный остаток.
Проверьте понимание
Вопросы к этой главе
Порядок всегда равен φ(m)?
Нет. Он только делит φ(m); в примере период в четыре раза короче общего показателя.
Почему проверяют только простые делители кандидата?
Любой собственный делитель d убирает хотя бы один простой множитель, поэтому такая проверка обнаруживает возможность дальнейшего сокращения.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
§6.5: циклические группы и порядок элемента; конечный период проверен независимо. Проверены релевантные определения и условия, а не прочитан весь учебник. Условия задач и расчёты главы подготовлены отдельно.
Квадратный корень по модулю: единственность подъёма не универсальна
Корень сравнения по простому модулю можно искать на следующем уровне в виде r+pt. Один линейный шаг объясняет как единственность регулярного подъёма, так и ветвление при нулевой производной.
Перед началом: Сравнения; Разложение квадрата.
Раскройте квадрат только до нужного модуля
Пусть r²≡a по модулю простого p. Любой остаток по модулю p², продолжающий r, имеет вид r+pt с t=0,…,p−1. Его квадрат равен r²+2rpt+p²t². Последнее слагаемое исчезает по модулю p². Поскольку r²−a уже кратно p, деление условия на p даёт линейное сравнение (r²−a)/p+2rt≡0 по модулю p. Так нелинейная задача следующего уровня становится конечной линейной.
Ненулевая производная даёт один выбор
Если 2r не делится на p, коэффициент t обратим и продолжение единственно. Это частный случай подъёма Гензеля. При 2r≡0 возможны два исхода: свободный член тоже нулевой, и тогда подходят все p значений t, либо он ненулевой, и не подходит ни одно. Поэтому утверждение «каждый корень поднимается единственным образом» требует регулярности. Для p=2 квадратный пример особенно часто попадает в исключительный случай.
Проверьте полноту через исходные классы
Каждый корень по модулю p² при сокращении по p обязательно даёт исходный корень. Следовательно, достаточно перебрать подъёмы всех исходных корней; новых классов из ниоткуда появиться не может. Это удобная структура доказательства полноты. На малом модуле независимый полный перебор подтверждает список. Для больших степеней процедуру повторяют, каждый раз контролируя делимость и коэффициент производной на соответствующем уровне.
Число корней на следующем уровне не обязано совпадать с числом корней исходного сравнения. Регулярный случай сохраняет каждый отдельный корень единственным образом, а особый может дать разветвление или исчезновение. Поэтому сначала перечисляют исходные классы и для каждого отдельно решают линейное условие подъёма. Смешение этих ветвей способно пропустить часть ответа даже при правильной формуле разложения квадрата.
Два корня на следующем уровне
Условие. Решите x²≡4 по модулю 25 через корни по модулю 5.
По модулю 5 корни равны r=2 и r=3.
Для r=2 условие становится 4t≡0, значит t=0 и x=2.
Для r=3 имеем (9−4)/5+6t≡1+t≡0 по модулю 5; t=4.
Второй корень x=3+5·4=23. Другие корни невозможны, потому что должны продолжать 2 или 3.
Ответ. Корни по модулю 25: 2 и 23.
Проверка. 2²=4, 23²=529≡4. Для контраста корень 0 у x²≡0 mod5 имеет пять подъёмов mod25: 0,5,10,15,20.
Где легко ошибиться. Нельзя делить на производную, если она не обратима по рассматриваемому простому модулю.
Проверьте понимание
Вопросы к этой главе
Почему в разложении исчезает t²?
Он умножен на p², поэтому не влияет на остаток по модулю p².
Что показывает пример x²≡0?
При нулевой производной подъём может разветвляться; регулярная единственность здесь не применима.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
Раздел о модульных квадратных корнях и Hensel lifting, печатные страницы 351–352; особый случай производной показан отдельно. Проверены релевантные определения и условия, а не прочитан весь учебник. Условия задач и расчёты главы подготовлены отдельно.
Связанные методы
Как алгоритм Евклида сохраняет общий делитель
Алгоритм Евклида заменяет пару положительных целых чисел парой «меньшее число и остаток от деления». Общие делители при такой замене не меняются. Когда остаток становится нулём, предыдущий ненулевой остаток является искомым наибольшим общим делителем.
Обратный элемент по модулю: условие существования и проверка
Обратный к a по модулю m ≥ 2 — такой целый остаток u, что au ≡ 1 по модулю m. Он существует тогда и только тогда, когда НОД(a,m) = 1. Это не обычное действительное число 1/a, а класс целых чисел.
Как НОД определяет число решений линейного сравнения
Сравнение ax ≡ b по модулю m разрешимо тогда и только тогда, когда d = НОД(a,m) делит b. При разрешимости оно имеет ровно d разных классов решений по исходному модулю; после сокращения получают один класс по модулю m/d.
Можно, но обычно удобнее сначала разделить большее на меньшее. При обратном порядке первое частное будет нулём, а следующая пара всё равно поменяет порядок.
Может число быть обратным самому себе?
Да. Например, 5·5 оставляет остаток один по модулю двенадцать. Условие касается произведения, а не различия двух чисел.
Есть решение, если НОД не равен единице?
Да, если он делит правую часть. Тогда будет несколько разных классов по исходному модулю.
Сохранять историю слов и ошибок в этом браузере? О cookies