Нахождение всех делителей числа, число делителей числа
Мы помогаем студентам с дипломными, курсовыми, контрольными Узнать стоимость

Нахождение всех делителей числа, число делителей числа

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

    Как найти все делители числа

    Чтобы понять материал, изложенный в данном пункте, нужно хорошо знать, что вообще из себя представляют кратные числа и делители. Здесь мы поговорим только о поиске делителей натуральных чисел, т.е. целых положительных. Этим можно ограничиться, поскольку свойство делимости гласит, что делители целого отрицательного числа аналогичны делителям целого положительного, которое будет противоположным по отношению к этому числу. Также сразу уточним, что у нуля есть бесконечно большое число делителей, и находить их смысла не имеет, поскольку в итоге все равно получится 0.

    Если речь идет о простом числе, то его можно разделить только на единицу и на само себя. Значит, у любого простого числа a есть всего 4 делителя, два из которых больше 0 и два меньше: 1, -1, a, -a. Возьмем простое число 7: у него есть делители 7, -7, 1 и -1, и все. Еще один пример: 367 – тоже простое число, которое можно разделить лишь на 1, -1, 367 и -367.

    Сложнее определить все делители составного числа. Сформулируем теорему, которая лежит в основе данного действия.

    Теорема 1

    Допустим, у нас есть выражение, означающее каноническое разложение числа на простые множители, вида a=p1s1·p2s2··pnsn. Тогда натуральными делителями числа a будут следующие числа: d=p1t2·p2t2··pntn, где t1=0, 1, , s1, t2=0, 1, , s2, , tn=0, 1, , sn.

    Доказательство 1

    Перейдем к доказательству этой теоремы. Зная основное определение делимости, мы можем утверждать, что a можно разделить на d, если есть такое число q, что делает верным равенство a=d·q, т.е. q=p1(s1t1)·p2(s2-t2)··pn(sn-tn).

    Любое число, делящее a, будет иметь именно такой вид, поскольку, согласно свойствам делимости, других простых множителей, кроме p1, p2, , pn, оно иметь не может, а их показатели в данном случае не превысят s1, s2, , sn.

    Учитывая доказательство этой теоремы, мы можем сформировать схему нахождения всех положительных делителей данного числа.

    Для этого нужно выполнить следующие действия:

    1. Выполнить каноническое разложение на простые множители и получить выражение вида a=p1s1·p2s2··pnsn.
    2. Найти все значения d=p1t2·p2t2··pntn, где числа t1, t2, , tn будут принимать независимо друг от друга каждое из значений t1=0, 1, , s1, t2=0, 1, , s2, , tn=0, 1, , sn.

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

    Пример 1

    Условие: найти все делители 8.

    Решение

    Разложим восьмерку на простые множители и получим 8=2·2·2.  Переведем разложение в каноническую форму и получим 8=23. Следовательно, a=8, p1=2, s1=3.

    Поскольку все делители восьмерки будут значениями p1t1=2t1, то t1 может принять значения нуля, единицы, двойки, тройки. 3 будет последним значением, ведь s1=3. Таким образом, если t1=0, то 2t1=20=1, если 1, то 2t1=21=2, если 2, то 2t1=22=4, а если 3, то 2t1=23=8.

    Для нахождения делителей удобно все полученные значения оформлять в виде таблицы:

    t1 2t1
    0 20=1
    1 21=2
    2 22=4
    3 23=8

    Значит, положительными делителями восьмерки будут числа 1, 2, 4 и 8, а отрицательными 1, 2, 4 и 8.

    Ответ: делителями данного числа будут ±1, ±2, ±4, ±8.

    Возьмем пример чуть сложнее: в нем при разложении числа получится не один, а два множителя.

    Пример 2

    Условие: найдите все делители числа 567, являющиеся натуральными числами.

    Решение

    Начнем с разложения данного числа на простые множители.

    56718963217133337

    Приведем разложение к каноническому виду и получим 567=34·7. Затем перейдем к вычислению всех натуральных множителей. Для этого будем присваивать t1 и t2 значения 0, 1, 2, 3, 4 и 0, 1, вычисляя при этом значения 3t1·7t2. Результаты будем вносить в таблицу:

    t1 t2 3t1·7t2
    0 0 30·70=1
    0 1 30·71=7
    1 0 31·70=3
    1 1 31·71=21
    2 0 32·70=9
    2 1 32·71=63
    3 0 33·70=27
    3 1 33·71=189
    4 0 34·70=81
    4 1 34·71=567

    Ответ: натуральными делителями 567 будут числа 27, 63, 81, 189, 1, 3, 7, 9, 21 и 567.

    Продолжим усложнять наши примеры – возьмем четырехзначное число.

    Пример 3

    Условие: найти все делители 3 900, которые будут больше 0.

    Решение

    Проводим разложение данного числа на простые множители. В каноническом виде оно будет выглядеть как 3 900=22·3·52·13. Теперь приступаем к нахождению положительных делителей, подставляя в выражение 2t1·3t2·5t3·13t4 значения t1, равные 0, 1 и 2, t2=0,1t3=0, 1, 2t4=0, 1. Результаты представляем в табличном виде:

    t1 t2 t3 t4 2t1·3t2·5t3·13t4
    0 0 0 0 20·30·50·130=1
    0 0 0 1 20·30·50·131=13
    0 0 1 0 20·30·51·130=5
    0 0 1 1 20·30·51·131=65
    0 0 2 0 20·30·52·130=25
    0 0 2 1 20·30·52·131=325
    0 1 0 0 20·31·50·130=3
    0 1 0 1 20·31·50·131=39
    0 1 1 0 20·31·51·130=15
    0 1 1 1 20·31·51·131=195
    0 1 2 0 20·31·52·130=75
    0 1 2 1 20·31·52·131=975

     

    t1 t2 t3 t4 2t1·3t2·5t3·13t4
    1 0 0 0 21·30·50·130=2
    1 0 0 1 21·30·50·131=26
    1 0 1 0 21·30·51·130=10
    1 0 1 1 21·30·51·131=130
    1 0 2 0 21·30·52·130=50
    1 0 2 1 21·30·52·131=650
    1 1 0 0 21·31·50·130=6
    1 1 0 1 21·31·50·131=78
    1 1 1 0 21·31·51·130=30
    1 1 1 1 21·31·51·131=390
    1 1 2 0 21·31·52·130=150
    1 1 2 1 21·31·52·131=1950

     

    t1 t2 t3 t4 2t1·3t2·5t3·13t4
    2 0 0 0 22·30·50·130=4
    2 0 0 1 22·30·50·131=52
    2 0 1 0 22·30·51·130=20
    2 0 1 1 22·30·51·131=260
    2 0 2 0 22·30·52·130=100
    2 1 0 1 22·30·52·131=1300
    2 1 0 0 22·31·50·130=12
    2 1 0 1 22·31·50·131=156
    2 1 1 0 22·31·51·130=60
    2 1 1 1 22·31·51·131=780
    2 1 2 0 22·31·52·130=300
    2 1 2 1 22·31·52·131=3900

    Ответ: делителями числа 3 900 будут:195, 260, 300, 325, 390, 650, 780, 975, 75, 78, 100, 130, 150, 156, 13,15, 20, 25, 26, 30, 39, 50,52, 60, 65, 1, 2, 3, 4, 5, 6, 10, 12, 1 300, 1 950, 3 900

    Как определить количество делителей конкретного числа

    Чтобы узнать, сколько положительных делителей у конкретного числа a, каноническое разложение которого выглядит как a=p1s1·p2s2··pnsn, нужно найти значение выражения (s1+1) ·(s2+1) ··(sn+1). О количестве наборов переменных t1, t2, , tn мы можем судить по величине записанного выражения.

    Покажем на примере, как это вычисляется. Определим, сколько будет натуральных делителей у числа 3 900, которое мы использовали в предыдущей задаче. Каноническое разложение мы уже записывали: 3 900=22·3·52·13. Значит, s1=2, s2=1, s3=2, s4=1. Теперь подставим значения s1, s2, s3 и s4 в выражение (s1+1) ·(s2+1) ·(s3+1) ·(s4+1) и вычислим его значение. Имеем (2+1)·(1+1)·(2+1)·(1+1)=3·2·3·2=36. Значит, это число имеет всего 36 делителей, являющихся натуральными числами. Пересчитаем то количество, что у нас получилось в предыдущей задаче, и убедимся в правильности решения. Если учесть и отрицательные делители, которых столько же, сколько и положительных, то получится, что у данного числа всего будет 72 делителя.

    Пример 4

    Условие: определите, сколько делителей имеет 84.

    Решение 

    Раскладываем число на множители.

    844221712237

    Записываем каноническое разложение: 84=22·3·7. Определяем, сколько у нас получится положительных делителей: (2+1)·(1+1)·(1+1) =12. Для учета отрицательных нужно умножить это число на 2:2·12=24.

    Ответ: всего у 84 будет 24 делителя – 12 положительных и 12 отрицательных.

    Как вычислить общие делители нескольких чисел

    Зная свойства наибольшего общего делителя, можно утверждать, что количество делителей некоторого набора целых чисел будет совпадать с количеством делителей НОД тех же чисел. Это будет справедливо не только для двух чисел, но и для большего их количества. Следовательно, чтобы вычислить все общие делители нескольких чисел, надо определить их наибольший общий множитель и найти все его делители.

    Разберем пару таких задач.

    Пример 5

    Условие: сколько будет натуральных общих делителей у чисел 140 и 50? Вычислите их все.

    Решение

    Начнем с вычисления НОД (140, 50).

    Для этого нам потребуется алгоритм Евклида:

    140=50·2+40, 50=40·1+10, 40=10·4, значит, НОД (50, 140)=10.

    Далее выясним, сколько положительных делителей есть у десяти. Разложим его на простые множители и получим 20·50=1, 20·51=5, 21·50=2 и  21·51=10. Значит, все натуральные общие делители исходного числа – это 1, 2, 5 и 10, а всего их четыре.

    Ответ: данные числа имеют четыре натуральных делителя, равные 10, 5, 2 и 1.

    Пример 6

    Условие: выясните, сколько общих положительных делителей есть у чисел 585, 315, 90 и 45.

    Решение

    Вычислим их наибольший общий делитель, разложив число на простые множители. Поскольку 90=2·3·3·5, 45=3·3·5, 315=3·3·5·7 и 585=3·3·5·13, то таким делителем будет 5: НОД (90, 45, 315, 585) =3·3·5=32·5.

    Чтобы узнать количество этих чисел, нужно выяснить, сколько положительных делителей имеет НОД.

    Считаем:

    НОД (90, 45, 315, 585) =32·5:(2+1)·(1+1) =6.

    Ответ: у данных чисел шесть общих делителей.

    Если вы заметили ошибку в тексте, пожалуйста, выделите её и нажмите Ctrl+Enter
    Средняя оценка статьи
    4,5 из 5 (12 голосов)