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


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


Download 1.44 Mb.
bet6/9
Sana02.06.2024
Hajmi1.44 Mb.
#1837140
TuriЗакон
1   2   3   4   5   6   7   8   9
Bog'liq
Символ Лежандра

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 и х0 a1(mod m1), х0 а2(mod т2),..., х0 ar (mod mr)
Доказательство. Докажем теорему для r=2. Пусть х a1(mod m1), х а2(mod т2), НОД(m12) = 1.
Пусть x0 — решение первого сравнения, то есть для некоторого целого числа и. Найдем такое и, чтобы х0 было решением и второго сравнения. Подставляем выражение для х0 во второе сравнение: . Получаем сравнение первой степени относительно неизвестного и. Числа m1 и т2 вза­имно просты, поэтому по теореме 2.5 это сравнение имеет единственное решение. Найдем его по теореме Эйлера:

или

для некоторого целого v.
Подставляем найденное решение в выражение для х0:
,
то есть
. (2.4)

Упражнение. Доказать теорему в общем случае методом мате­матической индукции, используя доказанное утверждение в качестве базы индукции.
Замечание. Приведем выражение (2.4) к симметричному виду.
Для этого сначала покажем, что . Действительно, так как числа m1, т2взаимно просты, можем применить к ним
теорему Эйлера: , то есть разность делится на т2. Но точно так же , , то есть разность делится на m1. Тогда выражение делится на m1m2.
Раскроем скобки в формуле (2.4) и воспользуемся только что доказанным соотношением:
.
или, в другой записи,
.
В общем случае получаем целочисленный аналог интерполяционной формулы Лагранжа:

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


Download 1.44 Mb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8   9




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling