Поверните устройство

Поверните устройство

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\).