НОД и НОК и их применение в решении задач

XXVII Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке

Личный портфель

НОД и НОК и их применение в решении задач

Милованова Е.А. 1
1МАОУ СШ 8
Сидорова Е.В. 1
1МАОУ СШ 8
Автор работы награжден дипломом победителя II степени
Диплом школьникаСвидетельство руководителя
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF

Введение

«В каждой естественной науке заключено столько истины,

сколько в ней есть математики» (И. Кант).

Одно из самых удивительных занятий нашего времени – математика.

Математика является фундаментальной наукой, которая на протяжении всей истории человечества служит основой для развития других дисциплин и практических применений. При изучении математики я хорошо развивается логическое, алгоритмическое и творческое мышление, необходимое не только на уроках математики, но и повседневной школьной жизни. Логическое мышление, способствующее лучшему усвоению школьной программы. В 6 классе мы познакомились с двумя важными понятиями: наименьшим общим кратным (НОК) и наибольшим общим делителем (НОД), в этом проекте мы рассмотрим тему «НОК и НОД применение в решении и задачах».

Тип проекта: исследовательский

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

Предмет исследования: свойства делимости связанные с НОК и НОК, связь между НОК и НОД.

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

Актуальность темы: Актуальность проекта в том , в современном образовании важно развивать математическое мышление, через практическое применение задач. 

Цель исследования: изучить понятия НОД и НОК, освоить методы их нахождения, включая алгоритм Евклида методом вычитания, и делением и научиться применять эти знания для решения практических задач.

Для достижения намеченной цели, поставлены следующие задачи:

Задачи проекта:

  1. Описать теоретические основы НОД и НОК — рассмотреть определения этих терминов, основные свойства, алгоритмы их нахождения, включая алгоритм Евклида.

2. Провести анкетирование среди одноклассников, интересно и помнят ли тему НОК и НОД.

3. Разработать программу для решения задач в Python.

4. Привести примеры и задачи практического применения НОД и НОК.

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

В процессе выполнения данной работы был проведён опрос среди одноклассников:

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

№

п/п

Вопросы

Да

Нет

1

Помните ли, вы тему НОК и НОД?

    

2

Используешь ли, ты НОД и НОК при решении задач и упражнений по математике?

    

3

Познакомились ли, вы с алгоритмом Евклида?

    

4

Считаете ли вы, решение задач НОД и НОК это что-то сложное ?

    

5

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

    

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

Глава I. Понятие НОД и НОК

    1. Теоретические основы понятий НОД и НОК

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

Делитель и кратное — это математические понятия, связанные с делением чисел. Давайте разберемся в их определениях:

Делитель:

Определение: Делитель числа — это число, на которое данное число делится нацело, без остатка.

Пример: Для числа 12, делителями будут 1, 2, 3, 4, 6 и 12, так как 12 делится нацело на каждое из этих чисел.

Кратное:

Определение: Кратное числа — это число, которое делится на данное число нацело, без остатка.

Пример: для числа 3, кратными будут 6 (так как 6 делится нацело на 3), 9, 12, 15 и так далее.

Как не путать:

Делитель — это число, на которое делится другое число.

Кратное — это число, которое делится на другое число.
Пример: Рассмотрим число 5:

Делители 5: 1, 5 (потому что 5 делится нацело на 1 и на само себя).
Кратные 5: 10, 15, 20 (потому что эти числа делятся нацело на 5).

Таким образом, можно запомнить, что делитель сужает (уменьшает) число, а кратное расширяет (увеличивает) его.

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

— Натуральное число называют простым, если оно имеет только два делителя: единицу и само это число.

— Натуральное число, которое имеет более двух делителей, называют составным (например, 4, 6, 8, 9, 10...).

У числа 1 только один делитель — само это число, поэтому оно не является ни составным, ни простым числом.

Вот первые десять простых чисел: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Число 2 — наименьшее простое число. Оно единственное чётное простое число, все остальные простые числа — нечётные.

Число 90 — составное: оно делится не только на 1 и 90, но и, например, на 5, т. е. 90 = 5 • 18.

Говорят, что число 90 разложено на множители 5 и 18.

Любое составное число можно разложить на множители, каждый из которых больше 1.

Любое составное число можно разложить на простые множители.

Простое число нельзя разложить на множители, каждый из которых больше 1.

Определить, является ли число простым или составным, бывает сложно, например 827 и 837. Таблица, в которой записаны все простые числа первой тысячи

Например, число 770 — произведение чисел 77 и 10: 77 • 10 = 770.

Но числа 77 и 10 тоже составные, и их также можно представить в виде произведений: 77 = 7 • 11 и 10 = 2 • 5.

Получим 770 = 7 • 11 • 2 • 5.

