Работы моих учеников. Крюкова Е. "Нахождение и применение НОК и НОД"

Муниципальное бюджетное общеобразовательное учреждение

"Многопрофильный лицей" городского поселения "Рабочий поселок Чегдомын" Верхнебуреинского муниципального

района Хабаровского края.

Реферативно-исследовательская работа по математике:

Тема: "Нахождение и применение НОК и НОД"

Выполнила: Крюкова Екатерина

ученица 6"А" класса

Руководитель: Терентьева О. А.

учитель математики

пгт. Чегдомын

2019г.

Содержание:

1.Введение 3 2.История возникновения алгоритмов вычисления НОД и НОК 4

метода математической индукции

3.Основные результаты исследования 5-10

4.Заключение 11 5.Список литературы 12

Введение.

В каждодневной жизни человеку приходится решать большое число разного рода задач, которые требуют применения определённых алгоритмов. Когда мы приготавливаем чай, пользуемся определённым алгоритмом.

Слово алгоритм стало широко употребляться в последнее время. Оно означает описание совокупности действий, составляющих некоторый процесс. Обычно здесь подразумевают процесс решения некоторой задачи, но и кулинарный рецепт, и инструкция по пользованию стиральной машиной, и ещё многие другие правила, не имеющие отношения к математике, являются алгоритмами.

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

Цель исследования: изучить разные алгоритмы вычисления НОД и НОК, выявить наиболее рациональные способы решения, красиво и сравнительно просто приводящие к ответу.

Достижение поставленной цели требует решения следующих основных задач:

1. Рассмотреть несколько алгоритмов вычисления НОД и НОК

2. Провести анкетирование «Нахождение и применение НОД и НОК»

3. Составить список памятку «Применение НОД И НОК»

История возникновения алгоритмов вычисления НОД и НОК

Для данного алгоритма существует множество теоретических и практических применений. В частности, он широко распространён в электронной коммерции. Также алгоритм используется при решении диофантовых уравнений. Алгоритм Евклида является основным инструментом для доказательства теорем в современной теории чисел.

Алгоритм Евклида — эффективный алгоритм для нахождения наибольшего общего делителя двух целых чисел. Алгоритм назван в честь греческого математика Евклида, который впервые описал его в VII и X книгах «Начал».

В самом простом случае алгоритм Евклида применяется к паре положительных целых чисел и формирует новую пару, которая состоит из меньшего числа и разницы между большим и меньшим числом. Процесс повторяется, пока числа не станут равными. Найденное число и есть наибольший общий делитель исходной пары.

Первое описание алгоритма находится в «Началах Евклида» (около 300 лет до н. э.), что делает его одним из старейших численных алгоритмов, используемых в наше время. Оригинальный алгоритм был предложен только для натуральных чисел и геометрических длин (вещественных чисел). Позже алгоритм Евклида также был обобщен на другие математические структуры, такие как узлы и многомерные полиномы (многочлен от нескольких переменных).

Долгое время алгоритм Евклида был самым эффективным способом отыскания наибольшего общего делителя, однако с появлением электронно-вычислительных машин ситуация изменилась Учет специфических особенностей выполнения арифметических операций компьютером позволил построить более эффективную (для программной реализации) версию алгоритма Евклида.

Основные результаты исследования

Давайте рассмотрим все алгоритмы нахождения НОД.

• Алгоритм простого перебора: Чтобы найти наибольший общий делитель двух данных натуральных чисел можно действовать по определению: выписать все делители этих чисел, выделить среди них общие и выбрать среди всех общих делителей наибольший.

Пример. Найдем все делители чисел 54 и 36.

54 делится на 1; 2; 3; 6; 9; 18; 27; 54.

36 делится на 1; 2; 3; 4; 6; 9; 18; 36.

Общими делителями являются числа: 1, 2, 3, 6, 9, 18.

Наибольший из них является 18.

Значит НОД (54; 36) = 18

• Нахождение НОД с помощью разложения чисел на простые множители:

Рассмотрим еще один способ нахождения НОД. Наибольший общий делитель может быть найден по разложениям чисел на простые множители.

Что такое разложение на множители? Это способ превращения неудобного и сложного примера в простой. Встречается на каждом шагу и в элементарной, и в высшей математике.

Смысл разложения на множители предельно прост и понятен. Прямо из самого названия. Например, надо разложить число 12. Можно смело записать: 12=3·4

А можно разложить 12 по-другому: 12=3·4=2·6=3·2·2=........

Сформулируем правило: НОД двух целых положительных чисел a и b равен произведению всех общих простых множителей, находящихся в разложениях чисел a и b на простые множители.

Приведем пример для пояснения правила нахождения НОД.

Пусть нам известны разложения чисел 220 и 600 на простые множители, они имеют вид 220=2·2·5·11 и 600=2·2·2·3·5·5. Общими простыми множителями, участвующими в разложении чисел 220 и 600, являются 2, 2 и 5. Следовательно, НОД (220, 600) =2·2·5=20.

Таким образом, если разложить числа a и b на простые множители и найти произведение всех их общих множителей, то будет найден наибольший общий делитель чисел a и b.

Пример. Найдите наибольший общий делитель чисел 72 и 96.

Решение. Разложим числа 72 и 96 на простые множители.

72=2·2·2·3·3 и 96=2·2·2·2·2·3. Общими простыми множителями являются 2, 2, 2 и 3. Таким образом, НОД (72, 96) = 2·2·2·3=24.

Ответ: НОД (72, 96) = 24.

В заключение этого пункта заметим, что справедливость приведенного правила нахождения НОД следует из свойства наибольшего общего делителя, которое утверждает, что

