Задача
NT-B2-M09-P018 Избежать конечного набора остатков
#18
★★★★★ Уровень 5 из 5
Пусть заданы попарно взаимно простые модули \(m_1,\ldots,m_k\), и для каждого \(i\) запрещён один остаток \(a_i\pmod {m_i}\). Докажите, что существует бесконечно много целых \(x\), которые не сравнимы с \(a_i\) по модулю \(m_i\) ни при одном \(i\).
Выберите для каждого модуля разрешённый остаток \(b_i\ne a_i\).
Так как \(m_i>1\), можно выбрать остаток \(b_i\), отличный от \(a_i\) по модулю \(m_i\). По CRT существует \(x_0\), такое что \(x_0\equiv b_i\pmod {m_i}\) для всех \(i\). Тогда все числа \(x=x_0+tM\), где \(M=m_1\cdots m_k\), имеют те же остатки по всем модулям. Следовательно, они избегают всех запрещённых классов, и таких чисел бесконечно много.
Хорошая задача на CRT как инструмент выбора, а не только делимости.