В правой части равенства все множители — простые числа. Число 770 разложено на простые множители:

На простые множители разложить 770 можно и так:

770 = 70 • 11 = 7 • 10 • 11 = 7 • 2 • 5 • 11.

В этом разложении те же простые множители, но запи­санные в другом порядке.

Обычно записывают множители в порядке их возрастания:

770 = 2 • 5•7 • 11.

— Представление числа в виде произведения его простых делителей называют разложением числа на простые мно­жители.

— Любое составное число можно разложить на простые множители. В таком разложении может быть только разный порядок записи множителей.

— Признаки делимости помогают при разложении числа на простые множители. Разложение на простые множители удобно записывать с помощью вертикальной черты.

Пример. Разложим на простые множители число 660.

Проведём вертикальную черту и слева запишем делимое 660.

  1. Число 660 оканчивается чётной цифрой и потому де­лится на 2: 660 : 2 = 330. Справа от черты запишем делитель 2, а под делимым 660 запишем частное 330.

  2. Число 330 тоже делится на 2: 330 : 2 = 165. Опять за­пишем справа 2, а слева 165.

  3. Число 165 делится на 3, так как сумма цифр 12 делит­ся на 3: 165 : 3 = 55.

  4. Число 55 делится на 5, так как оканчивается цифрой 5: 55 : 5 = 11

  5. Простое число 11 делится само на себя: 11 : 11 = 1.

Разложение закончено:

660 = 2 • 2 • 3 • 5 • 11.

Мною рассмотрены традиционные задачи, которые помогают познакомится с понятиями НОК и НОД.

    1. Свойства и характеристики (НОД и НОК)

В таблице ключевые свойства и характеристики (НОД)

Факт о наибольшем общем делителе

Описание

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

Основное свойство НОД

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

В детском саду детей нарядили к празднику «Весна пришла»: 18 детей в костюмы зайчиков и 24 в костю­мы белочек. На какое наибольшее число групп можно раз­бить детей для танца, чтобы в каждой группе было одинако­вое количество «зайчиков» и «белочек»?

Решение. Число 18 и число 24 должны делиться на чис­ло групп. Поэтому выпишем все делители чисел 18 и 24.

Делители 18: 1, 2, 3, 6, 9, 18.

Делители 24: 1, 2, 3, 4, 6, 8, 12, 24.

Общими делителями этих чисел будут: 1, 2, 3, 6.

Самым большим из этих делителей является 6.

Детей можно разделить на 6 групп. В каждой группе будет 3 «зайчика» (18 : 6 = 3) и 4 «белочки» (24 : 6 = 4).

Ответ: 6 групп.

Число 6 называют наибольшим общим делителем чисел 18 и 24.

НОД взаимно простых чисел

Например, найдём наибольший общий делитель чисел 21 и 40.

Делители числа 21: 1, 3, 7, 21.

Делители числа 40: 1, 2, 4, 5, 8, 10, 20, 40.

Числа 21 и 40 имеют только один общий делитель - число 1. Такие числа называют взаимно простыми.

Натуральные числа называют взаимно простыми, если их наибольший общий делитель равен 1.

Если НОД двух или более чисел равен 1, такие числа называются взаимно простыми. Числа 21 и 40 имеют только один общий делитель — число 1. Такие числа называют взаимно простыми.

Примеры

28 = 4 • 7 (у взаимно простых множителей 4 и 7 нет общих делителей, кроме 1)
30= 2 • 15 (у взаимно простых множителей 2 и 15 нет общих делителей, кроме 1)

НОД любого числа с нулем

Важное свойство НОД:

  • НОД любого числа и 0 равен самому этому числу.

Это свойство можно объяснить так: любое число делится на 0 без остатка, поскольку при делении на 0 результат всегда равен бесконечности (в математическом смысле), но в контексте НОД мы рассматриваем только целые числа.

Примеры:

  • НОД(17, 0) = 17НОД(17,0)=17

  • НОД(25, 0) = 25НОД(25,0)=25

  • НОД(0, 0) = 0НОД(0,0)=0

Практическое применение:

  1. При решении задач на нахождение НОД.

  2. В алгоритмах Евклида для нахождения наибольшего общего делителя.

  3. В теории чисел и криптографии.

  4. При упрощении дробей.

  5. В задачах на делимость чисел.

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

НОД и 0 — НОД любого числа и 0 равен этому числу. Пример: НОД чисел 17 и 0 равен 17, потому что 17 делится на 0 без остатка. Пример: НОД чисел 17 и 0 равен 17. Потому что 17 делится на 0 без остатка.

Свойство делимости

НОД и делимость — если одно число делится на другое, то НОД этих чисел равен меньшему из них.

