Методы решения диофантовых уравнений составляют отдельный сектор теории чисел, точнее, ее элементарного раздела (этому термину не стоит придавать большого внимания — математические проблемы, поднимаемые в этой области, далеко не элементарные). Название уравнений произошло от античного ученого Диофанта, о котором до нас дошло не так много сведений (наиболее известны несколько томов «Арифметики» и эпитафия-задача, написанная на его могиле).
Линейные диофантовы уравнения
В средних классах школы для подготовки к математическим олимпиадам различного уровня изучают методы решения линейных диофантовых уравнений. Это частный случай уравнений, они имеют две переменных и записываются в виде многочлена 1 степени Ах+By=C, где:
- A, В, С — целые числа;
- x,y — переменные (также целые числа).
На практике задачи такого рода приходится решать, например, продавцам, имеющим монеты двух достоинств. Им надо определить, смогут ли они набрать нужную сумму монетами, присутствующими в кассе. В большинстве случаев такие практические задачи решаются в уме.
Житейский опыт подсказывает, что, имея, например, монеты в 5 и 10 рублей можно набрать сумму в 1 рубль 20 копеек различными способами. Это означает, что линейное диофантово уравнение в общем случае также имеет не одно решение, но может и не иметь ни одного. Например, монетами в 5 рублей и 2 рубля невозможно набрать сумму в 9 рублей.
Чтобы определить решаемость каждого уравнения, надо найти наибольший общий делитель (НОД) коэффициентов при переменных и посмотреть, делится ли свободный член на это число (при этом НОД должен быть больше 1). Так, в первой задаче, которую можно записать в виде уравнения 5x+10y=120, наименьший общий делитель для 5 и 10 составит 5. 120 делится на 5 без остатка, это означает, что задача разрешима.
В данном простом случае наименьший общий делитель находится интуитивно. В других, более сложных случаях, может потребоваться вычисление по какому-либо алгоритму. Наиболее распространённым является бинарный алгоритм Евклида.
Вторая задача сводится к уравнению 5x+2y=9. Здесь числа 5 и 2 являются взаимно простыми. Для них не существует никакого общего делителя, помимо 1. Это означает, что уравнение неразрешимо.
Отдельно можно рассмотреть класс линейных однородных диофантовых уравнений. Они записываются в виде Ах+By=0. Если числа A и В имеют общий делитель, отличный от 1, то уравнение может быть разделено на этот делитель так, чтобы числа A и В стали взаимно простыми. В этом случае уравнение имеет бесконечно большое количество корней, которые могут быть записаны в виде {х=B*n; y=A*n}, где n – любое целое число.
Классические диофантовы уравнения
Классические диофантовы уравнения могут быть предложены к решению на математических олимпиадах для старшеклассников. Они имеют в общем случае n переменных и могут быть записаны в виде S(t1,t2,t3..tn)=0. В этом случае ti — переменные, которые могут принимать только целые значения, а S(t) — целочисленная функция. Это может быть, например, многочлен с целыми коэффициентами. Иными словами, это такие уравнения, корни которого принадлежат множеству Z, и коэффициенты принадлежат тому же множеству. Задача часто состоит не только в нахождении корней, но и в нахождении коэффициентов. В этом случае их обычно называют параметрами и уравнение записывают в виде U(b1, b2, b3..bn;t1, t2, t3..tn)=0, где:
- bi — коэффициенты полинома;
- ti — переменные полинома.
К категории диофантовых уравнений относят и великую теорему Ферма, доказательство которой получено лишь недавно. Ее суть в том, что уравнение вида xm+уm=zm где m – целое число, большее 3, не имеет натуральных корней.
Среди уравнений 2 степени, относящихся к данному классу, выделяют уравнение Пелля. Оно имеет вид x2-ау2=1, где а – множитель, не являющийся квадратом целого числа. Интересно, что независимо от значения коэффициента а, любое уравнение подобного вида имеет набор тривиальных корней {-1;1;0}. Остальных корней имеется бесконечное множество (такие корни называются нетривиальными). Интерес представляет нахождение наименьшего нетривиального корня.
Еще один вид диофантовых уравнений был сформулирован бельгийским математиком Каталаном в 19 веке. Они могут быть записаны в виде xa—yb=1, где все переменные и коэффициенты больше 1. Каталан предположил, что такое уравнение имеет единственное решение 32-23=1, однако доказана его гипотеза была лишь в 2002 году.
Нельзя не упомянуть и об уравнении Маркова, имеющего вид x2+у2+z2=3xyz. Молодой Петербургский ученый нашел способ решать такие уравнения в рамках исключительно школьного курса математики.
Что касается общих методов решения диофантовых уравнений, то, несмотря на попытки в течение веков их найти, лишь в 1970 году советский ученый Ю.В. Матиясевич доказал, что всеобъемлющего метода не существует. Однако разработаны частные методы, позволяющие решать диофантовы уравнения. Выбор способа определяется в каждом случае отдельно.
Самый простой, но при этом зачастую самый долгий и трудоемкий способ – перебор всех возможных корней уравнения. Несколько сокращает время и усилия метод разложения на множители. Например, уравнение x3—y3=91 может быть разложено на множители (y−x)*(y2+xy+x2)=91. Далее находятся все делители числа 91, из них составляются пары и с помощью анализа (или перебора, но уже меньшего количества чисел) находятся корни уравнения. Если эти относительно простые способы не помогают, приходится применять и другие методы:
- выражение одной переменной через другую и выделении целой части дроби;
- выделение полного квадрата;
- решение уравнения с двумя переменными как квадратного относительно одной из переменных;
- оценка выражений, входящих в уравнение;
- метод бесконечного (непрерывного) спуска;
- другие существующие методы решения диофантовых уравнений.
Эти способы обычно состоят из громоздких вычислений, поэтому их использование требует повышенного внимания, чтобы не допустить ошибок.
Научиться решать различные типы диофантовых уравнений, углубляя знания и навыки, можно самостоятельно или с преподавателем. А в завершение можно самостоятельно решить задачу, которая упоминалась в начале и по легенде была высечена на могильном камне Диофанта. В вольном переводе она звучит так:
Детство ученого, что лежит в этой могиле, заняло 1/6 его жизни, а юность, которая быстро прошла – еще 1/12. Повзрослев, он 1/7 жизненного пути пробыл холостым, затем вступил в брак. Через 5 лет после этого у него родился первенец, но прожил недолго – в два раза меньше, чем Диофант. Прожив 4 года после смерти сына, ученый скончался. Сколько лет Диофант прожил?
