2.2.2. Китайская теорема об остатках

Рассмотрим систему сравнений первой степени:

хa₁(mod m₁), ха₂(mod т₂),..., хa_r, (mod m_r,), (2.3)

где числа m₁т₂, .... т_r попарно взаимно простые, и найдем значение x₀, удовлетворяющее всем r сравнениям.

Теорема 2.6(китайская теорема об остатках). Пусть числа m₁т₂, .... т_r попарно взаимно простые и числа a₁a₂, .... a_r, произвольные целые. Тогда существует такое целое число x₀, что 0≤x₀<m₁т₂ .... т_r и х₀a₁(mod m₁), х₀а₂(mod т₂),..., х₀a_r (mod m_r)

Доказательство. Докажем теорему для r=2. Пусть хa₁(mod m₁), ха₂(mod т₂), НОД(m₁,т₂) = 1.

Пусть x₀ — решение первого сравнения, то есть для некоторого целого числа и. Найдем такое и, чтобы х₀ было решением и второго сравнения. Подставляем выражение для х₀ во второе сравнение: . Получаем сравнение первой степениотносительно неизвестногои. Числа m₁ и т₂ вза­имно просты, поэтому по теореме 2.5 это сравнение имеет единственное решение. Найдем его по теореме Эйлера:

или

для некоторого целого v.

Подставляем найденное решение в выражение для х₀:

,

то есть

. (2.4)

□

Упражнение. Доказать теорему в общем случае методом мате­матической индукции, используя доказанное утверждение в качестве базы индукции.

Замечание. Приведем выражение (2.4) к симметричному виду. Для этого сначала покажем, что . Действительно, так как числаm₁, т₂взаимно просты, можем применить к ним теорему Эйлера:, то есть разность делится нат₂. Но точно так же, , то есть разностьделится наm₁. Тогда выражение делится наm₁m₂.

Раскроем скобки в формуле (2.4) и воспользуемся только что доказанным соотношением:

.

или, в другой записи,

.

В общем случае получаем целочисленный аналог интерполяционной формулы Лагранжа:

где и

Определение2.4. Пусть — полином n-й степени с целыми коэффициентами от переменных . Уравнение вида , которое нужно решить в целых (или рациональных) числах, называетсядиофантовым.

Следствие. Диофантово уравнение разрешимо в целых числах тогда и только тогда, когда оно разрешимо по модулю любого простого числа.