Пример: НОД чисел 20 и 5 — 20 делится на 5, поэтому НОД равен 5.

НОД и одинаковые числа

НОД двух одинаковых чисел равен этому числу.

Пример: НОД чисел 7 и 7 равен 7. Потому что оба числа одинаковы, и наибольшее число, на которое можно разделить оба, это само число.

НОД и умножение чисел на другое число

Если оба числа умножить на одно и то же число, то их НОД также умножится на это число.

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

Свойства НОК

НОК всегда не меньше каждого из чисел, для которых оно находится.

НОК делится на любое из исходных чисел без остатка.

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

Например, НОК (2, 7) = 2 × 7 = 14.

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

Например, НОК (60, 15) = 60.

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

    1. Освоение методов нахождения НОД и НОК

Рассмотрим освоение методов нахождения НОД и НОК, включая алгоритм Евклида, разложение чисел на простые множители и другие подходы

  • Алгоритмы нахождения наибольшего общего делителя (НОД)

Способ 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

Общие делители: 1; 2; 4

Самый большой из них: 4.

Вывод Недостаток алгоритма перебора делителей — необходимо проверять много вариантов. Если числа достаточно большие, нахождение НОД путём перечисления всех делителей может быть трудоёмким и ненадёжным.

  • Способ 2: Алгоритм нахождения НОД - методом разложение натуральных чисел на простые множители.

Чтобы найти наибольший общий делитель нескольких натуральных чисел, надо:

1) разложить числа на простые множители;

2) подчеркнуть общие множители в каждом разложении;

3) найти произведение общих множителей.

1) Каждое число нужно разложить на простые множители

2) Потом подчеркнуть множители которые встречаются в обоих числах

3) Перемножить все общие множители

4) Результатом умножения общих множителей будет НОД

Найдём НОД (16,32)

Разложим числа

16 = 2 × 2 × 2 × 2

32 = 2 × 2 × 2 × 2 × 2

Подчеркнём общие множители

16 = 2 × 2 × 2 × 2

32 = 2 × 2 × 2 × 2 × 2

Перемножим общие множители

НОД (16, 32) = 2 × 2 × 2 × 2 = 16

Пример

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

Решение

Разложить 72 и 96 на простые множители на простые множители;

выбрать одинаковые множители, входящие в оба разложения;

найти их произведение.

Отсюда:

1. Раскладываем 72 и 96 на простые множители:

72 96 96 2

36 2 48 2

18 2 24 2

9 3 6 2

3 3 3 3

1 1

Общими для двух чисел простые множители: 2, 2, 2 и 3.

Это значит, что НОД (72, 96) =2⋅2⋅2⋅3=24

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

Рассмотрим пример (НОД) чисел 260 и 430:

260=2⋅2⋅5⋅13

430=2⋅2⋅43

260=22⋅5⋅13

430=2⋅5⋅43

Найдём общие множители: В обоих числах есть множители 2 и 5.

Вычислим НОД: НОД (260, 430) = 2⋅5=10

Проверка:

260 делится на 10: 260 : 10 = 26

430 делится на 10: 430 : 10 = 43

Ответ: НОД чисел 260 и 430 равен 10.

  Метод разложения на простые множители позволяет эффективно находить НОД, так как:

— упрощает процесс поиска общих делителей;

— позволяет быстро определить наибольший общий делитель;

— даёт возможность проверить результат деления.

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

Чтобы найти наибольший общий делитель нескольких натуральных чисел, надо:

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

  2. подчеркнуть общие множители в каждом разложении;

  3. найти произведение общих множителей.

Если все данные числа делятся на одно из них (делитель данных чисел), то это число и является наибольшим общим делителем этих чисел.

Рассмотрим пример: Найдём НОД (14, 42, 84, 140):

Найдём НОД (14, 42):

Разложим числа на простые множители:

14 = 2 × 7

42 = 2 × 3 × 7

Общие множители: 2 и 7 НОД (14,42) = 2 × 7 = 14

Найдём НОД (14, 84):

84 = 2 × 2 × 3 × 7

Общие множители: 2, 2 и 7 (то есть 2 × 7) НОД (14,84) = 14

Найдём НОД (14, 140):

140 = 2 × 2 × 5 × 7

Общие множители: 2, 2 и 7 (2 × 7) НОД (14,140) = 14

Теперь найдём НОД (14, НОД (42,84,140)):

НОД (42, 84, 140) = 14

НОД(14, 14) = 14 (так как любое число делится на себя)

Ответ: НОД(14, 42, 84, 140) = 14.

Это означает, что наибольшее число, на которое делятся все четыре числа без остатка, равно 14.

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

НОК можно найти несколькими способами: 

I способ: Алгоритм нахождения НОК методом полного перебора кратных двух чисел: 

