Для a, b, c ∈ Z доказать, что gcd(a, b) = gcd(a − bc, b).Вывести верхнюю оценку числа арефметических операций расширенного алгоритма Евклида

Предыдущий
вопрос Следующий
вопрос

Для доказательства равенства gcd(a, b) = gcd(a − bc, b), предположим, что d = gcd(a, b), то есть d является наибольшим общим делителем a и b. Тогда d делит и a, и b, и любую их линейную комбинацию, в том числе a − bc. Следовательно, d также делит gcd(a − bc, b).

Обратно, предположим, что d = gcd(a − bc, b), тогда d делит и a − bc, и b. Так как d делит b, то он также делит bc, а значит d делит a − bc + bc = a. Следовательно, d также делит gcd(a, b).

Таким образом, у нас доказано равенство gcd(a, b) = gcd(a − bc, b).

Относительно числа арифметических операций расширенного алгоритма Евклида, верхняя оценка для нахождения наибольшего общего делителя двух чисел a и b равна O(log(min(a, b))), где log обозначает логарифм по основанию 2.