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