1. Взять большее из чисел.

2. Найти числа, кратные выбранному (умножая выбранное число последовательно на 1, 2, 3, 4, 5 и т. д.).

3. Каждое полученное кратное проверить, делится ли оно на оставшиеся числа. Первое такое кратное и есть НОК.

Рассмотрим пример для чисел 45 и 60:

Выпишем числа, кратные 45 и 60.

— Кратные числа 45: 45, 90, 135, 180, 225, 270.

— Кратные числа 60: 60, 120, 180, 240, 300.

— Общие кратные: 180, 360.

— Наименьшее кратное — 180.

— Наименьшим из них является 180.

Таким образом, НОК (45, 60) = 180.

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

II способ:  Алгоритм нахождения НОК с помощью разложения чисел на простые множители

1) разложить числа на простые множители;

2) выписать множители из разложения большего из чисел;

3) добавить к ним недостающие множители из разложений остальных чисел;

4) найти произведение этих множителей

Нахождение НОК 45 и 60

Наименьшее общее кратное (НОК) целых чисел 45 и 60 — это наименьшее натуральное число, которое делится на 45 и на 60 без остатка.

Как найти НОК 45 и 60 :

Как найти наименьшее общее кратное для 45 и 60

  1. Разложим на простые множители 45

45 = 3 • 3 • 5

  1. Разложим на простые множители 60

60 = 2 • 2 • 3 • 5

  1. Выберем в разложении меньшего числа (45) множители, которые не вошли в разложение

3

  1. Добавим эти множители в разложение бóльшего числа

2, 2, 3, 5, 3

Полученное произведение запишем в ответ.

НОК (45, 60) = 2 • 2 • 3 • 5 • 3 = 180

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

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

Пример: нахождения НОК (45; 60)

Шаг 1. Разложение чисел на простые множители

Число 45:  45 = 3⋅3⋅5=32⋅5

Число 60:  60 =2⋅2⋅3⋅5=22⋅3⋅5

Шаг 2. Выбор и дополнение множителей

Выбираем множители из первого разложения (45):

— 32 (два множителя 3)

— 5

Добавляем недостающие множители из второго разложения (60):

— Два множителя 2 (22)

Шаг 3. Вычисление произведения

НОК = 22 ⋅32 ⋅5 = 4⋅ 9 ⋅5 = 180

Таким образом, наименьшее общее кратное чисел (НОК) 45 и 60 равно 180.

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

— Разложить каждое число на простые множители

— Выбрать множители из первого числа

— Добавить недостающие множители из второго числа

— Перемножить все выбранные множители

Этот метод является универсальным и применим для нахождения НОК любых натуральных чисел.

Пример: нахождения НОК (45; 60)

1. Раскладываем 45 и 60 на простые множители:

45 = 3 · 3 · 5 60 = 2 · 2 · 3 · 5

45 3 60 2

15 3 30 2

5 5 15 3

1 5 5

1

2. Берем множители из первого разложения, добавляем к ним отсутствующие множители со второго разложения и вычисляем произведение.

Ответ: НОК (45; 60) = 2 · 2 · 3 · 5 · 3 = 180

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

III способ: Алгоритм нахождения НОК через НОД

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

  2. Умножить первое число на второе

  3. Найти частное полученного числа и НОД. НОК (a, b) = a·b: НОД (a, b).

Примеры

Пример: найти НОК чисел 16 и 36: 

  1. Вычислить НОД, разложив числа на множители: 16 = 2 × 2 × 2 × 2, 36 = 2 × 2 × 9.

  2. Найти НОД: 2 × 2 = 4.

  3. Найти произведение и разделить его на полученное значение: (16 × 36): 4 = 144.

 Пример: найти НОК чисел 84 и 70: 

  1. Найти НОД чисел 84 и 70, используя алгоритм Евклида:

НОД (a и b), то есть НОК (a, b) = a·b: НОД (a, b).

Решение:

Найдём наибольший общий делитель (НОД) чисел 84 и 70 с помощью алгоритма Евклида.

  1. Разделим большее число на меньшее: 84 : 70 = 1 (остаток 14)

  2. Заменим большее число остатком от деления: 70 : 14 = 5 (остаток 0)

  3. Когда остаток равен 0, процесс завершается. Последний ненулевой остаток — это и есть НОД.

Ответ: НОД (84, 70) = 14

Проверка:

84 = 6 × 14

70 = 5 × 14

Таким образом, 14 — это наибольшее число, на которое делятся оба числа без остатка.

  1. Вычислить НОК: НОК (84, 70) = 84 × 70 : 14 = 420.

