Нахождение НОД (a, b) с помощью алгоритма Евклида. 6-й класс

Разделы: Математика

Класс: 6

Цели урока:

  • закрепить алгоритм нахождения наибольшего общего делителя с помощью разложения на множители;
  • повторить сопутствующие определения и понятия;
  • познакомить учащихся с алгоритмом Евклида;
  • формировать навыки математической культуры

Оборудование: компьютер, проектор, экран.

Ход урока

1. Орг.момент (проверка готовности учащихся к уроку, отметка отсутствующих) (1 мин)

Презентация.

2. Устная работа: (6 мин)

1. Замените произведение степенью:

    а)3*3*3*3*3

    б) 7*7*7

    в)5*5

    г) а*а*а*а*а

  1. Вычислите: 23 ; 52 ; 33 ; 104.
  2. Найдите значение выражения: (3?3?5?11): (3?11). Какой вывод можно сделать?
  3. Выполните деление a на b, если а=170, b=35. Запишите равенством, чему равно а .

    4. Данное равенство записать в общем виде: а будет делимым, а b - делителем. Пусть частное равно q, а остаток r, тогда: а = bq + r, причем q может быть как натуральным числом, так и нулем. Любым ли числом может быть r? [ r - натуральное число, причем 0 < r < b.] Что можно сказать о числах а и b, если r = 0? Деление нацело - частный случай деления с остатком.

  4. Выясните и объясните, делится ли без остатка число а на число b, если:

а) а = 23 * 3 * 5 * 7;

b = 22 * 7

б) а = 24 * 3 * 57;

b = 27 * 3 * 54

в) а = 2 * 34 * 5 * 13;

b = 2 * 33 * 5 * 11.

3. Актуализация базовых знаний (10 мин)

1) Вопросы:

- что называют делителем числа а?

- какое число называют простым?

- что значит разложить число на простые множители?

- сформулируйте признаки делимости на 2, 3, 5, 9,10;

- приведите пример однозначного составного числа;

- верно ли, что число 77-простое число?

- почему, если одно число можно разложить на 2 простых множителя, а другое на 3 простых множителя, то эти числа не равны?

- каким числом: простым или составным является произведение двух простых чисел?

- что называется наибольшим общим делителем двух или более чисел?

- какие числа называются взаимно-простыми?

-повторить способы нахождения НОД: Для поиска НОД натуральных чисел существуют различные алгоритмы

1 способ: Если даны два числа и они сравнительно невелики, то лучший алгоритм - непосредственный перебор. Однако для больших чисел находить НОД(а;b) путем перечисления всех делителей чисел а и b - процесс трудоемкий и ненадежный.

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

2 способ: с помощью разложения чисел на множители (наиболее распространенный) (Приложение, слайд1)

2) Вычислите НОД чисел 24 и 16.

3) Разложите на простые множители числа: 875 и 8000 и вычислите НОД этих чисел.

(На примере числа 8000 повторить более простой способ разложения на простые множители чисел, оканчивающихся нулями: так как 10=2 *5, то 8000=2 * 5 * 2 * 5 *2 * 5 * 2 * 2 * 2==26 * 53)

4) Может ли НОД трех чисел быть равен 15, если их произведение равно 3000? [ нет, так как

15 = 3 * 5, значит, число 3 должно входить в разложение каждого из трех чисел. Но, 3000 = 23 * 3 * 53.]

5) Решите задачу "В класс привезли учебники: по математике 24, по истории 36 и по географии 48. Какое наибольшее число комплектов можно составить из этих книг так, чтобы в каждом было одинаковое число книг по математике, истории и географии? По сколько книг будет в каждом комплекте?"

4. Проверочная работа (Приложение, слайд 2) (6 мин)

5. Изучение нового материала (10 мин)

Учитель: изученный способ отыскания НОД(а, b) прост, понятен и удобен, но у него есть существенный недостаток: если данные числа велики, да еще не очень легко раскладываются на множители, то задача отыскания НОД(а, b) становится довольно трудной. К тому же может оказаться, что, основательно потрудившись, мы убедимся, что НОД(а, b)=1 и вроде вся работа проделана зря.

