Различные способы нахождения наибольшего общего делителя двух натуральных чисел (6 класс)

Муниципальное бюджетное

общеобразовательное учреждение

«Средняя общеобразовательная

школа №3 «Пеликан»

Различные способы нахождения
наибольшего общего делителя двух натуральных чисел.

Математика.

Выполнил: Первухин

Дмитрий Евгеньевич

ученик 6 А класса,

Руководитель: Козлова

Наталья Дмитриевна,

учитель математики

г. Бердск. 2014 г.

Оглавление:

1. Введение……………………………………………………………………….2

1.2.Цель работы и ее задачи…………………………………………………2

2. Различные способы нахождения наибольшего общего делителя

двух натуральных чисел………………………………………………………

0. 2.1.Что такое НОД…………………………………………………………….2

1. 2.2. Свойства НОД…………………………………………………………….3

2.3. Метод полного перебора для нахождения НОД  натуральных чисел..5

2.4. Метод перебора делителей меньшего числа для нахождения

наибольшего общего делителя (НОД)  натуральных чисел……………5

2.5. Метод нахождения наибольшего общего делителя (НОД)

натуральных чисел с помощью разложения на множители……………6

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

(НОД)  двух натуральных чисел вычитанием……………………………6

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

(НОД)  двух натуральных чисел делением………………………………7

2.8. Бинарный алгоритм Евклида нахождения наибольшего общего

делителя (НОД)  двух натуральных чисел………………………………7

2.9. Геометрический метод нахождения наибольшего общего

делителя (НОД)  натуральных чисел с помощью квадратов………….8

3. Выводы………………………………………………………………………….9

4. Список используемой литературы……………..…………………………….9

5. Приложение 1. Мои примеры нахождения наибольшего общего

делителя двух натуральных чисел (способы 1- 4)………………………….10

3. Приложение 2. Мои примеры нахождения наибольшего общего

делителя двух натуральных чисел (способы 5- 7)………………………….11

1. Введение

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

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

1.2.Цель работы и её задачи

Цель работы:

1. Изучить различные способы нахождения НОД натуральных чисел;

2. Научиться пользоваться этими способами;

3. Выбрать самый удобный и рациональный.

Достижение этих целей возможно путем решения следующих задач:

1. Изучить литературу о наибольшем общем делителе;

2. Рассмотреть различные способы нахождения НОД;

3. Проверить эффективность найденных способов нахождения НОД на конкретных примерах.

2. Различные способы нахождения наибольшего общего делителя двух натуральных чисел.

2. 1. Что такое НОД двух чисел?

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

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

Обозначения наибольшего общего делителя чисел a и b: НОД(a; b).

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

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

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

1. Наибольший общий делитель чисел a и b равен наибольшему общему делителю чисел b и a, то есть, НОД(a; b)=НОД(b; a).

Это свойство НОД напрямую следует из определения наибольшего общего делителя.

2. Если a>b, то НОД(a; b) = НОД(a – b; b).

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

Легко доказать это свойство. Пусть k — общий делитель a и b (a> b). Это значит, что a = mk, b = nk, где m, n — натуральные числа, причем m > n. Тогда a — b = k(m — n), откуда следует, что k — делитель числа a — b. Значит, все общие делители чисел a и b являются делителями их разности a — b, в том числе и наибольший общий делитель. На этом свойстве основан алгоритм Евклида нахождения НОД двух чисел вычитанием.

3.Если a делится на b, то множество общих делителей чисел a и b совпадает с множеством делителей числа b, в частности, НОД(a;b)=b.

В частности, если числа a и b равны, то  НОД(а;b)=НОД(a;a)= НОД(b;b)=a=b. К примеру, НОД(132, 132)=132.

Данное свойство наибольшего делителя позволяет нам находить НОД двух чисел, когда одно из них делится на другое. При этом НОД равен одному из этих чисел, на которое делится другое число. Например,  НОД(8, 24)=8, так как 24 кратно восьми.

4. Если a=b·q+c, где a, b, c и q – целые числа, то множество общих делителей чисел a и b совпадает с множеством общих делителей чисел b и c, в частности, НОД(a, b)=НОД(b, c).

