2.2.2. Китайская теорема об остатках
Рассмотрим систему сравнений первой степени:
хa1(mod m1), ха2(mod т2),..., хar, (mod mr,), (2.3)
где числа m1т2, .... тr попарно взаимно простые, и найдем значение x0, удовлетворяющее всем r сравнениям.
Теорема 2.6(китайская теорема об остатках). Пусть числа m1т2, .... тr попарно взаимно простые и числа a1a2, .... ar, произвольные целые. Тогда существует такое целое число x0, что 0≤x0<m1т2 .... тr и х0a1(mod m1), х0а2(mod т2),..., х0ar (mod mr)
Доказательство. Докажем теорему для r=2. Пусть хa1(mod m1), ха2(mod т2), НОД(m1,т2) = 1.
Пусть x0 — решение первого сравнения, то есть для некоторого целого числа и. Найдем такое и, чтобы х0 было решением и второго сравнения. Подставляем выражение для х0 во второе сравнение: . Получаем сравнение первой степениотносительно неизвестногои. Числа m1 и т2 взаимно просты, поэтому по теореме 2.5 это сравнение имеет единственное решение. Найдем его по теореме Эйлера:
или
для некоторого целого v.
Подставляем найденное решение в выражение для х0:
,
то есть
. (2.4)
□
Упражнение. Доказать теорему в общем случае методом математической индукции, используя доказанное утверждение в качестве базы индукции.
Замечание. Приведем выражение (2.4) к симметричному виду. Для этого сначала покажем, что . Действительно, так как числаm1, т2взаимно просты, можем применить к ним теорему Эйлера:, то есть разность делится нат2. Но точно так же, , то есть разностьделится наm1. Тогда выражение делится наm1m2.
Раскроем скобки в формуле (2.4) и воспользуемся только что доказанным соотношением:
.
или, в другой записи,
.
В общем случае получаем целочисленный аналог интерполяционной формулы Лагранжа:
где и
Определение2.4. Пусть — полином n-й степени с целыми коэффициентами от переменных . Уравнение вида , которое нужно решить в целых (или рациональных) числах, называетсядиофантовым.
Следствие. Диофантово уравнение разрешимо в целых числах тогда и только тогда, когда оно разрешимо по модулю любого простого числа.
- 1.2. Наибольший общий делитель н наименьшее общее кратное
- 1.3. Вычисление наибольшего общего делителя
- 1.3.1. Алгоритм Евклида
- 1.4. Простые числа
- 1.4.2. Распределение простых чисел
- Глава 2 сравнения с одним неизвестным
- 2.1. Отношение сравнимости
- 2.2. Решение сравнений
- 2.2.1 Сравнения первой степени
- 2.2.2. Китайская теорема об остатках
- 2.2.3. Сравнения произвольной степени по простому модулю
- 2.3. Сравнения второй степени
- 2.3.1. Символы Лежандра и Якоби
- Решение сравнений для случаев простого модуля.
- Случаи составного модуля