Линейные диофантовые уравнения

Введение

Линейным диофантовым уравнением называется уравнение с несколькими неизвестными вида а₁ х₁ + ... + а _n х _n = с, где (известные) коэффициенты а₁ ,..., а _n и с — целые числа, а неизвестные х₁ , … x_n также являются целыми числами. К решению подобных уравнений сводятся разнообразные текстовые задачи, в которых неизвестные величины выражают количество предметов того или иного рода и потому являются натуральными (или неотрицательными целыми) числами.

Теория решения подобных уравнений является классическим разделом элементарной математики. В ней не приходится писать сложные и громоздкие формулы, а необходимо проводить аккурат­ные рассуждения, базирующиеся на определенных понятиях теории чисел и связанные в стройную логическую конструкцию. В рамках этой теории можно дать исчерпывающее решение рассматриваемого класса задач с четко описанным алгоритмом получения ответа.

Конкретные задачи такого рода были решены еще в Древнем Вавилоне около 4 тысяч лет тому назад. Древнегреческий мысли­тель Диофант, который жил около 2 тысяч лет тому назад, в своей книге «Арифметика» решил большое число таких и более сложных уравнений в целых числах и в сущности описал общие методы их решения.

В школьных учебниках эта тема затрагивается вскользь, да и то лишь в 8-м классе, в то время как задачи, где требуется решать уравнения описанного типа, относительно часто предлагаются на вступительных экзаменах.

В настоящей брошюре на примерах решения конкретных экза­менационных задач МГУ им. М.И. Ломоносова мы расскажем об основных результатах и методах теории линейных диофантовых уравнений. Поскольку, за редким исключением, на экзаменах предлагаются уравнения с двумя неизвестными, мы ограничим­ся этим случаем, то есть будем рассматривать уравнения вида

ах + Ьу = с. Это позволит упростить теоретические рассмотрения, не ограничивая, в сущности, общности описываемых методов (мы продемонстрируем это в задаче 13 на примере конкретного уравне­ния вида ах + Ьу + сz = d.

Следует отметить, что каждая конкретная задача в целых числах может решаться с помощью раз­ных методов. Целью нашей работы является демонстрация возможностей теории линейных диофан­товых уравнений.

Однородные уравнения

Прежде всего, мы рассмотрим однородные линейные уравнения, то есть уравнения вида

ах + by = 0, все члены которых являются одночленами первой степени.

Если коэффициенты а и Ь имеют общий делитель d , то обе части уравнения ах + by = 0 можно сократить на d . Поэтому, не нарушая общности, можно считать, что числа а и b — взаимно про­стые.

Рассмотрим, например, уравнение 80х + 126y = 0.

Разложим коэффициенты а = 80 и b=126 на простые множители: а = 2⁴ • 5, b = 2 • З² • 7. Наибольший общий делитель чисел а = 80 и b = 126 равен 2, и после сокращения на 2 мы получим уравнение

40x + 63y = 0, (1)

в котором коэффициенты а = 40 = 2³ • 5 и b = 63 = З² • 7 являются взаимно простыми целыми чис­лами.

Разложение на простые множители коэффициентов уравнения, которое мы использовали для сокраще­ния на наибольший общий делитель, можно использовать и для завершения решения. Пере­пишем уравнение (1) в виде:

2³ •5 •х = -3² •7 •у. (2)

Левая часть уравнения (2) делится на 2³ • 5. Поэтому и правая часть, которая равна левой, должна делиться на 2³ • 5, а это возможно тогда и только тогда, когда неизвестная у делится на 2³ • 5:

у = 2³ • 5 • u = 40u,(3)

где и — некоторое целое число.

Аналогичные рассуждения применимы и к правой части урав­нения (2). Правая часть делится на

З² • 7. Поэтому и левая часть, которая равна правой, должна делиться на З² • 7, а это возможно тогда и только тогда, когда неизвестная х делится на З² • 7:

x = З ² • 7 • v = 63v,(4)

где v — некоторое целое число.

Равенства (3) и (4) фактически вводят новые целочисленные неизвестные u , v вместо основных неизвестных х, у. Для новых неизвестных уравнение (2) примет вид: u = - v . Множество решений этого уравнения состоит из бесконечного количества пар:

(-3; 3), (-2; 2), (-1; 1), (0; 0), (1; -1), (2; -2), (3; -3), ...

Иначе говоря, этому уравнению удовлетворяют все пары (-u; u) вида (-n; n), где n — произволь­ное целое число, и только они. Пе­ременная n в этих формулах является своеобразным «номером» решения.

Возвращаясь к основным неизвестным х и у, мы получим, что множество решений уравнения (2) можно записать в виде: х_п = 63n, у = - 40n, где n — произвольное целое число.

Как ясно из приведенного решения (2), оно совершенно не привя­зано к точным значениям коэффици

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать