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

Обновлено: 03.05.2024

Эта статья посвящена такому вопросу, как нахождение наибольшего общего делителя. Сначала мы объясним, что это такое, и приведем несколько примеров, введем определения наибольшего общего делителя 2 , 3 и более чисел, после чего остановимся на общих свойствах данного понятия и докажем их.

Что такое общие делители

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

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

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

Вот примеры такого делителя: тройка будет общим делителем для чисел - 12 и 9 , поскольку верны равенства 9 = 3 · 3 и − 12 = 3 · ( − 4 ) . У чисел 3 и - 12 есть и другие общие делители, такие, как 1 , − 1 и − 3 . Возьмем другой пример. У четырех целых чисел 3 , − 11 , − 8 и 19 будет два общих делителя: 1 и - 1 .

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

Также отметим, что если у нас есть общий для нескольких чисел делитель b , то те же числа можно разделить и на противоположное число, то есть на - b . В принципе, мы можем взять лишь положительные делители, тогда все общие делители также будут больше 0 . Такой подход также можно использовать, однако совсем игнорировать отрицательные числа не следует.

Что такое наибольший общий делитель (НОД)

Согласно свойствам делимости, если b является делителем целого числа a , которое не равно 0, то модуль числа b не может быть больше, чем модуль a , следовательно, любое число, не равное 0 , имеет конечное число делителей. Значит, число общих делителей нескольких целых чисел, хотя бы одно из которых отличается от нуля, также будет конечным, и из всего их множества мы всегда можем выделить самое большое число (ранее мы уже говорили о понятии наибольшего и наименьшего целого числа, советуем вам повторить данный материал).

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

Переходим к формулировке основного определения.

Наибольшим общим делителем нескольких чисел является самое большое целое число, которое делит все эти числа.

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

Какой можно привести пример НОД для двух целых чисел? Например, для 6 и - 15 это будет 3 . Обоснуем это. Сначала запишем все делители шести: ± 6 , ± 3 , ± 1 , а потом все делители пятнадцати: ± 15 , ± 5 , ± 3 и ± 1 . После этого мы выбираем общие: это − 3 , − 1 , 1 и 3 . Из них надо выбрать самое большое число. Это и будет 3 .

Для трех и более чисел определение наибольшего общего делителя будет почти таким же.

Наибольшим общим делителем трех чисел и более будет самое большое целое число, которое будет делить все эти числа одновременно.

Для чисел a 1 , a 2 , … , a n делитель удобно обозначать как НОД ( a 1 , a 2 , … , a n ) . Само значение делителя записывается как НОД ( a 1 , a 2 , … , a n ) = b .

Приведем примеры наибольшего общего делителя нескольких целых чисел: 12 , - 8 , 52 , 16 . Он будет равен четырем, значит, мы можем записать, что НОД ( 12 , - 8 , 52 , 16 ) = 4 .

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

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

Так, наибольший общий делитель чисел 60 , 15 и - 45 равен 15 , поскольку пятнадцать делится не только на 60 и - 45 , но и на само себя, и большего делителя для всех этих чисел не существует.

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

Основные свойства НОД и алгоритм Евклида

У наибольшего общего делителя есть некоторые характерные свойства. Сформулируем их в виде теорем и докажем каждое из них.

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

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

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

Если число a можно разделить на число b , то множество общих делителей этих двух чисел будет аналогично множеству делителей числа b , то есть НОД ( a , b ) = b .

Докажем это утверждение.

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

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

Если верно равенство a = b · q + c (здесь все переменные являются целыми числами), то все общие делители двух чисел 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 ) справедливо.

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

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

Допустим, у нас есть два целых числа больше 0 , для которых будут справедливы следующие равенства:

a = b · q 1 + r 1 , 0 r 1 b b = r 1 · q 2 + r 2 , 0 r 2 r 1 r 1 = r 2 · q 3 + r 3 , 0 r 3 r 2 r 2 = r 3 · q 4 + r 4 , 0 r 4 r 3 ⋮ 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 1 > r 2 > r 3 , … представляет собой ряд убывающих целых чисел, который может включать в себя только конечное их количество. Значит, r k является наибольшим общим делителем a и b , то есть, r k = НОД ( a , b ) .

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