НОД (m ·a, m ·b) = m· НОД (a, b), где m – любое целое положительное число.

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

Одним из простейших алгоритмов нахождения наибольшего общего делителя является Алгоритм Евклида. Он может быть реализован, как при помощи вычитания, так и деления. Рассмотрим каждый из этих двух способов.

Описание алгоритма нахождения НОД вычитанием:

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

Пример:

Найти НОД 30 и 18.

30 - 18 = 12

18 - 12 = 6

12 - 6 = 6

6 – 6 =0

НОД – это уменьшаемое или вычитаемое. НОД (30, 18) = 6

• Описание алгоритма нахождения НОД делением:

Большее число делим на меньшее. Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла). Если есть остаток, то большее число заменяем на остаток от деления. Переходим к пункту 1.

Пример:

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

30 / 18 = 1 (остаток 12)
18 / 12 = 1 (остаток 6)
12 / 6 = 2 (остаток 0) 
НОД – это делитель 6.
НОД (30, 18) = 6

Способов нахождения НОД очень много, мы рассмотрели самые известные.

Теперь давайте рассмотрим несколько способов нахождения НОК.

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

• Способ перемножения чисел: Он гораздо лучше подходит для простых однозначных или двухзначных чисел. Большие числа принято разделять на множители, чем больше число, тем больше множителей будет.

Найти НОК можно, по очереди, для каждого из заданных чисел, выписывая в порядке возрастания все числа, которые получаются путем их умножения на 1, 2, 3, 4 и так далее.

Найдем НОК (6; 9)
Умножаем число 6, последовательно, на 1, 2, 3, 4, 5.
Получаем: 6, 12, 18, 24, 30
Умножаем число 9, последовательно, на 1, 2, 3, 4, 5.
Получаем: 9, 18, 27, 36, 45
Общее кратное у них =18 ,следовательно НОК(6;9)=18

• Наименьшее общее кратное через НОД.

НОК (а; b) = a*b:НОД (a, b)

Рассмотрим примеры нахождения НОК по приведенной формуле:

НОК(126;70)

Сначала нам предстоит найти наибольший общий делитель, после чего мы должны вычислить НОК.

Найдем НОД(126;70), используя алгоритм Евклида:

126=70*1+56;

70=56х1+14;

56=14х4, следовательно, НОД(126;70) =14

Теперь находим требуемое наименьшее общее кратное:

НОК(126;70) =126х70: НОД (126;70126х70:14=630

Способов нахождения НОК не много, мы рассмотрели самые известные.

Памятка. НОД и НОК

Признаки делимости натуральных чисел.

Признак делимости на 2

Если запись натурального числа оканчивается четной цифрой, то это число делится без остатка на 2, а если запись числа оканчивается нечетной цифрой, то это число не делится без остатка на 2.

Например, числа 60, 308, 84 делятся без остатка на 2, а числа 51, 85, 167 не делятся без остатка на 2.

Признак делимости на 3

Если сумма цифр числа делится на 3, то и число делится на 3; если сумма цифр числа не делится на 3, то и число не делится на 3.

Например, выясним, делится ли на 3 число 2772825. Для этого подсчитаем сумму цифр этого числа: 2+7+7+2+8+2+5 = 33 — делится на 3. Значит, число 2772825 делится на 3.

Признак делимости на 5

Если запись натурального числа оканчивается цифрой 0 или 5, то это число делится без остатка на 5. Если же запись числа оканчивается иной цифрой, то число без остатка на 5 не делится.

Например, числа 15, 30, 1765, 475300 делятся без остатка на 5, а числа 17, 378, 91 не делятся.

Признак делимости на 9

Если сумма цифр числа делится на 9, то и число делится на 9; если сумма цифр числа не делится на 9, то и число не делится на 9.

Например, выясним, делится ли на 9 число 5402070. Для этого подсчитаем сумму цифр этого числа: 5+4+0+2+0+7+0 = 16 — не делится на 9. Значит, число 5402070 не делится на 9.

Признак делимости на 10

Если запись натурального числа оканчивается цифрой 0, то это число делится без остатка на 10. Если запись натурального числа оканчивается другой цифрой, то оно не делится без остатка на 10.

Например, числа 40, 170, 14090 делятся без остатка на 10, а числа 17, 93, 14307 — не делятся.

Заключение.

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

Научиться быстро и правильно вычислять НОК и НОД чисел не так уж сложно. Вышеперечисленные алгоритмы рассчитаны на ум "обычного" человека и не требуют уникальных способностей. Главное - более или менее продолжительная тренировка.

Собранный мной материал можно использовать на факультативных занятиях, на занятиях математического кружка. Учителя математики могут использовать его при изучении данной темы. Также рекомендуем ознакомиться с моей работой тем сверстникам, которые хотят знать о математике больше, чем рядовой школьник.

В будущем я планирую продолжить исследование по данной теме и рассмотреть алгоритм Евклида для многочленов, при решении уравнений в целых числах.

Список использованной литературы

1. Виленкин Н.Я. и др. Математика, 6 класс: учебник для общеобразовательных учреждений. – М.: Мнемозина, 2013.- 288с.

2. Макарычев Ю.Н., Миндюк Н.Г. Алгебра: Дополнительные главы к школьному учебнику 8 кл.: учебное пособие для школ и классов с углубленным изучением математики.- М.:Просвещение,1996.- 207 с.

3. Пичурин Л.Ф. За страницами учебника алгебры- Москва: Просвещение, 1990г.

4. Щетников А. И. Алгоритм Евклида и непрерывные дроби. - Новосибирск: АНТ, 2003 г.

http://www.rusnauka.com

Список используемых источников информации:

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

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

3. http://www.rusnauka.com

12