СДЕЛАЙТЕ СВОИ УРОКИ ЕЩЁ ЭФФЕКТИВНЕЕ, А ЖИЗНЬ СВОБОДНЕЕ

Благодаря готовым учебным материалам для работы в классе и дистанционно

Скидки до 50 % на комплекты
только до

Готовые ключевые этапы урока всегда будут у вас под рукой

Организационный момент

Проверка знаний

Объяснение материала

Закрепление изученного

Итоги урока

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

Категория: Математика

Нажмите, чтобы узнать подробности

Теоремы о числе решений линейного диофантового уравнения

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

 

Теорема 1. Если в уравнении (ax + by) = 1,  (a,b) = 1, то уравнение имеет, по крайней мере, одно решение.

Теорема 2. Если в уравнении (ax + by) = с , (a,b) = d >1  и с не делится на d , то уравнение целых решений не имеет.

Теорема 3. Если в уравнении (ax + by) = с , (a,b) = d >1 , и  d⋮c, то оно равносильно уравнению (a1x + b1y) = 1 , в котором (a1,b1) = 1.

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

x = x0c + bt

y = y0c - at

где х0 , у0 – целое решение уравнения  (ax + by) = 1,  t- любое целое число.

 

Cформулируем на основании этих теорем алгоритм решения уравнения

 

Алгоритм решения уравнения в целых числах

Сформулированные теоремы позволяют составить следующий алгоритм решения в целых числах уравнения вида (ax + by) = с .

1. Найти наибольший общий делитель чисел a и b ,

если (a,b) = d >1  и с не делится на d , то уравнение целых решений не имеет;

если (a,b) = d >1  и  c⋮d , то переходим к этапу 2.

2. Разделить почленно уравнение (ax + by) = с  на d, получив при этом уравнение (a1x + b1y) = c1 , в котором (a1,b1) = 1.

3. Найти целое решение (х0 , у0 ) уравнения (a1x + b1y) = 1 путем представления 1 как линейной комбинации чисел  a и b ;

4. Составить общую формулу целых решений данного уравнения

x = x0c + bt

y = y0c - at

где х0 , у0 – целое решение уравнения (ax + by) = 1, t- любое целое число.

 

Способы решения уравнений

При решении уравнений в целых и натуральных числах можно условно выделить следующие методы:

1. Алгоритм Евклида.

2. Способ перебора вариантов.

3. Метод разложения на множители.

4. Метод остатков.

5. Решение уравнений в целых числах как квадратных относительно какой-либо переменной.

6. Цепные дроби.

7. Метод бесконечного спуска.

 

Пример. Решить уравнение в целых числах 407х – 2816y = 33.

Воспользуемся составленным алгоритмом.

1. Используя алгоритм Евклида, найдем наибольший общий делитель чисел 407 и 2816:

2816 = 407·6 + 374;

407 = 374·1 + 33;

374 = 33·11 + 11;

33 = 11·3

Следовательно (407,2816) = 11, причем 33 делится на 11

2. Разделим обе части первоначального уравнения на 11, получим уравнение 37х – 256y = 3, причем (37, 256) = 1

3. С помощью алгоритма Евклида найдем линейное представление числа 1 через числа 37 и 256.

256 = 37·6 + 34;

37 = 34·1 + 3;

34 = 3·11 + 1

Выразим 1 из последнего равенства, затем последовательно поднимаясь по равенствам будем выражать 3; 34 и полученные выражения подставим в выражение для 1.

1 = 34 – 3·11 = 34 – (37 – 34·1) ·11 = 34·12 – 37·11 = (256 – 37·6) ·12 – 37·11 =

– 83·37 – 256·(–12)

Таким образом, 37·(– 83) – 256·(–12) = 1, следовательно пара чисел х0 = – 83 и у0 = – 12 есть решение уравнения 37х – 256y = 3.

4. Запишем общую формулу решений первоначального уравнения

х = - 83с + bt = -83*3 - 256 t = -249 - 256t

y = -12c - at = -12*3 - 37t = -36 - 37t

где t - любое целое число.

 

Метод остатков

Пример.  Решить в целых числах уравнение:

а) x3 + y3 = 3333333;

б) x3 + y3 = 4(x2y + xy2 + 1).

Решение.

а) Так как x3 и y3 при делении на 9 могут давать только остатки 0, 1 и 8 , то x3+ y3 может давать только остатки 0, 1, 2, 7 и 8. Но число 3333333 при делении на 9 даёт остаток 3. Поэтому исходное уравнение не имеет решений в целых числах.

Ответ: целочисленных решений нет.

б) Перепишем исходное уравнение в виде (x + y)3 = 7(x2y + xy2) + 4. Так как кубы целых чисел при делении на 7 дают остатки 0, 1 и 6, но не 4, то уравнение не имеет решений в целых числах.

Ответ: целочисленных решений нет.


Скачать

Рекомендуем курсы ПК и ППК для учителей

Вебинар для учителей

Свидетельство об участии БЕСПЛАТНО!