Как найти наибольший общий делитель чисел

3.9. НОД и НОК: наибольший общий делитель и наименьшее общее кратное

Главная > Образование > Математика > МАТЕМАТИКА «С НУЛЯ» (учебник) >

Множество делителей

Рассмотрим такую задачу: найти делитель числа 140. Очевидно, что у числа 140 не один делитель, а несколько. В таких случаях говорят, что задача имеет множество решений. Найдем их все. Прежде всего разложим данное число на простые множители:

140 = 2 ∙ 2 ∙ 5 ∙ 7.

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

2, 5, 7.

Затем выпишем те, которые получаются попарным умножением простых делителей:

2∙2 = 4, 2∙5 = 10, 2∙7 = 14, 5∙7 = 35.

Затем — те, которые содержат в себе три простых делителя:

2∙2∙5 = 20, 2∙2∙7 = 28, 2∙5∙7 = 70.

Наконец, не забудем единицу и само разлагаемое число:

1, 140.

Все найденные нами делители образуют множество делителей числа 140, которое записывается с помощью фигурных скобок:

Множество делителей числа 140 =

{1, 2, 4, 5, 7, 10, 14, 20, 28, 35, 70, 140}.

Для удобства восприятия мы выписали здесь делители (элементы множества) в порядке возрастания, но, вообще говоря, это делать необязательно. Кроме того, введем сокращение записи. Вместо «Множество делителей числа 140» будем писать «Д(140)». Таким образом,

Д(140) = {1, 2, 4, 5, 7, 10, 14, 20, 28, 35, 70, 140}.

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

105 = 3 ∙ 5 ∙ 7

мы получаем:

Д(105) = {1, 3, 5, 7, 15, 21, 35, 105}.

От множества всех делителей следует отличать множество простых делителей, которые для чисел 140 и 105 равны соответственно:

ПД(140) = {2, 5, 7}.

ПД(105) = {3, 5, 7}.

Следует особо подчеркнуть, что в разложении числа 140 на простые множители двойка присутствует два раза, в то время как во множестве ПД(140) — только один. Множество ПД(140) — это, по своей сути, все ответы на задачу: «Найти простой множитель числа 140». Ясно, что один и тот же ответ не следует повторять больше одного раза.

Сокращение дробей. Наибольший общий делитель

Рассмотрим дробь

105 / 140.

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

Д(105) = {1, 3, 5, 7, 15, 21, 35, 105};

Д(140) = {1, 2, 4, 5, 7, 10, 14, 20, 28, 35, 70, 140}.

Общие элементы множеств Д(105) и Д(140) =

{1, 5, 7, 35}.

Последнее равенство можно записать короче, а именно:

Д(105) ∩ Д(140) = {1, 5, 7, 35}.

Здесь специальный значок «∩» («мешок отверстием вниз») как раз и указывает на то, что из двух множеств, записанных по разные стороны от него, надо выбрать только общие элементы. Запись «Д(105) ∩ Д(140)» читается «пересечение множеств Дэ от 105 и Дэ от 140».

[Заметим по ходу дела, что с множествами можно производить разные бинарные операции, почти как с числами. Другой распространенной бинарной операцией является объединение, которое обозначается значком «∪» («мешок отверстием вверх»). В объединение двух множеств входят все элементы как того, так и другого множества:

ПД(105) = {3, 5, 7};

ПД(140) = {2, 5, 7};

ПД(105) ∪ ПД(140) = {2, 3, 5, 7}. ]

Итак, мы выяснили, что дробь

105 / 140

можно сократить на любое из чисел, принадлежащих множеству

Д(105) ∩ Д(140) = {1, 5, 7, 35}

и нельзя сократить ни на какое другое натуральное число. Вот все возможные способы сокращения (за исключением неинтересного сокращения на единицу):

105	=	105/5	=	21	;
140	140/5	28

105	=	105/7	=	15	;
140	140/7	20

105	=	105/35	=	3	.
140	140/35	4

Очевидно, что практичнее всего сокращать дробь на число, по возможности большее. В данном случае это число 35, про которое говорят, что оно является наибольшим общим делителем (НОД) чисел 105 и 140. Это записывается как

НОД(105, 140) = 35.

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

105 = 3 ∙ 5 ∙ 7;

140 = 2 ∙ 2 ∙ 5 ∙ 7.

Перемножая подчеркнутые числа (в любом из разложений), получаем:

НОД(105, 140) = 5 ∙ 7 = 35.

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

168 = 2 ∙ 2 ∙ 2 ∙ 3 ∙ 7;

396 = 2 ∙ 2 ∙ 3 ∙ 3 ∙ 11.

