Но многие натуральные числа делятся нацело ещё и на другие натуральные числа.
Например :
Число 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 .
Общим кратным нескольких чисел называется число, которое делится на каждое из этих чисел. Например , числа 9, 18 и 45 имеют общее кратное 180. Но 90 и 360 - тоже их общие кратные. Среди всех jбщих кратных всегда есть наименьшее, в данном случае это 90. Это число называется наименьшим общим кратным (НОК) .
НОК всегда натуральное число, которое должно быть больше самого большого из чисел, для которых оно определяется.
Наименьшее общее кратное (НОК). Свойства.
Коммутативность:
Ассоциативность:
В частности, если и — взаимно-простые числа , то:
Наименьшее общее кратное двух целых чисел m и n является делителем всех других общих кратных m и n . Более того, множество общих кратных m, n совпадает с множеством кратных для НОК(m, n ).
Асимптотики для могут быть выражены через некоторые теоретико-числовые функции.
Так, функция Чебышёва . А также:
Это следует из определения и свойств функции Ландау g(n) .
Что следует из закона распределения простых чисел.
Нахождение наименьшего общего кратного (НОК).
НОК(a, b ) можно вычислить несколькими способами:
1. Если известен наибольший общий делитель , можно использовать его связь с НОК:
2. Пусть известно каноническое разложение обоих чисел на простые множители:
где p 1 ,...,p k — различные простые числа, а d 1 ,...,d k и e 1 ,...,e k — неотрицательные целые числа (они могут быть нулями, если соответствующее простое отсутствует в разложении).
Тогда НОК (a ,b ) вычисляется по формуле:
Другими словами, разложение НОК содержит все простые множители , входящие хотя бы в одно из разложений чисел a, b , причём из двух показателей степени этого множителя берётся наибольший.
Пример :
Вычисление наименьшего общего кратного нескольких чисел может быть сведено к нескольким последовательным вычислениям НОК от двух чисел:
Правило. Чтобы найти НОК ряда чисел, нужно:
— разложить числа на простые множители;
— перенести во множители искомого произведения самое большое разложение (произведение множителей самого большого числа из заданных), а потом добавить множители из разложения других чисел, которые не встречаются в первом числе или стоят в нем меньшее число раз;
— полученное произведение простых множителей будет НОК заданных чисел.
Любые два и более натуральных чисел имеют свое НОК. Если числа не кратны друг другу или не имеют одинаковых множителей в разложении, то их НОК равно произведению этих чисел.
Простые множители числа 28 (2, 2, 7) дополнили множителем 3 (числа 21), полученное произведение (84) будет наименьшим числом, которое делится на 21 и 28 .
Простые множители наибольшего числа 30 дополнили множителем 5 числа 25, полученное произведение 150 больше самого большого числа 30 и делится на все заданные числа без остатка. Это наименьшее произведение из возможных (150, 250, 300...), которому кратны все заданные числа.
Числа 2,3,11,37 — простые, поэтому их НОК равно произведению заданных чисел.
Правило . Чтобы вычислить НОК простых чисел, нужно все эти числа перемножить между собой.
Еще один вариант:
Чтобы найти наименьшее общее кратное (НОК) нескольких чисел нужно:
1) представить каждое число как произведение его простых множителей, например:
504 = 2 · 2 · 2 · 3 · 3 · 7 ,
2) записать степени всех простых множителей:
504 = 2 · 2 · 2 · 3 · 3 · 7 = 2 3 · 3 2 · 7 1 ,
3) выписать все простые делители (множители) каждого из этих чисел;
4) выбрать наибольшую степень каждого из них, встретившуюся во всех разложениях этих чисел;
5) перемножить эти степени.
Пример . Найти НОК чисел: 168, 180 и 3024.
Решение . 168 = 2 · 2 · 2 · 3 · 7 = 2 3 · 3 1 · 7 1 ,
180 = 2 · 2 · 3 · 3 · 5 = 2 2 · 3 2 · 5 1 ,
3024 = 2 · 2 · 2 · 2 · 3 · 3 · 3 · 7 = 2 4 · 3 3 · 7 1 .
Выписываем наибольшие степени всех простых делителей и перемножаем их:
НОК = 2 4 · 3 3 · 5 1 · 7 1 = 15120.
Рассмотрим три способа нахождения наименьшего общего кратного.
Нахождение путём разложения на множители
Первый способ заключается в нахождении наименьшего общего кратного путём разложения данных чисел на простые множители.
Допустим, нам требуется найти НОК чисел: 99, 30 и 28. Для этого разложим каждое из этих чисел на простые множители:
Чтобы искомое число делилось на 99, на 30 и на 28, необходимо и достаточно, чтобы в него входили все простые множители этих делителей. Для этого нам необходимо взять все простые множители этих чисел в наибольшей встречающейся степени и перемножить их между собой:
2 2 · 3 2 · 5 · 7 · 11 = 13 860
Таким образом, НОК (99, 30, 28) = 13 860. Никакое другое число меньше 13 860 не делится нацело на 99, на 30 и на 28.
Чтобы найти наименьшее общее кратное данных чисел, нужно разложить их на простые множители, затем взять каждый простой множитель с наибольшим показателем степени, с каким он встречается, и перемножить эти множители между собой.
Так как взаимно простые числа не имеют общих простых множителей, то их наименьшее общее кратное равно произведению этих чисел. Например, три числа: 20, 49 и 33 - взаимно простые. Поэтому
НОК (20, 49, 33) = 20 · 49 · 33 = 32 340.
Таким же образом надо поступать, когда отыскивается наименьшее общее кратное различных простых чисел. Например, НОК (3, 7, 11) = 3 · 7 · 11 = 231.
Нахождение путём подбора
Второй способ заключается в нахождении наименьшего общего кратного путём подбора.
Пример 1. Когда наибольшее из данных чисел делится нацело на другие данные числа, то НОК этих чисел равно большему из них. Например, дано четыре числа: 60, 30, 10 и 6. Каждое из них делится нацело на 60, следовательно:
НОК (60, 30, 10, 6) = 60
В остальных случаях, чтобы найти наименьшее общее кратное используется следующий порядок действий:
- Определяем наибольшее число из данных чисел.
- Далее находим числа, кратные наибольшему числу, умножая его на натуральные числа в порядке их возрастания и проверяя делятся ли на полученное произведение остальные данные числа.
Пример 2. Дано три числа 24, 3 и 18. Определяем самое большое из них - это число 24. Далее находим числа кратные 24, проверяя делится ли каждое из них на 18 и на 3:
24 · 1 = 24 - делится на 3, но не делится на 18.
24 · 2 = 48 - делится на 3, но не делится на 18.
24 · 3 = 72 - делится на 3 и на 18.
Таким образом, НОК (24, 3, 18) = 72.
Нахождение путём последовательного нахождения НОК
Третий способ заключается в нахождении наименьшего общего кратного путём последовательного нахождения НОК.
НОК двух данных чисел равно произведению этих чисел, поделённого на их наибольший общий делитель.
Пример 1. Найдём НОК двух данных чисел: 12 и 8. Определяем их наибольший общий делитель: НОД (12, 8) = 4. Перемножаем данные числа:
Делим произведение на их НОД:
Таким образом, НОК (12, 8) = 24.
Чтобы найти НОК трёх и более чисел используется следующий порядок действий:
- Сначала находят НОК каких-нибудь двух из данных чисел.
- Потом, НОК найденного наименьшего общего кратного и третьего данного числа.
- Затем, НОК полученного наименьшего общего кратного и четвёртого числа и т. д.
- Таким образом поиск НОК продолжается до тех пор, пока есть числа.
Пример 2. Найдём НОК трёх данных чисел: 12, 8 и 9. НОК чисел 12 и 8 мы уже нашли в предыдущем примере (это число 24). Осталось найти наименьшее общее кратное числа 24 и третьего данного числа - 9. Определяем их наибольший общий делитель: НОД (24, 9) = 3. Перемножаем НОК с числом 9:
Делим произведение на их НОД:
Таким образом, НОК (12, 8, 9) = 72.
Рассмотрим решение следующей задачи. Шаг мальчика составляет 75 см, а шаг девочки 60 см. Необходимо найти наименьшее расстояние, на котором они оба сделают по целому числу шагов.
Решение. Весь путь который пройдут ребята, должен делиться без остатка на 60 и на 70, так как они должны сделать каждый целое число шагов. Другими словами, в ответе должно быть число, кратное как 75 так и 60.
Сначала будем выписывать все кратные числа, для числа 75. Получаем:
- 75, 150, 225, 300, 375, 450, 525, 600, 675, … .
Теперь выпишем числа, которые будут кратны 60. Получаем:
- 60, 120, 180, 240, 300, 360, 420, 480, 540, 600, 660, … .
Теперь находим числа которые есть в обоих рядах.
- Общими кратными чисел будут числа, 300, 600, и т.д.
Самое наименьшее из них, это число 300. Оно в данном случае будет называться наименьшим общим кратным чисел 75 и 60.
Возвращаясь к условию задачи, наименьшее расстояние, на котором ребята сделают целое число шагов будет 300 см. Мальчик пройдет этот путь за 4 шага, а девочке потребуется сделать 5 шагов.
Определение наименьшего общего кратного
- Наименьшим общим кратным двух натуральных чисел a и b называется наименьшее натуральное число, которое кратно как a, так и b.
Для того, чтобы найти наименьшее общее кратное двух чисел, не обязательно выписывть подряд все кратные для этих чисел.
Можно воспользоваться следующим методом.
Как найти наименьшее общее кратное
Сначала необходимо разложить данные числа на простые множители.
- 60 = 2*2*3*5,
- 75=3*5*5.
Теперь выпишем все множители которые есть в разложении первого числа (2,2,3,5) и добавим к нему все недостающие множители из разложения второго числа (5).
Получим в итоге ряд простых чисел: 2,2,3,5,5. Произведение этих чисел и будет наименьшим общим сомножителем для данных чисел. 2*2*3*5*5 = 300.
Общая схема нахождения наименьшего общего кратного
- 1. Разложить числа на простые множители.
- 2. Выписать простые множители которые входят в состав одного из них.
- 3. Добавить к этим множителям все те, которые есть в разложении остальных, но нет в выбранном.
- 4. Найти произведение всех выписанных сомножителей.
Данный способ универсален. С его помощью можно найти наименьшее общее кратное любого количества натуральных чисел.
Второе число: b=
Разделитель разрядов Без разделителя пробел " ´
Результат:
Наибольший общий делитель НОД(a ,b )=6
Наименьшее общее кратное НОК(a ,b )=468
Наибольшее натуральное число, на которое делятся без остатка числа a и b, называется наибольшим общим делителем (НОД) этих чисел. Обозначается НОД(a,b), (a,b), gcd(a,b) или hcf(a,b).
Наименьшее общее кратное (НОК) двух целых чисел a и b есть наименьшее натуральное число, которое делится на a и b без остатка. Обозначается НОК(a,b), или lcm(a,b).
Целые числа a и b называются взаимно простыми , если они не имеют никаких общих делителей кроме +1 и −1.
Наибольший общий делитель
Пусть даны два положительных числа a 1 и a 2 1). Требуется найти общий делитель этих чисел, т.е. найти такое число λ , которое делит числа a 1 и a 2 одновременно. Опишем алгоритм.
1) В данной статье под словом число будем понимать целое число.
Пусть a 1 ≥ a 2 , и пусть
где m 1 , a 3 некоторые целые числа, a 3 <a 2 (остаток от деления a 1 на a 2 должен быть меньше a 2).
Предположим, что λ делит a 1 и a 2 , тогда λ делит m 1 a 2 и λ делит a 1 −m 1 a 2 =a 3 (Утверждение 2 статьи "Делимость чисел. Признак делимости"). Отсюда следует, что всякий общий делитель a 1 и a 2 является общим делителем a 2 и a 3 . Справедливо и обратное, если λ общий делитель a 2 и a 3 , то m 1 a 2 и a 1 =m 1 a 2 +a 3 также делятся на λ . Следовательно общий делитель a 2 и a 3 есть также общий делитель a 1 и a 2 . Так как a 3 <a 2 ≤a 1 , то можно сказать, что решение задачи по нахождению общего делителя чисел a 1 и a 2 сведено к более простой задаче нахождения общего делителя чисел a 2 и a 3 .
Если a 3 ≠0, то можно разделить a 2 на a 3 . Тогда
,
где m 1 и a 4 некоторые целые числа, (a 4 остаток от деления a 2 на a 3 (a 4 <a 3)). Аналогичными рассуждениями мы приходим к выводу, что общие делители чисел a 3 и a 4 совпадают с общими делителями чисел a 2 и a 3 , и также с общими делителями a 1 и a 2 . Так как a 1 , a 2 , a 3 , a 4 , ... числа, постоянно убывающие, и так как существует конечное число целых чисел между a 2 и 0, то на каком то шаге n , остаток от деления a n на a n+1 будет равен нулю (a n+2 =0).
.
Каждый общий делитель λ чисел a 1 и a 2 также делитель чисел a 2 и a 3 , a 3 и a 4 , .... a n и a n+1 . Справедливо и обратное, общие делители чисел a n и a n+1 являются также делителями чисел a n−1 и a n , .... , a 2 и a 3 , a 1 и a 2 . Но общий делитель чисел a n и a n+1 является число a n+1 , т.к. a n и a n+1 без остатка делятся на a n+1 (вспомним, что a n+2 =0). Следовательно a n+1 является и делителем чисел a 1 и a 2 .
Отметим, что число a n+1 является наибольшим из делителей чисел a n и a n+1 , так как наибольший делитель a n+1 является сам a n+1 . Если a n+1 можно представить в виде произведения целых чисел, то эти числа также являются общими делителями чисел a 1 и a 2 . Число a n+1 называют наибольшим общим делителем чисел a 1 и a 2 .
Числа a 1 и a 2 могут быть как положительными, так и отрицательными числами. Если один из чисел равен нулю, то наибольший общий делитель этих чисел будет равен абсолютной величине другого числа. Наибольший общий делитель нулевых чисел не определен.
Вышеизложенный алгоритм называется алгоритмом Евклида для нахождения наибольшего общего делителя двух целых чисел.
Пример нахождения наибольшего общего делителя двух чисел
Найти наибольший общий делитель двух чисел 630 и 434.
- Шаг 1. Делим число 630 на 434. Остаток 196.
- Шаг 2. Делим число 434 на 196. Остаток 42.
- Шаг 3. Делим число 196 на 42. Остаток 28.
- Шаг 4. Делим число 42 на 28. Остаток 14.
- Шаг 5. Делим число 28 на 14. Остаток 0.
На шаге 5 остаток от деления равен 0. Следовательно наибольший общий делитель чисел 630 и 434 равен 14. Заметим, что числа 2 и 7 также являются делителями чисел 630 и 434.
Взаимно простые числа
Определение 1. Пусть наибольший общий делитель чисел a 1 и a 2 равен единице. Тогда эти числа называются взаимно простыми числами , не имеющими общего делителя.
Теорема 1. Если a 1 и a 2 взаимно простые числа, а λ какое то число, то любой общий делитель чисел λa 1 и a 2 является также общим делителем чисел λ и a 2 .
Доказательство. Рассмотрим алгоритм Евклида для нахождения наибольшего общего делителя чисел a 1 и a 2 (см. выше).
.
Из условия теоремы следует, что наибольшим общим делителем чисел a 1 и a 2 , и следовательно a n и a n+1 является 1. Т.е. a n+1 =1.
Умножим все эти равенства на λ , тогда
.
Пусть общий делитель a 1 λ и a 2 есть δ . Тогда δ входит множителем в a 1 λ , m 1 a 2 λ и в a 1 λ -m 1 a 2 λ =a 3 λ (см. "Делимость чисел",Утверждение 2). Далее δ входит множителем в a 2 λ и m 2 a 3 λ , и, следовательно, входит множителем в a 2 λ -m 2 a 3 λ =a 4 λ .
Рассуждая так мы убеждаемся, что δ входит множителем в a n−1 λ и m n−1 a n λ , и, следовательно, в a n−1 λ −m n−1 a n λ =a n+1 λ . Так как a n+1 =1, то δ входит множителем в λ . Следовательно число δ является общим делителем чисел λ и a 2 .
Рассмотрим частные случаи теоремы 1.
Следствие 1. Пусть a и c простые числа относительно b . Тогда их произведение ac является простым числом относительно b .
Действительно. Из теоремы 1 ac и b имеют тех же общих делителей, что и c и b . Но числа c и b взаимно простые, т.е. имеют единственный общий делитель 1. Тогда ac и b также имеют единственный общий делитель 1. Следовательно ac и b взаимно простые.
Следствие 2. Пусть a и b взаимно простые числа и пусть b делит ak . Тогда b делит и k .
Действительно. Из условия утверждения ak и b имеют общий делитель b . В силу теоремы 1, b должен быть общим делителем b и k . Следовательно b делит k .
Следствие 1 можно обобщить.
Следствие 3. 1. Пусть числа a 1 , a 2 , a 3 , ..., a m простые относительно числа b . Тогда a 1 a 2 , a 1 a 2 ·a 3 , ..., a 1 a 2 a 3 ···a m , произведение этих чисел простое относительно числа b .
2. Пусть имеем два ряда чисел
таких, что каждое число первого ряда простое по отношению каждого числа второго ряда. Тогда произведение
Требуется найти такие числа, которые делятся на каждое из этих чисел.
Если число делится на a 1 , то оно имеет вид sa 1 , где s какое-нибудь число. Если q есть наибольший общий делитель чисел a 1 и a 2 , то
где s 1 - некоторое целое число. Тогда
является наименьшим общим кратным чисел a 1 и a 2 .
a 1 и a 2 взаимно простые, то наименьшее общее кратное чисел a 1 и a 2:
Нужно найти наименьшее общее кратное этих чисел.
Из вышеизложенного следует, что любое кратное чисел a 1 , a 2 , a 3 должно быть кратным чисел ε и a 3 , и обратно. Пусть наименьшее общее кратное чисел ε и a 3 есть ε 1 . Далее, кратное чисел a 1 , a 2 , a 3 , a 4 должно быть кратным чисел ε 1 и a 4 . Пусть наименьшее общее кратное чисел ε 1 и a 4 есть ε 2 . Таким образом выяснили, что все кратные чисел a 1 , a 2 , a 3 ,...,a m совпадают с кратными некоторого определенного числа ε n , которое называют наименьшим общим кратным данных чисел.
В частном случае, когда числа a 1 , a 2 , a 3 ,...,a m взаимно простые, то наименьшее общее кратное чисел a 1 , a 2 как было показано выше имеет вид (3). Далее, так как a 3 простое по отношению к числам a 1 , a 2 , тогда a 3 простое по отношению числа a 1 ·a 2 (Следствие 1). Значит наименьшее общее кратное чисел a 1 ,a 2 ,a 3 является число a 1 · a 2 ·a 3 . Рассуждая аналогичным образом мы приходим к следующим утверждениям.
Утверждение 1. Наименьшее общее кратное взаимно простых чисел a 1 , a 2 , a 3 ,...,a m равен их произведению a 1 ·a 2 ·a 3 ···a m .
Утверждение 2. Любое число, которое делится на каждое из взаимно простых чисел a 1 , a 2 , a 3 ,...,a m делится также на их произведение a 1 ·a 2 ·a 3 ···a m .
