С помощью алгоритма Евклида найдите наибольший общий делитель чисел \(\displaystyle 50\) и \(\displaystyle 138\):
\(\displaystyle \text{НОД}(50, 138) = \)
Алгоритм Евклида для НОД(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 \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\).