Существует ли наименьший общий делитель. Деление

НОД - это наибольший общий делитель.

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

• определить множители, общие для обоих чисел;
• найти произведение общих множителей.

Пример нахождения НОД:

Найдем НОД чисел 315 и 245.

315 = 5 * 3 * 3 * 7;

245 = 5 * 7 * 7.

2. Выпишем множители, общие для обоих чисел:

3. Найдем произведение общих множителей:

НОД(315; 245) = 5 * 7 = 35.

Ответ: НОД(315; 245) = 35.

Нахождение НОК

НОК - это наименьшее общее кратное.

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

• разложить числа на простые множители;
• выписать множители, входящие в разложение одного из чисел;
• допишем к ним недостающие множители из разложения второго числа;
• найти произведение получившихся множителей.

Пример нахождения НОК:

Найдем НОК чисел 236 и 328:

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

236 = 2 * 2 * 59;

328 = 2 * 2 * 2 * 41.

2. Выпишем множители, входящие в разложение одного из чисел и допишем к ним недостающие множители из разложения второго числа:

2; 2; 59; 2; 41.

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

НОК(236; 328) = 2 * 2 * 59 * 2 * 41 = 19352.

Ответ: НОК(236; 328) = 19352.

Для нахождения НОД (наибольшего общего делителя) двух чисел необходимо:

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

3. Найти произведение общих простых множителей.

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

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

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

3. Вычислить произведение полученных множителей.

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

Навигация по странице.

Вычисление наименьшего общего кратного (НОК) через НОД

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

Пример.

Найдите наименьшее общее кратное двух чисел 126 и 70 .

Решение.

В этом примере a=126 , b=70 . Воспользуемся связью НОК с НОД, выражающуюся формулой НОК(a, b)=a·b:НОД(a, b) . То есть, сначала нам предстоит найти наибольший общий делитель чисел 70 и 126 , после чего мы сможем вычислить НОК этих чисел по записанной формуле.

Найдем НОД(126, 70) , используя алгоритм Евклида: 126=70·1+56 , 70=56·1+14 , 56=14·4 , следовательно, НОД(126, 70)=14 .

Теперь находим требуемое наименьшее общее кратное: НОК(126, 70)=126·70:НОД(126, 70)= 126·70:14=630 .

Ответ:

НОК(126, 70)=630 .

Пример.

Чему равно НОК(68, 34) ?

Решение.

Так как 68 делится нацело на 34 , то НОД(68, 34)=34 . Теперь вычисляем наименьшее общее кратное: НОК(68, 34)=68·34:НОД(68, 34)= 68·34:34=68 .

Ответ:

НОК(68, 34)=68 .

Заметим, что предыдущий пример подходит под следующее правило нахождения НОК для целых положительные чисел a и b : если число a делится на b , то наименьшее общее кратное этих чисел равно a .

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

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

Озвученное правило нахождения НОК следует из равенства НОК(a, b)=a·b:НОД(a, b) . Действительно, произведение чисел a и b равно произведению всех множителей, участвующих в разложениях чисел a и b . В свою очередь НОД(a, b) равен произведению всех простых множителей, одновременно присутствующих в разложениях чисел a и b (о чем написано в разделе нахождение НОД с помощью разложения чисел на простые множители).

Приведем пример. Пусть мы знаем, что 75=3·5·5 и 210=2·3·5·7 . Составим произведение из всех множителей данных разложений: 2·3·3·5·5·5·7 . Теперь из этого произведения исключим все множители, присутствующие и в разложении числа 75 и в разложении числа 210 (такими множителями являются 3 и 5 ), тогда произведение примет вид 2·3·5·5·7 . Значение этого произведения равно наименьшему общему кратному чисел 75 и 210 , то есть, НОК(75, 210)= 2·3·5·5·7=1 050 .

Пример.

Разложив числа 441 и 700 на простые множители, найдите наименьшее общее кратное этих чисел.

Решение.

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

Получаем 441=3·3·7·7 и 700=2·2·5·5·7 .

