Делимость 3

Пусть дано число 360. На какое наименьшее простое число оно делится? Очевидно, на 2: 360 = 2·180. На какое наименьшее простое число делится 180? Тоже на 2: 180 = 2·90, так что 360 = 2·2·90. На какое наименьшее простое число делится 90? Опять на 2: 90 = 2·45, так что 360 = 2·2·2·45. На какое наименьшее простое число делится 45? На 3: 45 = 3·15, так что 360 = 2·2·2·3·15. Наконец, 15 = 3·5, 360 = 2·2·2·3·3·5, и на этом начатый нами процесс останавливается: все получившиеся множители являются простыми, и дальнейшее разложение числа 360 на множители оказывается невозможным.

Точно такую же процедуру можно проделать и для любого другого числа. Это утверждение есть знаменитая основная теорема арифметики: любое натуральное число (кроме единицы) можно единственным образом представить в виде произведения простых множителей. Такое произведение называется разложением на простые множители или каноническим разложением. Выше было получено каноническое разложение числа 360: 360 = 2·2·2·3·3·5 или, как это обычно записывают, 360 = 2^­­3·3²·5. Мы видим, таким образом, что любое число состоит как бы из «кирпичиков» — простых множителей, возникающих в его каноническом разложении. Простое число состоит из одного такого «кирпичика» — самого себя.

Каноническое разложение удобнее всего находить по следующей схеме:

(Слева от вертикальной черты пишется раскладываемое число, справа — его наименьший простой делитель. Результат деления записывается слева строчкой ниже. Процесс продолжается до тех пор, пока слева не получится 1.)

Каноническое разложение является мощным инструментом решения целого ряда задач. Благодаря ему перед нами открывается вся картина делителей данного числа. Так, для числа 360 = 2^­­3·3²·5 мы теперь можем сразу сказать, что оно делится, например, на 2³ = 8, на 2²·3 = 12, на 2·3²·5 = 90 (так как эти числа «сконструированы» из отдельных элементов канонического разложения) и не делится, скажем, на 7 и на 33 = 3·11 (так как ни 7, ни 11 не входят в каноническое разложение).

Теперь — два важнейших определения.

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

Наименьшим общим кратным чисел а и b называется наименьшее число, которое делится как на а, так и на b. Наименьшее общее кратное чисел а и b обозначается НОК(a,b).

Для небольших чисел нам уже много раз приходилось интуитивно искать НОК — вспомните приведение дробей к общему знаменателю! Пусть, например, нужно сложить 1/6 и 1/9. Можно, конечно, поступить формально и привести их к общему знаменателю 6·9 = 54, но лучше все же сообразить, что общим знаменателем является 18. Ведь 18 — наименьшее число, делящееся одновременно на 6 и 9: НОК(6,9) = 18. Итак, 1/6 + 1/9 = 3/18 + 2/18 = 5/18. Мы видим, таким образом, что «самый хороший» общий знаменатель двух дробей — это НОК их знаменателей!

Найти НОД для небольших чисел также не составляет труда — достаточно простого перебора всех общих делителей. Очевидно, например, что НОД(6,9) = 3, НОД(18,24) = 6. Ну а как найти НОД и НОК, скажем, чисел 120 и 252? Здесь снова приходит на помощь каноническое разложение.

Имеем: 120 = 2³·3·5, 252 = 2²·3²·7 (найди эти разложения самостоятельно!). В данных разложениях фигурируют множители 2, 3, 5, 7 — каждый в своей степени. Вот из этих множителей и будут конструироваться искомые НОД и НОК.

Какие из них войдут в НОД? Поскольку НОД — общий делитель, в него войдут только те множители, которые входят в оба разложения одновременно, а именно 2 и 3. В самом деле, 7 не может войти в НОД, так как 120 не делится на 7 (ведь 7 не входит в каноническое разложение числа 120); аналогично и 5 не может войти в НОД, так как 252 не делится на 5. А в каких степенях будут входить в НОД множители 2 и 3? Поскольку НОД — наибольший общий делитель, эти степени должны быть максимально возможными. Видим, что 2² еще может войти в НОД (оба числа делятся на 2²), а 2³ — уже нет (252 не делится на 2³). Аналогично, 3 еще может войти в НОД (оба числа делятся на 3), а 3² — уже нет (120 не делится на 3²). Итак, НОД(120,252) = 2²·3 = 12.

А какие из множителей 2, 3, 5, 7 войдут в НОК? НОК делится и на 120, и на 252, поэтому НОК обязано делиться и на каждый множитель чисел 120 и 252. Это означает, что каждый из множителей 2, 3, 5, 7 войдет в НОК. В каких степенях? Поскольку НОК — наименьшее общее кратное, эти степени должны быть минимально возможными. Видим, что 2³ еще может войти в НОК (только в этом случае НОК разделится и на 120, и на 252), а 2² — уже нет (потому что тогда НОК не разделится на 120). Аналогично, 3² еще может войти в НОК (снова только в этом случае НОК разделится и на 120, и на 252), а просто 3 — уже нет (потому что тогда НОК не разделится на 252). По тем же соображениям в НОК должны войти множители 5 и 7, так что НОК(120,252) = 2³·3²·5·7 = 2520.

Совершенно аналогично отыскиваются НОД и НОК трех и более чисел.

1. Найди каноническое разложение чисел 36, 42, 54, 60, 108, 156, 432, 666, 1001, 1200, твоего года рождения и почтового индекса.
2. Найди каноническое разложение числа 3150. Покажи, что оно делится на 6, 14, 18, 21, 35, 42, 45. Найди еще десять делителей этого числа. Делится ли оно на 12, 22, 26, 27?
3. Число А делится на 3 и 4. Следует ли отсюда, что А делится на 3·4 = 12?
4. Число А делится на 4 и 6. Следует ли отсюда, что А делится на 4·6 = 24?
5. Число 3А делится на 7. Следует ли отсюда, что А делится на 7?
6. Число 9А делится на 6. Следует ли отсюда, что А делится на 6?
7. Сформулируй признаки делимости на 6, 15, 18, 45.
8. Докажи, что произведение трех последовательных натуральных чисел делится на 6.
9. Докажи, что произведение пяти последовательных натуральных чисел делится на 120.
10. Найди НОД чисел: а) 72 и 108; б) 168 и 180; в) 360 и 1050; г) 270, 450 и 555.
11. Найди НОК чисел: а) 15 и 18; б) 36 и 48; в) 252 и 360; г) 72, 120 и 264.
12. Сравни: а) НОК(18,24)·НОД(18,24) и 18·24; б) НОК(96,112)·НОД(96,112) и 96·112. Почему так получается? Чему равно произведение НОК(a,b)·НОД(a,b)?
13. У Деда Мороза 525 мандаринов и 735 конфет. Нужно составить из них одинаковые наборы, причем так, чтобы раздать их наибольшему количеству детей. Сколько мандаринов и сколько конфет должно быть тогда в наборе? Сколько детей получат подарки?
14. Длина шага Вани равна 75 см, Тани — 60 см, а их папы — 1 м 05 см. Гуляя, все трое сделали целое число шагов. Какое наименьшее расстояние они могли пройти?
15. Какая из дробей больше: 23/135 или 31/180? На сколько?
16. Числа называются взаимно простыми, если их НОД равен 1. Покажи, что числа 175 и 198 являются взаимно простыми. Придумай три пары взаимно простых чисел и найди их НОК. Чему равно НОК(a,b) для взаимно простых чисел a и b? Почему?