Творческая исследовательская работа НОД и НОК и их применение в практических задачах

 

 

 

 

 

 

 

 

Творческая исследовательская работа

 

НОД и НОК и их применение в практических задачах.

 

 

 

 

 

 

 

 

Подготовили учащиеся  6Б класса

Видяпина АнастасияЭдуардовна,

Михайлов Дмитрий Александрович

 

 

Руководитель: учитель математики

Пастухова Н.А.

 

 

 

 

 

 

 

Оглавление

1. Введение………………………………………………………………2

2. Наибольший общий делитель натуральных чисел…………………3

2.1.Определение  НОД и его свойства

2.2. Различные способы нахождения наибольшего общего делителя

    натуральных чисел

2.3. Алгоритм Евклида и его применение……………………………...4-6

3. Наименьшее общее кратное натуральных чисел……………………7-8

3.1.Определение НОК и его свойства.

3.2 Различные способы нахождения наименьшего общего кратного

    натуральных чисел

4. Решение практических задач………………………………………….9-10

5. Заключение……………………………………………………………..11

6.Литература и информационные источники…………………………...12

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

Актуальность

На уроках математики мы познакомились с НОД – наибольшим общим делителем натуральных чисел и НОК – наименьшим общим кратным двух и нескольких натуральных чисел. Мы узнали некоторые способы нахождения  НОД и НОК.  

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

 Также мы решили узнать при решении каких практических задач применяются НОД и НОК.

 

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

Для достижения  цели пришлось решить следующие задачи:

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

2.Оценить рациональность применения разных способов вычисления НОД и НОК.

3.Подобрать практические задачи на применение НОД и НОК.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Наибольший общий делитель   двух натуральных чисел.

2. 1. Определение  НОД и его свойства

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

Обозначение наибольшего общего делителя чисел a и b:   НОД(a; b).

Свойства наибольшего общего делителя.

1. Наибольший общий делитель чисел a и b равен наибольшему общему делителю чисел b и a, то есть, НОД(a; b)=НОД(b; a).

2. Если a делится на b, то множество общих делителей чисел a и b совпадает с множеством делителей числа b, в частности, НОД(a;b)=b.

Например, НОД(8; 24)=8, так как 24 кратно восьми.

3. Если числа a и b - взаимно простые числа, то НОД(a;b)=1.

Например, НОД(8; 3)=1, так как 8 и 3 взаимно простые числа.

4. Если m – любое натуральное число, то НОД(m*a, m*b)=m*НОД(a; b).

5. Пусть p – любой общий делитель чисел a и b, тогда 

НОД(a:p, b:p) =  НОД(a; b):p.

Это  свойство наибольшего общего делителя лежит в основе сокращения обыкновенных  дробей до несократимых дробей.

2.2. Различные способы нахождения наибольшего общего делителя

    натуральных чисел

1 способ метод полного перебора.

1. Выписываем все делители числа а;

2. Выписываем все делители числа b;

3. Выбираем среди них общие делители;

4. Среди общих делителей выбираем самое большое число – это и есть НОД(a, b).

Например:  Найти НОД(32;48).

Делители 32: 1; 2; 4; 8; 16; 32;    делители 48: 1; 2; 3; 4; 6; 8; 12; 16; 24; 48.

 Общие делители 32; 48: 1; 2; 4; 8; 16.   НОД(32; 48) = 16.

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

2 способ разложение чисел на простые множители.

1. Находим разложение чисел на простые множители.

2. Подчеркиваем общие множители.

3. Находим произведение общих множителей у одного числа – НОД .

Например:  НОД(36; 48) =2*2*3 =12.     

48 24 12 6 3 1

2 2 2 2 3

 

36 18 9 3 1

2 2 3 3

 

 

 

 

 

 

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

2.3. Алгоритм Евклида и его применение

Этот алгоритм приписывают Евклиду, одному из величайших математиков древности. Евклид жил в III-II в до н.э. в Александрии. Он оставил несколько сочинений, известных в латинских и арабских переводах, наиболее значительное из которых – состоящие из 13 книг «Начала» («Elements»)- представляет собой систематическое изложение математики того времени.

 

1 алгоритм: Алгоритм Евклида нахождения наибольшего общего делителя двух натуральных чисел вычитанием.

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

 1. Из большего числа вычитается меньшее.

 2.  Если получается 0, то числа равны друг другу и являются наибольшим  общим делителем.

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

Например: Найти НОД(30; 18).                        

30 - 18 = 12; 18 - 12 = 6; 12 - 6 = 6; 6 – 6 = 0.

 

НОД – это уменьшаемое или вычитаемое.

НОД (30; 18) = 6.

Приведенный метод вычисления не является оптимальным. Например, для нахождения НОД(648; 20) следует выполнить много таких  операций.

 

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

1. Большее число делится на меньшее

2. Если делится без остатка, то меньшее число и есть наибольший общий делитель.

