Дата публикации: 26.02.2025

Доказательство тождеств D(a, b) = D(a - bq, b) = D(b, r)

Содержимое статьи:

Подзаголовок: Введение В теории чисел наибольший общий делитель (НОД) двух целых чисел a и b обозначается как D(a, b) и представляет собой наибольшее целое число, которое делит и a, и b.
Подзаголовок: Доказательство Теорема 1: Если a = bq + r, то D(a, b) = D(a - bq, b)

Доказательство:
Пусть d = D(a, b).
Тогда d делит a и b, т. е. существуют целые числа x и y такие, что a = xd и b = yd.
Подставив a = bq + r в уравнение a = xd, получим:
```
bq + r = xd
```
Вычитая из обеих частей yd, получим:
```
bq - yd + r = xd - yd
```
Упрощая, получим:
```
(b)(q - y) + r = (x - y)d
```
Таким образом, d делит a - bq и b, поэтому d <= D(a - bq, b).
Поскольку d = D(a, b), то D(a, b) <= D(a - bq, b).
Аналогично можно доказать, что D(a - bq, b) <= D(a, b).
Отсюда следует, что D(a, b) = D(a - bq, b).
Теорема 2: Если a = bq + r, то D(a, b) = D(b, r)
Доказательство:
По теореме 1, D(a, b) = D(a - bq, b).
Но a - bq = r, поэтому D(a, b) = D(r, b).
Отсюда следует, что D(a, b) = D(b, r).