Этому виду задач более 1600 лет

38

Этому виду задач более 1600 лет

Б. А. Кордемский

Менялась фабула и форма записи задачи, накапливались способы решения, но суть оставалась неизменной: найти целые (чаще натуральные) $x$ и $y$, удовлемворюшение уравнения
$$ax + by = c$$
(1)
с. заданных целыми коэффициентами $a$, $b$ и $c$.

Может быть, $c$ — это 1001 сказка Шехерезды, а нас интересует, сколько ночей потребуется Шехерезде, чтобы рассказыть все свои сказки, если $x$ ночей она будет рассказывать по 5 сказок, а остальные сказки по 3 за $y$ ночей.

Сказочные, очевидно, потребуется $x+y$ ночей, где $x$ и $y$ — натуральные корни уравнения $5x+3y=1001$.

А может быть, $c$ — это 10 $p$. 01 $\kappa$., которые некоют израсходовал на $x$ поездок автовусом (по 5 копеек за рейс) и $y$ поездок трамваем (3 копейки за рейс). Ответ на вопрос, сколько совершено поездок, заложен в том же уравнения $5x+3y=1001$.

Корни этого уравнения рассказывают также и о тех точках на прямой

Рис. 1.

$5x+3y=1001$ (см. рисунок), обе координаты которых — натуральные числа (или целые — в какой-нибудь другой задаче).

Уравнения, в которых из множества решений выделены только целочисленные значения неизвестных, часто называют диофантовым в честь значенного математика II—III веков и э. Диофанта из Александрии.

Вопросы теории, связанные с условиям существования целочисленных, в частности, натуральных решений уравнения вида $ax+by=c$, рассмотрены в статье В. Н. Вагутена «Алгоритм Евклида и основная теория арифметики» («Квант» № 6, 1972). Мы этой теорией занимаемся не будем, а присутствим к решению конкретного уравнения $5x+3y=1001$, чтобы показать на этом примере разнообразные приемы, помогающие отыскать целочисленные решения уравнения *).

Решение способом «изобретательного школьника»

Делим обе части уравнения $5x+3y=1001$ на меньший коэффициент: $\frac{5}{3}x+y=\frac{1001}{3}$; справа и следваем целые части:
$$x+\frac{2}{3}x+y=333+\frac{2}{3};$$
$$x+y+\frac{2(x-1)}{3}=333.$$ (2)

Так как $x$ и $y$ целые, то должно быть целым и $\frac{x-1}{3}$; полагаем $\frac{x-1}{3}=t$; тогда $x=3t+1$. Подставляя в (2), получаем
$$3t+1+y+2t=333; y=332-5t.$$

В упомянутой статье В. Н. Вагутена доказывает, что полученные для $x$ и $y$ выражения являются «обшимми решениями», то есть содерж_

*) Напомним только, что существование целочисленных решений уравнения (1) гарантирует условия НОД ($a,b)=1$, так что уравнение $5x+3y=1001$ имеет решения в целых числах.

39

жат в себе все целочисленные решения данного уравнения.

Придавая параметру $t$ значения $t = 0, 1, 2, \dots, 66$, найдем 67 пар возможных натуральных корней данного уравнения.

Тепер предположим дополнительно, что Шехерезада хотела бы распределить свою тысячу и одну сказку между как можно большем числом ночей *). Этому требованию удовлетворяет max $(x + y)$ — наиболее из сумм пар корней уравнения. Имеем $x + y = 333 - 2t$; очевидно, max $(x + y)$ достигается при $t = 0$.

Итак, Шехерезада расскажет свои сказки самое большее за 333 ночи, если 332 ночи будет рассказывать по 3 сказки и только одну ночь — 5 сказок. Она может сократить срок своей «работы» и довести его до 201 ночи, если только 2 раза (при максимальной возможности изобретательного школьника), вы получили $x + y + \frac{4y - 1}{3} = 77$. Как теперь надо расчудать и действовать, чтобы подхождение образом выражить сначала $y$, а затем $x$ через целое $t$?

Решение способом «изобретательного математика» **)

Для уравнения $ax + by = c$ порядок действия таков: найти остаток $m$ от деления $a$ на $b$ (пусть $a > b$) и остаток $n$ от деления $c$ на $b$; если $n = 0$, то получаем сразу $x = bt$, $y = \frac{c}{b} - at$, $t = 0, \pm 1, \pm 2, \dots$;

*) Разумеется, при условии, что каждую ночь она рассказывает либо три, либо пять сказок.
**) Изобретатель способа Taylor L. F., «Numbers», London, 1970 не дал ему названия.

если $n \neq 0$, то умножить $m$ последовательно на 1, 2, …, $(b - 1)$ и выписать последовательность остатков от деления этих произведений на $b$. В полученной последовательности будет число $n$ (если его не будет, то и целочисленные решения уравнения не будет). Номер места, занимаемого числом $n$ в последовательности остатков, и есть одно из возможных значений $x$.

