Задача
NT-B1-M04-P023 Минус один и ноль
#23
★★★★☆ Уровень 4 из 5
Найдите наименьшее положительное \(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\).
Конструктивная задача, ведущая к будущему CRT-модулю.