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

Делимость чисел

7 класс

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

НОД = наибольший общий делитель двух натуральных чисел – это наибольшее число, на которое оба исходных числа делятся без остатка.

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

НОД(a, b)= НОД(a-b, b)= НОД(a, b-a)

Заменяем большее из двух чисел разностью большего и меньшего до тех пор, пока они не станут равны. Это и есть НОД.

Пример :

НОД (18, 45) = НОД (18, 45-18) = НОД (18, 27)= НОД (18, 9) = =НОД(9,9)=9

Задача № 1

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

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

1) НОД (123, 82) =

= НОД (123-82, 82) =

= НОД (41, 82)=

= НОД (41, 82 – 41) = 41

2) 123 : 41 = 3 (апельсина)

3) 82 : 41 = 2 (яблока)

Ответ: 41 ребенок; 3 апельсина; 2 яблока.

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

Евклид

(365-300 до. н. э.)

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

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

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

Пример: Найти НОД (451, 287).

451 : 287 = 1 (остаток 123)

287 : 164 = 1 (остаток 6)

123 : 41 = 3 (остаток 0)

Конец: НОД – это последний, не равный нулю остаток.

НОД (451, 287) = 41

Найти НОД (357;273).

НОД(357,273) =21

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

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

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

НОК (14, 28) = 28

НОК (18,36) = 36

Найдите НОК (12 , 18)

12 | 2 18 | 2

6 | 2 9 | 3

3 | 3 3 | 3

1 1

12 = 2*2*3

18 = 2*3*3

НОК (12, 18) = 2*3 = 6

Задача № 2

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

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

НОК (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) = 2*2*3*5 = 60

Ответ: через 60 суток.

ДОМАШНЕЕ ЗАДАНИЕ

стр.47-53 (учить теорию), № 177 (г - и)

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