Задача
NT-B1-M08-P021 CRT для нескольких модулей
#21
★★★★☆ Уровень 4 из 5
Пусть \(m_1,\ldots,m_s\) попарно взаимно просты. Объясните, почему система \(x\equiv a_i\pmod{m_i}\) имеет бесконечно много целых решений.
Достаточно сослаться на CRT для существования одного решения и затем прибавлять произведение модулей.
По китайской теореме об остатках существует решение \(x_0\) по модулю \(M=m_1m_2\cdots m_s\). Тогда каждое число \(x=x_0+kM\), где \(k\in\mathbb Z\), имеет те же остатки по всем модулям \(m_i\). Так как \(k\) можно выбирать бесконечно многими способами, решений бесконечно много.
Теоретическая задача на формулировку результата.