Отсюда видно, что

НОД(168, 396) = 2 ∙ 2 ∙ 3 = 12.

Особого упоминания заслуживает ситуация, когда общих множителей совсем нет и подчеркивать нечего, например:

42 = 2 ∙ 3 ∙ 7;

55 = 5 ∙ 11.

В этом случае,

НОД(42, 55) = 1.

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

42 / 55,

то такая дробь является несократимой.

Вообще говоря, правило сокращения дробей можно записать в таком виде:

a	=	a / НОД(a, b)	.
b	b / НОД(a, b)

Здесь предполагается, что a и b — натуральные числа, а вся дробь положительна. Если мы теперь припишем знак «минус» к обоим частям этого равенства, то получим соответствующее правило для отрицательных дробей.

Сложение и вычитание дробей. Наименьшее общее кратное

Пусть требуется вычислить сумму двух дробей:

Мы уже знаем, как раскладываются на простые множители знаменатели:

105 = 3 ∙ 5 ∙ 7;

140 = 2 ∙ 2 ∙ 5 ∙ 7.

Из этого разложения сразу следует, что, для того чтобы привести дроби к общему знаменателю, достаточно числитель и знаменатель первой дроби умножить на 2 ∙ 2 (произведение неподчеркнутых простых множителей второго знаменателя), а числитель и знаменатель второй дроби — на 3 («произведение» неподчеркнутых простых множителей первого знаменателя). В результате знаменатели обеих дробей станут равны числу, которое можно представить так:

2 ∙ 2 ∙ 3 ∙ 5 ∙ 7 = 105 ∙ 2 ∙ 2 = 140 ∙ 3 = 420.

Нетрудно видеть, что оба исходных знаменателя (как 105, так и 140) являются делителями числа 420, а число 420, в свою очередь, кратно обоим знаменателям, — и не просто кратно, оно является наименьшим общим кратным (НОК) чисел 105 и 140. Это записывается так:

НОК(105, 140) = 420.

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

105 ∙ 140 = НОК(105, 140) ∙ НОД(105, 140).

Точно так же, для произвольных натуральных чисел b и d:

b ∙ d = НОК(b, d) ∙ НОД(b, d).

Теперь давайте доведем до конца суммирование наших дробей:

1	+	1	=
3 ∙ 5 ∙ 7	2 ∙ 2 ∙ 5 ∙ 7

2 ∙ 2	+	3	=
2 ∙ 2 ∙ 3 ∙ 5 ∙ 7	2 ∙ 2 ∙ 3 ∙ 5 ∙ 7

4 + 3	=
2 ∙ 2 ∙ 3 ∙ 5 ∙ 7

Подобным же образом можно посчитать разность:

Из «бесконечного» сборника типовых упражнений

Задачи, где требуется разлагать числа на простые множители

Примечание. Для решения некоторых задач требуется знать, что такое квадрат числа. Квадратом числа a называется число a, помноженное само на себя, то есть a∙a. (Как нетрудно видеть, оно равно площади квадрата со стороной a).

Источник: http://nekin.info/math/m0309.htm

Подскажите как найти наибольший общий делитель нескольких натуральных чисел ((6 класс))

Анатолий Бежин Профи (702) 4 года назадчтобы найти наибольший общий делитель нескольких натуральных чисел, надо: 1)разложить их на простые множители; 2)выписать те множители, которые входят в разложение каждого из чисел; 3)найти произведение этих множителей.

Примеры: а) найти НОД (6600; 6300): 6600 = 2 • 2 • 2 • 3 • 5 • 5 • 11, 6300 = 2 • 2 • 3 • 3 • 5 • 5 • 7, НОД (6600; 6300) = 2 • 2 • 3 • 5 • 5 = 300; б) найти НОД (34 398; 1260; 6552): 34 398 — 2 • 3 • 3 • 3 • 7 • 7 • 13, 1260 = 2 • 2 • 3 • 3 • 5 • 7, 6562 = 2 • 2 • 2 • 3 • 3 • 7 • 13, НОД (34 398; 1260; 6652) = 2 • 3 • 3 • 7 = 126.

При нахождении наибольшего общего делителя двух чисел полезно знать еще одно правило, называемое «алгоритмом Евклида» . Пример. Найти НОД (270; 186). Разделим 270 на 186 с остатком: 270 : 186 = 1 (ост. 84). Далее разделим делитель на остаток и т. д. : 186 : 84 = 2 (ост. 18), 84 : 18 = 4 (ост. 12), 18 : 12 = 1 (ост. 6), 12 : 6 = 2 (ост. 0).

