Смекни!
smekni.com

Линейные диофантовые уравнения (стр. 1 из 4)

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

40x + 63y = 0, (1)

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

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

235х = -327у.(2)

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

у = 23 • 5 • u = 40u,(3)

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

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

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

x = З 2 • 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), оно совершенно не привя­зано к точным значениям коэффициен­тов а и bи не изменится, если вместо чисел а = 40, b = 63 рассмотреть произвольные взаимно про­стые числа. Таким образом, справедлива следующая теорема, которая дает полное решение диофантовых уравнений вида ах + by = 0.

Теорема 1. Если числа а и b— взаимно простые, то уравне­ние ах + by= 0 имеет бесконечно много решений в целых чис­лах, которые находятся во взаимно однозначном соответствии с множест­вом целых чисел Z(то есть могут быть занумерованы целыми числами) и описываются формулой: хп = bn, yn = -an, где n

Z— «номер» решения.

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

В качестве простого примера применения теоремы 1 рассмотрим следующую задачу.

Задача 1. Найти все целочисленные решения уравне­ния

х2 + 5y2 + 34z2 + 2ху - 10xz - 22уz- 0.

Решение. Рассмотрим уравнение

х2 + 5у2 + 34z2 + 2ху - 10xz - 22yz = 0

как квадратное уравнение относительно одной неизвестной х:

х2 + 2х(у - 5г) + by2 + 34z2 - 22yz = 0.

Тогда

= (y-5z)2-(5y2+34z2-22yz)=-(2y-3z)2.

Если это уравнение имеет решение, то дискриминант должен быть неотрицательным, что воз­можно только в случае - 3z = 0. Тогда дискриминант равен нулю, и уравнение имеет единствен­ное решение х = 5z- у.

Итак, исходное уравнение равносильно системе

Общее решение первого уравнения в целых числах дается форму­лами у = Зn, z= 2n, где n

Z. Из второго уравнения теперь можно найти х (причем х автоматически будет целым числом): х = In.

Таким образом, исходное уравнение имеет бесконечно много целочисленных решений, которые могут быть описаны формулой (х; у; z) — (7n; Зn; 2n), n

Z.

Ответ: (х; у, z) = (7n; Зn; 2n), neZ.

Общие линейные уравнения

В этом разделе мы будем рассматривать диофантовы уравнения вида ах + by= с.

Прежде всего отметим, что, вообще говоря, такое уравнение может и не иметь целочисленных реше­ний.

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

Теорема 2. Если наибольший общий делитель dкоэффициентов а и bбольше 1, а свободный член с не делится на d, то уравнение ах + by = с не имеет решений в целых числах.

Это простое утверждение часто используется, например, для доказательства иррациональности чисел, записанных с помощью радикалов.

Задача 2.Дока­зать, что число

не является рациональным числом.

Решение. Допустим противное, что

— число рациональное.

Тогда существуют натуральные т, п такие, что

.

Избавляясь от радикала и дроби, получим:

2n3= т3(5)

Разложим числа т иnна простые множители (мы явно указы­ваем только простой множитель 2):

т = 2х...

n = 2y•...

где х, у — неотрицательные целые числа (отсутствие простого мно­жителя 2 в разложении озна­чает, что соответствующий показатель степени равен нулю).

Тогда равенство (5) примет вид:

23y+1•... = 2•...

В силу единственности разложения натурального числа на про­стые множители

Зу + 1 = 3x

3(х - у) = 1.

Последнее уравнение является линейным диофантовым уравнени­ем вида ах + Ьу = с, причем коэффи­циенты а = 3, b= -3 делятся на 3, в то время как свободный член с = 1 — нет. Значит, это уравнение не имеет целочисленных решений, что означает ложность исходного предположения о рациональности числа

.