|
Найти линейное представление наибольшего общего делителя чисел 1232 и 1672.
Решение.
Составим равенства алгоритма Евклида:
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 в виде линейной комбинации чисел а и в.
Достарыңызбен бөлісу: |
