Эксперт по предмету «Математика»
Задать вопрос автору статьи
Наибольший общий делитель
Определение 2
Если натуральное число a делится на натуральное число $b$, то $b$ называют делителем числа $a$, а число $a$ называют кратным числа $b$.
Пусть $a$ и $b$-натуральные числа. Число $c$ называют общим делителем и для $a$ и для $b$.
Множество общих делителей чисел $a$ и $b$ конечно, так как ни один из этих делителей не может быть больше, чем $a$. Значит ,среди этих делителей есть наибольший, который называют наибольшим общим делителем чисел $a$ и $b$ и для его обозначения используют записи :
Сдай на права пока
учишься в ВУЗе
Вся теория в удобном приложении. Выбери инструктора и начни заниматься!
Получить скидку 3 000 ₽
$НОД (a;b) или D (a;b)$
Чтобы найти наибольший общий делитель двух, чисел необходимо:
- разложить числа на простые множители
- Выбрать числа, которые входят в разложение этих чисел
- Найти произведение чисел , найденных на шаге 2. Полученное число и будет искомым наибольшим общим делителем.
Пример 1
Найти НОД чисел $121$ и $132.$
Будем находить согласно представленному алгоритму. Для этого
-
разложить числа на простые множители
$242=2cdot 11cdot 11$
$132=2cdot 2cdot 3cdot 11$
-
Выбрать числа, которые входят в разложение этих чисел
$242=2cdot 11cdot 11$
$132=2cdot 2cdot 3cdot 11$
-
Найти произведение чисел , найденных на шаге 2.Полученное число и будет искомым наибольшим общим делителем.
$НОД=2cdot 11=22$
Пример 2
Найти НОД одночленов $63$ и $81$.
Будем находить согласно представленному алгоритму. Для этого:
-
Разложим числа на простые множители
$63=3cdot 3cdot 7$
$81=3cdot 3cdot 3cdot 3$
-
Выбираем числа, которые входят в разложение этих чисел
$63=3cdot 3cdot 7$
$81=3cdot 3cdot 3cdot 3$
-
Найдем произведение чисел , найденных на шаге 2.Полученное число и будет искомым наибольшим общим делителем.
$НОД=3cdot 3=9$
«НОД и НОК двух чисел, алгоритм Евклида» 👇
Найти НОД двух чисел можно и по-другому, используя множество делителей чисел.
Пример 3
Найти НОД чисел $48$ и $60$.
Решение:
Найдем множество делителей числа $48$: $left{{rm 1,2,3.4.6,8,12,16,24,48}right}$
Теперь найдем множество делителей числа $60$:$ left{{rm 1,2,3,4,5,6,10,12,15,20,30,60}right}$
Найдем пересечение этих множеств: $left{{rm 1,2,3,4,6,12}right}$- данное множество будет определять множество общих делителей чисел $48$ и $60$. Наибольший элемент в данном множестве будет число $12$. Значит наибольший общий делитель чисел $48$ и $60$ будет $12$.
$D(48;60)=12$
Определение НОК
Определение 3
Общим кратным натуральных чисел $a$ и $b$ называется натуральное число, которое кратно и $a$ и $b$.
Общими кратными чисел называются числа которые делятся на исходные без остатка.Например для чисел $25$ и $50$ общими кратными будут числа $50,100,150,200$ и т.д
Наименьшее из общих кратных будет называться наименьшим общим кратным и обозначается НОК$(a;b)$ или K$(a;b).$
Чтобы найти НОК двух чисел, необходимо:
- Разложить числа на простые множители
- Выписать множители, входящие в состав первого числа и добавить к ним множители, которые входят в состав второго и не ходят в состав первого
- Найти произведение чисел , найденных на шаге 2.Полученное число и будет искомым наименьшим общим кратным
Пример 4
Найти НОК чисел $99$ и $77$.
Будем находить согласно представленному алгоритму. Для этого
-
Разложить числа на простые множители
$99=3cdot 3cdot 11$
$77=7cdot 11$
-
Выписать множители, входящие в состав первого
$3,3,11$
добавить к ним множители, которые входят в состав второго и не ходят в состав первого
$7$
-
Найти произведение чисел , найденных на шаге 2.Полученное число и будет искомым наименьшим общим кратным
$НОК=3cdot 3cdot 11cdot 7=693$
Составление списков делителей чисел часто очень трудоемкое занятие. Существует способ нахождение НОД, называемый алгоритмом Евклида.
Утверждения, на которых основан алгоритм Евклида:
-
Если $a$ и $b$ —натуральные числа, причем $avdots b$, то $D(a;b)=b$
-
Если $a$ и $b$ —натуральные числа, такие что $b
Пользуясь $D(a;b)= D(a-b;b)$, можно последовательно уменьшать рассматриваемые числа до тех пор, пока не дойдем до такой пары чисел, что одно из них делится на другое. Тогда меньшее из этих чисел и будет искомым наибольшим общим делителем для чисел $a$ и $b$.
Свойства НОД и НОК
- Любое общее кратное чисел $a$ и $b$ делится на K$(a;b)$
- Если $avdots b$ , то К$(a;b)=a$
-
Если К$(a;b)=k$ и $m$-натуральное число, то К$(am;bm)=km$
Если $d$-общий делитель для $a$ и $b$,то К($frac{a}{d};frac{b}{d}$)=$ frac{k}{d}$
-
Если $avdots c$ и $bvdots c$ ,то $frac{ab}{c}$ — общее кратное чисел $a$ и $b$
-
Для любых натуральных чисел $a$ и $b$ выполняется равенство
$D(a;b)cdot К(a;b)=ab$
-
Любой общийй делитель чисел $a$ и $b$ является делителем числа $D(a;b)$
Находи статьи и создавай свой список литературы по ГОСТу
Поиск по теме
Нахождение НОК и НОД двух натуральных чисел
Содержание:
- Что такое НОК и НОД двух натуральных чисел
- Особенности вычисления, алгоритм Евклида
- Правило нахождения наибольшего общего делителя (НОД)
- Правило нахождения наименьшего общего кратного (НОК)
Что такое НОК и НОД двух натуральных чисел
Натуральными числами называют числа, которые используются при счете – 1, 2, 3, 16, 25, 101, 2560 и далее до бесконечности. Ноль, отрицательные и дробные или нецелые числа не относятся к натуральным.
Наименьшее общее кратное (НОК) двух натуральных чисел a и b – это наименьшее число, которое делится без остатка на каждое из рассматриваемых чисел.
Наибольший общий делитель (НОД) двух натуральных чисел a и b – это наибольшее число, на которое делится без остатка каждое рассматриваемое число.
Осторожно! Если преподаватель обнаружит плагиат в работе, не избежать крупных проблем (вплоть до отчисления). Если нет возможности написать самому, закажите тут.
Свойства НОК и НОД для натуральных чисел a и b
- (НОД (a, b) = НОД (b, a);)
- (НОК (a, b) = НОК (b, a);)
- (НОК;(a,b)=frac{a;times;b}{НОД;(a,b)}.)
Особенности вычисления, алгоритм Евклида
Рассмотрим два способа определения НОД и НОК с помощью алгоритма Евклида:
- Способ деления.
При делении целых чисел с остатком, где a — делимое, b – делитель (b не равно 0) находят целые числа q и r согласно равенству (a=btimes) q+r, в котором q – неполное частное, r – остаток при делении (не отрицательное, по модулю меньше делителя).
Чтобы вычислить НОД, первоначально нужно выбрать наибольшее из двух чисел и поделить его на меньшее. Пока остаток не станет равным нулю, повторяется цикл деления делителя на остаток от деления в соответствии с формулой.
Пример №1
Вычислим НОД для чисел 12 и 20. Делим 20 на 12 и получаем 1 и 8 в остатке. Запишем иначе:
(20=12times1+8), так как остаток не равняется нулю, продолжаем деление. Делим 12 на 8 и получаем 1 и 4 в остатке. Записываем: (12=8times1+4) и по аналогии делим 8 на 4 и получаем 2 и 0 в остатке. НОД равен остатку, предшествующему нулю.
НОД (12;20) = 4
НОК получаем согласно свойству (НОК (a, b) = НОК;(a,b)=frac{a;times;b}{НОД;(a,b)}.) Подставляем числовые значения:
НОК (12; 20) = (12times20div4=60)
НОК (12;20) = 60
- Способ вычитания.
Здесь повторяется цикл вычитания из наибольшего числа меньшего числа до момента, пока разность не станет равна нулю. НОД равен предшествующей нулю разности.
Пример №2
Вычислим НОД для тех же чисел, 12 и 20.
20 – 12 = 8 (разность не равна нулю, продолжаем)
12 – 8 = 4
8 – 4 = 4
4 – 4 = 0
НОД (12;20) = 4
НОК находим также, как и при методе деления.
Правило нахождения наибольшего общего делителя (НОД)
Для нахождения наибольшего общего делителя воспользуемся пошаговым алгоритмом:
- Разложить числа на простые множители.
- Найти общий множитель одного и другого числа.
- Перемножить общие множители, если их несколько, и их произведение будет НОД.
Пример №3
Возьмем натуральные числа 24 и 36.
(24=2times2times2times3)
(36=2times2times3times3)
Правильно записать следующим образом:
(НОД (24;36)=2times3=6)
Примечание
В случае, когда одно или оба числа относятся к простым, т.е. делятся только на единицу и на само себя, то их НОД равняется 1.
Правило нахождения наименьшего общего кратного (НОК)
Для нахождения наименьшего общего кратного воспользуемся подробным алгоритмом:
- Наибольшее из чисел, а затем остальные разложить на простые множители.
- Выделить те множители, которые отсутствуют у наибольшего.
- Перемножить множители п. 2 и множители наибольшего числа, получить НОК.
Пример №4
Возьмем натуральные числа 9 и 12.
(12=2times2times3)
(9=3times3) (видим, что у числа 12 отсутствует одна тройка)
Правильно записать следующим образом:
(НОК (9;12)=2times2times3times3=36)
Насколько полезной была для вас статья?
Рейтинг: 3.00 (Голосов: 4)
Выделите текст и нажмите одновременно клавиши «Ctrl» и «Enter»
Текст с ошибкой:
Расскажите, что не так
Поиск по содержимому
Наибольший общий делитель (НОД) чисел a и b — это наибольшее число, на которое делятся без остатка числа a и b.
Среди всех способов нахождения наибольшего общего делителя для двух чисел алгоритм Евклида наиболее удобный и простой.
Нахождения НОД и НОК по алгоритму Евклида методом деления
Как известно, деление с остатком целых чисел a — делимое и b — делитель, где b ≠ 0, подразумевает нахождение таких целых чисел q и r, что выполняется равенство:
a = b ∙ q + r, где
q — называется неполным частным,
r — остаток от деления, который не может быть отрицательным числом и по модулю не может быть больше делителя.
Суть метода состоит в том, что сначала выбираем наибольшее из двух чисел, для которых требуется найти НОД и делим большее число на меньшее. Если остаток от деления не равен нулю, делим делитель на остаток от деления, так продолжаем до тех пор, пока остаток от деления не будет равен нулю.
Пример 1
Найдем НОД (36; 30), для этого сначала найдем остаток от деления 36 на 30
36 : 30 = 1 (остаток 6), так как 36 = 30 ∙ 1 + 6, остаток от деления не равен нулю, поэтому продолжаем деление, разделим 30 на 6
30 : 6 = 5 (остаток 0) так как 30 = 6 ∙ 5 + 0, остаток от деления равен нулю, значит НОД равен предыдущему остатку от деление 6
Ответ: НОД (36; 30) = 6
Чтобы найти наименьшее общее кратное НОК чисел a и b необходимо произведение a и b разделить на НОД (a; b)
НОК (36; 30) = (36 ∙ 30) : 6 = 180
Пример 2
Найдем НОД (176; 36), для этого сначала найдем остаток от деления 176 на 36
176 : 36 = 4 (остаток 32) так как 176 = 36 ∙ 4 + 32, остаток от деления не равен нулю, поэтому продолжаем деление, разделим 36 на 32
36 : 32 = 1 (остаток 4) так как 36 = 32 ∙ 1 + 4, остаток от деления не равен нулю, поэтому продолжаем деление, разделим 32 на 4
32 : 4 = 8 (остаток 0) так как 32 = 4 ∙ 8 + 0, остаток от деления равен нулю, значит НОД равен предыдущему остатку от деление 4
Ответ: НОД (176; 36) = 4
Чтобы найти наименьшее общее кратное НОК чисел a и b необходимо произведение a и b разделить на НОД (a; b)
НОК (176; 36) = (176 ∙ 36) : 4 = 1584
Нахождения НОД и НОК по алгоритму Евклида методом вычитания
Суть метода вычитания состоит в том, что необходимо из большего числа вычитать меньшее, если результат вычитания не равен нулю,
тогда уменьшаемое заменяем на получившуюся разность, если разность равна нулю, то НОД равен предыдущему значению разности.
Приведем примеры:
Пример 1
Найдем НОД (36; 30)
36 — 30 = 6
30 — 6 = 24
24 — 6 = 18
18 — 6 = 12
12 — 6 = 6
6 — 6 = 0
Ответ: НОД (36; 30) = 6
Чтобы найти наименьшее общее кратное НОК чисел a и b необходимо произведение a и b разделить на НОД (a; b)
НОК (36; 30) = (36 ∙ 30) : 6 = 180
Пример 2
Найдем НОД (176; 36)
176 — 36 = 140
140 — 36 = 104
104 — 36 = 68
68 — 36 = 32
36 — 32 = 4
32 — 4 = 28
28 — 4 = 24
24 — 4 = 20
20 — 4 = 16
16 — 4 = 12
12 — 4 = 8
8 — 4 = 4
4 — 4 = 0
Ответ: НОД (176; 36) = 4
Чтобы найти наименьшее общее кратное НОК чисел a и b необходимо произведение a и b разделить на НОД (a; b)
НОК (176; 36) = (176 ∙ 36) : 4 = 1584
Алгоритм нахождения НОД и НОК
Скачать материал
Скачать материал
- Сейчас обучается 24 человека из 19 регионов
- Сейчас обучается 48 человек из 25 регионов
Описание презентации по отдельным слайдам:
-
1 слайд
Алгоритм нахождения НОД и НОК
-
2 слайд
Наибольший общий делитель (НОД)
Наибольший общий делитель (НОД) двух данных чисел «a» и «b» — это наибольшее число, на которое оба числа «a» и «b» делятся без остатка. -
3 слайд
Нахождение НОД
Чтобы найти НОД двух или более натуральных чисел нужно:
1) Разложить числа на простые множители.
2) Взять одинаковые простые множители в обоих числах.
3) Найти произведение одинаковых простых множителей. -
4 слайд
Найдем НОД двух чисел 30 и 18
30=2*3*5
18=2*3*3
НОД=2*3=6 -
5 слайд
Определите НОД 2450 и 3500
-
6 слайд
Определите НОД 324, 111 и 432
-
7 слайд
Что такое алгоритм?
Алгори́тм — набор инструкций, описывающих порядок действий исполнителя для достижения некоторого результата -
8 слайд
Пример алгоритма из жизни
-
9 слайд
Евклид
Евкли́д или Эвкли́д (др.-греч. Εὐκλείδης, от «добрая слава», время расцвета — около 300 года до н. э.) — древнегреческий математик, автор первого из дошедших до нас теоретических трактатов по математике. Биографические сведения об Евклиде крайне скудны. Достоверным можно считать лишь то, что его научная деятельность протекала в Александрии в III в. до н. э.
Евклид — первый математик Александрийской школы. Его главная работа «Начала» (Στοιχεῖα, в латинизированной форме — «Элементы») содержит изложение планиметрии, стереометрии и ряда вопросов теории чисел; в ней он подвёл итог предшествующему развитию древнегреческой математики и создал фундамент дальнейшего развития математики. Из других его сочинений по математике надо отметить «О делении фигур», сохранившееся в арабском переводе, 4 книги «Конические сечения», материал которых вошёл в произведение того же названия Аполлония Пергского, а также «Поризмы», представление о которых можно получить из «Математического собрания» Паппа Александрийского. Евклид — автор работ по астрономии, оптике, музыке и др. -
10 слайд
Алгоритм Евклида
Алгоритм Евклида – это алгоритма нахождения НОД.
Выделяют два способа реализации алгоритма: методом деления и методом вычитания. Рассмотрим отдельно каждый из них. -
11 слайд
Метод вычитания
Из большего числа вычитаем меньшее.
Если получается 0, то значит, что числа равны друг другу и являются НОД (следует выйти из цикла).
Если результат вычитания не равен 0, то большее число заменяем на результат вычитания.
Переходим к пункту 1. -
12 слайд
Блок-схема алгоритма Евклида (Вычитанием)
-
13 слайд
Метод деления
Большее число делим на меньшее.
Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла).
Если есть остаток, то большее число заменяем на остаток от деления.
Переходим к пункту 1. -
14 слайд
Блок-схема алгоритма Евклида (делением)
-
15 слайд
Реализация алгоритма в программе Кумир (вычитание)
-
16 слайд
Реализация алгоритма в программе Кумир (деление)
-
17 слайд
Реализация алгоритма Евклида на языке программирования Python
-
18 слайд
Наименьшее общее кратное (НОК)
Наименьшее общее кратное двух целых чисел m и n есть наименьшее натуральное число, которое делится на m и n без остатка. -
19 слайд
Алгоритм нахождения НОК
Для нахождения НОК при помощи алгоритма Евклида нужно:
1. Найти НОД по описанным выше алгоритмам.
2. Разделить произведение чисел m и n на НОД -
20 слайд
Найдем НОК чисел 30 и 18
НОД(30,18)=6
НОК=30*12:6=60 -
-
Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:
6 268 118 материалов в базе
- Выберите категорию:
- Выберите учебник и тему
- Выберите класс:
-
Тип материала:
-
Все материалы
-
Статьи
-
Научные работы
-
Видеоуроки
-
Презентации
-
Конспекты
-
Тесты
-
Рабочие программы
-
Другие методич. материалы
-
Найти материалы
Материал подходит для УМК
Другие материалы
Вам будут интересны эти курсы:
-
Курс повышения квалификации «Внедрение системы компьютерной математики в процесс обучения математике в старших классах в рамках реализации ФГОС»
-
Курс повышения квалификации «Педагогическое проектирование как средство оптимизации труда учителя математики в условиях ФГОС второго поколения»
-
Курс повышения квалификации «Изучение вероятностно-стохастической линии в школьном курсе математики в условиях перехода к новым образовательным стандартам»
-
Курс профессиональной переподготовки «Экономика: теория и методика преподавания в образовательной организации»
-
Курс повышения квалификации «Специфика преподавания основ финансовой грамотности в общеобразовательной школе»
-
Курс повышения квалификации «Особенности подготовки к сдаче ОГЭ по математике в условиях реализации ФГОС ООО»
-
Курс профессиональной переподготовки «Теория и методика обучения информатике в начальной школе»
-
Курс профессиональной переподготовки «Математика и информатика: теория и методика преподавания в образовательной организации»
-
Курс профессиональной переподготовки «Инженерная графика: теория и методика преподавания в образовательной организации»
-
Курс повышения квалификации «Развитие элементарных математических представлений у детей дошкольного возраста»
-
Курс повышения квалификации «Методика преподавания курса «Шахматы» в общеобразовательных организациях в рамках ФГОС НОО»
-
Курс повышения квалификации «Методика обучения математике в основной и средней школе в условиях реализации ФГОС ОО»
-
Курс профессиональной переподготовки «Черчение: теория и методика преподавания в образовательной организации»
-
Скачать материал
-
10.11.2017
19573
-
PPTX
839.8 кбайт -
84
скачивания -
Рейтинг:
2 из 5 -
Оцените материал:
-
-
Настоящий материал опубликован пользователем Минеев Дмитрий Юрьевич. Инфоурок является
информационным посредником и предоставляет пользователям возможность размещать на сайте
методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них
сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайтЕсли Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с
сайта, Вы можете оставить жалобу на материал.Удалить материал
-
- На сайте: 7 лет и 3 месяца
- Подписчики: 0
- Всего просмотров: 21277
-
Всего материалов:
4
