Skip to main content

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

Задание

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

\(\displaystyle \text{НОД}(5,30)=\)

Решение

Алгоритм

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

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 5\) и \(\displaystyle 30\):

\(\displaystyle \text{НОД}(5,30)= \, ?\)

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

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

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

Ответ: \(\displaystyle \text{НОД}(5,30)=5\).