Просмотрим список равенств, приведенный выше, снизу вверх. Согласно последнему равенству,
r k − 1 можно разделить на r k . Исходя из этого факта, а также предыдущего доказанного свойства наибольшего общего делителя, можно утверждать, что r k − 2 можно разделить на r k , так как
r k − 1 делится на r k и r k делится на r k .

Третье снизу равенство позволяет нам сделать вывод, что r k − 3 можно разделить на r k , и т.д. Второе снизу – что b делится на r k , а первое – что a делится на r k . Из всего этого заключаем, что r k – общий делитель a и b .

Теперь докажем, что r k = НОД ( a , b ) . Что для этого нужно сделать? Показать, что любой общий делитель a и b будет делить r k . Обозначим его r 0 _.

Просмотрим тот же список равенств, но уже сверху вниз. Исходя из предыдущего свойства, можно заключить, что r 1 делится на r 0 , значит, согласно второму равенству r 2 делится на r 0 . Идем по всем равенствам вниз и из последнего делаем вывод, что r k делится на r 0 . Следовательно, r k = НОД ( a , b ) .

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

Перейдем к другим свойствам.

Если a и b являются целыми числами, не равными 0 , то должны существовать два других целых числа u 0 и v 0 , при которых будет справедливым равенство НОД ( a , b ) = a · u 0 + b · v 0 .

Равенство, приведенное в формулировке свойства, является линейным представлением наибольшего общего делителя a и b . Оно носит название соотношения Безу, а числа u 0 и v 0 называются коэффициентами Безу.

Докажем данное свойство. Запишем последовательность равенств по алгоритму Евклида:

Первое равенство говорит нам о том, что r 1 = a − b · q 1 _. Обозначим 1 = s 1 и − q 1 = t 1 и перепишем данное равенство в виде r 1 = s 1 · a + t 1 · b . Здесь числа s 1 и t 1 будут целыми. Второе равенство позволяет сделать вывод, что r 2 = b − r 1 · q 2 = b − ( s 1 · a + t 1 · b ) · q 2 = − s 1 · q 2 · a + ( 1 − t 1 · q 2 ) · b . Обозначим − s 1 · q 2 = s 2 и 1 − t 1 · q 2 = t 2 и перепишем равенство как r 2 = s 2 · a + t 2 · b , где s 2 и t 2 также будут целыми. Это объясняется тем, что сумма целых чисел, их произведение и разность также представляют собой целые числа. Точно таким же образом получаем из третьего равенства r 3 = s 3 · a + t 3 · b , из следующего r 4 = s 4 · a + t 4 · b и т.д. В конце заключаем, что r k = s k · a + t k ·b при целых s k и t k . Поскольку r k = НОД ( a , b ) , обозначим s k = u 0 и t k = v 0 , В итоге мы можем получить линейное представление НОД в требуемом виде: НОД ( a , b ) = a · u 0 + b · v 0 .

НОД ( m · a , m · b ) = m · НОД ( a , b ) при любом натуральном значении m .

Обосновать это свойство можно так. Умножим на число m обе стороны каждого равенства в алгоритме Евклида и получим, что НОД ( m · a , m · b ) = m · r k , а r k – это НОД ( a , b ) . Значит, НОД ( m · a , m · b ) = m ·НОД ( a , b ) . Именно это свойство наибольшего общего делителя используется при нахождении НОД методом разложения на простые множители.