Теперь составим произведение из всех множителей, участвующих в разложениях данных чисел: 2·2·3·3·5·5·7·7·7 . Исключим из этого произведения все множители, одновременно присутствующие в обоих разложениях (такой множитель только один – это число 7 ): 2·2·3·3·5·5·7·7 . Таким образом, НОК(441, 700)=2·2·3·3·5·5·7·7=44 100 .

Ответ:

НОК(441, 700)= 44 100 .

Правило нахождения НОК с использованием разложения чисел на простые множители можно сформулировать немного иначе. Если ко множителям из разложения числа a добавить недостающие множители из разложения числа b , то значение полученного произведения будет равно наименьшему общему кратному чисел a и b .

Для примера возьмем все те же числа 75 и 210 , их разложения на простые множители таковы: 75=3·5·5 и 210=2·3·5·7 . Ко множителям 3 , 5 и 5 из разложения числа 75 добавляем недостающие множители 2 и 7 из разложения числа 210 , получаем произведение 2·3·5·5·7 , значение которого равно НОК(75, 210) .

Пример.

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

Решение.

Получаем сначала разложения чисел 84 и 648 на простые множители. Они имеют вид 84=2·2·3·7 и 648=2·2·2·3·3·3·3 . К множителям 2 , 2 , 3 и 7 из разложения числа 84 добавляем недостающие множители 2 , 3 , 3 и 3 из разложения числа 648 , получаем произведение 2·2·2·3·3·3·3·7 , которое равно 4 536 . Таким образом, искомое наименьшее общее кратное чисел 84 и 648 равно 4 536 .

Ответ:

НОК(84, 648)=4 536 .

Нахождение НОК трех и большего количества чисел

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

Теорема.

Пусть даны целые положительные числа a 1 , a 2 , …, a k , наименьшее общее кратное m k этих чисел находится при последовательном вычислении m 2 =НОК(a 1 , a 2) , m 3 =НОК(m 2 , a 3) , …, m k =НОК(m k−1 , a k) .

Рассмотрим применение этой теоремы на примере нахождения наименьшего общего кратного четырех чисел.

Пример.

Найдите НОК четырех чисел 140 , 9 , 54 и 250 .

Решение.

В этом примере a 1 =140 , a 2 =9 , a 3 =54 , a 4 =250 .

Сначала находим m 2 =НОК(a 1 , a 2)=НОК(140, 9) . Для этого по алгоритму Евклида определяем НОД(140, 9) , имеем 140=9·15+5 , 9=5·1+4 , 5=4·1+1 , 4=1·4 , следовательно, НОД(140, 9)=1 , откуда НОК(140, 9)=140·9:НОД(140, 9)= 140·9:1=1 260 . То есть, m 2 =1 260 .

Теперь находим m 3 =НОК(m 2 , a 3)=НОК(1 260, 54) . Вычислим его через НОД(1 260, 54) , который также определим по алгоритму Евклида: 1 260=54·23+18 , 54=18·3 . Тогда НОД(1 260, 54)=18 , откуда НОК(1 260, 54)= 1 260·54:НОД(1 260, 54)= 1 260·54:18=3 780 . То есть, m 3 =3 780 .

Осталось найти m 4 =НОК(m 3 , a 4)=НОК(3 780, 250) . Для этого находим НОД(3 780, 250) по алгоритму Евклида: 3 780=250·15+30 , 250=30·8+10 , 30=10·3 . Следовательно, НОД(3 780, 250)=10 , откуда НОК(3 780, 250)= 3 780·250:НОД(3 780, 250)= 3 780·250:10=94 500 . То есть, m 4 =94 500 .

Таким образом, наименьшее общее кратное исходных четырех чисел равно 94 500 .

Ответ:

НОК(140, 9, 54, 250)=94 500 .

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

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

Пример.

Найдите наименьшее общее кратное пяти чисел 84 , 6 , 48 , 7 , 143 .

Решение.

Сначала получаем разложения данных чисел на простые множители: 84=2·2·3·7 , 6=2·3 , 48=2·2·2·2·3 , 7 (7 – простое число , оно совпадает со своим разложением на простые множители) и 143=11·13 .