Обоснуем это свойство НОД.

Так как имеет место равенство a=b·q+c, то всякий общий делитель чисел a и b делит также и c (это следует из свойств делимости). По этой же причине, всякий общий делитель чисел b и c делит a. Поэтому совокупность общих делителей чисел a и b совпадает с совокупностью общих делителей чисел b и c. В частности, должны совпадать и наибольшие из этих общих делителей, то есть, должно быть справедливо следующее равенство  НОД(a, b)=НОД(b, c).

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

Прежде чем дать формулировку теоремы, рекомендуем освежить в памяти теорему, которая утверждает, что делимое a может быть представлено в виде b·q+r, где b – делитель, q – некоторое целое число, называемое неполным частным, а r – целое число, удовлетворяющее условию 0≤ r< |b|, называемое остатком.

Итак, пусть для двух ненулевых целых положительных чисел a и b справедлив ряд равенств:

a = b·q₁ + r₁, 0< r₁< b

b = r₁·q₂ + r₂, 0< r₂< r₁

r₁ = r₂·q₃ + r₃, 0< r₃< r₂

r₂ = r₃·q₄ + r₄, 0< r₄< r₃

_·

_·

_·

r _k-2 = r_k-1·q_k + r_k, 0< r_k< r_k-1

r _k-1 = r_k·q_k+1
заканчивающийся, когда r_k+1=0 (что неизбежно, так как b>r₁>r₂>r₃, … — ряд убывающих целых чисел, и этот ряд не может содержать более чем конечное число положительных чисел), тогда r_k – это наибольший общий делитель чисел a и b, то есть, r_k=НОД(a, b).

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

От прямоугольника отрежем несколько квадратов со стороной 48 мм – таких квадратов три.

Остался прямоугольник со сторонами 48 мм и 162-3*48=18 мм.

От полученного прямоугольника снова отрезаем квадраты, у которых сторона равна 18 мм – таких квадратов получится два.

Остался прямоугольник со сторонами 18 мм и 48-2*18=12 мм.

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

Остался прямоугольник со сторонами 12 мм и 18-12=6 мм, который , в свою очередь состоит из двух квадратов 6мм х 6 мм.

Длина стороны последнего полученного квадрата и есть наибольший общий делитель чисел 162 и 48.

Ответ: НОД(162; 48)=6.

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

4. Вывод работы

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

Список используемой литературы:

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

2. Макарычев Ю.Н., Миндюк Н.Г. Алгебра: Дополнительные главы к школьному учебнику 8 кл.: учебное пособие для школ и классов с углубленным изучением математики.- М.:Просвещение,1996.- 207 с.

3. Пичурин Л.Ф. За страницами учебника алгебры- Москва: Просвещение, 1990г. —

4. Щетников А. И. Алгоритм Евклида и непрерывные дроби. — Новосибирск: АНТ, 2003 г.

Список используемых источников информации:

1. Википедия (свободная энциклопедия), 

7 способ: 1) НОД(160;40)

160мм

40

мм

1. Построим прямоугольник со сторонами 160мм и 40 мм.

2. От прямоугольника отрежем несколько квадратов со стороной 40 мм – таких квадратов четыре.

3. Длина стороны последнего полученного квадрата и есть наибольший общий делитель чисел 160 и 40.

НОД(160;40)=40

2) НОД(85,125)

1. Построим прямоугольник со сторонами 125мм и 85 мм.

5мм

40 мм

125 мм

2. От прямоугольника отрежем квадрат со стороной 85 мм – такой квадрат один.

3. Остался прямоугольник со сторонами 85 мм и 125-85=40 мм. От полученного прямоугольника снова отрезаем квадраты, у которых сторона равна 40 мм – таких квадратов получится два.

4. Остался прямоугольник со сторонами 40 мм и 85-2*40=5 мм. От полученного прямоугольника снова отрезаем квадраты, у которых сторона равна 8 мм – таких квадратов получится восемь.

5. Длина стороны последнего полученного квадрата и есть наибольший общий делитель чисел 125 и 8. НОД(85,125)=5