Объясните доказательство свойства НОД

Лень писать. Читай статью https://ru.wikipedia.org/wiki/Алгоритм_Евклида#Алгоритм_Евклида_для_целых_чисел
там всё подробно и понятно изложено

Ну это только если Кейн знает

Рассмотрим множество общих делителей a и b и обозначим его D1, аналогично D2 - множество общих делителей b и c
1)Рассмотрим произвольный элемент d из D1: так как d делит и а и b, то он делит и a-bq=c => d является делителем c, значит он принадлежит D2
Отсюда следует что множество D1 является подмножеством D2
2) рассмотрим произвольный элемент d из D2, он делит b и c => он делит bq+c=a => d является делителем а => d принадлежит d1 => D2 является подмножеством D1, а значит множества делителей D1 и D2 совпадают и следовательно совпадают и их наибольшие элементы.
Если интересуетесь элементарной теорией чисел рекомендую лекции на teach-in от Николая Германовича Мощевитина, а так же если вы очень в себе уверены - книжку Ю.В. Нестеренко Теория Чисел)

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

Предположим, у нас есть числа a, b и c, такие что a = bq + c, где q - целое число, а c - остаток при делении a на b.

Давайте рассмотрим множество общих делителей чисел a и b. Если d является делителем и a, и b, то оно также является делителем и bq, так как bq является произведением целых чисел.

Теперь рассмотрим множество общих делителей чисел b и c. Если d является делителем и b, и c, то оно также является делителем и bq и c.

Из этого следует, что множество общих делителей чисел a и b содержит все делители чисел b и c, а множество общих делителей чисел b и c содержит все делители чисел a и b.

Таким образом, множество общих делителей чисел a и b совпадает со множеством общих делителей чисел b и c.

Отсюда следует, что НОД (a, b) = НОД (b, c), так как оба числа являются наибольшими общими делителями соответствующих пар чисел.

Это доказательство основано на свойстве деления с остатком, которое позволяет выразить одно число через другое с помощью остатка от деления.