3.  Если есть остаток, то делитель делим на остаток  от деления,

продолжаем аналогичное деление до тех пор, пока не получим в остатке нуль. Последний неравный нулю остаток и есть НОД данных чисел.

 

     r_n – НОД(a, b).

 

Пример1: Найти НОД (273;1014).

Решение.

Выполняем деление с остатком:

1014=273*3+195; 

273=195*1+78; 

195=78*2+39; 

78=39*2                                          

НОД (273;1014) = НОД(195;273) = НОД(195;78) = НОД(78;39)= 39

 Пример 2: Найти НОД (661,113)

Решение:

Выполняем деление с остатком: 

661=113*5+96; 113=96*1+17; 96=17*5+11; 17=11*1+6; 11=6*1+5; 6= 5*1+1,  5=1*5. НОД(661, 113)=1, то есть, 661 и 113 – взаимно простые числа.

 

3 алгоритм: Бинарный алгоритм Евклида нахождения наибольшего общего делителя двух натуральных чисел.

 Данный алгоритм быстрее обычного алгоритма Евклида, т.к. вместо медленных операций деления и умножения используются сдвиги. Алгоритм был известен еще в Китае 1-го века, но опубликован был лишь в 1967 году израильским физиком и программистом Джозефом Стайном.

Алгоритм выглядит так:

1.     Если a, b чётные, то НОД(a; b) = 2*НОД(a/2; b/2);

2.     Если a чётное, b нечётное, то НОД(a; b) = НОД(a/2; b);

3.     Если b чётное, a нечётное, то НОД(a; b) = НОД(a; b/2);

4.     Если a, b нечётные и b > a, то НОД(a; b) = НОД((b-a)/2; a);

5.     Если a, b нечётные и b < a, то НОД(a; b) = НОД((a-b)/2; b);

Например:

НОД(1978;2666) = 2*НОД(989;1333) = 2*НОД(989;344/2) = 2*НОД(989;172)=  =2*НОД(989;86/2) = 2*НОД(989;43) = 2*НОД(946/2;43) = 2*НОД(473;43) =  =2*НОД(430/2;43 ) = 2*НОД(215; 43) = 2*НОД(172/2; 43) = 2НОД*(86/2; 43) = =2*НОД(43; 43) = 2*43=86.

НОД(1978; 2666)=86

Бинарный алгоритм Евклида сокращает количество операций при вычислении НОД, но требует знания применяемых формул.

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

 

Пример задачи с диофантовым уравнением.

Для газификации жилого дома требуется проложить газопровод протяженностью 150 м. Имеются трубы 13 м и 9м длиной. Сколько требуется труб, чтобы не приходилось их разрезать при прокладке газопровода.

Для решения составляем уравнение: x*9 + y* 13 = 150.

Ответ. Для прокладывания газопровода потребуется 8 труб длиной по 9м и 6 труб длиной по 13м.

 

Пример применения алгоритма Евклида вычитанием.

Задача 1.

 Лист фанеры имеет прямоугольную форму, его ширина равна 56см, длина – 77см. Какое наибольшее количество квадратов можно получить из этого листа, отрезая постепенно квадраты с наибольшей стороной из оставшейся части прямоугольника, и чему равна сторона меньшего квадрата?

Решение.

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

Получилось 6 квадратов, меньший квадрат со стороной 7см. Заметим, что НОД(56; 77) = 7.

Ответ: 6 квадратов, 7см.

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

 

 

 

 

 

 

3. Наименьшее общее кратное натуральных чисел

3.1.Определение НОК и его свойства

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

Обозначение наименьшего общего кратного чисел a и b:   НОК(a; b).

Свойства наименьшего общего кратного:

1. Наименьшее общее кратное чисел a и b равно наименьшему общему кратному чисел b и a, то есть, НОК(a; b) = НОК(b; a).

2. Если a делится на b, то НОК(a; b) = а.

Например, НОД(8; 24) = 24, так как 24 кратно восьми.

3. Если числа a и b - взаимно простые числа, то НОК(a; b) = a* b.

Например, НОК(8; 3)  =  8*3 = 24, так как 8 и 3 взаимно простые числа.

3.2 Различные способы нахождения наименьшего общего кратного

    натуральных чисел

1 способ метод полного перебора.

1. Выписываем несколько кратных числа а;

2. Выписываем несколько кратных числа b;

3. Выбираем среди них общие кратные;

4. Среди общих кратных выбираем самое маленькое число – это и есть НОК(a, b).

Например: Найти НОК(6;4).

Решение

Кратные числа 6: 6; 12; 18; 24; 30;…

Кратные числа 4: 4; 8; 12; 16; 20; 24; 28;…

НОК(6;4) = 12.

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

2 способ разложение чисел на простые множители.

1. Найти разложение чисел на простые множители.

