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

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

скачать

Реферат на тему:

План:

1 Связанные определения
- 1.1 Наименьшее общее кратное
- 1.2 Взаимно простые числа
2 Способы вычисления
3 Свойства
4 Вариации и обобщения

Введение

Наибольшим общим делителем (НОД) для двух целых чисел m и n называется наибольший из их общих делителей.[1] Пример: для чисел 70 и 105 наибольший общий делитель равен 35.

Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел m или n не ноль.

Возможные обозначения наибольшего общего делителя чисел m и n:

НОД(m, n)
(m, n)
gcd(m, n) (от англ. Greatest Common Divisor)

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

1. Связанные определения

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

Наименьшее общее кратное (НОК) двух целых чисел m и n — это наименьшее натуральное число, которое делится на m и n. Обозначается НОК(m,n) или [m,n], а в английской литературе lcm(m,n).

НОК для ненулевых чисел m, n всегда существует и связан с НОД следующим соотношением:

$(m,n)\cdot[m,n]=m\cdot n$

Это частный случай более общей теоремы:

Если $D, a_1, a_2, \dots , a_n$ — ненулевые числа, тогда $[a_1, a_2, \dots , a_n]=D/(D/a_1, D/a_2, \dots , D/a_n)$

1.2. Взаимно простые числа

Числа m и n называются взаимно-простыми, если у них нет общих делителей, кроме единицы. Для таких чисел НОД(m,n) = 1. Обратно, если НОД(m,n) = 1, то числа взаимно просты.

Аналогично, целые числа $a_1, a_2, \dots a_k$ , где $k\geq 2$ , называются взаимно простыми, если их наибольший общий делитель равен единице.

Следует различать понятия взаимной простоты, когда НОД набора чисел равен 1, и попарной взаимной простоты, когда НОД равен 1 для каждой пары чисел из набора. Из попарной простоты вытекает взаимная простота, но не наоборот. Например, НОД(6,10,15) = 1, но любые пары из этого набора не взаимно просты.

2. Способы вычисления

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

Кроме того, значение НОД(m,n) можно легко вычислить, если известно каноническое разложение чисел m, n на простые множители:

$n=p_1^{d_1}\cdot\dots\cdot 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)}\cdot\dots\cdot p_k^{\min(d_k,e_k)},$ $[n,m]=p_1^{\max(d_1,e_1)}\cdot\dots\cdot p_k^{\max(d_k,e_k)}.$

Если чисел более двух: $a_1, a_2,\dots a_n$ , их НОД находится по следующему алгоритму:

d2 = (a1,a2) d3 = (d2,a3) ……… dn = (dn − 1,an) — это и есть искомый НОД.

3. Свойства

Основное свойство: наибольший общий делитель делится на любой общий делитель m и n. Пример: для чисел 12 и 18 наибольший общий делитель равен 6; он делится на все общие делители этих чисел: 1, 2, 3, 6.
- Следствие 1: множество общих делителей m, n совпадает с множеством делителей НОД(m, n).
- Следствие 2: множество общих кратных m, n совпадает с множеством кратных НОК(m, n).
Если m делится на n, то НОД(m, n) = n. В частности, НОД(n, n) = n.
$(a\cdot m, a\cdot n) = |a|\cdot (m, n)$ — общий множитель можно выносить за знак НОД.
Если D = (m,n), то после деления на D числа становятся взаимно простыми, то есть, $\left({\frac{m}{D},\frac{n}{D}}\right)=1$ . Это означает, в частности, что для приведения дроби к несократимому виду надо разделить её числитель и знаменатель на их НОД.
Мультипликативность: если a1,a2 взаимно просты, то:

$(a_1 \cdot a_2, b) = (a_1, b) \cdot (a_2, b)$

Наибольший общий делитель чисел m и n может быть определен как наименьший положительный элемент множества всех их линейных комбинаций:

$\left\{ a\cdot m + b\cdot n\mid a,b\in\Z \right\}$ и поэтому (m,n) представим в виде линейной комбинации чисел m и n: $(m,n) = u\cdot m + v\cdot n$ . Это соотношение называется соотношением Безу, а коэффициенты u и v — коэффициентами Безу. Коэффициенты Безу эффективно вычисляются расширенным алгоритмом Евклида. Это утверждение обобщается на наборы натуральных чисел — его смысл в том, что подгруппа группы $\mathbb{Z}$ , порождённая набором $\{a_1, a_2, \dots , a_n\}$ , — циклическая и порождается одним элементом: НОД $(a_1, a_2, \dots , a_n)$ .

4. Вариации и обобщения

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

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

НОД двух элементов коммутативного кольца, вообще говоря, не обязан существовать. Например, для нижеследующих элементов a, b кольца $\mathbb{Z}\left[\sqrt{-3}\right]$ не существует наибольшего общего делителя:

$a = 4 = 2\cdot 2 = \left(1+\sqrt{-3}\right)\left(1-\sqrt{-3}\right),\qquad b = \left(1+\sqrt{-3}\right)\cdot 2.$

В евклидовых кольцах наибольший общий делитель всегда существует и определён с точностью до делителей единицы.

wreferat.baza-referat.ru

Зачем вводить понятия "Наибольший общий делитель (НОД)" и "Наименьшее общее кратное (НОК)" чисел в школьный курс математики?

Разделы: Математика, Конкурс «Презентация к уроку»

Презентация к уроку

Загрузить презентацию (1,9 МБ)

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

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

При изучении темы "Сложение и вычитание дробей с разными знаменателями" мы учим детей находить общий знаменатель двух или более чисел. Например, нужно сложить дроби 1/3 и 1/5. Учащиеся без труда находят число, делящееся без остатка на 3 и 5 . Это число 15. Действительно , если числа небольшие, то их общий знаменатель найти легко, зная хорошо таблицу умножения . Кто-то из ребят замечает, что это число является произведением чисел 3 и 5. У детей складывается мнение, что всегда таким образом можно найти общий знаменатель для чисел. К примеру вычитаем дроби 7/18 и 5/24. Найдем произведение чисел 18 и 24 . Оно равно 432. Получили уже большое число, а если дальше нужно производить какие-то вычисления(особенно это касается примеров на все действия), то вероятность ошибки возрастает. А вот найденное наименьшее общее кратное чисел (НОК), что в этом случае равнозначно наименьшему общему знаменателю (НОЗ)-число 72 -значительно облегчит вычисления и приведет к более быстрому решению примера, а тем самым сэкономит время, отведенное на выполнение данного задания, что играет немаловажную роль при выполнении итоговых тестовых, контрольных работ, особенно во время итоговой аттестации.

При изучении темы "Сокращение дробей" можно двигаться последовательно деля числитель и знаменатель дроби на одно и то же натуральное число, используя при этом признаки делимости чисел, получив в конечном итоге несократимую дробь. Например, нужно сократить дробь 128/344. Разделим сначала числитель и знаменатель дроби на число 2, получим дробь 64/172. Ещё раз поделим числитель и знаменатель полученной дроби на 2, получим дробь 32/86. Поделить ещё раз числитель и знаменатель дроби на 2 , получим несократимую дробь 16/43. Но сокращение дроби можно выполнить гораздо проще , если мы найдем наибольший общий делитель чисел 128 и 344. НОД(128, 344) = 8. Разделив числитель и знаменатель дроби на это число, получим сразу несократимую дробь.

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

16 = 2*2*2*2
120 = 2*2*2*3*5

Затем из множителей, входящих в разложение одного из этих чисел, вычеркиваем те, которые не входят в разложение другого числа. Произведение оставшихся множителей и будет являться наибольшим общим делителем этих чисел. В данном случае это число 8. На своем опыте убедилась в том, что детям более понятно, если мы подчеркиваем одинаковые множители в разложениях чисел , а затем в одном из разложений находим произведение подчеркнутых множителей. Это и есть наибольший общий делитель данных чисел. В шестом классе дети активны и любознательны. Можно поставить перед ними следующую задачу: попробуйте описанным способом найти наибольший общий делитель чисел 343 и 287. Сразу не видно, как разложить их на простые множители. И вот здесь можно рассказать им про замечательный способ, придуманный древними греками, позволяющий искать наибольший общий делитель(НОД)без разложения на простые множители. Этот метод отыскания наибольшего общего делителя впервые описан в книге Евклида "Начала". Его называют алгоритмом Евклида. Заключается он в следующем : Вначале делят большее число на меньшее. Если получается остаток, то делят меньшее число на остаток. Если снова получается остаток, то делят первый остаток на второй. Так продолжают делить до тех пор, пока в остатке не получится нуль. Последний делитель и есть наибольший общий делитель (НОД)данных чисел.

Вернемся к нашему примеру и для наглядности запишем решение в виде таблицы.

Делимое	Делитель	Частное	Остаток
343	287	1	56
287	56	5	7
56	7	8	0

Итак, НОД(344,287) = 7

А как найти наименьшее общее кратное (НОК) тех же чисел? Нет ли и для этого какого-нибудь способа, не требующего предварительного разложения этих чисел на простые множители? Оказывается, есть, и притом очень простой. Нужно перемножить эти числа и разделить произведение на найденный нами наибольший общий делитель(НОД). В данном примере произведение чисел равно 98441. Делим его на 7 и получаем число 14063. НОК(343,287) = 14063.

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

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

- позволяет экономить время, отводимое на выполнение работы, что приводит к значительному увеличению объема выполненных заданий;

- повышает скорость и точность выполнения арифметических операций, что ведет к значительному уменьшению количества допускаемых вычислительных ошибок;

- позволяет находить красивые способы решения нестандартных текстовых задач;

- развивает любознательность учащихся, расширяет их кругозор;

- создает предпосылки для воспитания разносторонней творческой личности.

Поделиться страницей:

xn--i1abbnckbmcl9fb.xn--p1ai

Тест на нок и нод

Тест по теме «Наибольший общий делитель. Наименьшее общее кратное»

Вариант I

1. Наибольший общий делитель чисел a и b – это:

а) натуральное число, на которое делятся без остатка числа a и b;

б) натуральное число, которое делится без остатка на числа a и b;

в) наибольшее натуральное число, на которое делятся без остатка числа a и b;

г) наибольшее натуральное число, которое делится без остатка на числа a и b.

2. Какие числа являются общими делителями чисел 24 и 16?

а) 4, 8; б) 6, 2, 4; в) 2, 4, 8; г) 8, 6.

3. Какое число является общим кратным чисел 8, 12 и 6?

а) 16; б) 140; в) 96; г) 2.

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

а) 280 = 2·2·2·5·7; б) 280 = 1·2·2·2·5·7; в) 280 = 8·5·7; г) свой ответ.

5. Наибольшим общим делителем чисел 45 и 60 является число:

а) 5; б) 180; в) 3; г) 15.

6. Наименьшим общим кратным чисел 28 и 49 является число:

а) 196; б) 14; в) 7; г) 98.

7. Какие числа являются взаимно простыми:

а) 5 и 25; б) 64 и 2; в) 12 и 10; г) 100 и 9.

8. У каких из предложенных пар чисел НОД равен 4:

1) 24 и 20; 2) 24 и 30; 3) 24 и 32; 4) 18 и 32; 5) 4 и 16.

а) 2, 3, 5; б) 1, 5; в) 1, 3, 5; г) у всех.

9. Числа x и y – взаимно простые. Чему равно их наименьшее общее кратное?

а) х; б) y; в) xy; г) x + y.

10. Для спортивной команды купили 45 маек и 27 футболок. Какое наибольшее число спортсменов может быть в команде, если каждый получит одинаковый набор одежды и будут использованы все вещи?

11. Наименьшее общее кратное чисел a и b – это:

а) натуральное число, на которое делятся без остатка числа a и b;

б) натуральное число, которое делится без остатка на числа a и b;

в) наименьшее натуральное число, на которое делятся без остатка числа a и b;

г) наименьшее натуральное число, которое делится без остатка на числа a и b.

12. Какие числа являются общими делителями чисел 18 и 12?

а) 9, 6, 3; б) 2, 3, 4, 6; в) 3, 2; г) 2, 3, 6.

13. Какое число является общим кратнымчисел 5, 10 и 15?

а) 5; б) 100; в) 15; г) 300.

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

а) 420 = 2·2·3·5·7; б) 420 = 1·2·2·3·5·7; в) 420 = 4·3·5·7; г) свой ответ.

15. Наибольшим общим делителем чисел 90 и 54 является число:

а) 2; б) 9; в) 18; г) 270.

16. Наименьшим общим кратным чисел 80 и 96 является число:

а) 480; б) 8; в) 16; г) 240.

17. Какие числа являются взаимно простыми:

а) 9 и 18; б) 105 и 65; в) 44 и 45; г) 6 и 16.

18. У каких из предложенных пар чисел НОД равен 6:

1) 24 и 20; 2) 24 и 30; 3) 24 и 32; 4) 18 и 30; 5) 6 и 200.

а) 2, 4; б) 1, 3; в) 1, 2, 4, 5; г) у всех.

19. Число a кратно числу b. Чему равен их наибольший общий делитель?

а) a; б) b; в) a + b; г) ab.

20. Какое наибольшее число одинаковых наборов можно составить из 72 ручек и 54 фломастеров, если они все должны быть использованы?

21. Какие из данных сумм кратны 5:

1)7316 + 97564; 2)4523 + 7415; 3) 678 + 991 + 31; 4) 230 + 179?

а) 1,3; б) 1, 4; в)1; г) другой ответ

22. Какие из данных чисел не кратны 3:1)1706; 2)12364; 3) 40215; 4) 131421; 5) 18279?а) 1 и 5; б)1 и 2; в) 1 и 4; г) другой ответ.

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

а) 420 = 2·2·3·5·7; б) 420 = 1·2·2·3·5·7; в) 420 = 3·4·5·7; г) другой ответ.

24. У каких из предложенных пар чисел НОД равен 6:

1) 24 и 20; 2) 24 и 30; 3) 24 и 32; 4) 18 и 30; 5) 6 и 200?

а) 2 и 4; б) 1 и 3; в) 1,2,4,5; г) другой ответ.

25. У каких из предложенных пар чисел НОК равно 60:

1) 30 и 2; 2) 18 и 15; 3) 4 и 15; 4) 12 и 60; 5) 10 и 6?а) 2,3,4; б)3,4; в) 2,4; г) у всех.

Ключи