НОД

[xyzman]

Верно ли такое равенство:
$(a+b,a)=(b,a)$
для любых натуральных a и b

[bot]

Для любых целых $t,a,b$ справедливо $(ta+b, a) = (b, a)$ - на этом простом замечании основан алгоритм Евклида.

[xyzman]

А как обосновать справедливость этого простого замечания?

[Sonic86]

Это кстати очень удобный способ вычислять НОД в некоторых случаях.
Доказывается по определению алгоритма Евклида.
Обозначьте первый остаток для $(a,b)$ как $r_1$ и тогда первый остаток для $(a+b,b)$ будет тоже равен $r_1$. То есть будет $(a,b) = (r_1 ,b)$ и $(a+b,b) = (r_1 ,b)$, откуда и следует то, что надо.

З.Ы. Как-то на алгебре я так НОД вычислил, а мне алгебраичка сказала, что так низя, пришлось доказывать

[PAV]

Любой делитель одной пары является делителем другой и наоборот.