Алгоритм Эвклида

Алгоритм Эвклида

Сообщение EgorovAD MEPhI » 09 дек 2013, 08:35

Алгоритм Эвклида
Древнегреческие математики называли этот алгоритм ἀνθυφαίρεσις или ἀνταναίρεσις — «взаимное вычитание». Этот алгоритм не был открыт Евклидом, так как упоминание о нём имеется уже в Топике Аристотеля.
Смысл алгоритма заключается в том, что два любых числа a и b могут быть представлены в следующей форме:
Код: выделить все
a=q_0*b+r_1
b=r_1*q_1+r_2
r_1=r_2*q_2+r_3

r_(n-2)=r_(n-1)*q_(n-1)+r_n
r_(n-1)=r_n*q_n
НОД(a,b)=r_n


Существование таких r и q эквивалентно возможности деления целого числа на другое целое не нулевое число с остатком.
Верность последнего утверждения следует из следующего равенства:
Код: выделить все
НОД(a,b)=НОД(b,r),если a=b*q+r.

Докажем это

Необходимость

Пусть существует такое k, которое является делителем и числа a и числа b, т.е.:
Код: выделить все
a=k*t,   b=k*s.

Но тогда, по определению числа r:
Код: выделить все
r=a-b*q=k(t-b*s),

r тоже делится на k.

Достаточность
Если b,r делится на некоторое k, то их взвешенная целыми коэффициентами сумма тоже делится на k.
EgorovAD MEPhI
Администратор
 
Сообщений: 155
Зарегистрирован: 04 ноя 2011, 11:49

Вернуться в Алгоритмы

Кто сейчас на форуме

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

cron