Паскаль. Основы программирования


Задачи с применением НОД - часть 2


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

Решение

1) Применим алгоритм Евклида и найдем НОД(15, 37):

НОД(15, 37) = 1

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

, т. е.

x0

= 5, y0 = -2.

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

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

Решение

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

Теорема 4. Если в уравнении ах + by = с (a, b) = d > 1 и c делится на d, то оно равносильно уравнению а1х + b1у = c1, в котором (a1, b1) = 1.

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

где x0, y0 - целое решение уравнения ах + by = 1, t - любое целое число.

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

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

2) составляется общая формула целых решений данного уравнения:

где x0, y0 - целое решение уравнения ах + by = 1, t—любое целое число.

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

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

Решение

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

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

 

.

3) Найдем решения данного уравнения по формулам:

 

Ответ:

Для составления программы решения неопределенных уравнений, нам предстоит решить три задачи:

1) нахождение НОД, для последующего выяснения числа решений уравнения, - это легко сделать с помощью известной процедуры;

2) нахождение одного решения уравнения вида ах + by = 1 и




Начало  Назад  Вперед



Книжный магазин