Вывод: связь между НОК и НОД позволяет вычислить НОК через произведение чисел и их НОД. Это следует из того, что если перемножить первое число на второе, то общая часть (НОД) будет повторена дважды, а достаточно и одного раза. Поэтому, чтобы убрать повтор, произведение нужно разделить на НОД.

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

Изучим алгоритм Евклида: Алгоритм Евклида — эффективный алгоритм для нахождения наибольшего общего делителя двух целых чисел. Алгоритм назван в честь греческого математика Евклида.

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

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

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

Алгоритм Евклида — это древний и очень красивый способ находить НОД (Наибольший общий делитель), не раскладывая их на множители. Это как «математический чит-код», особенно для очень больших чисел.

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

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

Алгоритм основан на свойстве: НОД (a, b) = НОД(b, a % b), где % — операция взятия остатка от деления. Это свойство позволяет свести задачу нахождения НОД двух чисел к задаче нахождения НОД меньшего числа и остатка от деления большего числа на меньшее. 

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

  • Алгоритм методом Евклида с помощью вычитания.

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

Метод вычитания (простой) — чтобы найти НОД двух чисел нужно из большего вычитать меньшее до тех пор, пока числа не станут равными. Это общие число и будет НОД.

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

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

  3. Если результат отличен от нуля, то большее число заменяем на результат вычитания.

Возвращаемся к первому пункту, пока не получим нуль.

Пример: Найти НОД (40; 24).

40 - 24 = 16, 24 - 16 = 8, 16 - 8 = 8, 8 – 8 =0

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

НОД (40, 24) = 8
Пример: Найти НОД (30; 18).                        

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

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

НОД (30; 18) = 6.

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

48 > 18. Вычитаем: 48 – 18 = 30. (Теперь пара чисел 30 и 18).

30 > 18. Вычитаем: 30 – 18 = 12. (Теперь пара 12 и 18).

18 > 12. Вычитаем: 18 – 12 = 6. (Теперь пара 12 и 6).

12 > 6. Вычитаем: 12 – 6 = 6. (Пара 6 и 6).

Числа стали равными!

Ответ: НОД (48, 18) = 6.

Вывод: Метод вычисления, легок в применении, но не является оптимальным, может быть достаточно длинным, выполнять много таких операций.

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

«Метод деления» (Быстрый)

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

Перебор делителей может быть долгим, особенно для больших чисел. 

— Почему он лучше? Если числа огромные, вычитать можно бесконечно.

Деление экономит время. Делим большее на меньшее и смотрим на остаток.

Алгоритм Евклида заключается в следующем: 

1. Делим большее число на меньшее и находить остаток.

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

3. Повторяем, пока остаток не станет равен 0.

4. Последний делитель (на который делили) — это и есть НОД равен последнему ненулевому остатку.

Пример:

Найти НОД чисел 48 и 18:

48 : 18 = 2 (остаток 12);

18 : 12 = 1 (остаток 6);

12 : 6 = 2 (остаток 0).

Таким образом: НОД чисел 48 и 18 равен 6.

Пример:

Найти НОД чисел 1071 и 462:

    1. : 462 → остаток 147, новая пара (462, 147);

2. 462 : 147 → остаток 21, новая пара (147, 21);

  1. 147 : 21 → остаток 0 → стоп.

Таким образом: НОД = 21.

Пример: НОД (1147 и 899)

1. 1147:899=1(остаток 248)

2. 899:248=3(остаток 155)

3. 248:155=1(остаток 93)

4. 155:93=1(остаток 62)

5. 93:62=1(остаток 31)

6. 62:31=2(остаток 0)

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

Вывод. Легок в применении.

Почему алгоритм Евклида до сих пор так популярен?

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

Как алгоритм Евклида помогает в решении задач НОД в программировании?

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

Связь НОД с НОК

Связь НОД с НОК

Понятия НОД (наибольший общий делитель) и НОК (наименьшее общее кратное) связаны в теории чисел теоремой.

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

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

Также произведение НОК и НОД некоторых чисел равно произведению самих этих чисел: НОК(a; b) · НОД(a; b) = a · b.

Из изученного мною материала можно сделать выводы:

  • НОД (наибольший общий делитель) и НОК (наименьшее общее кратное) нужны для решения различных задач в математике и других дисциплинах. Эти понятия тесно взаимосвязаны и часто используются совместно при решении различных математических задач. 

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

Глава II. Практическое применение НОК и НОД

Разработка программы алгоритма Евклида на Python

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

def find_gcd_with_steps (a, b):

    print(f"\n--- Начинаем поиск НОД для чисел {a} и {b} ---") Введите первое число:

        # Сначала убедимся, что 'a' больше 'b' >>> 2000

    if a < b: Введите второе число:

        a, b = b, a >>> 550

        print(f"Меняем числа местами, чтобы большее было первым: {a} и {b}") -- Начинаем поиск НОД для чисел 2000 и 550 -

