Skip to main content

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

Задание

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

\(\displaystyle \text{НОД}(17, 18) = \)

Решение

Алгоритм

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

 

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

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

2. \(\displaystyle \text{НОД}(17,18)=\text{НОД}(17,{\bf 1})\).

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

 

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

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

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

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

 

Ответ: \(\displaystyle \text{НОД}(17, 18)=1\).