Если у чисел a и b есть общий делитель p , то НОД ( a : p , b : p ) = НОД ( a , b ) : p . В случае, когда p = НОД ( a , b ) получим НОД ( a : НОД ( a , b ) , b : НОД ( a , b ) = 1 , следовательно, числа a : НОД ( a , b ) и b : НОД ( a , b ) являются взаимно простыми.

Поскольку a = p · ( a : p ) и b = p · ( b : p ) , то, основываясь на предыдущем свойстве, можно создать равенства вида НОД ( a , b ) = НОД ( p · ( a : p ) , p · ( b : p ) ) = p ·НОД ( a : p , b : p ) , среди которых и будет доказательство данного свойства. Это утверждение мы используем, когда приводим обыкновенные дроби к несократимому виду.

Наибольшим общим делителем a 1 , a 2 , … , a k будет число d k , которое можно найти, последовательно вычисляя НОД ( a 1 , a 2 ) = d 2 , НОД ( d 2 , a 3 ) = d 3 , НОД ( d 3 , a 4 ) = d 4 , … , НОД ( d k - 1 , a k ) = d k .

Это свойство полезно при нахождении наибольшего общего делителя трех и более чисел. С помощью него можно свести это действие к операциям с двумя числами. Его основой является следствие из алгоритма Евклида: если множество общих делителей a 1 , a 2 и a 3 совпадает с множеством d 2 и a 3 , то оно совпадет и с делителями d 3 . Делители чисел a 1 , a 2 , a 3 и a 4 совпадут с делителями d 3 , значит, они совпадут и с делителями d 4 , и т.д. В конце мы получим, что общие делители чисел a 1 , a 2 , … , a k совпадут с делителями d k , а поскольку наибольшим делителем числа d k будет само это число, то НОД ( a 1 , a 2 , … , a k ) = d k .

Это все, что мы хотели бы рассказать о свойствах наибольшего общего делителя.

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

О чем эта статья:

5 класс, 6 класс

Понятие наибольшего общего делителя

Для начала разберемся, что такое общий делитель. У целого числа может быть несколько делителей. А сейчас нам особенно интересно, как обращаться с делителями сразу нескольких целых чисел.

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

Общий делитель нескольких целых чисел — это такое число, которое может быть делителем каждого числа из указанного множества. Например, у чисел 12 и 8 общими делителями будут 4 и 1. Чтобы это проверить, напишем верные равенства: 8 = 4 * 2 и 12 = 3 * 4.

Любое число можно разделить на 1 и на само себя. Значит, у любого набора целых чисел будет как минимум два общих делителя.

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

Например, для 4 и 16 НОД будет 4. Как мы к этому пришли:

Зафиксируем все делители четырех: 4, 2, 1.
А теперь все делители шестнадцати: 16, 8, 4 и 1.
Выбираем общие: это 4, 2, 1. Самое большое общее число: 4. Вот и ответ.

Найдем наибольший общий делитель нескольких целых чисел: 10, 6, 44, 18. Он будет равен трем. Ответ можно записать так: НОД (12, 6, 42, 18) = 3. А чтобы проверить правильность ответа, нужно записать все делители и выбрать из них самые большие.

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

Еще один пример. Рассчитаем НОД для 28 и 64.

Д (64) = 2 * 2 * 2 * 2 * 2 * 2

НОД (28; 64) = 2 * 2 = 4

Ответ: НОД (28; 64) = 4

Оформить поиск НОД можно в строчку, как мы сделали выше или в столбик, как на картинке.

Способы нахождения наибольшего общего делителя

Найти наибольший общий делитель можно двумя способами. Рассмотрим оба, чтобы при решении задач выбирать самую оптимальную последовательность действий.

1. Разложение на множители

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

Пример 1. Найти НОД (84, 90).

Ответ: НОД (84, 90) = 6.

Пример 2. Найти НОД (15, 28).

Ответ: НОД (15, 28) = 1.

Пример 3. Найти НОД для 24 и 18.

НОД (24, 18) =2 * 3 = 6

Ответ: НОД (24, 18) = 6

Онлайн-курсы математики для детей помогут подтянуть оценки, подготовиться к контрольным, ВПР и экзаменам.

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

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

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

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

Пример 1. Найти НОД для 24 и 8.

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

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

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

Пример 2. Найти наибольший общий делитель чисел 140 и 96:

140 : 96 = 1 (остаток 44)
96 : 44 = 2 (остаток 8)
44 : 8 = 5 (остаток 4)
8 : 4 = 2

Последний делитель равен 4 — это значит: НОД (140, 96) = 4.

Ответ: НОД (140, 96) = 4

Пошаговое деление можно записать столбиком:

Чтобы найти наибольший общий делитель трех и более чисел, делаем в такой последовательности:

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

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

У наибольшего общего делителя есть ряд определенных свойств. Опишем их в виде теорем и сразу приведем доказательства.

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

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

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

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

Доказательство

Любой общий делитель чисел а и b является делителем каждого из этих чисел, в том числе и числа b. Так как а кратно b, то любой делитель числа b является делителем и числа а, благодаря свойствам делимости. Из этого следует, что любой делитель числа b является общим делителем чисел а и b.

Значит, если а делится на b, то совокупность делителей чисел а и b совпадает с совокупностью делителей одного числа b. А так как наибольшим делителем числа b является само число b, то наибольший общий делитель чисела и b также равен b, то есть НОД (а, b) = b.

В частности, если a = b, то НОД (a, b) = НОД (a, a) = НОД (b, b) = a = b.

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

Свойство 3. Если a = bq + c, где а, b, с и q — целые числа, то множество общих делителей чисел а и b совпадает со множеством общих делителей чисел b и с. Равенство НОД (a, b) = НОД (b, c) справедливо.

Доказательство

Существует равенство a = bq + c, значит всякий общий делитель чисел а и b делит также и с, исходя из свойств делимости. По этой же причине, всякий общий делитель чисел b и с делит а. Поэтому совокупность общих делителей чисел а и b совпадает с совокупностью общих делителей чисел b и c.

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

Свойство 4. Если m — любое натуральное число, то НОД (mа, mb) = m * НОД(а, b).

Доказательство

Если умножить на m обе стороны каждого из равенств алгоритма Евклида, то получим, что НОД (mа, mb)= mr, где r — это НОД (а, b). На этом свойстве наибольшего общего делителя основан поиск НОД с помощью разложения на простые множители.

Свойство 5. Пусть р — любой общий делитель чисел а и b, тогда НОД (а : p, b : p) = НОД (а, b) : p. А именно, если p = НОД (a, b) имеем НОД (a : НОД (a, b), b: НОД (a, b)) = 1, то есть, числа a : НОД (a, b) и b : НОД (a, b) — взаимно простые.

Так как a = p(a : p) и b = p(b : p), и в силу предыдущего свойства, мы можем записать цепочку равенств вида НОД (a, b) = НОД (p(a : p), p(b : p)) = p * НОД (a : p, b : p), откуда и следует доказываемое равенство.

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

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

Вложение	Размер
nok_i_nod.pptx	2.43 МБ

Предварительный просмотр:

Подписи к слайдам:

Актуальность : многие школьники считают изучение НОК и НОД бесполезным занятием, или заучивают правила лишь для получения оценки, но в дальнейшем сталкиваясь с ситуациями аналогичными ситуациям задач учебника, не могут грамотно действовать, приходят в тупик. Цель работы: приобщение школьников к изучению математических терминов НОК и НОД и математики в целом, приобретение математических знаний для будущей учебной и практической деятельности. Гипотеза: я считаю, изучение исследуемых мною понятий поможет мне и моим сверстникам в дальнейшей жизни . Методика работы : Метод теоретического исследования Исследование. Опрос. Счёт. Наблюдение. Фотографирование. Обобщение и систематизация полученных данных.

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

Самые распространенные среди школьников алгоритмы нахождения НОК и НОД: НОК ( a и b ) НОД ( a и b ) Метод перебора. Метод перебора 1.Выписать все делители числа а. 2. Выписать все делители числа b. 3. Выбрать среди них общие делители. 4. Среди общих делителей выбрать самое большое число. Метод нахождения НОД с помощью разложения на простые множители. 1. Найти разложение чисел a и b на простые множители. 2. Подчеркнуть общие числа. 3. Найти произведение подчеркнутых чисел у одного числа. Метод нахождения НОК с помощью разложения на простые множители. 1.Выписать первые кратные a и b 2 .Затем выбрать среди этих кратных самое маленькое число, которое будет общим для a и b . 1.Найти разложение чисел a и b на простые множители. 2. Выписать множители, входящие в разложение a . 3. Добавить к ним недостающие множители из разложения b . 4.Найти произведение получившихся множителей. Эти способы также применяются также при нахождении НОК и НОД 3-х и более чисел. Причем самый эффективный и удобный из представленных ( т. к. ещё существует древний алгоритм Евклида на нахождение НОД, о котором речь пойдет позже) второй - при помощи разложения на простые множители.

Важность НОК и НОД в понимании взрослых и школьников. Чтобы выяснить, чем является НОК и НОД для учащихся и взрослых, я провела анкетирование и выяснила: НОК и НОД для: Школьников (20 ч.) Взрослых (20 ч.) 5 % (1 ч.) 65 % (13 ч.) 30% (6 ч.) 10 % (2 ч.) 60% (12 ч.) 30% (6 ч.)

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

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

Метод перебора общих делителей.

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

Пример: найдите НОД (24; 60).

Введём обозначения: делители числа обозначим буквой Д.

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

Метод нахождения НОД натуральных чисел с помощью разложения на простые множители.

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

Пример: найдите НОД (24; 60).

Произведём разложение на простые множители числа

НОД (36, 48) = 2·2·3 = 12 [1, c. 24]

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

Рассмотрим другой способ нахождения общего делителя двух чисел. Он называется алгоритмом Евклида.

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

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

Пример: найти НОД (24; 60).

Решение: найдем разность чисел 60 и 24: 60–24 = 36. Затем большее число заменим на результат вычитания. Теперь найдем НОД (24; 36).

36–24 = 12. Далее заменим 36 на 12. Затем находим НОД (24; 12).

24–12 = 12. Заменив 24 на 12, находим НОД (12; 12).

12–12 = 0, так как разность равна 0, то НОД — это уменьшаемое или вычитаемое.

НОД (24; 60) = НОД (24; 36) = НОД (24; 12) = НОД (12; 12) = 12.

Рассмотренный метод нахождения наибольшего общего делителя имеет свои особенности. Например, в случае нахождения НОД (300; 5) придётся исполнить 60 операций вычитания. Поэтому рассмотрим другой алгоритм Евклида, который может способствовать ускорению вычислительных действий.

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

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

4. Переход к пункту 1.

Пример: найти НОД (432; 111).

Решение: разделив 432 на 111, получаем равенство 432 = 111*3+99.

Выполнив деление 111 на 99, получаем равенство 111 = 99*1+12.

Деление 99 на 12 дает равенство 99 = 12*8+3.

12 делится на 3 без остатка, то есть 12 = 3*4, следовательно НОД (432; 111) = 3 [2, c 88].

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

Бинарный алгоритм Евклида вычисления НОД несёт в себе более быстрый характер. Рассмотрим структуру данного алгоритма:

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

Пример: найти НОД (1118; 2064).

Решение: НОД (1118; 2064) = 2*НОД (559; 1032) = 2*НОД (559; 516) = 2*НОД (559;258) = 2*НОД (559; 129) = 2*НОД (430; 129) = 2*НОД (215; 139) = 2*НОД (86; 129) =

= 2*НОД (43; 129) = 2*НОД (43; 86) = 2*НОД (43; 43) = 2*43 = 86.

НОД (1118; 2064) = 86 [3].

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

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

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

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

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

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

Что такое общие делители

Что такое наибольший общий делитель (НОД)

Основные свойства НОД и алгоритм Евклида

Понятие наибольшего общего делителя

Способы нахождения наибольшего общего делителя

1. Разложение на множители

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

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

Предварительный просмотр:

Подписи к слайдам:

Похожие статьи

Исследование алгоритмов генерации простых чисел

Теория чисел в криптографии | Статья в журнале.

Разработка способа представления длинных чисел в памяти.

Применение метода математической индукции к решению задач на.

Сложение коммутативных полугрупп натуральных чисел.

Роль больших простых чисел в современной криптографии

Основные термины (генерируются автоматически): число.

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

Похожие статьи

Исследование алгоритмов генерации простых чисел

Теория чисел в криптографии | Статья в журнале.

Разработка способа представления длинных чисел в памяти.

Применение метода математической индукции к решению задач на.

Сложение коммутативных полугрупп натуральных чисел.

Роль больших простых чисел в современной криптографии

Основные термины (генерируются автоматически): число.

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