Skip to main content

Теория: Алгоритм Евклида

Задание

С помощью алгоритма Евклида найдите наибольший общий делитель чисел 5 и 30:

\text{НОД}(5,30)=

Решение

Алгоритм

Алгоритм Евклида для НОД(a, b)

1. Пусть b>a. Делим большее b на меньшее a с остатком:

b=a\cdot n+ {\bf r}.

2. \text{НОД}(a,b)=\text{НОД}(a,{\bf r}).

3. Если {\bf r}=0, то \text{НОД}(a,{\bf r})=a. Если {\bf r}\not=0, то ищем \text{НОД}(a,{\bf r}) (но теперь a>{\bf r}).

 

В нашем случае нам надо найти наибольший общий делитель чисел 5 и 30:

\text{НОД}(5,30)= \, ?

1. Так как 30 > 5, то делим 30 на 5 с остатком: 30=5\cdot 6+{\bf 0}.

2. \text{НОД}(5,30)=\text{НОД}(5,{\bf 0}).

3. \text{НОД}(5,{\bf 0})=5.

Ответ: \text{НОД}(5,30)=5.