Skip to main content

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

Задание

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

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

 

\(\displaystyle \text{НОК}(50, 138) = \frac{50\cdot 138}{\text{НОД}(50, 138)}=\)

Решение

Алгоритм

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

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

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

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

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

 

Правило

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

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

 

Найдем \(\displaystyle \text{НОД}(50, 138){\small :}\)

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

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

2. \(\displaystyle \text{НОД}(50, 138)=\text{НОД}(50,{\bf 38}){\small .}\)

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

 

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

1. Так как \(\displaystyle 50> 38{\small ,}\) то делим \(\displaystyle 50\) на \(\displaystyle 38\) с остатком: \(\displaystyle 50=38\cdot 1+{\bf 12}{\small .}\)

2. \(\displaystyle \text{НОД}(38, 50)=\text{НОД}(38,{\bf 12}){\small .}\)

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

 

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

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

2. \(\displaystyle \text{НОД}(12, 38)=\text{НОД}(12,{\bf 2}){\small .}\)

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

 

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

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

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

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

Таким образом, \(\displaystyle \text{НОД}(50,138)=2{\small .}\)

 

Найдем \(\displaystyle \text{НОК}(50, 138){\small :}\)

\(\displaystyle \text{НОК}(50, 138)= \frac{50\cdot 138}{\text{НОД}(50, 138)}=\frac{50\cdot 138}{2}=50\cdot 69=3450{\small .}\)

 

Ответ: \(\displaystyle \text{НОК}(50, 138)=3450{\small .}\)