Skip to main content

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

Задание

Найдите наименьшее общее кратное чисел 5 и 30, используя алгоритм Евклида и формулу

\text{НОК}(a,b)= \displaystyle\frac{a\cdot b}{\text{НОД}(a, b)}.

 

\text{НОК}(5, 30) = \displaystyle\frac{5\cdot 30}{\text{НОД}(5, 30)}=

Решение

Алгоритм

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

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}).

 

Правило

Если \text{НОД}(a, b) найден, то

\text{НОК}(a, b) = \displaystyle\frac{a\cdot b}{\text{НОД}(a, b)}.

 

Найдем \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.

 

Найдем \text{НОК}(5, 30):

\text{НОК}(5, 30)= \displaystyle\frac{5\cdot 30}{\text{НОД}(5, 30)}=\displaystyle\frac{150}{5}=30.

 

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