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


Задачи с применением НОД


Пример 5. Один мастер делает на длинной ленте пометки синим карандашом от ее начала через каждые 36 см. Другой мастер делает пометки красным карандашом от начала через каждые 25 см. Может ли синяя пометка оказаться на расстоянии 1 см от какой-нибудь красной?

Решение

Ответ: может. Например, 9-я синяя пометка и 13-я красная находятся друг от друга на расстоянии 1 см, так как 13

25 - 9
36 = 1.

В этой задаче нам фактически надо было найти какое-нибудь решение в целых числах одного из уравнений 25x - 36y = 1, 25x - 36y = - 1

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

 если
 Продемонстрируем ее на нашей задаче. Выпишем все шаги алгоритма Евклида для нахождения НОД(36; 25):

    36 = 25

1 + 11; 25 = 11
2 + 3; 11 = 3
3 + 2; 3 = 2
1 + 1.

 Перепишем эту цепочку равенств по остаткам:

11 = 36 - 25

1; 3 = 25 - 11
2; 2 = 11 - 3
3; 1 = 3 - 2
1.

Тогда получим:

               1 = 3 - (11 - 3

3) = 3
4 - 11 = (25-11
2)
4 - 11 = 25
4 - 11
9 =

= 25

4 - 11
9 = 25
4 - (36 - 25)
9 = 25
13 - 36
9.

В результате получается равенство 25

13 - 36
9 = 1, дающее одно решение уравнения 25x - 36y = 1.

Определение. Неопределенные уравнения - уравнения, содержащие более одного неизвестного. 

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

Уравнения вида ax + by = c, где a, b, c - целые числа, отличные от нуля

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

.

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

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

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




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