Наибольшим общим делителем чисел 270 и 186 является последний ненулевой остаток, т. е. число 6. Пример. Найти НОД (234; 180). 1)234 : 180 = 1 (ост. 54), 2)180: 54 = 3 (ост. 18), 3)54 : 18 = 3 (ост. 0). Следовательно, НОД (234; 180) = 18. Натуральные числа называют взаимно простыми, если их наибольший общий делитель равен единице.

Примеры: а) 75 и 14 — взаимно простые числа, так как НОД (75; 14)= 1;

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

Источник: http://shpargalka.kz/matematika/naibolshii-obshii-delitel

*DAN* Профи (792) 4 года назадНаибольшим общим делителем (НОД) для двух целых чисел m и n называется наибольший из их общих делителей. Пример: для чисел 70 и 105 наибольший общий делитель равен 35. Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел m или n не ноль. Возможные обозначения наибольшего общего делителя чисел m и n: НОД (m, n) (m, n) gcd(m, n) (от англ. Greatest Common Divisor) hcf(m, n) (от брит. англ. Highest Common Factor) Эффективными способами вычисления НОД двух чисел являются алгоритм Евклида и бинарный алгоритм. Кроме того, значение НОД (m,n) можно легко вычислить, если известно каноническое разложение чисел m, n на простые множители: n=p_1^{d_1}cdotdotscdot p_k^{d_k}, m=p_1^{e_1}cdot dots cdot p_k^{e_k}, где p_1,dots,p_k — различные простые числа, а d_1,dots,d_k и e_1,dots,e_k — неотрицательные целые числа (они могут быть нулями, если соответствующее простое отсутствует в разложении) . Тогда НОД (m,n) и НОК (m,n) выражаются формулами: (n,m)=p_1^{min(d_1,e_1)}cdotdotscdot p_k^{min(d_k,e_k)}, [n,m]=p_1^{max(d_1,e_1)}cdotdotscdot p_k^{max(d_k,e_k)}. Если чисел более двух: a_1, a_2,dots a_n, их НОД находится по следующему алгоритму: d_2=(a_1, a_2) d_3=(d_2, a_3) ………

d_n=(d_{n-1}, a_n) — это и есть искомый НОД.

Источник: Красный диплом

Денис Билокрилец Ученик (124) 2 года назадчтобы найти наибольший общий делитель нескольких натуральных чисел, надо: 1)разложить их на простые множители; 2)выписать те множители, которые входят в разложение каждого из чисел; 3)найти произведение этих множителей. Примеры: а) найти НОД (6600; 6300): 6600 = 2 • 2 • 2 • 3 • 5 • 5 • 11, 6300 = 2 • 2 • 3 • 3 • 5 • 5 • 7, НОД (6600; 6300) = 2 • 2 • 3 • 5 • 5 = 300; б) найти НОД (34 398; 1260; 6552): 34 398 — 2 • 3 • 3 • 3 • 7 • 7 • 13, 1260 = 2 • 2 • 3 • 3 • 5 • 7, 6562 = 2 • 2 • 2 • 3 • 3 • 7 • 13, НОД (34 398; 1260; 6652) = 2 • 3 • 3 • 7 = 126.

При нахождении наибольшего общего делителя двух чисел полезно знать еще одно правило, называемое «алгоритмом Евклида» . Пример. Найти НОД (270; 186). Разделим 270 на 186 с остатком: 270 : 186 = 1 (ост. 84). Далее разделим делитель на остаток и т. д. : 186 : 84 = 2 (ост. 18), 84 : 18 = 4 (ост. 12), 18 : 12 = 1 (ост. 6), 12 : 6 = 2 (ост. 0).

Примеры: а) 75 и 14 — взаимно простые числа, так как НОД (75; 14)= 1;

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

Кристина Анисимова Ученик (121) 1 год назадПримеры: а) найти НОД (6600; 6300): 6600 = 2 • 2 • 2 • 3 • 5 • 5 • 11, 6300 = 2 • 2 • 3 • 3 • 5 • 5 • 7, НОД (6600; 6300) = 2 • 2 • 3 • 5 • 5 = 300; б) найти НОД (34 398; 1260; 6552): 34 398 — 2 • 3 • 3 • 3 • 7 • 7 • 13, 1260 = 2 • 2 • 3 • 3 • 5 • 7, 6562 = 2 • 2 • 2 • 3 • 3 • 7 • 13, НОД (34 398; 1260; 6652) = 2 • 3 • 3 • 7 = 126. При нахождении наибольшего общего делителя двух чисел полезно знать еще одно правило, называемое «алгоритмом Евклида» . Пример. Найти НОД (270; 186). Разделим 270 на 186 с остатком: 270 : 186 = 1 (ост. 84). Далее разделим делитель на остаток и т. д. : 186 : 84 = 2 (ост. 18), 84 : 18 = 4 (ост. 12), 18 : 12 = 1 (ост. 6), 12 : 6 = 2 (ост. 0).

