Изменения

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