Глава
Теория
Линейное сравнение \(ax\equiv b\pmod m\) похоже на линейное уравнение, но делить в нем можно не всегда. Главный вопрос: совместим ли коэффициент \(a\) с модулем \(m\)?
Если \(\gcd(a,m)=1\), у \(a\) есть обратный элемент по модулю \(m\). Если \(\gcd(a,m)>1\), сравнение может не иметь решений или иметь несколько классов решений.
Если условие звучит как "число дает такие-то остатки", сразу записывайте систему сравнений. Если встречается \(ax\equiv b\pmod m\), сначала вычислите \(\gcd(a,m)\), а не пытайтесь делить на \(a\).
Для систем с не взаимно простыми модулями сначала проверьте совместимость по общему делителю модулей.
Примеры
Если коэффициент взаимно прост с модулем, его можно обратить.
Задача. Решите \(3x\equiv5\pmod7\).
Обратный к \(3\) по модулю \(7\) равен \(5\), потому что \(3\cdot5\equiv1\). Умножаем: \(x\equiv5\cdot5=25\equiv4\pmod7\).
Комментарий. Это корректная замена деления.
Перед делением смотрим на НОД.
Задача. Решите \(6x\equiv5\pmod9\).
\(\gcd(6,9)=3\), но \(3\nmid5\). Значит, сравнение не имеет решений.
Комментарий. Одна проверка НОД сразу закрывает задачу.
Если общий делитель делит правую часть, решений будет несколько.
Задача. Решите \(6x\equiv12\pmod{18}\).
Делим \(6,12,18\) на \(6\): \(x\equiv2\pmod3\). По модулю \(18\) это дает \(x\equiv2,5,8,11,14,17\pmod{18}\).
Комментарий. Модуль изменился: это главное место ошибки.
Для взаимно простых модулей решение единственно по модулю произведения.
Задача. Решите систему \(x\equiv2\pmod3\), \(x\equiv3\pmod5\).
Числа \(2,5,8,11,\ldots\) имеют остаток \(2\) по модулю \(3\). Среди них \(8\equiv3\pmod5\). Значит, \(x\equiv8\pmod{15}\).
Комментарий. Можно решать перебором одного класса.
Не взаимно простые модули требуют проверки по общему делителю.
Задача. Докажите, что система \(x\equiv2\pmod6\), \(x\equiv3\pmod9\) не имеет решений.
Если \(x\equiv2\pmod6\), то \(x\equiv2\pmod3\). Если \(x\equiv3\pmod9\), то \(x\equiv0\pmod3\). Одно число не может иметь два разных остатка по модулю \(3\). Решений нет.
Комментарий. Это совместимость по \(\gcd(6,9)=3\).
Если остатки согласованы по общему делителю, систему можно решать.
Задача. Решите \(x\equiv4\pmod6\), \(x\equiv10\pmod{15}\).
Оба остатка дают \(1\) по модулю \(3\), значит, совместимость есть. Пусть \(x=6k+4\). Тогда \(6k+4\equiv10\pmod{15}\), то есть \(6k\equiv6\pmod{15}\). Делим на \(3\): \(2k\equiv2\pmod5\), откуда \(k\equiv1\pmod5\). Значит, \(x\equiv10\pmod{30}\).
Комментарий. Ответ записан по модулю \(\operatorname{lcm}(6,15)=30\).
Иногда задача уже содержит скрытое противоречие.
Задача. Найдите все \(x\pmod{84}\), для которых \(x\equiv2\pmod3\), \(x\equiv3\pmod7\), \(x\equiv4\pmod{12}\).
Из \(x\equiv4\pmod{12}\) следует \(x\equiv1\pmod3\). Но первое условие требует \(x\equiv2\pmod3\). Противоречие, решений нет.
Комментарий. Сначала проверяем совместимость, потом считаем.
Переменный делитель можно заставить делить маленькое число.
Задача. Найдите все положительные \(n\), для которых \(2n+1\mid n^2+n+7\).
Если \(2n+1\mid n^2+n+7\), то он делит \(4(n^2+n+7)=(2n+1)^2+27\). Значит, \(2n+1\mid27\). Так как \(n>0\), \(2n+1\in\{3,9,27\}\). Получаем \(n=1,4,13\), и все три значения подходят.
Комментарий. Это не прямое сравнение, но оно приводит к линейному ограничению.
Задачи
Решите сравнение \(x+3\equiv1\pmod7\).
Вычтите \(3\) из обеих частей.
\(x\equiv1-3\equiv-2\equiv5\pmod7\).
Решите \(3x\equiv1\pmod7\).
Найдите число, которое при умножении на \(3\) дает \(1\) по модулю \(7\).
\(3\cdot5=15\equiv1\pmod7\). Значит, \(x\equiv5\pmod7\).
Найдите обратный элемент к \(5\) по модулю \(12\).
Проверьте \(5\cdot5\).
\(5\cdot5=25\equiv1\pmod{12}\). Поэтому обратный элемент к \(5\) по модулю \(12\) равен \(5\).
Решите систему \(x\equiv2\pmod3\), \(x\equiv1\pmod5\).
Переберите числа \(2,5,8,11,\ldots\).
Числа, равные \(2\) по модулю \(3\): \(2,5,8,11,\ldots\). Из них \(11\equiv1\pmod5\). Значит, \(x\equiv11\pmod{15}\).
Докажите, что сравнение \(2x\equiv1\pmod4\) не имеет решений.
Левая часть всегда четна.
Число \(2x\) четно, значит, по модулю \(4\) оно может иметь остаток \(0\) или \(2\). Остаток \(1\) невозможен. Также \(\gcd(2,4)=2\nmid1\), поэтому решений нет.
Решите \(4x\equiv6\pmod{10}\).
Разделите \(4,6,10\) на их общий делитель \(2\).
\(\gcd(4,10)=2\), и \(2\mid6\). Делим на \(2\): \(2x\equiv3\pmod5\). Обратный к \(2\) по модулю \(5\) равен \(3\), значит, \(x\equiv9\equiv4\pmod5\). По модулю \(10\): \(x\equiv4\) или \(9\).
Решите \(6x\equiv12\pmod{18}\).
После сокращения получится модуль \(3\).
Делим \(6,12,18\) на \(6\): \(x\equiv2\pmod3\). По модулю \(18\) это классы \(2,5,8,11,14,17\).
Решите \(9x\equiv6\pmod{15}\).
Сократите на \(\gcd(9,15)=3\).
Получаем \(3x\equiv2\pmod5\). Обратный к \(3\) по модулю \(5\) равен \(2\), поэтому \(x\equiv4\pmod5\). По модулю \(15\): \(x\equiv4,9,14\).
Решите систему \(x\equiv3\pmod4\), \(x\equiv2\pmod5\).
Переберите числа \(3,7,11,15,19,\ldots\).
Из чисел \(3,7,11,15,19,\ldots\), сравнимых с \(3\) по модулю \(4\), число \(7\) имеет остаток \(2\) по модулю \(5\). Ответ: \(x\equiv7\pmod{20}\).
Докажите, что система \(x\equiv2\pmod6\), \(x\equiv3\pmod9\) не имеет решений.
Сравните оба условия по модулю \(3\).
Первое условие дает \(x\equiv2\pmod3\). Второе дает \(x\equiv0\pmod3\). Это невозможно одновременно. Решений нет.
Решите систему \(x\equiv4\pmod6\), \(x\equiv1\pmod9\).
Пусть \(x=6k+4\).
Подставим: \(6k+4\equiv1\pmod9\), значит, \(6k\equiv6\pmod9\). Делим на \(3\): \(2k\equiv2\pmod3\), откуда \(k\equiv1\pmod3\). Тогда \(x=6(3t+1)+4=18t+10\). Ответ: \(x\equiv10\pmod{18}\).
Найдите наименьшее положительное число, которое дает остаток \(2\) при делении на \(5\) и остаток \(3\) при делении на \(7\).
Проверьте числа \(2,7,12,17,\ldots\).
Числа вида \(5k+2\): \(2,7,12,17,\ldots\). Первое из них, дающее остаток \(3\) по модулю \(7\), это \(17\). Ответ: \(17\).
Докажите, что сравнение \(ax\equiv b\pmod m\) имеет решение тогда и только тогда, когда \(\gcd(a,m)\mid b\).
Перепишите сравнение как \(ax-b=my\).
Сравнение эквивалентно уравнению \(ax-my=b\) в целых \(x,y\). Все числа вида \(ax-my\) делятся на \(d=\gcd(a,m)\), значит, необходимо \(d\mid b\). Обратно, если \(d\mid b\), то по тождеству Безу существуют \(u,v\), для которых \(au+mv=d\). Умножив на \(\frac bd\), получаем представление \(b\) в виде \(aX+mY\), то есть решение сравнения.
Найдите все положительные \(n\), для которых \(2n+1\mid n^2+n+7\).
Умножьте выражение на \(4\).
Если \(2n+1\mid n^2+n+7\), то \(2n+1\mid4(n^2+n+7)\). Но \(4(n^2+n+7)=(2n+1)^2+27\). Значит, \(2n+1\mid27\). Для положительного \(n\): \(2n+1=3,9,27\), откуда \(n=1,4,13\). Все три подходят.
Найдите все \(x\pmod{84}\), для которых \(x\equiv2\pmod3\), \(x\equiv3\pmod7\), \(x\equiv4\pmod{12}\).
Сравните первое и третье условия по модулю \(3\).
Из \(x\equiv4\pmod{12}\) следует \(x\equiv1\pmod3\). Но первое условие требует \(x\equiv2\pmod3\). Противоречие. Следовательно, решений нет.
Решите систему \(x\equiv5\pmod8\), \(x\equiv2\pmod9\), \(x\equiv1\pmod5\).
Сначала объедините первые два сравнения.
Пусть \(x=8a+5\). Условие modulo \(9\): \(8a+5\equiv2\), то есть \(-a\equiv-3\), \(a\equiv3\pmod9\). Значит, \(x\equiv29\pmod{72}\). Теперь \(x=29+72t\), и по модулю \(5\): \(4+2t\equiv1\), откуда \(2t\equiv2\), \(t\equiv1\pmod5\). Получаем \(x\equiv101\pmod{360}\).
Найдите все \(x\pmod{60}\), для которых \(4x\equiv8\pmod{12}\) и \(x\equiv3\pmod5\).
Сначала решите \(4x\equiv8\pmod{12}\).
Сравнение \(4x\equiv8\pmod{12}\) после деления на \(4\) дает \(x\equiv2\pmod3\). Совмещаем с \(x\equiv3\pmod5\). Числа \(3,8,13,\ldots\) по модулю \(5\); число \(8\equiv2\pmod3\). Значит, \(x\equiv8\pmod{15}\). По модулю \(60\) получаем \(x\equiv8,23,38,53\).
Найдите наименьшее положительное \(n\), такое что \(n\equiv1\pmod2\), \(n\equiv2\pmod3\), \(n\equiv3\pmod5\).
Сначала объедините условия по модулям \(2\) и \(3\).
Условия \(n\equiv1\pmod2\), \(n\equiv2\pmod3\) дают \(n\equiv5\pmod6\). Проверяем \(5,11,17,23,\ldots\); первое число, сравнимое с \(3\) по модулю \(5\), это \(23\). Ответ: \(23\).
Найдите все решения \(12x\equiv18\pmod{30}\).
\(\gcd(12,30)=6\).
Так как \(6\mid18\), делим на \(6\): \(2x\equiv3\pmod5\). Обратный к \(2\) по модулю \(5\) равен \(3\), поэтому \(x\equiv9\equiv4\pmod5\). По модулю \(30\): \(x\equiv4,9,14,19,24,29\).
Найдите все \(x\pmod{100}\), для которых \(x\equiv3\pmod4\) и \(x\equiv7\pmod{25}\).
Проверьте число \(7\).
Число \(7\) дает остаток \(3\) по модулю \(4\) и остаток \(7\) по модулю \(25\). Так как \(4\) и \(25\) взаимно просты, решение единственно по модулю \(100\). Ответ: \(x\equiv7\pmod{100}\).
Докажите: система \(x\equiv r\pmod m\), \(x\equiv s\pmod n\) имеет решение тогда и только тогда, когда \(r\equiv s\pmod{\gcd(m,n)}\).
Необходимость следует из того, что \(x-r\) делится на \(m\), а \(x-s\) делится на \(n\). Для достаточности сведите к линейному сравнению.
Пусть \(d=\gcd(m,n)\). Если решение \(x\) есть, то \(x-r\) делится на \(m\), а \(x-s\) делится на \(n\), значит, оба делятся на \(d\). Тогда \(r-s=(x-s)-(x-r)\) делится на \(d\).
Обратно, пусть \(d\mid r-s\). Ищем \(x=r+mk\). Нужно \(r+mk\equiv s\pmod n\), то есть \(mk\equiv s-r\pmod n\). Это линейное сравнение имеет решение ровно потому, что \(\gcd(m,n)=d\mid s-r\). Значит, исходная система совместна.
Найдите все положительные \(n\), для которых \(3n+2\mid n^2+5n+9\).
Заставьте \(3n+2\) делить константу.
Если \(3n+2\mid n^2+5n+9\), то он делит \(9(n^2+5n+9)=9n^2+45n+81\). Вычтем \((3n+2)^2=9n^2+12n+4\): получим, что \(3n+2\mid33n+77\). Теперь \(3(33n+77)-33(3n+2)=165\), значит, \(3n+2\mid165\). Положительные делители \(165\), сравнимые с \(2\) по модулю \(3\): \(5\) и \(11\). Поэтому \(3n+2=5\) или \(11\), откуда \(n=1\) или \(3\). Проверка показывает, что оба подходят.
Найдите наименьшее положительное \(n\), такое что \(n\equiv-1\pmod2\), \(n\equiv-1\pmod3\), \(n\equiv-1\pmod5\), но \(n\equiv0\pmod7\).
Первые три условия означают \(n\equiv-1\pmod{30}\).
Первые три условия дают \(n\equiv29\pmod{30}\). Пусть \(n=7k\). Тогда \(7k\equiv29\pmod{30}\). Обратный к \(7\) по модулю \(30\) равен \(13\), поэтому \(k\equiv29\cdot13\equiv17\pmod{30}\). Наименьшее положительное \(k=17\), значит, \(n=119\).
Найдите все \(x\pmod{420}\), удовлетворяющие условиям \(x\equiv1\pmod4\), \(x\equiv2\pmod5\), \(x\equiv3\pmod7\), \(6x\equiv12\pmod9\).
Сначала решите последнее линейное сравнение.
Сравнение \(6x\equiv12\pmod9\) сокращаем на \(3\): \(2x\equiv4\pmod3\), то есть \(-x\equiv1\pmod3\), значит, \(x\equiv2\pmod3\). Теперь решаем систему по взаимно простым модулям \(3,4,5,7\): \(x\equiv2\pmod3\), \(x\equiv1\pmod4\), \(x\equiv2\pmod5\), \(x\equiv3\pmod7\).
Совмещаем \(x\equiv1\pmod4\) и \(x\equiv2\pmod5\): получаем \(x\equiv17\pmod{20}\). Это число уже дает \(17\equiv2\pmod3\) и \(17\equiv3\pmod7\). Так как модули \(3,4,5,7\) взаимно просты, ответ единственен по модулю \(420\): \(x\equiv17\pmod{420}\).
Лестницы