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