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

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

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

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

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

ax+by=c,\hskip8cm(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}<br />
a(x-x_0)+b(y-y_0)=0\\<br />
a(x-x_0)=-b(y-y_0).<br />
\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). В случае, если c\not\vdots d, уравнение решений не имеет. Если же c\vdots 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.

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

ax-my=b,

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

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

x\equiv a\pmod{m},\ x\equiv b\pmod{n},
и любые два значения x, удовлетворяющие этим условиям, сравнимы по модулю mn.

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

1=НОД(m,n)=mu+nv.

Отсюда

mu\equiv1\pmod{n},\ nv\equiv1\pmod{m}.

Тогда

mub\equiv b\pmod{n},\ nva\equiv a\pmod{m}.

И, значит,

mub+nva\equiv a\pmod{m},\ mub+nva\equiv b\pmod{n}.

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

Пусть теперь есть два значения x_1 и x_2, удовлетворяющие условиям
\begin{array}{l}<br />
x_1\equiv a\pmod{m},x_1\equiv b\pmod{n};\\<br />
x_2\equiv a\pmod{m},x_2\equiv b\pmod{n}.<br />
\end{array}
Тогда имеем

x_1-x_2\equiv0\pmod{m},\ x_1-x_2\equiv0\pmod{n}.

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

x_1-x_2\equiv0\pmod{mn}.

Задачи.

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

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

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

x^{10}+3x\equiv14\pmod{11}.

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

x^{12}-5x\equiv8\pmod{13}.

Комментариев: 2

  1. 1 Алексей:

    Со шрифтами что-то не так. Всё очень мелко.
    (Браузер Google Chrome)

    [Ответить]

    Елизавета Александровна Калинина Reply:

    Спасибо, исправила!

    [Ответить]

Оставьте свой отзыв

Добавить изображение