Примеры: а) 75 и 14 — взаимно простые числа, так как НОД (75; 14)= 1;

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

Галина Донченко Знаток (282) 1 год назад

Вычислите наибольший общий делитель чисел 77164189341682084692124351766096496451364840671846455244761 и
46668734283684548617206823665104829826096872771679324943689.

Артём Булгаков Знаток (344) 1 год назад

разложить на простые множители

Егор Пашон Ученик (120) 1 год назадчтобы найти наибольший общий делитель нескольких натуральных чисел, надо:1)разложить их на простые множители;2)выписать те множители, которые входят в разложение каждого из чисел;3)найти произведение этих множителей.Примеры:а) найти НОД (6600; 6300):6600 = 2 • 2 • 2 • 3 • 5 • 5 • 11,6300 = 2 • 2 • 3 • 3 • 5 • 5 • 7,НОД (6600; 6300) = 2 • 2 • 3 • 5 • 5 = 300;б) найти НОД (34 398; 1260; 6552):34 398 — 2 • 3 • 3 • 3 • 7 • 7 • 13,1260 = 2 • 2 • 3 • 3 • 5 • 7,6562 = 2 • 2 • 2 • 3 • 3 • 7 • 13,НОД (34 398; 1260; 6652) = 2 • 3 • 3 • 7 = 126.При нахождении наибольшего общего делителя двух чисел полезно знать еще одно правило, называемое «алгоритмом Евклида» .Пример. Найти НОД (270; 186). Разделим 270 на 186 с остатком:270 : 186 = 1 (ост. 84). Далее разделим делитель на остаток и т. д. : 186 : 84 = 2 (ост. 18), 84 : 18 = 4 (ост. 12), 18 : 12 = 1 (ост. 6), 12 : 6 = 2 (ост. 0).Наибольшим общим делителем чисел 270 и 186 является последний ненулевой остаток, т. е. число 6.Пример. Найти НОД (234; 180).1)234 : 180 = 1 (ост. 54),2)180: 54 = 3 (ост. 18),3)54 : 18 = 3 (ост. 0). Следовательно, НОД (234; 180) = 18.Натуральные числа называют взаимно простыми, если их наибольший общий делитель равен единице.Примеры:а) 75 и 14 — взаимно простые числа, так как НОД (75; 14)= 1;

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

Александр Сергеев Ученик (112) 1 год назад

…

Даша Маньковская Знаток (257) 5 месяцев назад

ххх

Источник: https://otvet.mail.ru/question/94766490

Наибольший общий делитель

Главная ← Математика ← Теория ← Наибольший общий делитель

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

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

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

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

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

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

https://www.youtube.com/watch?v=Lkw7OMRlsLk

Пример 1:

Найдите наибольший общий делитель чисел 420 и 990.

Решение:

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

Получили, что:

420 = 2 ⋅ 2 ⋅ 3 ⋅ 5 ⋅ 7

990 = 2 ⋅ 3 ⋅ 3 ⋅ 5 ⋅ 11

Выпишем все совпадающие множители для обоих чисел и перемножим их:

Ответ: 30

Пример 2:

Найдите наибольший общий делитель чисел 588 и 1820.

Решение:

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

Получили, что:

588 = 2 ⋅ 2 ⋅ 3 ⋅ 7 ⋅ 7

1820 = 2 ⋅ 2 ⋅ 5 ⋅ 7 ⋅ 13

Выпишем все совпадающие множители для обоих чисел и перемножим их:

Ответ: 28

Пример 3:

Найдите наибольший общий делитель чисел 1000 и 3267.

Решение:

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

Получили, что:

1000 = 2 ⋅ 2 ⋅ 2 ⋅ 5 ⋅ 5 ⋅ 5

3267 = 3 ⋅ 3 ⋅ 3 ⋅ 11 ⋅ 11

Совпадающих множителей у этих 2 чисел нет, поэтому они являются взаимно простыми, то есть

Ответ: 1

Источник: http://worksbase.ru/matematika/teoriya/19-naibolshii-obshchii-delitel.html

Наибольший общий делитель

Найти наибольший общий делитель(НОД) Найти наименьшее общее кратное (НОК)Запомните!

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

Любое натуральное число всегда делится на 1 и на само себя.

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