Евклид нашел замечательный способ отыскания НОД(а,b) без какой бы то ни было предварительной обработки чисел. ( Приложение, слайды 3 и 4) Впоследствии этот алгоритм стали называть алгоритмом Евклида)

Познакомимся с алгоритмом Евклида. Пусть требуется найти НОД(102;84). Разделим одно число на другое и определим остаток.

102=84 *1+18

0 <18<84

Теперь проделаем такую же операцию для чисел 84 и 18:

84=18 *4+ 12

0 <12<18

Следующий шаг - для 18 и 12:

18=12 * 1+6

0 <6<12

Теперь -для 12 и 6:

12=6 * 2+0

0-остаток. Процесс закончился.

Этот процесс не может быть бесконечным, потому что остатки убывают, оставаясь неотрицательными целыми числами, множество которых, как известно, ограничено снизу:

84 >18 > 12> 6 >0

Если присмотреться к записанным равенствам, то можно установить, что НОД всех пар чисел равны между собой (предложить учащимся подумать -почему?),

то есть НОД(102;84)=НОД(84;18)=НОД(18;12)=НОД(12;6)=6. Но число 6-последний, не равный 0 остаток.

Действительно, если с - произвольный общий делитель чисел а и b, то r = a - bq делится на c; и наоборот, если с - произвольный общий делитель чисел b и r, то а делится на с. То есть, все общие делители пар (а; b) и (b; r) совпадают, а значит, совпадают и их наибольшие общие делители.

Удобство алгоритма Евклида становится особенно заметным, если применить форму записи в виде таблицы:

102

84

18

12

6
 

1

4

1

2

В этой табличке сначала записывают исходные числа, делят в уме, записывая остатки справа, а частные -внизу, пока процесс не закончится. Последний делитель и есть НОД.

Таким образом, наибольшим общим делителем двух чисел является последний, не равный 0 остаток при делении большего числа на меньшее, то есть если a = b * q + r, то НОД(a; b) = НОД(b; r)

Такая последовательность операций и называется алгоритмом Евклида. Данный алгоритм позволяет находить НОД чисел, не разлагая их на множители (Приложение, слайд 5)

6. Упражнения(10 мин)

1. Целесообразно рассмотреть пример. Пусть надо найти НОД чисел 323 и 437. Сделать это подбором или разложением на простые множители не просто, так как ни одно из этих чисел не кратно 2, 3, 5, 7, 11. Поступаем следующим образом (комментарий):

437 = 323 * 1 + 114;

323 = 114 * 2 + 95;

114 = 95 * 1 + 19;

95 = 19 * 5.

НОД (323; 437) = 19 ( параллельно решение оформить с помощью заполнения таблицы).

В частном случае, часто применяют следствие: НОД(a; b) = НОД (a - b; b), которое получается из общего правила при q = 1.

2. Найти НОД(458;252) и НОД(1920;1536).

7. Подведение итогов урока (1 мин)

Вопросы:

  1. С каким способом нахождения НОД чисел мы познакомились на уроке?
  2. Почему он называется алгоритмом Евклида?
  3. В чем он заключается?
  4. В каком случае его удобно применять?

8. Задание на дом: (1 мин)

1) С помощью алгоритма Евклида найти НОД чисел:2016 и 1320; 703 и 481

2) Решите задачу

(1 вариант): Для учащихся первого класса приготовили одинаковые подарки. Во всех подарках было 120 шоколадок, 280 конфет, и 320 орехов. Сколько учащихся в первом классе, если известно, что их больше 30?

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

Используемые источники информации

Литература.

[1].//Учебник для общеобразовательныхучреждений Математика 6 класс под ред. Н.Я Виленкина., Москва, Мнемозина,2009 г.

[2].//За страницами учебника алгебры. Л.Ф Пичурин, Москва, Просвещение, 1990г.

[3].//Сборник примеров и задач по математике, Н.А Терешин, Т.Н.Терешина Москва, Аквариум, 1997 г.

Интернет-ресурсы.

[1]. //Википедия (свободная энциклопедия), http://ru.wikipedia.org

[ 2]. //Сайт "Единая коллекция цифровых образовательных ресурсов".