Приименим этот способ к уравнению $5x + 3y = 1001$. Имеем: $m = 2$, $n = 2$, умножаем $m = 2$ на каждый член последовательности {1; 2}, получаем {2; 4}; делим на 3 и выписываем остатки: {2; 1}. Замечаем, что число $n = 2$ занимает в этой последовательности остатков первого места, следовательно, $x = 1$. Этим определяется и соответствующее значение $y = 332$.

Легкий и вполне общий способ решения в целях числа линейных неопределенных уравнений с двумя неизвестными!

Но «способ изобретательного математика», в отличие от предыдущого приема, дал нам всего лишь одну пару корней: (1; 332). Дефект способа? Отнюдь нет. Расмотите формулы «общего решения» задачи, полученные «способом школьника»: $x = 1 + 3t$, $y = 332 - 5t$.

《Частные решения》 $x_0 = 1, y_0 = 332$ одинаковы в общих способах, а коэффициенты при $t$ (3 и 5) определяются коэффициентами решения уравнения: $3 = b; -5 = -a$. И это не случайное совпадение, а закономерность: если $(x_0, y_0)$ — какое-либо целое решение уравнения $ax + by = c$, причем $a$ и $b$ взаимно просты, то все его целые решения определяются формулами: $x = x_0 + bt$, $y = y_0 - at$, $t = 0, \pm 1, \pm 2, \dots$.

Решение «способом сравнения по модлю»

Это приятный и часто самый быстрое способ отискания целочисленных решения уравнения $ax + by = c$.

Для нашей целого достаточно напомнить, что утверждение $a \equiv b$ (mod $m$)

40

эквивалентно тому, что $a-b$ делится на $m$, или $a=b+km$ ($a, b$ и $k$ — целые, $m$ — натуральное).

Далее, если $a \equiv b$ (mod $m$), то верно, что $a \equiv b+km$ (mod $m$), где $k$ — любое целое число $^*$). Пусть, например, $3x \equiv 2$ (mod 5), тогда $3x \equiv 2+2\cdot 5$ (mod 5), $3x \equiv 12$ (mod 5) и $x \equiv 4$ (mod 5).

Заметим, что деление обеих частей сравнения по modulo $m$ на общий множитель $q$ допустимо лишь в том случае, когда $q$ и $m$ — взаимно простые числа.

Предварительно пример. Пусть требуется решить сравнение $11x \equiv 2$ (mod 23). Непрактично прибавлять к правой части по 23 до получения числа, кратного 11. Надо искать более низший путь. Пригоден, например, такой: написать, что $22x \equiv 4$ (mod 23), затем из левой части вычесть $23x$; получим $-x \equiv 4$ (mod 23), $x \equiv -4$ (mod 23) и, наконец, $x \equiv 19$ (mod 23).

Для решения уравнения $5x+3y=1001$ «способом сравнения по modulo» действовать надо так: $3y=1001-5x; 3y=1001$ (mod 5). Так как $1001=200\cdot 5+1$, то $3y \equiv 1$ (mod 5), или $3y \equiv 6$ (mod 5); $y \equiv 2$ (mod 5), следовательно, $y=2+5k$ ($k=0, \pm 1, \pm 2, \dots$). Легко видеть, что это решение эквивалентно раннее получению

$$y=332-5t \ (t=0, \pm 1, \pm 2, \dots).$$

Решение «способом сравнения по modulo» действовать надо так: $3y=1001-5x; 3y=1001$ (mod 5). Так как $1001=200\cdot 5+1$, то $3y \equiv 1$ (mod 5), или $3y \equiv 6$ (mod 5); $y \equiv 2$ (mod 5), следовательно, $y=2+5k$ ($k=0, \pm 1, \pm 2, \dots$). Легко видеть, что это решение эквивалентно раннее получению

$$y=332-5t \ (t=0, \pm 1, \pm 2, \dots).$$

*) Много полезных сведений о сравнения целых чисел по modulo приведено в статьях А. А. Егорова «Сравнение по modulo и арифметике остатков» («Квант» № 5, 1970), М. И. Башмакова «Нравится ли вам возить с целыми числами» («Квант» № 3, 1971) и уполмунуто выше статьев В. Н. Вагутена.

уравнения, в «целину»:

$$\frac{a}{b} = [a_0; a_1, a_2, \dots, a_n],$$

вычислить числитель и знаменатель предпоследней «подходящей» дроби $\frac{P_{n-1}}{Q_{n-1}}$ непосредственно или пользову рекуррентными формулами

$$P_{k+1} = P_k \cdot a_{k+1} + P_{k-1};$$

$$Q_{k+1} = Q_k \cdot a_{k+1} + Q_{k-1},$$

где $P_0=a_0$, $Q_0=1$ и $P_1=a_0 \cdot a_1+1$ и $Q_1=a_1$, $k=0, 1, 2, \dots$.

Решение задачи завершается применением готовых формул*), представляющих общее решение данного уравнения

$$\begin{cases} x = (-1)^{n-1} \cdot c \cdot Q_{n-1} + b \cdot t, \\ y = (-1)^{n} \cdot c \cdot P_{n-1} - a \cdot t, \\ t = 0; \pm 1; \pm 2, \dots. \end{cases}$$

Обратимся к уравнению $5x+3y=1001$ в последний раз. Проделаем подробно превращение числа $\frac{5}{3}$ в цепную дробь:

$$\frac{-5}{3} \left| \frac{3}{1} \right| \dots a_0=1,$$

$$\frac{-3}{2} \left| \frac{2}{1} \right| \dots a_1=1,$$

$$\frac{2}{2} \left| \frac{1}{2} \right| \dots a_2=2,$$

откуда $\frac{5}{3} = [1; 1, 2]$. Составим «подходящей» дроби

$$\frac{P_0}{Q_0} = \frac{a_0}{1} = 1; \quad \frac{P_1}{Q_1} = a_0 + \frac{1}{a_1} = \frac{2}{1};$$

$$\frac{P_2}{Q_2} = a_0 + \frac{1}{a_1 + \frac{1}{a_2}} = \frac{5}{3}$$

(последняя подходящая дробь не нужна, кроме того, она всегда равна дан-

*) Вывод этих формул можно найти в специальных пособиях, или, например, в книге «Энциклопедия элементарной математики», книга первая, 1951 (статья А. Я. Хинчина «Элементы теории чисел»). О цепных дробях расссказано также в статье Н. М. Бескина «Цепные дроби» («Квант» № 1, 1970).

41

ной дроби; мы выполнили вычисление только для наполнения способа неопределенного составления «подходящих» дробей).

Так как здесь $n = 2$, то числитель $P_{n-1}$ и знаменатель $Q_{n-1}$ предпоследней «подходящей» дроби равны соответственно

$$P_{n-1} = P_1 = 2; \quad Q_{n-1} = Q_1 = 1.$$

Все готово к применению формул (3): $x = -1 \cdot 1001 \cdot 1 + 3t, y = 1 \cdot 1001 \cdot 2 - 5t, t = 0, \pm 1, \pm 2, \dots$.

Окончательно, $x = -1001 + 3t, y = 2002 - 5t, t = 0, \pm 1, \pm 2, \dots$.

По виду решения как будто опять получился иной результат, не сохранив с предыдущими, но легко обнаружить его эквивалентность всем предыдущим записям общего решения рассматриваемого уравнения. Так, $x = 1$ и $y = 332$ получаются отсюда при $t = 334$. Тепер решим еще одну задачу.

После корабlekрушения

Пять моряков высадились на остров и к вечеру собрали кучу кокосовых орехов. Дележ отложили на утро. Один из них, проснулись ночь, пересчитал добцыч, угостил одним орехом мартышку, а из остальных орехов взял себе точно $\frac{1}{5}$ часть, после чего вновь лег спать и быстро уснул. За ночь так же поступили один за другим и остальные моряки; при этом каждый не знал о действиях своих предшественников. Наутро они поделили оставшиеся орехи поровну, но для мартышки в этот раз лишнего ореха не осталось. Сколько орехов собрали моряки?

Решение. Обозначим искомое число орехов через $x$. Выражая последовательные действия моряков уравнениями, получаем $x = 5a + 1; 4a = 5b + 1; 4b = 5c + 1; 4c = 5d + 1; 4d = 25y + 1$ (обдумайте смысл предлагаемых уравнений).

Эта система сводится к одному неопределенному уравнению

$$256x = 2101 + 15625y.$$

Выстрое решение в целых числах этого громоздкого уравнения будет приятной наградой за терпельное ознакомление с предложенными четырьмя способами — можно выбрать из них наиболее эффективный для данной задачи. Ответ в этой задаче таков: $x = 3121$ — наиболее из возможных натуральных значений $x$.

Заметание. В книге М. Гарднера «Математические головоломки и развлечения» («Мир», 1971), в котором есть эта задача, написано, что она «принадлежит к числу наиболее часто решаемых, но наиболее поддающихся решению диофантовых головоломок» (стр. 234). Когда эта задача в 1926 году появилась в одной газете (без решения и ответа), то 20 лет после этого не прекрашался поток писем в газету либо с просьбой сообщить ответ, либо с вариантом собственных решений.

Уражения

1. Найти целые решения уравнения $10x + 21y = 23$ каждим из описанных способов.
2. Найти двузначное число, у которого увоссмереенное число единиц на 13 меньше утроенного числа десятиков.
3. Некоторые числа экскурсантов, размещенных поровну в 5 автобусах (каждый автовосвяает не более 54 человек), были доставлены на вокзал. Там к ним присоединились еще 7 человек, и все экскурсанты распределились поровну в 14 варонах. Сколько всего было экскурсантов?
4. Имеются ли на пример $13x - 5y + 96 = 0$ точки с целыми координатами, не превосходящими по абсолотной величины число 10?
5. Пусть $n$ — натуральное число. Найти целые решения уравнения

$$nx + (n + 1)y = 2n + 1.$$

6. Надо разлить 15 л жидкости в бутылки emкостью в 0,5 л и 0,8 л так, чтобы все использованные бутылки были полными. Сколько потребуется бутылей той и другой emкости?
7. Доказать, что при любом нечетном $x$ выполняется сравнение $x^2 \equiv 1$ (mod 8), то есть квадрат любого нечетного целого числа при делении на восемь дает в остатке единицу.