Простых чисел много, и первое среди них — число 2. Однако нет последнего простого числа. В разделе «Для учёбы» вы можете скачать таблицу простых чисел до 997.

Но многие натуральные числа делятся нацело ещё и на другие натуральные числа.

Например:

число 12 делится на 1, на 2, на 3, на 4, на 6, на 12;
число 36 делится на 1, на 2, на 3, на 4, на 6, на 12, на 18, на 36.

Числа, на которые число делится нацело (для 12 это 1, 2, 3, 4, 6 и 12) называются делителями числа.

Запомните!

Делитель натурального числа a — это такое натуральное число, которое делит данное число «a» без остатка.

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

Обратите внимание, что числа 12 и 36 имеют общие делители. Это числа: 1, 2, 3, 4, 6, 12. Наибольший из делителей этих чисел — 12.

Общий делитель двух данных чисел «a» и «b» — это число, на которое делятся без остатка оба данных числа «a» и «b».

Запомните!

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

Кратко наибольший общий делитель чисел «a» и «b» записывают так:

НОД (a; b).

Пример: НОД (12; 36) = 12.

Делители чисел в записи решения обозначают большой буквой «Д».

Пример.

Д (7) = {1, 7}

Д (9) = {1, 9}

НОД (7; 9) = 1

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

Запомните!

Взаимно простые числа — это натуральные числа, которые имеют только один общий делитель — число 1. Их НОД равен 1.

Как найти наибольший общий делитель

Чтобы найти НОД двух или более натуральных чисел нужно:

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

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

Поясним сразу на примере. Разложим на простые множители числа 28 и 64.

Подчёркиваем одинаковые простые множители в обоих числах.
28 = 2 · 2 · 7
64 = 2 · 2 · 2 · 2 · 2 · 2
Находим произведение одинаковых простых множителей и записать ответ;
НОД (28; 64) = 2 · 2 = 4
Ответ: НОД (28; 64) = 4

Оформить нахождение НОД можно двумя способами: в столбик (как делали выше) или «в строчку».

Первый способ записи НОД

Найти НОД 48 и 36.

НОД (48; 36) = 2 · 2 · 3 = 12

Второй способ записи НОД

Теперь запишем решение поиска НОД в строчку. Найти НОД 10 и 15.

Д (10) = {1, 2, 5, 10}

Д (15) = {1, 3, 5, 15}

Д (10, 15) = {1, 5}

НОД (10; 15) = 5

Источник: http://math-prosto.ru/?page=pages%2Ffind_nod_and_nok%2Ffind_nod.php

Наибольший общий делитель. Наименьшее общее кратное

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

Рассмотрим нахождения НОД на примере двух натуральных чисел 18 и 60:

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

324 = 2 × 2 × 3 × 3 × 3 × 3

111 = 3 × 37

432 = 2 × 2 × 2 × 2 × 3 × 3 × 3

Вычеркнуть из первого числа, множители которых нету во втором и третьем числе, получим:

2 × 2 × 2 × 2 × 3 × 3 × 3 = 3

В результате НОД(324, 111, 432)=3

Нахождение НОД с помощью алгоритма Евклида

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

Рекуррентная формула для НОД, НОД(a, b)=НОД(b, a mod b), где a mod b — остаток от деления a на b.

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

Найдем НОД(7920, 594) с помощью алгоритма Евклида, вычислять остаток от деления будем с помощью калькулятора.

НОД(7920, 594)
НОД(594, 7920 mod 594) = НОД(594, 198)
НОД(198, 594 mod 198) = НОД(198, )
НОД(198, ) = 198

7920 mod 594 = 7920 — 13 × 594 = 198
594 mod 198 = 594 — 3 × 198 = 0

В результате получаем НОД(7920, 594) = 198

Источник: http://calcs.su/html/calcs/math/nodnok.html

Нахождение наиМЕНЬШЕГО общего кратного (НОК) и наиБОЛЬШЕГО общего делителя (НОД) натуральных чисел. Примерно 6-класс (11-12 лет)

Нахождение наиМЕНЬШЕГО общего кратного (НОК) и наиБОЛЬШЕГО общего делителя (НОД) натуральных чисел.

Определение НОК: Наименьшим общим кратным (НОК) натуральных чисел а и в называют наименьшее натуральное число c, которное кратно и a, и b.

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

Нахождение наиМЕНЬШЕГО общего кратного (НОК) и наиБОЛЬШЕГО общего делителя НОД натуральных чисел. 6-класс (11-12 лет)

НОК — наименьшее общее кратное
НОД — наибольший общий делитель

