Математика, которая мне нравится

Диофант Александрийский (II–III вв. н.э.) был последним великим математиком античности. До нас дошли два его сочинения — “Арифметика” (из тринадцати книг сохранилось шесть) и “О многоугольных числах” (в отрывках). Творчество Диофанта оказало большое влияние на развитие алгебры, математического анализа и теории чисел.

Прах Диофанта гробница покоит: дивись ей — и камень
Мудрым искусством его скажет усопшего век.
Волею богов шестую часть жизни он прожил ребенком
И половину шестой встретил с пушком не щеках.
Только минула седьмая, с подругою он обручился.
С нею пять лет проведя, сына дождался мудрец.
Только полжизни отцовской сын его возлюбленный прожил,
Отнят он был у отца ранней могилой своей.
Дважды два года родитель оплакивал тяжкое горе.
Тут и увидел предел жизни печальной своей.

Пусть — целые числа, . Рассмотрим уравнение вида

где ищем только целочисленные решения.

Определение. Уравнение такого вида называется линейным диофантовым уравнением.

Определение. Алгебраическое уравнение с целыми коэффициентами, у которого отыскиваются целые или рациональные решения, называется диофантовым.

Теорема. Уравнение (1) имеет целочисленное решение в том и только в том случае, если НОД делит .

Если — целочисленное решение уравнения (1), где и — взаимно простые числа, то любое целочисленное решение этого уравнения имеет вид

где — целое число.

Доказательство. Пусть — решение уравнения (1). Тогда

Тогда

и — решение (1) для любого целого .

Предположим теперь, что уравнение (1) имеет какое-то решение , отличное от . Тогда

Вычтем из второго равенства первое:

Так как числа и взаимно просты, а , то , где целое, . А значит, и , .

Как найти решение уравнения (1) ?

Находим НОД. В случае, если , уравнение решений не имеет. Если же , делением на получаем уравнение

и НОД. Находим его линейное представление

Умножаем на : . Таким образом, нашли решение

Очевидно, что решение линейных сравнений находится так же, ведь это сравнение равносильно линейному диофантовому уравнению

только искать нужно , а   находить не требуется.

Теорема (Китайская теорема об остатках). Пусть и — взаимно простые числа. Тогда для любых целых чисел и существует такое целое число , что

и любые два значения , удовлетворяющие этим условиям, сравнимы по модулю .

Доказательство . Поскольку и — взаимно простые числа, то, по теореме о линейном представлении НОД, существуют целые числа и , такие, что

НОД

Отсюда

Тогда

И, значит,

Существование доказано.

Пусть теперь есть два значения и , удовлетворяющие условиям

Тогда имеем

Отсюда, ввиду взаимной простоты чисел и , получаем

Задачи.

1.Решить систему сравнений

2. Решить сравнение

3. Решить сравнение