Определение Множество натуральных чисел
Китайская теорема об остатках
Download 1.44 Mb.
|
Символ Лежандра
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), НОД(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-й степени с целыми коэффициентами от переменных . Уравнение вида , которое нужно решить в целых (или рациональных) числах, называется диофантовым. Следствие. Диофантово уравнение разрешимо в целых числах тогда и только тогда, когда оно разрешимо по модулю любого простого числа. Download 1.44 Mb. Do'stlaringiz bilan baham: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling