Общим делителем нескольких чисел называют такое число, на которое делится каждое из данных чисел. Например, дано два числа: 6 и 9. Число 6 имеет делители 1, 2, 3, 6. Число 9 имеет делители 1, 3, 9. Мы видим, что числа 6 и 9 имеют общие делители 1 и 3.

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

Таким образом, из всех общих делителей чисел 6 и 9, наибольшим общим делителем является число 3.

Обычно наибольший общий делитель записывают так: НОД (a , b , ...) = x .

Согласно этому, запишем наибольший общий делитель чисел 6 и 9:

НОД (6, 9) = 3.

Числа, НОД которых равен единице, называют взаимно простыми числами . Например, числа 14 и 15 являются взаимно простыми: НОД (14, 15) = 1.

Калькулятор НОД

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

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

Например :

Число 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}

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

Нахождение путём разложения на множители

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

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

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

Раскладываем числа 84 и 90 на простые множители:

Итак, мы подчеркнули все общие простые множители, осталось перемножить их между собой: 1 · 2 · 3 = 6.

Таким образом, НОД (84, 90) = 6.

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

Раскладываем 15 и 28 на простые множители:

Числа 15 и 28 являются взаимно простыми, так как их наибольший общий делитель - единица.

НОД (15, 28) = 1.

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

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

Сначала мы рассмотрим этот способ в применении только к двум данным числам, а затем разберёмся в том, как его применять к трём и более числам.

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

Пример 1. Возьмём два числа 27 и 9. Так как 27 делится на 9 и 9 делится на 9, значит, 9 является общим делителем чисел 27 и 9. Этот делитель является в тоже время и наибольшим, потому что 9 не может делиться ни на какое число, большее 9. Следовательно, НОД (27, 9) = 9.

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

1. Из двух данных чисел большее число делят на меньшее.
2. Затем, меньшее число делят на остаток, получившийся от деления большего числа на меньшее.
3. Далее, первый остаток делят на второй остаток, который получился от деления меньшего числа на первый остаток.
4. Второй остаток делят на третий, который получился от деления первого остатка на второй и т. д.
5. Таким образом деление продолжается до тех пор, пока в остатке не получится нуль. Последний делитель как раз и будет наибольшим общим делителем.

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

1) 140: 96 = 1 (остаток 44)

2) 96: 44 = 2 (остаток 8)

3) 44: 8 = 5 (остаток 4)

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

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

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

1. Сперва находим наибольший общий делитель любых двух чисел из нескольких данных.
2. Затем находим НОД найденного делителя и какого-нибудь третьего данного числа.
3. Затем находим НОД последнего найденного делителя и четвёртого данного числа и так далее.

Пример 3. Найдём наибольший общий делитель чисел 140, 96 и 48. НОД чисел 140 и 96 мы уже нашли в предыдущем примере (это число 4). Осталось найти наибольший общий делитель числа 4 и третьего данного числа - 48:

48 делится на 4 без остатка. Таким образом, НОД (140, 96, 48) = 4.

Продолжим разговор о наименьшем общем кратном, который мы начали в разделе « НОК – наименьшее общее кратное, определение, примеры». В этой теме мы рассмотрим способы нахождения НОК для трех чисел и более, разберем вопрос о том, как найти НОК отрицательного числа.

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

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

Определение 1

Найти наименьшее общее кратное через наибольший общий делитель можно по формуле НОК (a , b) = a · b: НОД (a , b) .

Пример 1

Необходимо найти НОК чисел 126 и 70 .

Решение

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

Найдет НОД чисел 70 и 126 . Для этого нам понадобится алгоритм Евклида: 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 .

Пример 2

Найдите нок чисел 68 и 34 .

Решение

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

Ответ: НОК (68 , 34) = 68 .

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

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

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

Определение 2

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

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

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

Пример 3

У нас есть два числе 75 и 210 . Мы можем разложить их на множители следующим образом: 75 = 3 · 5 · 5 и 210 = 2 · 3 · 5 · 7 . Если составить произведение всех множителей двух исходных чисел, то получится: 2 · 3 · 3 · 5 · 5 · 5 · 7 .

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

Пример 4

Найдите НОК чисел 441 и 700 , разложив оба числа на простые множители.

Решение

Найдем все простые множители чисел, данных в условии:

441 147 49 7 1 3 3 7 7

700 350 175 35 7 1 2 2 5 5 7

Получаем две цепочки чисел: 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 .

