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

 

Алгоритм Евклида дает правило вычисления наибольшего общего делителя

 

(НОД) 2-х натуральных чисел. (a,b)= d , где d – НОД НОК – наименьшее общее кратное

[a,b] = k, где k – НОК

 

Наибольший общий делитель (НОД) чисел а и b - это наибольшее целое число d, на которое и а, и b делятся: d = НОД(а, b). Если НОД(а, b)= 1, то числа а и b взаимно простые.

Наименьшим общим кратным (НОК) нескольких натуральных чисел называется наименьшее натуральное число, которое делится без остатка на каждое из данных чисел. НОК двух чисел a и b можно вычислить на знании НОД(a, b) по формуле: , т.е.

 

.

 

Существует рекуррентная запись запись алгоритма Евклида, которая заканчивается за определенное число шагов.

 

 

Разложим большее через меньшее b< a

 

 

 

 

 

…………………….

 

 

 

 

 

и

 

Существует теорема что предпоследний остаток и есть НОД

 

т.е. – НОД

 

На основание теоремы сделаем вывод что

 

 

Пример: a= 525, b= 231

 

525 231

 

462 2

 

231 63

 

189 3

 

63 42

 

42 1

 

42 21 - НОД

 

42 2

 

 

Пример2: a=1234, b= 54

 

1234= 54*22+46

 

54= 46*1+8

 

46= 8*5+6

 

8= 6*1+2

 

6=2*3+0

 

 

(a,b)=d

Расширенный алгоритм Евклида (РАЕ)

 

d можно разложить по формуле: