Skip to main content

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

• Демо - режим •
1
2
3
4
5
6
7
8
9
10

В демонстрационном режиме вы можете решить до 10 задач в день бесплатно.
После регистрации вы получите неделю бесплатного доступа ко всем разделам сайта!

 
 
Теория :: Пример

Найдите наименьшее общее кратное чисел 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.

Понятно, дальше  
Учебные блоки

1 /  4

Было проблемных задач: 0
0 из 100