Для нахождения НОК данных чисел к множителям первого числа 84 (ими являются 2 , 2 , 3 и 7 ) нужно добавить недостающие множители из разложения второго числа 6 . Разложение числа 6 не содержит недостающих множителей, так как и 2 и 3 уже присутствуют в разложении первого числа 84 . Дальше к множителям 2 , 2 , 3 и 7 добавляем недостающие множители 2 и 2 из разложения третьего числа 48 , получаем набор множителей 2 , 2 , 2 , 2 , 3 и 7 . К этому набору на следующем шаге не придется добавлять множителей, так как 7 уже содержится в нем. Наконец, к множителям 2 , 2 , 2 , 2 , 3 и 7 добавляем недостающие множители 11 и 13 из разложения числа 143 . Получаем произведение 2·2·2·2·3·7·11·13 , которое равно 48 048 .

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

Найдём наибольший общий делитель чисел 24 и 35.
Делителями 24 будут числа 1, 2, 3, 4, 6, 8, 12, 24, а делителями 35 будут числа 1, 5, 7, 35.
Видим, что числа 24 и 35 имеют только один общий делитель - число 1. Такие числа называют взаимно простыми .

Определение. Натуральные числа называют взаимно простыми , если их наибольший общий делитель (НОД) равен 1.

Наибольший общий делитель (НОД) можно найти, не выписывая всех делителей данных чисел.

Разложим на множители числа 48 и 36, получим:
48 = 2 * 2 * 2 * 2 * 3, 36 = 2 * 2 * 3 * 3.
Из множителей, входящих в разложение первого из этих чисел, вычеркнем те, которые не входят в разложение второго числа (т. е. две двойки).
Остаются множители 2 * 2 * 3. Их произведение равно 12. Это число и является наибольшим общим делителем чисел 48 и 36. Так же находят наибольший общий делитель трёх и более чисел.

Чтобы найти наибольший общий делитель

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

Если все данные числа делятся на одно из них, то это число и является наибольшим общим делителем данных чисел.
Например, наибольшим общим делителем чисел 15, 45, 75 и 180 будет число 15, так как на него делятся все остальные числа: 45, 75 и 180.

Наименьшее общее кратное (НОК)

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

Так же находят наименьшее общее кратное для трёх и более чисел.

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

Заметим, что если одно из данных чисел делится на все остальные числа, то это число и является наименьшим общим кратным данных чисел.
Например, наименьшим общим кратным чисел 12, 15, 20 и 60 будет число 60, так как оно делится на все данные числа.

Пифагор (VI в. до н. э.) и его ученики изучали вопрос о делимости чисел. Число, равное сумме всех его делителей (без самого числа), они называли совершенным числом. Например, числа 6 (6 = 1 + 2 + 3), 28 (28 = 1 + 2 + 4 + 7 + 14) совершенные. Следующие совершенные числа - 496, 8128, 33 550 336. Пифагорейцы знали только первые три совершенных числа. Четвёртое - 8128 - стало известно в I в. н. э. Пятое - 33 550 336 - было найдено в XV в. К 1983 г. было известно уже 27 совершенных чисел. Но до сих пор учёные не знают, есть ли нечётные совершенные числа, есть ли самое большое совершенное число.
Интерес древних математиков к простым числам связан с тем, что любое число либо простое, либо может быть представлено в виде произведения простых чисел, т. е. простые числа - это как бы кирпичики, из которых строятся остальные натуральные числа.
Вы, наверное, обратили внимание, что простые числа в ряду натуральных чисел встречаются неравномерно - в одних частях ряда их больше, в других - меньше. Но чем дальше мы продвигаемся по числовому ряду, тем реже встречаются простые числа. Возникает вопрос: существует ли последнее (самое большое) простое число? Древнегреческий математик Евклид (III в. до н. э.) в своей книге «начала», бывшей на протяжении двух тысяч лет основным учебником математики, доказал, что простых чисел бесконечно много, т. е. за каждым простым числом есть ещё большее простое число.
Для отыскания простых чисел другой греческий математик того же времени Эратосфен придумал такой способ. Он записывал все числа от 1 до какого-то числа, а потом вычёркивал единицу, которая не является ни простым, ни составным числом, затем вычёркивал через одно все числа, идущие после 2 (числа, кратные 2, т. е. 4, 6, 8 и т. д.). Первым оставшимся числом после 2 было 3. Далее вычёркивались через два все числа, идущие после 3 (числа, кратные 3, т. е. 6, 9, 12 и т. д.). в конце концов оставались невычеркнутыми только простые числа.

