Как доказать, что (Наибольший общий делитель) НОД (m, n) = НОД (x, y) Пусть x, y, m, n, a, b, c, d ∈ Z исполняют m = ax + by и n = cx + dy, где ad - bc = 1. Теперь как доказать что тогда НОД (m, n) =НОД (x, y).

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

Для начала заметим, что НОД(m, n) делит m и n, так как их общий делитель также делит их линейные комбинации.

Также заметим, что НОД(x, y) также делит x и y, так как их общий делитель также делит линейные комбинации x и y.

Теперь докажем, что НОД(m, n) и НОД(x, y) равны.

Пусть d - НОД(m, n) и g - НОД(x, y).

Так как d делит m и n, то d делит их линейную комбинацию, то есть d делит ax + by = m и cx + dy = n.

Таким образом НОД(m, n) делит НОД(x, y).

Аналогично, так как g делит x и y, то g делит их линейную комбинацию, то есть g делит m = ax + by и n = cx + dy.

Таким образом НОД(x, y) делит НОД(m, n).

Так как оба числа делят друг друга, то они равны НОД(m, n) = НОД(x, y).