Памятка: Существуют два подхода к определению натуральных чисел

числа, используемые при: перечислении (нумеровании) предметов (первый, второй, третий, …); — в школах, обычно так.
обозначении количества предметов (нет покемонов — ноль, один покемон, два покемона, …).

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

Памятка: Делителем натурального числа a называют число b, на которое a делится без остатка. Кратным натуральному числу b называют натуральное число a , которое делится на b без остатка.

Если число b — делитель числа a , то a кратно числу b . Пример: 2 — делитель 4, а 4 кратно двум. 3 — делитель 12, а 12 кратно 3.
Памятка: Натуральные числа называют простыми, если они делятся без остатка только на себя и на 1.

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

Определение как найти НОК в общем случае: Чтобы найти НОК (Наименьшее общее кратное) нескольких натуральных чисел надо:
1) Разложить их на простые множители. (Для этого Вам может очень пригодиться Таблица простых чисел.) 2) Выписать множители, входящие в разложение одного из них. 3) Добавить к ним недостающие множители из разложений других чисел.

4) Перемножить множители, получившиеся в п.3).

Задача 1 (на НОК): Коля Пузатов раньше съедал булочек на 60 рублей в день. Когда у него совсем не оставалось денег, он шел к любимой мамуле и получал определенную сумму авансом на булочки.

Потом Коля Пузатов подрос и стал съедать булочек на 75 рублей в день. Получив ту же сумму от мамы он обнаружил, что сдачи у него опять совсем не остается.

Какую наименьшую сумму давала ему мама на булочки авансом?

Пример 1.1. решения задачи на нахождение НОК. Нахождение НОК подбором.
Решение: Эта сумма дожна делиться и на 60 рублей, и на 75 рублей без остатка.

1) Выпишем числа кратные 60: 60, 120, 180, 240, 300, 360, 420, 480
2) Выпишем числа кратные 75: 75, 150, 225, 300 Выбираем наименьшее общее кратное. Опа-на! Нашли, эта сумма = 300.

Не забываем размерность и пишем ответ:
Ответ: Мама дает по 300 рублей.

Пример 1.2. решения задачи на нахождение НОК. Нахождение НОК в общем случае.
Решение: Эта сумма дожна делиться и на 60 рублей, и на 75 рублей без остатка.
1)Выполним разложение 75 и 60 на простые множители. (Для этого Вам может очень пригодиться Таблица простых чисел.)

60	2	75	5
30	2	15	5
15	3	3	3
5	5	1
1

60=2*2*3*5 75=3*5*5 2) Выпишем множители, входящие в разложение первого из этих чисел и добавим к ним недостающий множитель 5 из разложения второго числа. Получаем: 2*2*3*5*5=300. Нашли НОК, т.е. эта сумма = 300. Не забываем размерность и пишем ответ:

Ответ: Мама дает по 300 рублей.

НОК — наименьшее общее кратное
НОД — наибольший общий делитель

Определение НОД: Наибольшим общим делителем (НОД) натуральных чисел а и в называют наибольшее натуральное число c, на которое и a, и b делятся без остатка. Т.е. c это нибольшее натуральное число, для которого и а и б являются кратными.

Памятка: Существуют два подхода к определению натуральных чисел

числа, используемые при: перечислении (нумеровании) предметов (первый, второй, третий, …); — в школах, обычно так.
обозначении количества предметов (нет покемонов — ноль, один покемон, два покемона, …).

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

Определение как найти НОД в общем случае: Чтобы найти НОД (Наибольший общий делитель) нескольких натуральных чисел надо:
1) Разложить их на простые множители. (Для этого Вам может очень пригодиться Таблица простых чисел.) 2) Выписать множители, входящие в разложение одного из них. 3) Вычеркнуть те, которые не входят в разложение остальных чисел.

4) Перемножить множители, получившиеся в п.3).

Задача 2 на (НОК): К новому году Коля Пузатов купил в городе 48 хомяков и 36 кофейников. Фекла Дормидонтова, как самая честная девочка класса, получила задание разделить это имущество на наибольшее возможное число подарочных наборов для учителей. Какое число наборов получилось? Какой состав наборов?

Пример 2.1. решения задачи на нахождение НОД. Нахождение НОД подбором.
Решение: Каждое из чисел и 48, и 36 должно делиться на число подарков.

1) Выпишем делители 48: 48, 24, 16, 12, 8, 6, 3, 2, 1
2) Выпишем делители 36: 36, 18, 12, 9, 6, 3, 2, 1 Выбираем наибольший общий делитель. Оп-ля-ля! Нашли, это число наборов 12 штук.