Ключевые слова конспекта: Натуральные числа. Арифметические действия над натуральными числами. Делимость натуральных чисел. Простые и составные числа. Разложение натурального числа на простые множители. Признаки делимости на 2, 3, 5, 9, 4, 25, 10, 11. Наибольший общий делитель (НОД), а также наименьшее общее кратное (НОК). Деление с остатком.

Натуральные числа — это числа, которые используются для счета предметов - 1, 2, 3, 4 , … Но число 0 не является натуральным!

Множество натуральных чисел обозначают N . Запись «3 ∈ N» означает, что число три принадлежит множеству натуральных чисел, а запись «0 ∉ N» означает, что число нуль не принадлежит этому множеству.

Десятичная система счисления - позиционная система счисления по основанию 10 .

Арифметические действия над натуральными числами

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

Пусть a, b и c - натуральные числа, тогда

1. СЛОЖЕНИЕ. Слагаемое + Слагаемое = Сумма

Свойства сложения
1. Переместительное а + b = b + а.
2. Сочетательное а + (b + с) = (а + Ь) + с.
3. а + 0= 0 + а = а.

2. ВЫЧИТАНИЕ. Уменьшаемое — Вычитаемое = Разность

Свойства вычитания
1. Вычитание суммы из числа а — (b + с) = а — b — с.
2. Вычитание числа из суммы (а + b) — с = а + (b — с); (а + b) — с = (а — с) + b.
3. а — 0 = а.
4. а — а = 0.

3. УМНОЖЕНИЕ. Множитель * Множитель = Произведение

Свойства умножения
1. Переместительное а*b = b*а.
2. Сочетательное а*(b*с) = (а*b)*с.
3. 1 * а = а * 1 = а.
4. 0 * а = а * 0 = 0.
5. Распределительное (а + b) * с = ас + bс; (а — b) * с = ас — bс.

4. ДЕЛЕНИЕ. Делимое: Делитель = Частное

Свойства деления
1. а: 1 = а.
2. а: а = 1. Делить на ноль нельзя!
3. 0: а= 0.

Порядок действий

1. Прежде всего действия в скобках.
2. Потом умножение, деление.
3. И только в конце сложение, вычитание.

Делимость натуральных чисел. Простые и составные числа.

Делителем натурального числа а называется натуральное число, на которое а делится без остатка. Число 1 является делителем любого натурального числа.

Натуральное число называется простым , если оно имеет только два делителя: единицу и само это число. Например, числа 2, 3, 11, 23 - простые числа.

Число, имеющее более двух делителей, называется составным . Например, числа 4, 8, 15, 27 - составные числа.

Признак делимости произведения нескольких чисел: если хотя бы один из множителей делится на некоторое число, то и произведение делится на это число. Произведение 24 15 77 делится на 12 , поскольку множитель этого числа 24 делится на 12 .

Признак делимости суммы (разности) чисел: если каждое слагаемое делится на некоторое число, то и вся сумма делится на это число. Если а: b и c: b , то (а + c) : b . А если а: b , а c не делится на b , то a + c не делится на число b .

Если а: c и c: b , то а: b . Исходя из того, что 72:24 и 24:12, делаем вывод, что 72:12.

Представление числа в виде произведения степеней простых чисел называют разложением числа на простые множители .

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

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

Например, задание: разложить на простые множители число 330 . Решение:

Признаки делимости на 2, 5, 3, 9, 10, 4, 25 и 11.

Существуют признаки делимости на 6, 15, 45 и т. д., то есть на числа, произведение которых можно разложить на множители 2, 3, 5, 9 и 10 .

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

