Как найти с помощью перебора нок

НОД, НОД

НОД — это наибольший общий делитель.

НОК — это наименьшее общее кратное.

Определения:

1. Наибольшим общим делителем чисел a и b называется наибольшее число, на которое a и b делятся без остатка.
2. Наименьшее общее кратное (НОК) двух целых чисел m и n есть наименьшее натуральное число, которое делится на m и n без остатка

Способы нахождения НОД двух чисел:

1 способ (следует из определения): Метод полного перебора для нахождения наибольшего общего делителя (НОД)  натуральных чисел.

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

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

1. Найти делители меньшего из данных чисел.
2. Найти, начиная с большего, тот из выписанных делителей, который является также делителем другого числа.
3. Записать найденное число – НОД.

3 способ; Метод нахождения наибольшего общего делителя (НОД) натуральных чисел с помощью разложения на множители.

1. Находим разложение чисел на простые множители.
2. Подчеркиваем общие числа.
3. Находим произведение подчеркнутых чисел у одного числа.
4. Записываем ответ.

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

1. Из большего числа вычитается меньшее.
2. Если получается 0, то числа равны друг другу и являются наибольшим общим делителем.
3. Если результат вычитания не равен 0, то большее число заменяется на результат вычитания.
4. Переход к пункту 1.

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

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

2 способ; Метод нахождения наибольшего общего делителя (НОД) натуральных чисел с помощью разложения на множители

1.  Разложить данные числа на простые множители.
2.  Выписать в строчку множители, входящие в разложение самого большого из чисел, а под ним — разложение остальных чисел.
3.  Подчеркнуть в разложении меньшего числа множители, которые не вошли в разложение бóльшего числа и добавить эти множители в разложение большего числа. 
4.  Полученное произведение записать в ответ. 

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

1. НОД(a, b) = НОД(b, a)
2. НОД(a, b) = НОД(-a, b)
3. НОД(a, b) = НОД(|a|,|b|)
4. НОД(a, 0) = |a|
5. НОД(a, к • a) = |a|, при любом к ∈ Z
6. НОД(a, НОД(b, с)) = НОД(НОД(a, b), c)

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

1. НОК(a, b) = НОК(b, a)
2. НОД(a, b) = НОД(-a, b)
3. НОД(a, b) = НОД(|a|,|b|)
4. НОК(a, НОК(b, с)) = НОК(НОК(a, b), c)

ГОСУДАРСТВЕННОЕ
БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

СРЕДНЯЯ
ОБРАЗОВАТЕЛЬНАЯ ШКОЛА № 377

КИРОВСКОГО
РАЙОНА САНКТ-ПЕТЕРБУРГА

Тема: «НОД и
НОК.»

Памятка
по математике

Для
учеников 5 класса

Автор:
Кудрявцева Лилия Викторовна

НОД и НОК

9

1, 3, 9                                           18, 27, 36, 45 …

НОД	НОК
Наибольший общий делитель (НОД) двух данных чисел a и b — это наибольшее число, на которое оба числа a и b делятся без остатка.	Наименьшим общим кратным (НОК) двух и более натуральных чисел называется наименьшее натуральное число, которое делится нацело на каждое из этих чисел.
I способ нахождения НОД методом перебора делителей 1. Найти делители каждого числа; 2. Найти общие делители; 3. Выбрать наибольший общий делитель. Найти НОД 10 и 15. Д (10) = {1, 2, 5, 10} Д (15) = {1, 3, 5, 15} Д (10, 15) = {1, 5} НОД (10; 15) = 5	I способ нахождения НОК методом перебора кратных 1. Берем большее из чисел 2. Находим числа кратные выбранному (умножая выбранное число последовательно на 1, 2, 3, 4, 5 , и тд) 3. Каждое полученное кратное проверяем делится ли оно на оставшиеся число; первое такое кратное и есть НОК. Найти НОК 18 и 24 24•1=24  (не делится на 18) 24•2=48   (не делится на 18) 24•3=72  —  делится на 18 НОК (24, 18)=72
II способ нахождения НОД через разложения на простые множители 1. Разложить числа на простые множители; 2. Подчеркнуть одинаковые простые множители в  обоих числах; 3. Найти произведение одинаковых простых множителей и записать ответ. Найти НОД  48 и 36. НОД (48; 36) = 2 • 2 • 3 = 12	II способ нахождения НОК через разложения на простые множители 1. Разложить на простые множители каждое число; 2. Выписать все множители из разложения одного любого числа; 3. Добавить к ним недостающие множители из разложения другого числа; 4. Найти произведение получившихся множителей. Найти НОК  24 и 60. 60 = 2 • 2 • 3 • 5   24 = 2 • 2 • 2 • 3                                                                 60 НОК (24; 60) = 2 • 2 • 3 • 5 • 2 =120
Примечание 1: Если a и b взаимно простые* числа, то НОД(a,b)=1 Например:     НОД(4,9)=1	Примечание 1: Если a и b взаимно простые* числа, то НОК(a,b)=a•b Например:     НОК(4, 9)=4•9=36
Примечание 2:  Если a делится на b, то НОД(a,b)=b Например: НОД(120, 60)=60	Примечание 2:  Если a делится на b, то НОК(a,b)=a Например: НОК(120, 60)=120

*Взаимно
простые числа – это те, у которых нет общих
простых делителей. (Например: 4 и 9)

Примечание 1:  Простые числа (1,2,3,5,7,11,13,17 и т.д.) —
взаимно просты

Примечание 2:  Два соседних
натуральных числа (например:  24 и 25) —  взаимно просты

Наименьшее о́бщее кратное (HOK) двух целых чисел — это наименьшее натуральное число, которое делится на оба без остатка, то есть кратно им обоим. К примеру, для чисел 6 и 4, наименьшим общим кратным будет 12.

Как найти НОК?

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

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

Примеры нахождения наименьшего общего кратного

Рассмотрим приведенный алгоритм на конкретных примерах:

Пример 1: найти НОК 4 и 6

2. Возьмем первую группу множителей: 2 · 3.

3. Смотрим вторую группу (2 · 2) и видим, что из двух двоек, одна присутствует в первом разложении. Таким образом, берем только одну двойку. Добавляем к первому разложению и получаем: 2 · 3 · 2

4. Вычисляем произведение: 2 · 3 · 2 = 12.

Ответ: НОК (6; 4) = 12

Пример 2: найти НОК 32 и 20

2. Возьмем первую группу множителей: 2 · 2 · 2 · 2 · 2.

3. Смотрим вторую группу (2 · 2 · 5) и видим, что из двух двоек и пятерки, обе двойки присутствуют в первом разложении. Таким образом, берем только пятерку. Добавляем к первому разложению и получаем: 2 · 3 · 2

4. Вычисляем произведение: 2 · 2 · 2 · 2 · 2 · 5 = 160.

Ответ: НОК (32; 20) = 160

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

Алгоритм поиска НОК

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

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

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

Примеры поиска наименьшего общего кратного

Рассмотрим, как найти НОК с помощью алгоритма на нескольких примерах.

НОК чисел онлайн

Похожие калькуляторы