Евклид алгоритмін қолдана отырып, \(\displaystyle 17\) және \(\displaystyle 18\) сандарының ең үлкен ортақ бөлгішін табыңыз:
\(\displaystyle \text{ЕҮОБ}(17, 18) = \)
ЕҮОБ (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{ЕҮОБ}(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\).