Skip to main content

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

Задание

С помощью алгоритма Евклида найдите наибольший общий делитель чисел \(\displaystyle 50\) и \(\displaystyle 138\):

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

Решение

Алгоритм

Алгоритм Евклида для НОД(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{НОД}(50, 138)\).

 

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

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

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

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

 

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

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

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

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

 

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

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

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

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

 

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

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

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

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

 

Ответ: \(\displaystyle \text{НОД}(50, 138)=2\).