2. Выписать множители, входящие в разложение самого большого из чисел (их произведение дает это число).

3. Подчеркнуть в разложении меньшего числа (меньших чисел) множители, которые не вошли в разложение большего числа,  и добавить эти множители в разложение большего числа.

Например:  НОД(36; 48) =(2*2*2*2*3)*3 =48*3 = 144.

48 24 12 6 3 1

2 2 2 2 3

 

36 18 9 3 1

2 2 3 3

 

 

 

 

 

 

 

 

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

3 способ использование связи НОД и НОК.

НОД(а;b)* НОК(а;b) = а*b.

Вычисляем используя алгоритм Евклида НОД(а;b),

 находим произведение а*b, затем вычисляем НОК(а;b) из данной формулы.

Например: Найти НОК(126;70)

Решение

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

126 =1*70 + 56; 70 = 1* 56 + 14; 56= 4*14;

НОД(126;70) = 14;   126*70 = 8820;   НОК(126;70) = 8820: 14 = 630.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4. Решение практических задач

№1

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

Решение.

Количество необходимых автомобилей - НОД(96 ; 64) = 32.

 Ответ: 32 автомобиля.

 

№2

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

Решение.

Количество школ – НОД(92 ; 138) = 46.

Ответ: 46 школ.

 

№3

Для новогодних подарков приобрели 96 шоколадок, 72 апельсина и 84 банана. Какое наибольшее количество одинаковых подарков можно из них составить, если необходимо использовать все продукты? Сколько в отдельности шоколадок, апельсинов и бананов будет в каждом подарке?

 Решение.

1) Количество подарков – НОД(96; 72; 84) = 2*2*3=12,

 

96 48 24 12 6 3 1

2 2 2 2 2 3

84 42 21 7 1

2 2 3 7

72 36 18 9 3 1

2 2 2 3 3

 

 

 

 

 

 

 

 

2)2*2*2 = 8 шоколадок,     3)7 бананов,     4)2*3 = 6 апельсинов.

Ответ: 12 подарков.

 

№4

Из 156 желтых, 234 белых и 390 красных роз составляли букеты. Какое наибольшее количество одинаковых букетов можно составить, если необходимо использовать все цветы?

Решение.

Количество букетов – НОД(156; 234; 390) = 78.  

Ответ: 78 букетов.

№5

На экскурсию по рекам и каналам нужно отправить несколько катеров с одинаковым количеством мест. В 12 часов нужно отправить 387 человек, а в 13 часов – 430 человек, заняв все места на катерах. Какое наименьшее количество катеров могло отправиться на экскурсию, и сколько мест было на каждом катере?

Решение.

1)Количество мест на катере – НОД(387; 430) = 43.

2)387+430 = 817 (пассажиров) - всего

3)817: 43 = 19–катеров.

Ответ: 19 катеров, 43 места.

 

№6

Саша ходит в бассейн один раз в 3 дня, Коля – раз в четыре дня, Петя – раз в 5 дней. Мальчики встретились в бассейне во вторник. Через сколько дней и в какой день недели они встретятся в следующий раз?

 Решение.

Они встретятся через – НОК(3; 4; 5) =  60 дней в субботу.

Ответ: через 60 дней в субботу

 

№7

Готовя подарки к Новому году, члены родительского комитета увидели, что имеющиеся конфеты можно разложить поровну по 15 штук или по 20 штук в один подарок. Сколько было конфет, если известно, что их было больше 600 и меньше 700?

Решение.

Найдем наименьшее количество конфет – НОК(15;20) = 60. 

2)60*11=660.

Ответ:660 конфет.

 

№8

Один экскурсионный автобус совершает полную экскурсию по городу за 2 часа, а другой – за 3 часа, оба автобуса выехали из базы в 10 часов утра. В какое время автобусы впервые встретятся на базе?

Решение.

Они встретятся через НОК(2;3) = 6( часов)

Ответ: в 16 часов.

 

 

 

 

 

 

 

 

Заключение

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

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

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

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

Мы планируем в старших классах научиться с помощью  алгоритма Евклида решать диофантовы уравнения и полученные знания использовать при подготовке к ОГЭ.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5.Литература

1.                 Мерзляк А.Г. и др. Математика, 6 класс: учебник для общеобразовательных учреждений. – М.: Вентана-Граф, 2016.- 304с.

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

3.                 Выговская В.В. Сборник практических задач по математике. – М.: ВАКО, 2016. – 64с.

4.                 Энциклопедический словарь юного математика/ сост. Э-68 А.П. Савин. – М.: Педагогика, 1989.-352 с.

5.                 Депман И.Я., Виленкин Н.Я. За страницами учебника математики: пособие для учащихся 5-6 класса средней школы. – М.: Просвещение, 1989. – 287с.

 

Информационные  источники:

 

1.                 https://ru.wikipedia.org/wiki

 

 

Скачано с www.znanio.ru