3) Поделим 48 на 12 получим 4, поделим 36 на 12, получим 3. Не забываем размерность и пишем ответ:

Ответ: Получится 12 наборов по 4 хомяка и 3 кофейника в каждом наборе.

Пример 2.2. решения задачи на НОД. Нахождение НОД в общем случае.
Решение: Каждое из чисел и 48, и 36 должно делиться на число подарков.
1)Выполним разложение 48 и 36 на простые множители. (Для этого Вам может очень пригодиться Таблица простых чисел.)

48	2	36	2
24	2	18	2
12	2	9	3
6	2	3	3
3	3	1
1

48=2*2*2*2*3 36=2*2*3*3

2) Выпишем множители, входящие в разложение первого из этих чисел и вычеркнем те, которые не входят в разложение второго числа. Получаем: 2*2*2*2*3=2*2*3=12. Нашли НОД = 12, т.е. это число наборов 12 штук.

3) Поделим 48 на 12 получим 4, поделим 36 на 12, получим 3. Не забываем размерность и пишем ответ:

Ответ: Получится 12 наборов по 4 хомяка и 3 кофейника в каждом наборе.

Источник: http://TehTab.ru/Guide/GuideMathematics/MathsForTheYoungest/FindingNODandNOK/

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

Наибольший общий делитель.

Наибольший общий делитель – это наибольшее натуральное число, на которое делятся без остатка числа a и b.

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

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

2) из множителей, входящих в разложение одного из этих чисел, вычеркнуть те, которые не входят в разложение других чисел;

3) найти произведение оставшихся множителей.

Пример: найдем НОД чисел 48 и 36. Для этого находим делители обоих чисел (рис.1):

Итак, 48 = 2 · 2 · 2· 2 · 3, а 36 = 2 · 2 · 3 · 3.

Из множителей, входящих в разложение первого числа, вычеркнем те, которые не входят в разложение второго числа -т.е. две двойки (рис.2)

В столбце с вычеркнутыми числами остаются множители 2 · 2 · 3. Их произведение равно 12. Это число и является НОД чисел 48 и 36. То есть 12 — наибольшее общее число, на которое делятся 48 и 36.

Если НОД натуральных чисел равен 1, то эти числа называют взаимно простыми (например, числа 24 и 35).

Наименьшее общее кратное.

Наименьшее общее кратное чисел a и b – это наименьшее натуральное число, которое делится на оба эти числа.

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

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

2) выписать множители, входящие в разложение одного из чисел;

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

4) найти произведение получившихся множителей.

Пример: найдем НОК тех же чисел 48 и 36.

Как и в случае с НОД, сначала находим делители обоих чисел. Впрочем, мы уже нашли их в предыдущем примере (рис.3):

Из разложения второго числа вычеркиваем множители, которые входят в разложение первого числа (рис.4).

Теперь выпишем множители, входящие в разложение первого числа, добавим к ним оставшийся множитель из разложения второго числа (3), перемножим их и получим результат:

2 ∙ 2 ∙ 2 ∙ 2 ∙ 3 ∙ 3 = 144.

Число 144 – это и есть НОК чисел 48 и 36. То есть 144 – это минимальное число, которое делится без остатка и на 48, и на 36.

Источник: http://raal100.narod.ru/index/0-220

Наибольший общий делитель. Алгоритм Евклида. Видеоурок. Математика 6 Класс

Давайте разберемся, что означает понятие «наибольший общий делитель».

Попробуем объяснить в не строгой форме.

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

Сейчас рассмотрим пример, который иллюстрирует данную идею:

У нас есть 48 шоколадок, и 36 конфет. Мы хотим из этого набора составить некоторые комплекты, которые мы подарим детям на Новый Год. Какое наибольшее количество комплектов мы можем сделать так, чтобы всем детям досталось поровну?

Решение:

Чтобы поделить шоколадки и конфеты поровну нам нужно разделить и шоколадки и кофеты нацело на количество подарков. Например, если поделить их на два подарка, то в каждом подарке будет по 24 шоколадки, и 18 конфет. То есть количество шоколадок или конфет нужно поделить на количество подарков, и оно будет делителем количества шоколадок или конфет.

Давайте найдем наибольший общий делитель чисел 48 и 36.

Выпишем все делители для обоих чисел:48:

1, 2, 3, 4, 6, 8, 12, 16, 24, 48
36: 1, 2, 3, 4, 6, 9, 12, 18, 36

Давайте выделим из них общие делители:

Наибольший из общих делителей – 12.

Значит, мы можем сделать 12 подарков, и не сложно посчитать, что в каждом из них будет по 4 шоколадки, и по 3 конфеты.

