Skip to main content

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

Задание

Найдите наименьшее общее кратное чисел \(\displaystyle 35\) и \(\displaystyle 45\), используя алгоритм Евклида и формулу

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

 

\(\displaystyle \text{НОК}(35, 45) = \frac{35\cdot 45}{\text{НОД}(35, 45)}=\)

Решение

Алгоритм

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

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

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

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

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

 

Правило

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

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

 

Найдем \(\displaystyle \text{НОД}(35, 45)\):

Шаг 1. Применим алгоритм Евклида к \(\displaystyle \text{НОД}(35, 45)\).

1. Так как \(\displaystyle 45> 35\), то делим \(\displaystyle 45\) на \(\displaystyle 35\) с остатком: \(\displaystyle 45=35\cdot 1+{\bf 10}\).

2. \(\displaystyle \text{НОД}(35, 45)=\text{НОД}(35,{\bf 10})\).

3. Так как \(\displaystyle {\bf 10} =\not 0\), то переходим к шагу \(\displaystyle 2\).

 

Шаг 2. Применим алгоритм Евклида к \(\displaystyle \text{НОД}(35, 10)=\text{НОД}(10, 35)\).

1. Так как \(\displaystyle 35> 10\), то делим \(\displaystyle 35\) на \(\displaystyle 10\) с остатком: \(\displaystyle 35=10\cdot 3+{\bf 5}\).

2. \(\displaystyle \text{НОД}(10, 35)=\text{НОД}(10,{\bf 5})\).

3. Так как \(\displaystyle {\bf 5} =\not 0\), то переходим к шагу \(\displaystyle 3\).

 

Шаг 3. Применим алгоритм Евклида к \(\displaystyle \text{НОД}(10, 5)=\text{НОД}(5, 10)\).

1. Так как \(\displaystyle 10> 5\), то делим \(\displaystyle 10\) на \(\displaystyle 5\) с остатком: \(\displaystyle 10=5\cdot 2+{\bf 0}\).

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

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

Таким образом, \(\displaystyle \text{НОД}(35, 45)=5\).

 

Найдем \(\displaystyle \text{НОК}(35, 45)\):

\(\displaystyle \text{НОК}(35, 45)= \frac{35\cdot 45}{\text{НОД}(35, 45)}=\frac{1575}{5}=315\).

 

Ответ: \(\displaystyle \text{НОК}(35, 45)=315\).