Практика
Решите сравнение \(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}\).