Изменения

|proof=Пусть <tex> k </tex> — любой общий делитель чисел <tex> a </tex> и <tex> b</tex>, не обязательно максимальный, тогда <tex> a = t_1 k </tex> ; <tex> b = t_2 k; </tex> где <tex> t_1 </tex> и <tex> t_2 </tex> — целые числа из определения.# Тогда <tex> k </tex> также общий делитель чисел <tex> b </tex> и <tex> r</tex>, так как <tex> b </tex> делится на <tex> k </tex> по определению, а <tex>r = a - bq = (t_1 - t_2 q)k </tex> (выражение в скобках есть целое число, следовательно, <tex> k </tex> делит <tex> r </tex> без остатка)# Обратное также верно и доказывается аналогично 2) — любой делитель <tex> b </tex> и <tex> r </tex> так же является делителем <tex> a </tex> и <tex> b</tex>.# Следовательно, все общие делители пар чисел <tex> a</tex>,<tex> b </tex> и <tex> b</tex>,<tex> r </tex> совпадают. Другими словами, нет общего делителя у чисел <tex> a</tex>,<tex> b</tex>, который не был бы также делителем <tex> b</tex>,<tex> r</tex>, и наоборот.