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

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

Skip to main content

Теориясы: ЕКОЕ және Евклид алгоритмі

Тапсырма

Евклид алгоритмі мен

\(\displaystyle \text{ЕКОЕ}(a,b)= \frac{a\cdot b}{\text{ЕҮОБ}(a, b)}\).

формуласын қолдана отырып, \(\displaystyle 5\) және \(\displaystyle 30\) сандарының ең кіші ортақ еселігін табыңыз.

 

\(\displaystyle \text{ЕКОЕ}(5, 30) = \frac{5\cdot 30}{\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 \text{ЕҮОБ}(a, b)\) табылса, онда

\(\displaystyle \text{ЕКОЕ}(a, b) = \frac{a\cdot b}{\text{ЕҮОБ}(a, b)}\).

 

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

 

\(\displaystyle \text{ЕКОЕ}(5, 30)\) табайық:

\(\displaystyle \text{ЕКОЕ}(5, 30)= \frac{5\cdot 30}{\text{ЕҮОБ}(5, 30)}=\frac{150}{5}=30\).

 

Жауабы: \(\displaystyle \text{ЕКОЕ}(5, 30)=30\).