Задача
NT-B2-M09-P015 Произвольные остатки
#15
★★★★☆ Уровень 4 из 5
Пусть \(m_1,\ldots,m_k\) — попарно взаимно простые положительные числа, а \(r_1,\ldots,r_k\) — любые целые числа. Докажите, что существует целое \(x\), для которого \(x\equiv r_i\pmod {m_i}\) при всех \(i\).
Используйте индукцию по количеству модулей.
Для \(k=2\) это обычная CRT. Пусть утверждение верно для \(k-1\) модулей. Тогда первые \(k-1\) условий дают одно сравнение \(x\equiv r\pmod M\), где \(M=m_1\cdots m_{k-1}\). Так как \(m_k\) взаимно просто с каждым \(m_i\), имеем \(\gcd(M,m_k)=1\). По CRT система \(x\equiv r\pmod M\), \(x\equiv r_k\pmod {m_k}\) совместна. Индукция завершена.
Общая теорема нужна для сильных construction-задач.