Презентация. Решение уравнений в целых числах

I Решение в целых числах алгебраических уравнений с целыми коэффициентами более чем с одним неизвестным представляет собой одну из труднейших и древнейших математических задач. Этими задачами много занимались самые выдающиеся математики древности, например, греческий математик Пифагор (VI век до н.э.), александрийский математик Диофант (III век н.э.), П.Ферма(XVII в.), Л.Эйлер(XVIII век), Ж.Л.Лагранж(XVIII век), П.Дирихле(XIX век), К.Гаусс(XIX век), П.Чебышев(XIX в.) и многие другие.

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

Поэтому сегодня мы и разберем некоторые методы решения таких уравнений.

1 Применение теории делимости к решению неопределенных уравнений в целых числах.

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

Для решения в целых числах уравнения вида ах + by = c, где а, b, c - целые числа, отличные от нуля, приведем ряд теоретических положений, которые позволят установить правило решения. Эти положения основаны также на уже известных фактах теории делимости.

Теорема 1. Если НОД(а, b) = d, то существуют такие целые числа х и у, что имеет место равенство ах + bу = d.

(Это равенство называется линейной комбинацией или линейным представлением наибольшего общего делителя двух чисел через сами эти числа.)

Доказательство теоремы основано на использовании равенства алгоритма Евклида для нахождения наибольшего общего делителя двух чисел (наибольший общий делитель выражается через неполные частные и остатки, начиная с последнего равенства в алгоритме Евклида).

Пример. Найти линейное представление наибольшего общего делителя чисел 1232 и 1672.

Решение. 1. Составим равенства алгоритма Евклида:

1672 = 1232 ∙1 + 440,

1232 = 440 ∙ 2 + 352,

440 = 352 ∙ 1 + 88,

352 = 88 ∙ 4, т.е. (1672,352) = 88.

2) Выразим 88 последовательно через неполные частные и остатки, используя полученные выше равенства, начиная с конца:

88 = 440 - 352∙1 = (1672 - 1232) - (1232 - 1672∙2 + 1232∙2) = 1672∙3 - 1232∙4, т.е. 88 = 1672∙3 + 1232∙(-4).

Теорема 2. Если уравнение ах + bу = 1, если НОД(а, b) = 1, достаточно представить число 1 в виде линейной комбинации чисел а и b.

Справедливость этой теоремы следует из теоремы 1. Таким образом, чтобы найти одно целое решение уравнения ах + bу = 1, если НОД (а, в) = 1, достаточно представить число 1 в виде линейной комбинации чисел а и в.

Пример. Найти целое решение уравнения 15х + 37у = 1.

Решение. 1. 37 = 15 ∙ 2 + 7, 15 = 7 ∙ 2 + 1.

2. 1 = 15 - 7∙2 = 15 - (37 - 15∙2) ∙2 = 15∙5 + 37∙(-2),

т.е. х= 5, у= -2 - решение данного уравнения.

Теорема 3. Если в уравнении ах + bу = с НОД(а, b) = d>1 и с не делится на d, то уравнение целых решений не имеет.

Для доказательства теоремы достаточно предположить противное.

Пример. Найти целое решение уравнения 16х - 34у = 7.

Решение. (16,34)=2; 7 не делится на 2, уравнение целых решений не имеет.

Теорема 4. Если в уравнении ах + bу = с НОД(а, b) = d>1 и сd, то оно равносильно уравнению ах + bу = с, в котором НОД(а, b) = 1.

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

Теорема 5. Если в уравнении ах + bу = с НОД(а, b) = 1, то все целые решения этого уравнения заключены в формулах:

х = хс + bt, у = yc-at, где х, y - целое решение уравнения ах + bу = 1, t - любое целое число.

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

Приведенные теоремы позволяют установить следующее правило решения в целых числах уравнения ах+ bу = с НОД(а, b) = 1:

Находится целое решение уравнения ах + bу = 1 путем представления 1 как линейной комбинации чисел а и b (существуют и другие способы отыскания целых решений этого уравнения, например при использовании цепных дробей);

Составляется общая формула целых решений данного уравнения х = хс + bt, у = yc - at, где х, y - целое решение уравнения ах + bу = 1, t - любое целое число.

Придавая t определенные целые значения, можно получить частные решения данного уравнения: наименьшие по абсолютной величине, наименьшие положительные (если можно) и т.д.

Пример. Найти целые решения уравнения 407х - 2816у = 33.

