Делимость
До того как начать разбирать эти две аббревиатуры, рассмотрим сначала понятие делимости. Что значит фраза "число А делится на число Б"? Например, 24 делится на 6. И что значит "не делится"? Например, 27 не делится на 2.
Когда мы говорим о делимости, то речь идет о целочисленном делении целых чисел. И делимость означает, что число делится на делитель нацело, без остатка.
24 делится на 6, частное равно 4, а остаток нулю.
27 не делится на 2, частное равно 13, а остаток равен одному.
Признаки делимости
Проверить, делится ли одно число на заданное, можно просто выполнив деление. Но если число большое, а результат самого деления нам не так чтобы нужен? Можно ли не находя частное, определить, делится ли число?
Существуют несколько признаков делимости, когда по внешнему вида числа мы можем определить, делится ли оно на заданное. Рассмотрим только некоторые из них, те, которые легко проверяются.
По последней цифре
Число делится на 2, если его последняя цифра - четная.
Число делится на 5, если его последняя цифра - 5 или 0.
Число делится на 10, если его последняя цифра - 0.
Например, 234 делится на 2, так как 4 - четная.
235 делится на 5, так как последняя цифра - 5.
190 делится на 10 и на 5, так как последняя цифра - 0.
По сумме цифр числа
Число делится на 3, если сумма цифр этого числа делится на 3.
Число делится на 9, если сумма цифр этого числа делится на 9.
Например, 393 делится на 3, так как сумма цифр этого числа 3+9+3=15 делится на 3.
180 делится на 9, так как сумма цифр этого числа 1+8+0=9 делится на 9.
Число делится на 6, если оно делится на 2 и на 3 одновременно.
Например, 36 делится на 2 (6 четная) и на 3 (3+6=9 - делится на 3), поэтому оно делится на 6.
Простые и составные числа
Среди натуральных чисел выделяют такие числа, которые делятся только на 1 и на самого себя. Такие числа называются простыми. Остальные числа, имеющие больше двух делителей, называют составными. Отдельно выделяют 1, у нее только один делитель.
Пример простого числа - 2, 3, 5, 7, 11, 13, 17, 19 и так далее. Существуют специальные таблицы простых чисел, но многие проблемы простых чисел до сих пор не решены.
Разложение на простые множители
Для составных чисел можно найти такие множители, которые будут только простыми числами, а произведение этих множителей будет равно исходному числу.
Например, 24=2*2*2*3.
Это произведение и называется разложением на простые множители. Если множители отсортированы по возрастанию, то для каждого конкретного числа это разложение будет единственным.
Для построения такого разложения существует четкий алгоритм.
- Записываем в левый столбец исходное число, проводим вертикальную черту, отделяя правый столбец.
- Проверяем, делится ли число на 2. Если да, то записываем 2 в правый столбец, в левый столбец в следующей строке записываем кратное исходного числа и 2.
- Проверяем, делится ли полученное число на 2, если да, то действуем как в пункте 2.
- Если нет, то проверяем, делится ли наше число на 3. Если да, то 3 записываем в правый столбец, а в левый столбец строчкой ниже пишем кратное от деления на 3 и переходим к пункту 3.
- Если число не делится на 3, то переходим к следующему числу в списке простых чисел - 5.
- Каждый раз начинаем проверку делимости с 2, постепенно переходя к все большим и большим простым числам, если это необходимо.
- Так действуем до тех пор, пока число в левом столбце не станет равно 1. Тогда останавливаемся.
- В правом столбце у нас записаны все простые множители числа.
Наибольший общий делитель
НОД или наибольший общий делитель для нескольких чисел - это такое наибольшее число, на которое делятся все эти числа.
Например, НОД(12, 18)=6.
Зная разложение чисел на простые множители, легко найти их НОД. Выписываем совпадающие множители, их произведение и даст нам НОД.
Наименьшее общее кратное
НОК или наименьшее общее кратное нескольких чисел - это такое наименьшее число, которое делится на все эти числа.
Например, НОК(4, 6)=12.
Зная разложение чисел на простые множители, легко найти их НОК. К множителям меньшего числа дописываем несовпадающие множители. Это произведение и даст нам НОК.
Взаимно простые числа
Если у двух составных чисел нет общих простых множителей, то такие числа называются взаимно простыми. НОК таких чисел равен их произведению, а НОД равен 1.