Шаг 1: 2000 = 550 * 3 + 350

    step = 1 Шаг 2: 550 = 350 * 1 + 200

    # Цикл продолжается, пока остаток не станет равен 0 Шаг 3: 350 = 200 * 1 + 150

    while b != 0: Шаг 4: 200 = 150 * 1 + 50

        quotient = a // b  # Сколько раз b помещается в a Шаг 5: 150 = 50 * 3 + 0

        remainder = a % b  # Остаток от деления -----------------------------------

        ПОБЕДА! Остаток стал равен 0.

        print(f"Шаг {step}: {a} = {b} * {quotient} + {remainder}") Последний делитель, на котором мы остановились: 50

        Значит, НОД = 50

        # Готовимся к следующему шагу: Нажми Enter, чтобы закрыть программу...

        # Теперь большее число (a) становится тем, на что мы делили (b) >>>

        # А меньшее число (b) становится остатком

        a = b

        b = remainder

        step += 1

    print("-" * 35 )

    print(f"ПОБЕДА! Остаток стал равен 0.")

    print(f"Последний делитель, на котором мы остановились: {a}")

    print(f"Значит, НОД = {a}")

# ГЛАВНАЯ ЧАСТЬ ПРОГРАММЫ

print("Привет! Я помогу тебе найти НОД методом Евклида.")

try:

    num1 = int(input("Введите первое число: "))

    num2 = int(input("Введите второе число: "))

    if num1 == 0 or num2 == 0:

        print("Ошибка: числа не должны быть равны нулю.")

    else:

        find_gcd_with_steps(num1, num2)

except ValueError:

    print("Ошибка: Пожалуйста, вводи только целые числа!")

input("\nНажми Enter, чтобы закрыть программу...")

Разработанная мною программа позволяет быстро определить делители чисел.

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

Задачи на применение НОД

  • Задача 1.

Садовый участок размером 54 м на 48 м по периметру оградили забором. Для этого через равные промежутки установили столбы для крепления забора. Сколько столбов установили и на каком максимальном расстоянии друг от друга?

Решение

Садовый участок имеет форму прямоугольника, находим его периметр:
P = 2 × (a + b) = 2 × (54 + 48) = 2 × 112 = 2 × 102 = 204 (м).

В условии сказано, что расстояние между столбами должно быть максимальным.

Находим НОД чисел 54 и 48.
Д (54) = 1, 2, 3, 6, 9, 18, 27, 54
Д (48) = 1, 2, 3, 4, 6, 8, 12, 16, 24, 48
Д (54, 48) = 1, 2, 3, 6;
НОД (54, 48) = 6 (м) – максимальное расстояние между столбами.
Находим необходимое количество столбов:
204: 6 = 34 (столба).
Ответ: необходимо 34 столба.

  • Задача 2.

В зоошколе у панды Лены12 одинаковых бамбуковых палочек, а у панды Кати –18 таких же. Сколько они могут составить многоугольников с наибольшим числом сторон так, чтобы были использованы все бамбуковые палочки?

Дано:

У панды Лены: 12 палочек

У панды Кати: 18 палочек

Решение:

  1. Найдём НОД (наибольший общий делитель) для чисел 12 и 18:

Разложим числа на простые множители:

12 = 2 × 2 × 3

18 = 2 × 3 × 3

Общие множители: 2 и 3

НОД = 2 × 3 = 6

  1. Чтобы составить многоугольник, используя все палочки, количество палочек должно делиться на число сторон многоугольника.

  2. Максимальное число сторон многоугольника, которое можно составить из данных палочек — это НОД(12, 18) = 6.

  3. Проверим возможность построения шестиугольника:

12 палочек можно разделить на 6 равных частей по 2 палочки

18 палочек можно разделить на 6 равных частей по 3 палочки

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

Ответ: панды Лены и Кати могут составить один шестиугольник, используя все бамбуковые палочки.

  • Задача 3.

Валя и Вера покупают одинаковые почтовые наборы. Каждый набор состоит из открытки с конвертом. Валя уплатит за наборы 65 руб., а Вера-на 26 руб. больше. Сколько стоит один набор? Сколько наборов купила Валя? И Вера?

Решение: найдем сколько потратила Вера 65+26=91 (руб.)

Найдем сколько стоит один набор, для этого вычислим НОД (65, 91)

Н ачальные данные: 65 и 91 91= 65·1+26

В аля: 65 5 91 7

13 13 13 13

1 1

НОД (65,91), следовательно стоимость одного набора равна 13руб.

  1. Количество наборов:

— У Вали:  65:13 = 5 наборов.

— У Веры:  91: 13 =7 наборов.

