С помощью алгоритма Евклида найдите наибольший общий делитель чисел \(\displaystyle 35\) и \(\displaystyle 45{\small .}\)
\(\displaystyle \text{НОД}(35, 45) = \)
Алгоритм Евклида для НОД(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{НОД}(35, 45){\small .}\)
Шаг 1. Применим алгоритм Евклида к \(\displaystyle \text{НОД}(35, 45){\small .}\)
1. Так как \(\displaystyle 45> 35{\small ,}\) то делим \(\displaystyle 45\) на \(\displaystyle 35\) с остатком: \(\displaystyle 45=35\cdot 1+{\bf 10}{\small .}\)
2. \(\displaystyle \text{НОД}(35, 45)=\text{НОД}(35,{\bf 10}){\small .}\)
3. Так как \(\displaystyle {\bf 10} =\not 0{\small ,}\) то переходим к шагу \(\displaystyle 2{\small .}\)
Шаг 2. Применим алгоритм Евклида к \(\displaystyle \text{НОД}(35, 10)=\text{НОД}(10, 35){\small .}\)
1. Так как \(\displaystyle 35> 10{\small ,}\) то делим \(\displaystyle 35\) на \(\displaystyle 10\) с остатком: \(\displaystyle 35=10\cdot 3+{\bf 5}{\small .}\)
2. \(\displaystyle \text{НОД}(10, 35)=\text{НОД}(10,{\bf 5}){\small .}\)
3. Так как \(\displaystyle {\bf 5} =\not 0{\small ,}\) то переходим к шагу \(\displaystyle 3{\small .}\)
Шаг 3. Применим алгоритм Евклида к \(\displaystyle \text{НОД}(10, 5)=\text{НОД}(5, 10){\small .}\)
1. Так как \(\displaystyle 10> 5{\small ,}\) то делим \(\displaystyle 10\) на \(\displaystyle 5\) с остатком: \(\displaystyle 10=5\cdot 2+{\bf 0}{\small .}\)
2. \(\displaystyle \text{НОД}(5, 10)=\text{НОД}(5,{\bf 0}){\small .}\)
3. \(\displaystyle \text{НОД}(5,{\bf 0})=5{\small .}\)
Ответ: \(\displaystyle \text{НОД}(35, 45)=5{\small .}\)