Исследовательская работа «Что такое НОД»

Министерство образования и науки Республики Бурятия

Мухоршибирский район

МБОУ « Калиновская СОШ»

Х Республиканская научно-практическая конференция

учащихся начальных классов

«СЕРЕБРЯНАЯ АЛЬФА»
 

Номинация: Окружающий мир

Тема: Что такое НОД

Автор: Болонева София , ученица 6 класса

МБОУ «Калиновской СОШ» Мухоршибирского района

Домашний адрес: Мухоршибирский район

 

Руководитель: Васильева Елизавета Фёдоровна,

 

с. Калиновка

2016 год

Содержание

1.введение

2. что такое НОД

3. методы отыскания НОД

4. эксперемент, какой метод более удобен

5. Вывод

6. Список использованной литературы
 

1. Введение

«Числа правят миром»

Пифагор

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

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

Цель работы:

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

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

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

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

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

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

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

2. что такое НОД

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

Чтобы лучше понять это определение, подставим вместо переменных a и b любые два числа, например, вместо переменной a подставим 12, а вместо переменной b подставим 9. Теперь попробуем прочитать это определение.

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

3 Методы отыскание НОД

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

1. Выписываем все делители числа а;

2. Выписываем все делители числа b;

3. Выбираем среди них общие делители;

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

Например: Найти НОД(32;48).

Обозначим делители числа буквой D.

D (32) = {1; 2; 4; 8; 16; 32};

D (48) = {1; 2; 3; 4; 6; 8; 12; 16; 24; 48}.

D (32; 48) = {1; 2; 4}.

НОД(32; 48) = 4.

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

1. Найти делители меньшего из данных чисел.

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

3. Записать найденное число – НОД.

Например: Найти НОД(12;32).

D(12) = {1; 2; 3; 4; 6; 12}.

12 не является делителем числа 32;

6 не является делителем числа 32;

4- делитель 32.

НОД(12; 32) = 4.

Этот алгоритм легко реализуется, но его недостатком является то, что

необходимо проверять много вариантов.

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

1. Находим разложение чисел на простые множители.

2. Подчеркиваем общие числа.

3. Находим произведение подчеркнутых чисел у одного числа.

4. Записываем ответ.

Например:

Найти НОД(36; 48).

36=2•2•3•3,

48=2•2•2•2•3.

НОД(36,48)=2•2•3=12

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

НОД(54739; 205 757).

Есть сравнительно простой алгоритм нахождения общего делителя двух чисел. Его приписывают Евклиду, одному из величайших математиков древности. Евклид жил в III-II в до н.э. в Александрии, а по другим источникам, в Дамаске. Оставил несколько сочинений, известных в латинских и арабских переводах, наиболее значительное из которых – состоящие из 13 книг «Начала» («Elements»)- представляет собой систематическое изложение математики того времени.

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

Древнегреческие математики называли этот алгоритм  ἀνθυφαίρεσις  или  ἀνταναίρεσις  — «взаимное вычитание». Этот алгоритм, видимо, не был открыт Евклидом, так как упоминание о нём имеется уже в Топике Аристотеля. В «Началах» Евклида он описан дважды — в VII книге для нахождения наибольшего общего делителя двух натуральных чисел и в X книге для нахождения наибольшей общей меры двух однородных величин. В обоих случаях дано геометрическое описание алгоритма, для нахождения «общей меры» двух отрезков.

1. Из большего числа вычитается меньшее.

2. Если получается 0, то числа равны друг другу и являются наибольшим общим делителем.

3. Если результат вычитания не равен 0, то большее число заменяется на результат вычитания

Например: Найти НОД(30; 18).

30 - 18 = 12;
18 - 12 = 6;
12 - 6 = 6;
6 – 6 = 0.

НОД – это уменьшаемое или вычитаемое.

НОД (30; 18) = 6. Приведенный метод вычисления не является оптимальным. Например, для нахождения НОД(100; 2) следует выполнить 50 (!!) операций вычитания. Для ускорения вычисления НОД операцию вычитания следует заменить операцией взятия остатка от деления.

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

1. Большее число делится на меньшее

2. Если делится без остатка, то меньшее число и есть наибольший общий делитель.

3. Если есть остаток, то большее число заменяем на остаток от деления.

4. Продолжаем деление до тех пор, пока не получим в остатке нуль. Последний неравный нулю остаток и есть НОД данных чисел.

Например: Найти НОД (273;1014).

Решение. Выполняем деление с остатком: По лемме:

1014=273*3+195

273=195*1+78

195=78*2+39

78=39*2 +0

НОД (273;1014) = НОД(195;273) = НОД(195;78) = НОД(78;39)= 39

НОД(273;1014)=39

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

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

НОД(2a; 2b) = 2 НОД(a; b),

НОД(2a; 2b+1) = НОД(a; 2b+1),

НОД(-a; b) = НОД(a; b)

Сам алгоритм выглядит так:

Если a, b чётные, то НОД(a; b) = 2*НОД(a/2; b/2);

Если a чётное, b нечётное, то НОД(a; b) = НОД(a/2; b);

Если b чётное, a нечётное, то НОД(a; b) = НОД(a; b/2);

Если a, b нечётные и b > a, то НОД(a; b) = НОД((b-a)/2; a);

Если a, b нечётные и b < a, то НОД(a; b) = НОД((a-b)/2; b);

Например: НОД(1978;2666)=2*НОД(989;1333)=2*НОД(989;344)=2*НОД(989;172)=2*НОД(989;86)=2*НОД(989;43)=2*НОД(946;43)=2*НОД(473;43)=2*НОД(430;43)= 2*НОД(215; 43)=2*НОД(172; 43)=2НОД*(86; 43)=2*НОД(43; 43)=2*43=86.

НОД(1978; 2666)=86

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

Этот алгоритм – геометрическая иллюстрация алгоритма Евклида, описанного в 5-ем способе.

Например: Найти НОД(162;48).

Построим прямоугольник со сторонами 162мм и 48 мм.

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

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

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

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

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

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

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

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

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

Эксперимент, какой метод более удобен?

Я считаю первые два метода не рациональными и слишком долгими поэтому начнем свой эксперимент с 3 способа: Метод нахождения наибольшего общего делителя натуральных чисел с помощью разложения на множители.

Найти наибольший общий делитель чисел 324 и 432

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

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

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

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

2 × 2 × 3 × 3 × 3=108

В результате НОД(324, 432)=108, я не буду выполнять отыскания НОД с помощью 4 способа, как мы уже сказали он слишком долгий.

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

НОД(432,324)=

432=324*1+108

324=108*3+0 получается, что НОД 432 и 324 равен 108 коротко и ясно.

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

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

Вывод

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

6. Список использованной литературы

[1].//Учебник для общеобразовательных учреждений Математика 6 класс под ред. В.В. Козлова (Инновационная школа 2015 год)

[2].//За страницами учебника алгебры. Л.Ф Пичурин, Москва, Просвещение, 1990г.

[3].//Сборник примеров и задач по математике, Н.А Терешин, Т.Н.Терешина Москва, Аквариум, 1997 г.

Интернет-ресурсы.

[1]. //Википедия (свободная энциклопедия), http://ru.wikipedia.org

[ 2]. //Сайт "Единая коллекция цифровых образовательных ресурсов".

[ 3]. // bymath.net — сайт «Вся элементарная математика», раздел «Общий делитель. Наибольший общий делитель»