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

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

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

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

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

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

$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)$ . В случае, если $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} x_1\equiv a\pmod{m},x_1\equiv b\pmod{n};\\ x_2\equiv a\pmod{m},x_2\equiv b\pmod{n}. \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}.$

Комментарии (RSS) | Трекбек

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

1 Алексей:

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

[Ответить]
Елизавета Александровна Калинина Reply:
Август 26th, 2016 at 22:17
Спасибо, исправила!

[Ответить]
7 Август 2016, 20:21

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

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

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

1 Алексей:

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

Навигация по сайту

Разделы

Новые комментарии

Хороший книжный магазин

Подписка на обновления сайта

Твиттер