Skip to main content

Алгоритм Евклида

• Демо - режим •
1
2
3
4
5
6
7
8
9
10

В демонстрационном режиме вы можете решить до 10 задач в день бесплатно.
После регистрации вы получите неделю бесплатного доступа ко всем разделам сайта!

 
 
Теория :: Пример

С помощью алгоритма Евклида найдите наибольший общий делитель чисел 5 и 30:

\text{НОД}(5,30)=

Теория :: Решение

Алгоритм

Алгоритм Евклида для НОД(a, b)

1. Пусть b>a. Делим большее b на меньшее a с остатком:

b=a\cdot n+ {\bf r}.

2. \text{НОД}(a,b)=\text{НОД}(a,{\bf r}).

3. Если {\bf r}=0, то \text{НОД}(a,{\bf r})=a. Если {\bf r}\not=0, то ищем \text{НОД}(a,{\bf r}) (но теперь a>{\bf r}).

 

В нашем случае нам надо найти наибольший общий делитель чисел 5 и 30:

\text{НОД}(5,30)= \, ?

1. Так как 30 > 5, то делим 30 на 5 с остатком: 30=5\cdot 6+{\bf 0}.

2. \text{НОД}(5,30)=\text{НОД}(5,{\bf 0}).

3. \text{НОД}(5,{\bf 0})=5.

Ответ: \text{НОД}(5,30)=5.

Понятно, дальше  
Учебные блоки

1 /  4

Было проблемных задач: 0
0 из 100