Наибольшее натуральное число, на которое делится нацело каждое из двух данных натуральных чисел, называется наибольшим общим делителем этих чисел (НОД ). Например, НОД (10; 25) = 5; а НОД (18; 24) = 6; НОД (7; 21) = 1.

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

Алгоритм нахождения наибольшего общего делителя (НОД)

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

Решение: Нахождение количества учащихся этого класса сводится к нахождению наибольшего общего делителя чисел 155 и 62, поскольку тетради и ручки поделили поровну. 155 = 5 31; 62 = 2 31. НОД (155; 62) = 31 .

Ответ: 31 ученик в классе.

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

Кратным натурального числа а называется натуральное число, которое делится на а без остатка. Например, число 8 имеет кратные: 8, 16, 24, 32 , … Любое натуральное число имеет бесконечно много кратных.

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

Алгоритм нахождения наименьшего общего кратного (НОК ):

НОК также часто применяется в задачах. Например, два велосипедиста одновременно стартовали по велотреку в одном направлении. Один делает круг за 1 мин, а другой - за 45 с. Через какое наименьшее количество минут после начала движения они встретятся на старте?

Решение: Количество минут, через которое они снова встретятся на старте, должно делиться на 1 мин , а также на 45 с . В 1 мин = 60 с. То есть необходимо найти НОК (45; 60). 45 = 32 5; 60 = 22 3 5. НОК (45; 60) = 22 32 5 = 4 9 5 = 180 . В результате получается, что велосипедисты встретятся на старте через 180 с = 3 мин.

Ответ: 3 мин.

Деление с остатком

Если натуральное число а не делится нацело на натуральное число b , то можно выполнить деление с остатком . В таком случае полученное частное называется неполным . Справедливо равенство:

а = b n + r,

где а - делимое, b - делитель, n - неполное частное, r - остаток. Например, пусть делимое равно 243 , делитель - 4 , тогда 243: 4 = 60 (остаток 3) . То есть а = 243, b = 4, n = 60, r = 3, тогда 243 = 60 4 + 3 .

Числа, которые делятся на 2 без остатка, называются четными : а = 2n , n ∈ N.

Остальные числа называются нечетными : b = 2n + 1 , n ∈ N.

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

• Перейти к следующему конспекту:

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

Например :

Число 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 записывают так:

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

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

Пример:

НОД (7; 9) = 1

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

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

Наибольший общий делитель (НОД), свойства.

• Основное свойство: наибольший общий делитель m и n делится на любой общий делитель этих чисел. Пример : для чисел 12 и 18 наибольший общий делитель равен 6; он делится на все общие делители этих чисел: 1, 2, 3, 6.
• Следствие 1: множество общих делителей m и n совпадает с множеством делителей НОД(m , n ).
• Следствие 2: множество общих кратных m и n совпадает с множеством кратных НОК (m , n ).

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

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

и поэтому представим в виде линейной комбинации чисел m и n :

Это соотношение называется соотношением Безу , а коэффициенты u и v — коэффициентами Безу . Коэффициенты Безу эффективно вычисляются расширенным алгоритмом Евклида. Это утверждение обобщается на наборы натуральных чисел — его смысл в том, что подгруппа группы , порождённая набором , — циклическая и порождается одним элементом: НОД (a 1 , a 2 , … , a n ).

Вычисление наибольшего общего делителя (НОД).

Эффективными способами вычисления НОД двух чисел являются алгоритм Евклида и бинарный алгоритм . Кроме того, значение НОД (m ,n ) можно легко вычислить, если известно каноническое разложение чисел m и n на простые множители:

где — различные простые числа, а и — неотрицательные целые числа (они могут быть нулями, если соответствующее простое отсутствует в разложении). Тогда НОД (m ,n ) и НОК (m ,n ) выражаются формулами:

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

— это и есть искомый НОД.

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

Разберем пошагово вычисление наибольшего общего делителя:

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

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

2. Подчёркиваем одинаковые простые множители в обоих числах:

28 = 2 . 2 . 7

64 = 2 . 2 . 2 . 2 . 2 . 2

3. Находим произведение одинаковых простых множителей и записываем ответ:

НОД (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}