Решение.1. Упрощаем данное уравнение, приводя его к виду 37х - 256у = 3.

2.Решаем уравнение 37х - 256у = 1.

256 = 37∙ 6 + 34,

37 = 34 ∙1 + 3,

34 = 3 ∙11 + 1.

1 = 34 - 3∙11 = 256 - 37∙6 - 11 (37 - 256 + 37∙6) = 256∙12 - 37∙83 =

= 37∙(-83) - 256∙(-12),

т.е. х= -83, y= -12.

3. Общий вид всех целых решений данного уравнения:

х = -83∙3 - 256t = -249 - 256t,

у = -12∙3 - 37 t = -36 - 37 t.

Положив t = -1, получим х= 7, у= 1 и общие формулы решений примут вид: х = 7 - 256t, у = 1-37t.

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

2. Метод полного перебора всех возможных значений переменных, входящих в уравнение.

Найти множество всех пар натуральных чисел, которые являются решениями уравнения 49х + 51у = 602.

Решение: Выразим из уравнения переменную х через у х =, так как х и у - натуральные числа, то х = 602 - 51у ≥ 49, 51у≤553, 1≤у≤10. Полный перебор вариантов показывает, что натуральными решениями уравнения являются х=5, у=7.

Ответ: (5;7).

3. Решение уравнений методом разложения на множители.

Диофант наряду с линейными уравнениями рассматривал квадратные и кубические неопределенные уравнения. Решение их, как правило, сложно.

Рассмотрим такой случай, когда в уравнениях можно применить формулу разности квадратов или другой способ разложения на множители.

Решить уравнение в целых числах: х² + 23 = у²

Решение: Перепишем уравнение в виде: у² - х² = 23, (у - х)(у + х) = 23. Так как х и у - целые числа и 23 - простое число, то возможны случаи: Решая полученные системы, находим:

Ответ: (-11;12);(11;12);(11;-12);(-11;-12).

4. Выражение одной переменной через другую и выделение целой части дроби.

Решить уравнение в целых числах: х² + ху - у - 2 = 0.

Решение:Выразим из данного уравнения у через х: у(х - 1) =2 - х²,

у = = - = - = - += -(х + 1) + , (х1)

Так как х, у - целые числа, то дробь должна быть целым числом.

Это возможно, если х - 1 =

1) 2)

Ответ: (0;-2);(2;-2).

5. Методы, основанные на выделении полного квадрата.

Найдите все целочисленные решения уравнения: х² - 6ху + 13у² = 29.

Решение:Преобразуем левую часть уравнения, выделив полные квадраты,

х2 - 6ху + 13у² = (х² - 6ху + 9у²) + 4у2 = (х - 3у)² + (2у)² = 29, значит (2у)² 29.

Получаем, что у может быть равен 0; .

1. у = 0, (х - 0)2 = 29. Не имеет решений в целых числах.

2. у = -1, (х + 3)² + 4 = 29, (х + 3)² = 25, х + 3 = 5 или х + 3 = -5

х=2 х=-8

3. у = 1, (х - 3)² +4 =29,

(х - 3)² =25, х - 3 = 5 или х - 3 = -5

х = 8 х = -2

4. у = -2, (х + 6)2 + 16 = 29, (х + 6)2 = 13. Нет решений в целых числах.

5. у=2, (х-6)2+16=29, (х-6)2=13. Нет решений в целых числах.

Ответ: (2;-1); (-8;-1); (8;1); (-2;1).

6. Решение уравнений с двумя переменными как квадратных

относительно одной из переменных.

Решить уравнение в целых числах: 5х²+5у²+8ху+2у-2х+2=0.

Решение:Рассмотрим уравнение как квадратное относительно х:

5х² + (8у - 2)х + 5у² + 2у + 2 = 0

D = (8у - 2)² - 4·5(5у² + 2у + 2) = 64у² - 32у + 4 = -100у² - 40у - 40 = = -36(у² + 2у + 1) = -36(у + 1)²

Для того, чтобы уравнение имело решения, необходимо, чтобы D = 0.

-36(у + 1)2 = 0. Это возможно при у = -1, тогда х = 1.

Ответ: (1;-1).

7. Оценка выражений, входящих в уравнение.

Решить в целых числах уравнение:(х² + 4)(у² + 1) = 8ху

Решение:

Заметим, что если (х;у) - решение уравнения, то (-х;-у) - тоже решение.