Ответ:

— Один набор стоит 13 рублей.

— Валя купила 5 наборов.

— Вера купила 7 наборов.

  • Задача 4.

На птицеферме вырастили птиц, занесенных в Красную Книгу Донбасса : 36 журавлей-красавок, 48 луговых тиркушек , 72 степных пустельг . Во сколько зоопарков можно отправить этих птиц так , чтобы в каждый попало одинаковое количество птиц каждого вида?

Решение

Чтобы узнать, в какое максимальное количество зоопарков можно отправить птиц, нужно найти наибольший общий делитель (НОД) чисел (36, 48 ,72): 

  1. Разложим каждое число на простые множители:

— 36 = 2 × 2 × 3 × 3;

— 48 = 2 × 2 × 2 × 2 × 3;

— 72 = 2 × 2 × 2 × 3 × 3.

  1. Найдём НОД, перемножив выбранные множители: НОД (36, 48, 72) = 2² × 3 = 4 × 3 = 12.

36 = 3 × 12, 48 = 4 × 12, 72 = 6 × 12.

Получили 12 заповедников, куда можно отправить по 3 журавля-красавки, по 4 луговых тиркушки и по 6 степных пустельги.

Ответ: 12 заповедников.

Задача 5.

Из 156 чайных, 234 белых и 390 красных роз сделали букеты, причем во всех букетах роз каждого вида было поровну и число таких букетов было больше 50. Сколько букетов сделали из этих роз и сколько роз каждого вида было в одном букете?

Решение

 Поскольку известно, что букетов больше 50, то 156 делится без остатка на 52 и 78.

Это можно вычислить, разложив на множители: 156 = 2 × 2 × 3 × 13.

Теперь разложим на множители оставшиеся числа 234 и 390.

234 = 2 × 3× 3 × 13.

390 = 2× 3 × 5 × 13.

НОД (156, 234, 390) = 2 × 3 × 13 = 78

Получили 78 букетов, в каждый из которых входят по 2 ромашки, 3 василька и 5 травинок.

Ответ: 78 букетов сделали флористы.

Решение задач на применение НОК

  • Задача 1. 

Из одного центра управления запущены три беспилотника для видеосъемки акватории Азовского моря. Время съемки первого 8 мин, второго 12 мин, а третьего -18 мин.

Через какое время беспилотники одновременно вернуться в центр управления, если их запускают вновь после очередной перезарядки?

Решение

Для определения времени, через которое все беспилотники одновременно вернутся в центр управления, следует найти наибольшее общее кратное их времен нахождения в воздухе без подзарядки.
Разложим числа, соответствующие этим временам, на простые множители:
8 = 23;
12 = 22 ×3;
18 = 32×2;
НОК(8,12,18) = 23 × 32 = 72;
Значит, беспилотники одновременно вернутся в центр управления через 72 мин или 1 час 12 мин.
Ответ: 1 час 12 мин.

  • Задача 2.

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

Дано:

— 12 остроугольных треугольников

— 15 тупоугольных треугольников

Найти: минимальное количество участников, которые могут пользоваться комплектами из одинакового количества каждого вида треугольников.

Решение:

1. Найдём наименьшее общее кратное (НОК) для чисел 12 и 15:

— Разложим на простые множители:

— 12 = 23×3

— 15 = 3×5

НОК = 22×3×5=60

2. Значит, комплекты должны содержать:

— Остроугольных: 60 : 12 = 5 комплектов

— Тупоугольных: 60 : 15 = 4 комплекта

3. Общее количество треугольников в одном комплекте: 5 × 12 + 4 ×15 = 60 + 60 = 120 треугольников

4. Следовательно, минимальное число участников, которые могут пользоваться такими комплектами — 120 человек.

Ответ: 120 участников.

  • Задача 3.

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

Решение.

Дано:

— Время спуска с первой горки: 15 секунд

— Время спуска со второй горки: 20 секунд

— Время спуска с третьей горки: 12 секунд

Решение: чтобы найти наименьшее общее кратное (НОК) для чисел 15, 20 и 12, разложим каждое число на простые множители:

15 = 3×5 

20 = 2×2×5= 22⋅5 

12= 2×2×3=22×3

Находим НОК (15,20,12)

22×3×5=4×3×5=60

Значит, через 60 секунд все три брата одновременно окажутся в бассейне.

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

  • Задача 4.

Военный биатлон открылся парадом военных пехотинцев. Сколько солдат на плацу, если они маршировали строем по 12 человек в шеренге и перестроились по 18 человек в шеренге?

Решение.

Чтобы решить эту задачу, нам нужно найти наименьшее общее кратное (НОК) чисел 12 и 18. Это число будет наименьшим количеством солдат, которое можно построить и по 12, и по 18 человек в шеренге.

