Итак, мы научились представлять составное число в виде произведения простых множителей.
Пришло время разобраться с делителями чисел и наибольшим общим делителем, его называют НОД.
Определение: Делителем числа m называют натуральное число n, если m делится на n без остатка. Другими словами, если m кратно n, то n делитель m.
Самым простым, но не самым эффективным методом поиска делителей является выписывание в ряд чисел: 1 2 3 4 … 24. Далее вычеркиваются все, которые не делят число 24 нацело, зачеркнем 5 7 9 и так далее. Все незачеркнутые будут делителями.
Более эффективным иногда бывает представить число в виде произведения простых множителей, которые сами по себе являются делителями числа, а так же всех возможных комбинаций произведений простых множителей.
Пример: 49 = 7 * 7, делители 49 это числа 49 7 и 1.
Определение: Наибольшим общим делителем (НОД) двух (или нескольких) чисел m и n будет наибольшее натуральное число, являющееся делителем m и n
Представим число 18 в виде произведения простых множителей: 18 = 2 · 3 · 3
Представим число 24 в виде произведения простых множителей: 24 = 2 · 2 · 2 · 3
Для наглядности я выделил общие простые множители жирным. И число 18 и число 24 одновременно содержат множители 2 и 3 по одному разу.
НОД ( 18 ; 24 ) = 2 · 3 = 6
То есть число 6, это максимальное натуральное число, на которое и число 18 и число 24 поделятся без остатка.
Делители числа 18 это 18 9 6 3 2 и 1
Делители числа 24 это 24 12 8 6 4 3 2 и 1
Число 6 — это максимальное число, которое содержится в обоих множествах делителей.
Есть масса способов нахождения НОД, в том числе алгоритм Евклида, который мы будем проходить по программированию.
Определение: Мы будем называть числа взаимно простыми, если их НОД = 1
Пример: НОД (25 ; 33) = 1
25 = 5 · 5
Делители числа 25 это числа 25 5 и 1
33 = 3 · 11
Делители числа 33 это числа 33 11 3 и 1
Поскольку максимальное число, на которое делятся без остатка числа 25 и 33 это 1, то 25 и 33 взаимно простые числа.
ДОМАШНЕЕ ЗАДАНИЕ
1) Выписать все делители числа 18.
2) Выписать все делители числа 20.
3) Выписать все делители числа 28.
4) Выписать все делители числа 42.
5) Выписать все делители числа 54.
6) Вычислить НОД (8 ; 12)
7) Вычислить НОД (45 ; 36)
8) Вычислить НОД (15 ; 25)
9) Вычислить НОД (6 ; 12)
10) Являются ли числа 32 и 49 взаимно простыми?
★ Найдите наименьшее натуральное число, которое при делении на 2 даст остаток 1, при делении на 5 даст остаток 2, при делении на 17 даст остаток 3.