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

Любое натуральное число всегда делится на 1 и на само себя. Число 2 - наименьшее простое число. Это единственное чётное простое число, остальные простые числа - нечётные.

Простых чисел много, и первое среди них - число 2. Однако нет последнего простого числа.

Таблица простых чисел до 1000.

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

Например:

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

НОД (a; b).

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

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

Пример:

Д (7) = {1, 7}

Д (9) = {1, 9}

НОД (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) = n. В частности, НОД(n, n) = n.
•  — общий множитель можно выносить за знак НОД.
• Если , то после деления на  числа становятся взаимно простыми, то есть, .

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

• Мультипликативность: если  взаимно просты, то:

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

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

.

Это соотношение называется соотношением Безу, а коэффициенты u и v — коэффициентами Безу. Коэффициенты Безу эффективно вычисляются расширенным алгоритмом Евклида. Это утверждение обобщается на наборы натуральных чисел — его смысл в том, что подгруппа группы , порождённая набором , — циклическая и порождается одним элементом: НОД (a₁, a₂, … , 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}

НОД (10; 15) = 5