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