Алгоритм Евклида. НОД и НОК

1. Записать в тетради.

Двадцатое февраля.
Классная работа.
Алгоритм Евклида для решения задач в
целых числах.

2.

Наибольшее натуральное число, на которое
делятся без остатка числа a и b, называют
наибольшим общим делителем этих чисел.

3.

4. Вычисление НОД

НОД = наибольший общий делитель двух натуральных чисел –
это наибольшее число, на которое оба исходных числа делятся
без остатка.
Вычисление НОД
НОД(a, b)= НОД(a-b, b)= НОД(a, b-a)
Заменяем большее из двух чисел разностью большего и
меньшего до тех пор, пока они не станут равны. Это и есть
НОД.
Пример :
НОД (18, 45) = НОД (18, 45-18) = НОД (18, 27)= НОД (18, 9) =
=НОД(9,9)=9

5.

Задача № 1
Ребята получили на новогодней елке одинаковые
подарки. Во всех подарках вместе было 123
апельсина и 82 яблока. Сколько ребят
присутствовало на елке? Сколько апельсинов и
сколько яблок было в каждом подарке?
(записать решение задачи)

6. Решение задачи

1) НОД (123, 82) =
= НОД (123-82, 82) =
= НОД (41, 82)=
= НОД (41, 82 – 41) = 41
2) 123 : 41 = 3 (апельсина)
3) 82 : 41 = 2 (яблока)
Ответ: 41 ребенок; 3 апельсина; 2 яблока.

7. АЛГОРИТМ ЕВКЛИДА

Евклид
(365-300 до. н. э.)
Алгоритм Евклида - это алгоритм нахождения наибольшего
общего делителя (НОД) двух целых неотрицательных чисел.

8.

Однако существует способ нахождения НОД, не
требующий знания всех простых множителей этих
чисел. Этот способ называется алгоритмом
Евклида:
•большее число делят на меньшее,
•затем меньшее на первый остаток,
•затем первый остаток – на второй остаток и
т.д.,пока не получится 0.
•Тогда последний остаток – это НОД.

9.

Пример. (разобрать):
Найти НОД (451, 287).
451 : 287 = 1 (остаток 123)
287 : 164 = 1 (остаток 6)
123 : 41 = 3 (остаток 0)
Конец: НОД – это последний, не равный нулю
остаток.
НОД (451, 287) = 41

10. Найти НОД (357;273) (разобрать и записать).

НОД(357,273) =21

11.

Наименьшим общим
кратным натуральных
чисел a и b называют
наименьшее
натуральное число,
которое кратно и a, и
b.

12. Особые случаи нахождения НОК

• Наименьшее общее кратное взаимно простых
чисел равно их произведению НОК (54, 65) = 54 ∙
65 = 3510
• Если одно из данных чисел делится на все
остальные, то это число и является наименьшим
общим кратным данных чисел
НОК (14, 28) = 28
НОК (18,36) = 36

13. Задача № 2 (разобрать и записать)

В
портовом
городе
начинаются
три
туристических теплоходных рейса, первый из
которых длится 15 суток, второй – 20 суток и
третий – 12 суток. Вернувшись в порт, теплоходы
в этот же день снова отправляются в рейс.
Сегодня из порта вышли теплоходы по всем трем
маршрутам. Через сколько суток они впервые
снова вместе уйдут в плавание?

14. Решение задачи

НОК (15, 20, 12)
15 | 3
20 | 2
12 | 2
5 |5
10 | 2
6|2
1
5 |5
3|3
1
1
15 = 3·5
20 = 2·2·5
12 = 2·2·3
НОК (15, 20, 12) = 15·2·3 = 60
Ответ: через 60 суток.

15. СПАСИБО ЗА ВНИМАНИЕ!

Домашнее задание: выучить правила
нахождения НОД и НОК, уметь их применять.
СПАСИБО ЗА ВНИМАНИЕ!