Текст статьиКордемский Б. А. Этому виду задач более 1600 лет : [уравнения в целых числах] // Квант. — 1973. — № 4. — С. 38—41.
Менялась фабула и форма записи задачи, накапливались способы решения, но суть оставалась неизменной: найти целые (чаще натуральные) $x$ и $y$, удовлетворяющие уравнению
$$
ax+by=c\tag1
$$
с заданными целыми коэффициентами$a$, $b$ и $c$.
Может быть, $c$ — это 1001 сказка Шехерезады, а нас интересует, сколько ночей потребуется Шехерезаде, чтобы рассказать все свои сказки, если $x$ ночей она будет рассказывать по 5 сказок, а остальные сказки по 3 за $y$ ночей.
Сказочнице, очевидно, потребуется $x+y$ ночей, где $x$ и $y$ — натуральные корни уравнения $5x+3y=1001$.
А может быть, $c$ — это 10 руб. 01 коп., которые некто израсходовал на $x$ поездок автобусом (по 5 копеек за рейс) и $y$ поездок трамваем (3 копейки за рейс). Ответ на вопрос, сколько всего совершено поездок, заложен в том же уравнении $5x+3y=1001$.
Корни этого уравнения рассказывают также и о тех точках на прямой $5x+3y=1001$ (см. рисунок), обе координаты которых — натуральные числа (или целые — в какой-нибудь другой задаче).
Уравнения, в которых из множества решений выделены только целочисленные значения неизвестных, часто называют диофантовыми в честь знаменитого математика II—III веков н. э. Диофанта из Александрии.
Вопросы теории, связанные с условием существования целочисленных, в частности, натуральных решений уравнения вида $ax+by=c$, рассмотрены в статье В. Н. Вагутена«Алгоритм Евклида и основная теорема арифметики» («Квант» № 6, 1972). Мы этой теорией заниматься не будем, а приступим к решению конкретного уравнения $5x+3y=1001$, чтобы показать на этом примере разнообразные приёмы, помогающие отыскать целочисленные решения уравнений.
Решение способом «изобретательного школьника»
Делим обе части уравнения $5x+3y=1001$ на меньший — коэффициент: $\dfrac53x+y=\dfrac{1001}3$, справа и слева выделяем целые части: $x+\dfrac23x+y=333+\dfrac23$;
$$
x+y+\dfrac{2(x-1)}3=333.\tag2
$$
Так как $x$ и $y$ целые, то должно быть целым и $\dfrac{x-1}3$; полагаем $\dfrac{x-1}3=t$; тогда $x=3t+1$. Подставляя в (2), получаем
$$
3t+1+y+2t=333;\quad y=332-5t.
$$
В упомянутой статье В. Н. Вагутена доказывается, что полученные для $x$ и $y$ выражения являются «общими решениями», т. е. содер жат в себе все целочисленные решения данного уравнения.
Придавая параметру $t$ значения $t=0$, 1, 2, $\ldots$, 66, найдём 67 пар возможных натуральных корней данного уравнения.
Теперь предположим дополнительно, что Шехерезада хотела бы распределить свою тысячу и одну сказку между как можно большим числом ночей. Этому требованию удовлетворяет $\max(x+y)$ — наибольшая из сумм пар корней уравнения. Имеем $x+y=333-2t$, очевидно, $\max(x+y)$ достигается при $t=0$.
Итак, Шехерезада расскажет свои сказки самое большее за 333 ночи, если 332 ночи будет рассказывать по 3 сказки и только одну ночь — 5 сказок. Она может сократить срок своей «работы» и довести его до 201 ночи, если только 2 раза (при максимально возможном $t=66$) будет рассказывать по 3 сказки и 199 раз — по 5 сказок.
Дополнительный вопрос для размышлений
Предположим, что, отыскивая целочисленные решения некоторого уравнения «способом изобретательного школьника», вы получили $x+y+\dfrac{4y-1}3=77$. Как теперь надо рассуждать и действовать, чтобы подходящим образом выразить сначала $y$, а затем $x$ через целое $t$?
Решение способом «изобретательного математика»
Для уравнения $ax+by=c$ порядок действий таков: найти остаток $m$ от деления $a$ на $b$ (пусть $a\gt b$) и остаток $n$ от деления $c$ на $b$; если $n=0$, то получаем сразу $x=bt$, $y=\dfrac cb-at$, $t=0$, $\pm1$, $\pm2$, $\ldots$; если $n\ne0$, то умножить $m$ последовательно на 1, 2, $\ldots$, $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$, $\pm1$, $\pm2$, $\ldots$.
Решение «способом сравнений по модулю»
Это приятный и часто самый быстрый способ отыскания целочисленных решений уравнения $ax+by=c$.
Для нашей цели достаточно напомнить, что утверждение $\global\def\pmod#1{~(\text{mod}~#1)}a\equiv b\pmod m$ эквивалентно тому, что $a-b$ делится на $m$, или $a=b+km$ ($a$, $b$ и $k$ — целые, $m$ — натуральное).
Далее, если $a\equiv b\pmod m$, то верно, что $a\equiv b+km\pmod m$, где $k$ — любое целое число. Пусть, например, $3x\equiv2\pmod5$, тогда
$$
3x\equiv2+2\cdot5\pmod5{,}~~3x\equiv12\pmod5~~\text{и}~~x\equiv4\pmod5.
$$
Заметим, что деление обеих частей сравнения по модулю $m$ на общий множитель $q$ допустимо лишь в том случае, когда $q$ и $m$ — взаимно простые числа.
Предварительный пример. Пусть требуется решить сравнение $11x\equiv2\pmod{23}$. Непрактично прибавлять к правой части по 23 до получения числа, кратного 11. Надо искать более изящный путь. Пригоден, например, такой: написать, что $22x\equiv4\pmod{23}$, затем из левой части вычесть $23x$; получим $-x\equiv4\pmod{23}$, $x\equiv-4\pmod{23}$ и, наконец, $x\equiv19\pmod{23}$.
Для решения уравнения $5x+3y=1001$ «способом сравнений по модулю» действовать надо так: $3y=1001-5x$; $3y\equiv1001\pmod5$. Так как $1001=200\cdot5+1$, то $3y\equiv1\pmod5$, или $3y\equiv6\pmod5$; $y\equiv2\pmod5$, следовательно, $y=2+5k$ ($k=0$, $\pm1$, $\pm2$, $\ldots$). Легко видеть, что это решение эквивалентно ранее полученному $y=332-5t$ ($t=0$, $\pm1$, $\pm2$, $\ldots$).
Решение «способом цепной дроби»
Этот способ отыскания целочисленных решений уравнения $ax+by=c$ предполагает умение превратить дробь $\dfrac ab$, составленную из коэффициентов уравнения, в «цепную»:
$$
\dfrac ab=[a_0;a_1,a_2,{\ldots},a_n],
$$
вычислить числитель и знаменатель предпоследней «подходящей» дроби $\dfrac{P_{n-1}}{Q_{n-1}}$ непосредственно или пользуясь рекуррентными формулами
$$
\begin{aligned}
P_{k+1}&=P_k\cdot a_{k+1}+P_{k-1};\\
Q_{k+1}&=Q_k\cdot a_{k+1}+Q_{k-1},
\end{aligned}
$$
где $P_0=a_0$, $Q_0=1$ и $P_1=a_0\cdot a_1+1$ и $Q_1=a_1$, $k=1$, 2, $\ldots$.
Решение задачи завершается применением готовых формул, представляющих общее решение данного уравнения
$$
\left\{\begin{array}{l}
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{;}~{\pm1}{;}~{\pm2}{;}~{\ldots}.
\end{array}\right.\tag3
$$
Обратимся к уравнению $5x+3y=1001$ в последний раз. Проделаем подробно превращение числа $\dfrac53$ в цепную дробь:
$$
\def\|{\rule[-3.5pt]{.4pt}{12pt}}
\def\-{\rule[2.3pt]{1em}{.4pt}}
\def\m{\mathllap-}
\def\n#1{\enspace\mathclap{#1}\enspace}
\colsep{0pt}{\begin{array}{cccccccc}
&&&&\n5&\|&\n3\\[-6pt]
&&&\m&&\|&\-\\[-6pt]
&&&&\n3&\|&\n1\mathrlap{~{\ldots}~~a_0=1,}\\[-6pt]
&&&\mathllap\-&\-\\[-6pt]
&&\n3&\|&\n2\\[-6pt]
&\m&&\|&\-\\[-6pt]
&&\n2&\|&\n1\mathrlap{~{\ldots}~~a_1=1,}\\[-6pt]
&\mathllap\-&\-\\[-6pt]
\n2&\|&\n1\\[-6pt]
&\|&\-\\[-6pt]
&\|&\n2\mathrlap{~{\ldots}~~a_2=2,}
\end{array}}\hphantom{~{\ldots}~~a_0=1,}
$$
откуда $\dfrac53=[1;1,2]$. Составим «подходящие» дроби
$$
\dfrac{P_0}{Q_0}=\dfrac{a_0}1=1;\quad\dfrac{P_1}{Q_1}=a_0+\dfrac1{a_1}=\dfrac21;\quad\dfrac{P_2}{Q_2}=a_0+\dfrac1{a_1+\dfrac1{a_2}}=\dfrac53
$$
(последняя подходящая дробь не нужна, кроме того, она всегда равна данной дроби; мы выполнили вычисление только для напоминания способа непосредственного составления «подходящих» дробей).
Так как здесь $n=2$, то числитель $P_{n-1}$ и знаменатель $Q_{n-1}$ предпоследней «подходящей» дроби равны соответственно
$$
P_{n-1}=P_1=2;\quad Q_{n-1}=Q_1=1.
$$
Всё готово к применению формул (3): $x=-1\cdot1001\cdot1+3t$, $y=1\cdot1001\cdot2-5t$, $t=0$, $\pm1$, $\pm2$, $\ldots$.
По виду решения как будто опять получился иной результат, не схожий с предыдущими, но легко обнаружить его эквивалентность всем предыдущим записям общего решения рассматриваемого уравнения. Так, $x=1$ и $y=332$ получаются отсюда при $t=334$. Теперь решим ещё одну задачу.
После кораблекрушения
Пять моряков высадились на остров и к вечеру собрали кучу кокосовых орехов. Делёж отложили на утро. Один из них, проснувшись ночью, пересчитал добычу, угостил одним орехом мартышку, а из остальных орехов взял себе точно $\dfrac15$ часть, после чего вновь лёг спать и быстро уснул. За ночь так же поступили один за другим и остальные моряки; при этом каждый не знал о действиях своих предшественников. Наутро они поделили оставшиеся орехи поровну, но для мартышки в этот раз лишнего ореха не осталось. Сколько орехов собрали моряки?
Решение. Обозначим искомое число орехов через $x$. Выражая последовательные действия моряков уравнениями, получаем $x=5a+1$; $4a=5b+1$; $4b=5c+1$; $4c=5d+1$; $4d=25y+1$ (обдумайте смысл предлагаемых уравнений).
Эта система сводится к одному неопределённому уравнению
$$
256x=2101+15\,625y.
$$
Быстрое решение в целых числах этого громоздкого уравнения будет приятной наградой за терпеливое ознакомление с предложенными четырьмя способами — можно выбрать из них наиболее эффективный для данной задачи. Ответ в этой задаче таков: $x=3121$ — наименьшее из возможных натуральных значений $x$.
Замечание. В книге М. Гарднера «Математические головоломки и развлечения» («Мир», 1971), в которой есть эта задача, написано, что она «принадлежит к числу наиболее часто решаемых, но наименее поддающихся решению диофантовых головоломок» (стр. 234). Когда эта задача в 1926 году появилась в одной газете (без решения и ответа), то 20 лет после этого не прекращался поток писем в газету либо с просьбой сообщить ответ, либо с вариантами собственных решений.
Упражнения
Найти целые решения уравнения $10x+21y=23$ каждым из описанных способов.
Найти двузначное число, у которого увосьмерённое число единиц на 13 меньше утроенного числа десятков.
Некоторое число экскурсантов, разместившихся поровну в 5 автобусах (каждый автобус вмещает не более 54 человек), были доставлены на вокзал. Там к ним присоединились ещё 7 человек, и все экскурсанты распределились поровну в 14 вагонах. Сколько всего было экскурсантов?
Имеются ли на прямой $13x-5y+96=0$ точки с целыми координатами, не превосходящими по абсолютной величине число 10?
Пусть $n$ — натуральное число. Найти целые решения уравнения
$$
nx+(n+1)y=2n+1.
$$
Надо разлить 15 л жидкости в бутыли ёмкостью в 0,5 л и 0,8 л так, чтобы все использованные бутыли были полными. Сколько потребуется бутылей той и другой ёмкости?
Доказать, что при любом нечётном $x$ выполняется сравнение $x^2\equiv1\pmod8$, т. е. квадрат любого нечётного целого числа при делении на восемь даёт в остатке единицу.
