11. Линейные диофантовы уравнения. Китайская теорема об остатках

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

О жизни Диофанта известно очень мало. В Палатинской антологии сохранилась эпитафия, из которой “мудрым искусством” мы узнаем отдельные факты из жизни ученого и ее продолжительность:

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

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

    [ax+by=c,eqno(1)]

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

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

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

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

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

    [x=x_0+bt, y=y_0-at,]

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

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

    [ax_0+by_0=c.]

Тогда

    [a(x_0+bt)+b(y_0-at)=ax_0+abt+by_0-bat=ax_0+by_0=c,]

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

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

    [ax_0+by_0=c, ax+by=c.]

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

    [begin{array}{l} a(x-x_0)+b(y-y_0)=0\ a(x-x_0)=-b(y-y_0). end{array}]

Так как числа 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). В случае, если cnotvdots d, уравнение решений не имеет. Если же cvdots d, делением на d получаем уравнение

    [a_1x+b_1y=c_1, a=a_1d,b=b_1d,c=c_1d]

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

    [1=a_1u+b_1v.]

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

    [x_0=c_1u, y_0=c_1v.]

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

    [ax-my=b,]

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

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

    [xequiv apmod{m}, xequiv bpmod{n},]

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

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

    [1=]

НОД

    [(m,n)=mu+nv.]

Отсюда

    [muequiv1pmod{n}, nvequiv1pmod{m}.]

Тогда

    [mubequiv bpmod{n}, nvaequiv apmod{m}.]

И, значит,

    [mub+nvaequiv apmod{m}, mub+nvaequiv bpmod{n}.]

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

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

    [begin{array}{l} x_1equiv apmod{m},x_1equiv bpmod{n};\ x_2equiv apmod{m},x_2equiv bpmod{n}. end{array}]

Тогда имеем

    [x_1-x_2equiv0pmod{m}, x_1-x_2equiv0pmod{n}.]

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

    [x_1-x_2equiv0pmod{mn}.]

Задачи.

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

    [x equiv 7 pmod{8},  x equiv -1 pmod{11}.]

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

    [x^{10}+3xequiv14pmod{11}.]

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

    [x^{12}-5xequiv8pmod{13}.]

Ссылка на основную публикацию