Ответ: 12 комплектов.

Давайте дадим точное определение наибольшему общему делителю.

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

Есть два числа , их наибольший делитель будет записан так:

Например,.

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

Существует еще такая форма записи НОД:

Но чаще используют первый вариант.

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

Первое свойство.

У любых двух чисел есть хотя бы один общий делитель, и это число 1.

И здесь мы введем понятие взаимно простых чисел.

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

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

Например, числа 2 и 3, которые мы рассматривали выше. Числа 3 и 7 также взаимно простые.

Очень важно не путать понятия взаимно простых чисел, и простых чисел.

Из того что числа взаимно простые еще не следует, что они простые.

Например,. Тем не менее ни 9, ни 10 не являются простыми числами, но они взаимно простые.

Второе свойство.

Как вы думаете, если даны два числа и , причем нацело делится на (), чему тогда равен?

– такое наибольшее число, на которое делятся и , и . Логично, что наибольшее число, на которое делится – , а – по условию.

Значит,.

Например,;

Аналогично;

, потому что и больше 1 результат быть не может.

Теперь давайте найдем удобный способ нахождения НОД.

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

Рассмотрим все те же числа 36 и 48:

– это т.н. «каноническое разложение» числа 36;

Давайте выделим общие множители столько раз, сколько они встречаются в результате разложения каждого числа: 2 ,2 ,3.

При перемножении этих чисел мы и получим НОД.

Ответ: 12.

Давайте рассмотрим другой пример.

Возьмем числа 25 и 40. Найдем НОД.

;

Ответ: 5.

Между прочим, если мы будем искать НОД трех чисел, то это делается без труда по такому же методу.

Давайте попробуем на примере.

Найти.

Ответ: 4;

Итак, мы с вами научились вычислять НОД двух чисел и трех чисел.

Давайте теперь рассмотрим еще несколько свойств НОД.

;

Вспомним, что такое простые числа. Простое число – это число, которое имеет ровно два натуральных делителя – единицу и себя.

; , – различные простые числа, следовательно эти числа – взаимно простые;
; т.е. последовательные числа также взаимно простые

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

Если взять числа больше, например, 143 и 257, разложение на множители уже не так очевидно, как в случае с 16 и 36, поэтому нужно найти универсальный метод, который бы работал для любых чисел, даже если разложение на множители затруднено. И такой универсальный метод есть. Он называется алгоритм Евклида. Этому алгоритму уже более двух тысяч лет, и тем не менее он радует глаз математиков и по сей день.

Найдем.

Идея алгоритма в следующем: заменяем большее из чисел их разностью.

при этом НОД не меняется.

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

Продолжим

Можно продолжать и дальше, но тут ответ уже очевиден

, т.к..

Ответ 11.

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

, т.к.

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

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

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

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

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

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

1. Виленкин Н.Я., Жохов В.И., Чесноков А.С., Шварцбурд С.И. Математика 6. – М.: Мнемозина, 2012.

2. Мерзляк А.Г., Полонский В.В., Якир М.С. Математика 6 класс. – Гимназия. 2006.

3. Депман И.Я., Виленкин Н.Я. За страницами учебника математики. – М.: Просвещение, 1989.

4. Рурукин А.Н., Чайковский И.В. Задания по курсу математика 5–6 класс. – М.: ЗШ МИФИ, 2011.

5. Рурукин А.Н., Сочилов С.В., Чайковский К.Г. Математика 5–6. Пособие для учащихся 6-х классов заочной школы МИФИ. – М.: ЗШ МИФИ, 2011.

6. Шеврин Л.Н., Гейн А.Г., Коряков И.О., Волков М.В. Математика: Учебник-собеседник для 5–6 классов средней школы. – М.: Просвещение, Библиотека учителя математики, 1989.

Рекомендованные ссылки на интернет ресурсы

Интернет портал «CleverStudents» (Источник)

Интернет портал «Фестиваль педагогических идей» (Источник)

Интернет портал «База презентаций» (Источник)

Рекомендованное домашнее задание

Найдите НОД чисел: 27, 15 и 9.

Найдите НОД (424;477) при помощи алгоритма Евклида.

Туристы проехали за первый день 56 км, а за второй – 72 км, причем их скорость была одинаковой и выражалась целым числом км/ч, и каждый день они были в пути целое число часов. Найдите скорость, с которой ехали туристы, если она была наибольшей из удовлетворяющих условию задачи.

Источник: https://interneturok.ru/matematika/6-klass/delimost-chisel/naibolshiy-obschiy-delitel-algoritm-evklida