1. Разложим каждое число на простые множители:

12 2 18 2

6 2 9 3

3 3 3 3

1 1

Найдем все простые множители и их наибольшую степень: 2× 2× 3 × 3 = 22 × 33 =36

НОК (12, 18) = 22 × 33 = 4 × 9 = 36

Ответ: На плацу было 36 солдат.

  • Задача 5.

Олины родители работают водителями трамваев: мама на2-м маршруте, папа на 5-м. Один рейс 2-го маршрута длится 48 мин, а 5-го 72 мин. У этих маршрутов есть общая конечная станция. Вскоре после начала работы папин и мамин вагоны подошли к ней одновременно. Через какое время они снова встретятся на этой станции?

Найдем через сколько минут вагоны окажутся на конечной станции, для этого вычислим НОК (48, 72)

Решение:

Чтобы определить, через какое время вагоны Олиных родителей снова встретятся на конечной станции, нужно найти наименьшее общее кратное (НОК) длительностей их рейсов.

Дано:

— Длительность рейса 2‑го маршрута (мама): 48 мин.

— Длительность рейса 5‑го маршрута (папа): 72 мин.

Шаг 1. Разложим числа на простые множители

48 2 72 2

24 2 36 2

12 2 18 2

6 2 9 3

3 3 3 3

1 1

Шаг 2. Найдём НОК

НОК (48,72)=24⋅32=16⋅9=144

Ответ:НОК равен 144 минутам. Это означает, что через 144 минуты после одновременного отправления оба вагона снова окажутся на конечной станции вместе, то есть через 2ч. 24 минут.

2.3. Решение задач на применение задач НОД и НОК

Задача1.

Какое наибольшее число наборов можно составить из 48 синих , 48 желтых, 48 зеленых , 72 красных карандашей и 120 картинок – раскрасок?

Дано:

— 48 синих карандашей;

— 48 жёлтых карандашей;

— 48 зелёных карандашей;

— 72 красных карандаша;

— 120 картинок—раскрасок.

Решение:

  1. Найдём общее количество карандашей:

  2. 48 + 48 + 48 + 72 = 216 карандашей.

  3. Общее количество наборов можно найти, разделив общее количество предметов на количество наборов. Предположим, что в одном наборе должно быть одинаковое количество карандашей каждого цвета и одинаковое количество раскрасок.

  4. Для определения максимального числа наборов нужно найти наибольший общий делитель (НОД) для всех количеств.

  5. Найдём НОД для чисел: 48, 48, 48, 72, 120.

  6. Разложим числа на простые множители:

48 = 24 × 3=24×3;

72 = 23× 32

  1. = 23⋅3⋅5.

НОД =23⋅3=24.

Максимальное число наборов:

216 : 24=9 наборов.

В каждом наборе будет:

— по 2 синих карандаша;

—по 2 жёлтых карандаша;

— по 2 зелёных карандаша;

— 3 красных карандаша;

— 5 картинок-раскрасок.

Ответ: максимальное число наборов — 9.

  • Задача 2.

Докажите, что произведение НОД и НОК двух данных чисел равно произведению этих чисел.

Решение:

Возьмём числа - 480 и 940, а следом найдём их НОД и НОК:

480 2 940 2

240 2 470 2

120 2 235 5

60 2 47 47

30 2 1

15 3

5 5

1

НОД (480; 940) = 22×5 = 20

НОК (480; 940) = 480 × 47 = 22.560

Теперь найдём произведение двух данных чисел (480; 940):

  1. 940 = 451.200

Ответ: произведение НОД и НОК двух данных чисел равно произведению этих чисел.

  • Задача 3.

Ученик вычислил НОК (33;198) = 99 . Без вычислений другой ученик определил, что допущена ошибка. В чем ошибка?

Решение:

Ошибка в том, что 99 не может быть НОК для чисел 33 и 198.

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

В данном случае 99 меньше, чем 198. Поэтому 99 не может быть НОК для этих чисел.

 

Заключение

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

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

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

Разработала программу для решения задач нахождения НОД через алгоритм Евклида в Python. А также рассмотрела их практическое применение при решении различных математических задач.

Вывод: цель исследования была достигнута

— НОД и НОК являются фундаментальными понятиями в теории чисел

— Алгоритм Евклида — эффективный способ нахождения НОД

— Метод разложения на простые множители позволяет находить как НОД, так и НОК

В процессе исследования мы выяснили, что навыки нахождения НОД и НОК:

—Помогают упростить вычисления

—Развивают логическое мышление

—Формируют алгоритмический подход к решению задач

— Находят широкое применение в реальной жизни

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

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

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

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

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

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

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

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

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

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

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

Просмотров работы: 13