Определение Множество натуральных чисел

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-й степени с целыми коэффициентами от переменных . Уравнение вида , которое нужно решить в целых (или рациональных) числах, называется диофантовым.
Следствие. Диофантово уравнение разрешимо в целых числах тогда и только тогда, когда оно разрешимо по модулю любого простого числа.