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

Любое натуральное число всегда делится на 1 и на само себя.

Число 2 — наименьшее простое число. Это единственное чётное простое число, остальные простые числа — нечётные.

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

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

Например:

• число 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» делятся без остатка.

Кратко наибольший общий делитель чисел «a» и «b» записывают так:

НОД (a; b)

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

Внимание!

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

Например, числа 15 и 28 - взаимно простые, у них нет общих делителей, кроме 1. Действительно, 15 = 3 х 5 , а 28 = 2 х 2 х 7. Но сами по себе (не в паре) числа 15 и 28 - составные.

Алгоритм нахождения НОД.

1 способ.

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

Например, НОД (10; 5) = 5

НОД (36; 12; 4) = 4

Если одно число не делится на другое, то переходите к пункту 2.

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

3. Подчеркните (обведите, выделите) общие множители во всех данных числах.

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

Например, НОД (12; 16) = 2 х 2 = 4, так как

12 = 2 х 2 х 3

16 = 2 х 2 х 2 х 2

2 способ (алгоритм Евклида).

Пусть даны два числа.

1. Найдите разность этих чисел.

2. Замените большее из чисел на найденную разность.

3. Снова найдите разность между оставшимся меньшим числом и полученной в пункте 1 разностью.

4. Снова замените большее из чисел на найденную в пункте 3 разность.

5. Этот процесс повторяется до тех пор, пока не останется одно ненулевое число. Это и будет НОД исходных чисел.

Например, НОД (420; 150) = НОД (270; 150) = НОД (120; 150) = НОД (120; 30) = НОД (90; 30) = НОД (60; 30) = НОД ( 30; 30) = 30, так как

420 - 150 = 270

270 - 150 = 120

150 - 120 = 30

120 - 30 = 90

90 - 30 = 60

60 - 30 = 30

3 способ (модифицированный алгоритм Евклида)

Пусть даны два числа.

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

2. Замените большее число на остаток от деления из пункта 1.

3. Снова разделите большее число (в пункте 1 оно было меньшим) на меньшее (это остаток от деления из пункта 1)

4. Замените большее число на остаток от деления, полученный в пункте 3.

5. Снова повторите деление.

6. Процесс продолжается до тех пор, пока остаток от деления не будет равным 0. Тогда последний делитель и будет НОД.

Например, НОД (420; 150) = НОД (120; 150) = НОД (120; 30) = 30, так как

420 : 150 = 2 (остаток 120)

150 : 120 = 1 (остаток 30)

120 : 30 = 4 (остаток 0)

Источники:

1. Михайлова Ж.Н. Алгоритмы - ключ к решению задач. 5 - 6 классы. - СПб, Издательский дом "Литера", 2019 - 288 с.

2. Смыкалова Е.В. Математика. Дополнительные главы для учащихся 6 класса. - СПБ, СМИО Пресс, 2018 - 48 с.

3. Электронный ресурс. Режим доступа: http://math-prosto.ru