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

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

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

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

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

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

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

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

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

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

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

Тогда

и x=x_0+bt,\ y=y_0-at — решение (1) для любого целого t.

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

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

Так как числа a и b взаимно просты, а a(x-x_0)\vdots b, то x-x_0=bn, где n целое, x=x_0+bn. А значит, и y-y_0=-an, y=y_0-an.

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

Находим d=НОД(a,b). В случае, если c\not\vdots d, уравнение решений не имеет. Если же c\vdots d, делением на d получаем уравнение

и НОД(a_1,b_1)=1. Находим его линейное представление

Умножаем на c_1: c_1=ac_1u+bc_1v. Таким образом, нашли решение

Очевидно, что решение линейных сравнений ax\equiv b\pmod{m} находится так же, ведь это сравнение равносильно линейному диофантовому уравнению

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

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

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

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

НОД

Отсюда

Тогда

И, значит,

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

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

Тогда имеем

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

Задачи.

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

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

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