И так как х = 0 и у = 0 не являются решением уравнения, то, разделив обе части уравнения на ху, получим:

∙ = 8, (х +2)(у +1) = 8.

Пусть х > 0, у > 0, тогда, согласно неравенству Коши, х + 2= 4, у +1 = 2,

тогда их произведение (х +2)(у +1) = 4·2 = 8, значит, х + 2 = 4 и у +1 = 2.

Отсюда находим х = 2 и у = 1 - решение, тогда х = -2 и у = -1 - тоже решение.

Ответ: (2;1); (-2;-1)

8.Примеры уравнений второй степени с тремя неизвестными.

Рассмотрим уравнение второй степени с тремя неизвестными: х2 + у2= z2.

Геометрически решение этого уравнения в целых числах можно истолковать как нахождение всех пифагоровых треугольников, т.е. прямоугольник треугольников, у которых и катеты х,у и гипотенуза z выражаются целыми числами.

По формуле х = uv, y =, z =, где u и v - нечетные взаимно простые числа (u > v > 0) можно найти те решения уравнения х² + у² = z², в которых числа х,у и z не имеют общих делителей (т.е. взаимно простые).

Для начальных значений u и v формулы приводят к следующим часто встречающимся равенствам:

32 + 42 = 52 (u = 1, v = 3), 52 + 122 = 132 (u = 1, v = 5), 152 + 82 = 172 (u = 3, v = 5)

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

III Решение уравнений в целых числах из Единого государственного

экзамена ((задания С6).

- Решить в целых числах уравнение ху = х + у.

Решение:

Данное уравнение можно записать в виде

ху - х - у + 1 = 1, или (х - 1)(у - 1) = 1.

Произведение двух целых чисел равно 1, значит, оба равны +1 или - 1;

следовательно, или х - 1 = у - 1 = 1 и х = у =2, или х - 1 = у - 1 = -1 и х = у = 0.

Ответ: х= 0; у= 0; х= 2; у= 2.

- Решить в целых числах уравнение 6х+5у= 74.

Решение:

Перепишем данное уравнение так: 6х- 24 = 50 - 5у, т.е. 6(х- 4)=5(10 - у), откуда имеем х- 4 = 5и, 10- у=6v и, следовательно, v=и. Итак, х= 4 + 5и, т.е. 4 + 5и 0, откуда и - 4/5;

аналогично 10 - у= 6и, т.е. 10 - 6и 0, откуда и 5/3, значит, и = 0 или и = 1.

При и = v = 0 получим 10 = у, где у - целое, что неверно. Пусть и = v = 1, тогда х= 9, у= 4.

Ответ:

-Решить в целых числах уравнение 19х+ 28у= 729.

Решение: Так как (18х+ 27у) + ( х+ у) = 729, то х+ у делится на 3, поэтому х = 3и, у = 3v и 19и + 28v= 81. Повторяя рассуждения, получим и = 3t, v = 3s и 19t+ 28s= 9.Последнее уравнение, очевидно, не имеет решений в целых числах, а значит, и исходное уравнение решений не имеет.

-Решить в натуральных числах уравнение + =10/7.

Решение:

Первое решение. Разложим 10/7 в цепную дробь: =1+ .

Из уравнения х+= получим х +=,

и из единственности разложения рационального числа в цепную дробь следует х=1, у=2, z=3.

Второе решение. Преобразуем уравнение х += 1 + .

Тогда х - целая, - дробная часть, поэтому

Из второго уравнения следует или у + = 2 + , откуда у = 2, z = 3.

Ответ: х = 1, у = 2, z = 3.

- Решить в натуральных числах уравнение х + y + z = xyz.

Решение:

Пусть хz, тогда х + у + z 3z, а так как x + y + z = xyz, то xyz 3z или ху 3.

Если бы х = у = z, то z= 3z или z= 3, что невозможно при целом z.

Значит, хотя бы два из чисел х, у, z неравные, поэтому ху < 3, т.е. ху = 2, либо ху = 1.

Если ху = 2, то х = 1, у = 2, и из исходного уравнения найдем z = 3.

Если бы ху = 1, то х = у = 1, и из исходного уравнения получим 2 + z = z, что невозможно.

Из найденного уравнения х = 1, у = 2,z = 3 найдем остальные перестановками.

Ответ: (1; 2; 3), (1; 3; 2), (2; 1; 3),(2; 3; 1), (3; 1; 2), (3; 2; 1).