Дадим еще одну формулировку метода нахождения НОК путем разложения чисел на простые множители.

Определение 3

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

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

Пример 5

Вернемся к числам 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 .

Пример 6

Необходимо вычислить НОК чисел 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 = 4536 . Это и есть наименьшее общее кратное чисел 84 и 648 ​​​​​​ ​.

Ответ: НОК (84 , 648) = 4 536 .

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

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

Теорема 1

Предположим, что у нас есть целые числа 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) .

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

Пример 7

Необходимо вычислить наименьшее общее кратное четырех чисел 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) . В ходе вычислений получаем m 3 = 3 780 .

Нам осталось вычислить m 4 = НОК (m 3 , a 4) = НОК (3 780 , 250) . Действуем по тому же алгоритму. Получаем m 4 = 94 500 .

НОК четырех чисел из условия примера равно 94500 .

Ответ: НОК (140 , 9 , 54 , 250) = 94 500 .

Как видите, вычисления получаются несложными, но достаточно трудоемкими. Чтобы сэкономить время, можно пойти другим путем.

Определение 4

Предлагаем вам следующий алгоритм действий:

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

Пример 8

Необходимо найти НОК пяти чисел 84 , 6 , 48 , 7 , 143 .

Решение

Разложим все пять чисел на простые множители: 84 = 2 · 2 · 3 · 7 , 6 = 2 · 3 , 48 = 2 · 2 · 2 · 2 · 3 , 7 , 143 = 11 · 13 . Простые числа, которым является число 7 , на простые множители не раскладываются. Такие числа совпадают со своим разложением на простые множители.

Теперь возьмем произведение простых множителей 2 , 2 , 3 и 7 числа 84 и добавим к ним недостающие множители второго числа. Мы разложили число 6 на 2 и 3 . Эти множители уже есть в произведении первого числа. Следовательно, их опускаем.

Продолжаем добавлять недостающие множители. Переходим к числу 48 , из произведения простых множителей которого берем 2 и 2 . Затем добавляем простой множитель 7 от четвертого числа и множители 11 и 13 пятого. Получаем: 2 · 2 · 2 · 2 · 3 · 7 · 11 · 13 = 48 048 . Это и есть наименьшее общее кратное пяти исходных чисел.

Ответ: НОК (84 , 6 , 48 , 7 , 143) = 48 048 .

Нахождение наименьшего общего кратного отрицательных чисел

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

Пример 9

НОК (54 , − 34) = НОК (54 , 34) , а НОК (− 622 , − 46 , − 54 , − 888) = НОК (622 , 46 , 54 , 888) .

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

Пример 10

Необходимо вычислить НОК отрицательных чисел − 145 и − 45 .

Решение

Произведем замену чисел − 145 и − 45 на противоположные им числа 145 и 45 . Теперь по алгоритму вычислим НОК (145 , 45) = 145 · 45: НОД (145 , 45) = 145 · 45: 5 = 1 305 , предварительно определив НОД по алгоритму Евклида.

Получим, что НОК чисел − 145 и − 45 равно 1 305 .

Ответ: НОК (− 145 , − 45) = 1 305 .

Если вы заметили ошибку в тексте, пожалуйста, выделите её и нажмите Ctrl+Enter

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

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

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

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

Определение 1

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

Пример 1

Вот примеры такого делителя: тройка будет общим делителем для чисел - 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 , нельзя.

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

Определение 2

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

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

Пример 2

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

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

Определение 3

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

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

Пример 3

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

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

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

Пример 4

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

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

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

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

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

Определение 4

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

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

Определение 5

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

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

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

Если у чисел 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 есть число, кратное восьми.

Определение 6 Доказательство 2

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

Определение 7

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

Перед тем, как сформулировать свойство, советуем вам повторить теорему, которую мы доказывали в статье о делении с остатком. Согласно ей, делимое число 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 аналогично множеству делителей НОД этих чисел. Это утверждение, которое является следствием из алгоритма Евклида, позволит нам вычислить все общие делители двух заданных чисел.

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

Определение 8

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

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

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

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

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 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 .

Определение 9

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

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

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

Определение 10

Если у чисел 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) , среди которых и будет доказательство данного свойства. Это утверждение мы используем, когда приводим обыкновенные дроби к несократимому виду.

Определение 11

Наибольшим общим делителем 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 .

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

Если вы заметили ошибку в тексте, пожалуйста, выделите её и нажмите Ctrl+Enter