Question

Докажите, что для любых целых чисел a и b НОД (a,b)=НОД(а,а-b). Нужно подробное решение, ПОЖАЛУЙСТА

Answer 1

Допустим, что для чисел a и b НОД(a,b) = n
Тогда
a = x*n
b = y*n
x и y-это некоторый множитель, при умножении которого на НОД получается само число.
Подставим эти значения в НОД, получится НОД(x*n,x*n-y*n) или НОД(x*n,n*(x-y)), если мы вынесем общий множитель за скобку.
Нетрудно заметить, что числа a и b имеют одинаковый множитель n значит они оба делятся на n  (n - этоНОД(a,b) ).
ЧТД

Answer 2

Для доказательства этого утверждения воспользуемся свойствами наибольшего общего делителя (НОД) и алгоритмом Евклида.

Для начала, предположим, что a и b - два целых числа, и d = НОД(a, b). Это означает, что d является наибольшим положительным целым делителем как a, так и b. Теперь рассмотрим НОД(a, a - b).

По определению НОД(a, a - b) - это наибольший положительный целый делитель числа a и (a - b). Мы можем выразить (a - b) как a - (a - b), что равносильно a - a + b, что просто равно b.

Теперь у нас есть НОД(a, b) и НОД(a, a - b), и мы хотим показать, что они равны друг другу, то есть d = НОД(a, b) = НОД(a, a - b).

Давайте воспользуемся алгоритмом Евклида для нахождения НОД(a, b) и НОД(a, a - b):

1. Пусть d1 = НОД(a, b) и d2 = НОД(a, a - b).

2. По алгоритму Евклида, мы начнем с последовательных делений. Начнем с деления a на b и затем a на (a - b), сохраняя остаток при каждом делении.

3. После первого деления мы получим остаток r1, который будет равен a % b (где % обозначает операцию взятия остатка).

4. После второго деления мы получим остаток r2, который будет равен a % (a - b).

5. По основному свойству НОД, НОД(a, b) = НОД(b, r1) и НОД(a, a - b) = НОД(a - b, r2).

6. Нам нужно показать, что r1 = r2, чтобы доказать, что d1 = d2.

Теперь давайте рассмотрим r1 и r2:

r1 = a % b r2 = a % (a - b)

Мы видим, что r1 и r2 вычисляются как остатки от деления a на b и (a - b) соответственно. Но если вы внимательно посмотрите, то (a - b) - это то же самое, что b. То есть a % (a - b) эквивалентно a % b.

Таким образом, мы видим, что r1 = r2, и поэтому d1 = d2. Это означает, что НОД(a, b) = НОД(a, a - b) для любых целых чисел a и b, что и требовалось доказать.