11. Линейные диофантовы уравнения. Китайская теорема об остатках
Диофант Александрийский (II–III вв. н.э.) был последним великим математиком античности. До нас дошли два его сочинения — “Арифметика” (из тринадцати книг сохранилось шесть) и “О многоугольных числах” (в отрывках). Творчество Диофанта оказало большое влияние на развитие алгебры, математического анализа и теории чисел.
О жизни Диофанта известно очень мало. В Палатинской антологии сохранилась эпитафия, из которой “мудрым искусством” мы узнаем отдельные факты из жизни ученого и ее продолжительность:
Прах Диофанта гробница покоит: дивись ей — и камень
Мудрым искусством его скажет усопшего век.
Волею богов шестую часть жизни он прожил ребенком
И половину шестой встретил с пушком не щеках.
Только минула седьмая, с подругою он обручился.
С нею пять лет проведя, сына дождался мудрец.
Только полжизни отцовской сын его возлюбленный прожил,
Отнят он был у отца ранней могилой своей.
Дважды два года родитель оплакивал тяжкое горе.
Тут и увидел предел жизни печальной своей.
Пусть — целые числа,
. Рассмотрим уравнение вида
где ищем только целочисленные решения.
Определение. Уравнение такого вида называется линейным диофантовым уравнением.
Определение. Алгебраическое уравнение с целыми коэффициентами, у которого отыскиваются целые или рациональные решения, называется диофантовым.
Теорема. Уравнение (1) имеет целочисленное решение в том и только в том случае, если НОД
делит
.
Если — целочисленное решение уравнения (1), где
и
— взаимно простые числа, то любое целочисленное решение этого уравнения имеет вид
где — целое число.
Доказательство. Пусть — решение уравнения (1). Тогда
Тогда
и — решение (1) для любого целого
.
Предположим теперь, что уравнение (1) имеет какое-то решение , отличное от
. Тогда
Вычтем из второго равенства первое:
Так как числа и
взаимно просты, а
, то
, где
целое,
. А значит, и
,
.
Как найти решение уравнения (1) ?
Находим НОД
. В случае, если
, уравнение решений не имеет. Если же
, делением на
получаем уравнение
и НОД. Находим его линейное представление
Умножаем на :
. Таким образом, нашли решение
Очевидно, что решение линейных сравнений находится так же, ведь это сравнение равносильно линейному диофантову уравнению
только искать нужно , а
находить не требуется.
Теорема (Китайская теорема об остатках). Пусть и
— взаимно простые числа. Тогда для любых целых чисел
и
существует такое целое число
, что
и любые два значения , удовлетворяющие этим условиям, сравнимы по модулю
.
Доказательство. Поскольку и
— взаимно простые числа, то, по теореме о линейном представлении НОД, существуют целые числа
и
, такие, что
НОД
Отсюда
Тогда
И, значит,
Существование доказано.
Пусть теперь есть два значения и
, удовлетворяющие условиям
Тогда имеем
Отсюда, ввиду взаимной простоты чисел и
, получаем
Задачи.
1.Решить систему сравнений
2. Решить сравнение
3. Решить сравнение
1 Алексей:
Со шрифтами что-то не так. Всё очень мелко.
(Браузер Google Chrome)
[Ответить]
Елизавета Александровна Калинина Reply:
Август 26th, 2016 at 22:17
Спасибо, исправила!
[Ответить]