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

Содержание:

Преподаватель математики и информатики. Кафедра бизнес-информатики Российского университета транспорта

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

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

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

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

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

Теорема 1

Допустим, у нас есть выражение, означающее каноническое разложение числа на простые множители, вида $a = p_{1}^{s_{1}} \cdot p_{2}^{s_{2}} \cdot \dots \cdot p_{n}^{s_{n}}$ . Тогда натуральными делителями числа $a$ будут следующие числа: $d = p_{1}^{t_{2}} \cdot p_{2}^{t_{2}} \cdot \dots \cdot p_{n}^{t_{n}}$ , где $t_{1} = 0, 1, \dots, s_{1}, t_{2} = 0, 1, \dots, s_{2}, \dots, t_{n} = 0, 1, \dots, s_{n}$ .

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

Перейдем к доказательству этой теоремы. Зная основное определение делимости, мы можем утверждать, что $a$ можно разделить на $d$ , если есть такое число $q$ , что делает верным равенство $a = d \cdot q$ , т.е. $q = p_{1}^{(s_{1} - t_{1})} \cdot p_{2}^{(s_{2} - t_{2})} \cdot \dots \cdot p_{n}^{(s_{n} - t_{n})}$ .

Любое число, делящее $a$ , будет иметь именно такой вид, поскольку, согласно свойствам делимости, других простых множителей, кроме $p_{1}, p_{2}, \dots, p_{n}$ , оно иметь не может, а их показатели в данном случае не превысят $s_{1}, s_{2}, \dots, s_{n}$ .

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

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

Выполнить каноническое разложение на простые множители и получить выражение вида $a = p_{1}^{s_{1}} \cdot p_{2}^{s_{2}} \cdot \dots \cdot p_{n}^{s_{n}}$ .
Найти все значения $d = p_{1}^{t_{2}} \cdot p_{2}^{t_{2}} \cdot \dots \cdot p_{n}^{t_{n}}$ , где числа $t_{1}, t_{2}, \dots, t_{n}$ будут принимать независимо друг от друга каждое из значений $t_{1} = 0, 1, \dots, s_{1}, t_{2} = 0, 1, \dots, s_{2}, \dots, t_{n} = 0, 1, \dots, s_{n}$ .

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

Пример 1

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

Решение

Разложим восьмерку на простые множители и получим $8 = 2 \cdot 2 \cdot 2$ . Переведем разложение в каноническую форму и получим $8 = 2^{3}$ . Следовательно, $a = 8, p_{1} = 2, s_{1} = 3$ .

Поскольку все делители восьмерки будут значениями $p_{1}^{t_{1}} = 2^{t_{1}}$ , то $t_{1}$ может принять значения нуля, единицы, двойки, тройки. $3$ будет последним значением, ведь $s_{1} = 3$ . Таким образом, если $t_{1} = 0$ , то $2^{t_{1}} = 2^{0} = 1$ , если $1$ , то $2^{t_{1}} = 2^{1} = 2$ , если $2$ , то $2^{t_{1}} = 2^{2} = 4$ , а если $3$ , то $2^{t_{1}} = 2^{3} = 8$ .

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

$t_{1}$	$2^{t_{1}}$
$0$	$2^{0} = 1$
$1$	$2^{1} = 2$
$2$	$2^{2} = 4$
$3$	$2^{3} = 8$

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

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

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

Пример 2

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

Решение

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

$\begin{matrix} 567 \\ 189 \\ 63 21 7 1 \end{matrix} \begin{matrix} 3 3 \\ 3 3 \\ 7 \end{matrix}$

Приведем разложение к каноническому виду и получим $567 = 3^{4} \cdot 7$ . Затем перейдем к вычислению всех натуральных множителей. Для этого будем присваивать $t_{1}$ и $t_{2}$ значения $0, 1, 2, 3, 4$ и $0, 1$ , вычисляя при этом значения $3^{t_{1}} \cdot 7^{t_{2}}$ . Результаты будем вносить в таблицу:

$t_{1}$	$t_{2}$	$3^{t_{1}} \cdot 7^{t_{2}}$
$0$	$0$	$3^{0} \cdot 7^{0} = 1$
$0$	$1$	$3^{0} \cdot 7^{1} = 7$
$1$	$0$	$3^{1} \cdot 7^{0} = 3$
$1$	$1$	$3^{1} \cdot 7^{1} = 21$
$2$	$0$	$3^{2} \cdot 7^{0} = 9$
$2$	$1$	$3^{2} \cdot 7^{1} = 63$
$3$	$0$	$3^{3} \cdot 7^{0} = 27$
$3$	$1$	$3^{3} \cdot 7^{1} = 189$
$4$	$0$	$3^{4} \cdot 7^{0} = 81$
$4$	$1$	$3^{4} \cdot 7^{1} = 567$

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

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

Пример 3

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

Решение

Проводим разложение данного числа на простые множители. В каноническом виде оно будет выглядеть как $3 900 = 22 \cdot 3 \cdot 52 \cdot 13$ . Теперь приступаем к нахождению положительных делителей, подставляя в выражение $2^{t_{1}} \cdot 3^{t_{2}} \cdot 5^{t_{3}} \cdot 13^{t_{4}}$ значения $t_{1}$ , равные $0, 1$ и $2$ , $t_{2} = 0$ , $1$ , $t_{3} = 0$ , $1$ , $2$ , $t_{4} = 0$ , $1$ . Результаты представляем в табличном виде:

$t_{1}$	$t_{2}$	$t_{3}$	$t_{4}$	$2^{t_{1}} \cdot 3^{t_{2}} \cdot 5^{t_{3}} \cdot 13^{t_{4}}$
$0$	$0$	$0$	$0$	$2^{0} \cdot 3^{0} \cdot 5^{0} \cdot 13^{0} = 1$
$0$	$0$	$0$	$1$	$2^{0} \cdot 3^{0} \cdot 5^{0} \cdot 13^{1} = 13$
$0$	$0$	$1$	$0$	$2^{0} \cdot 3^{0} \cdot 5^{1} \cdot 13^{0} = 5$
$0$	$0$	$1$	$1$	$2^{0} \cdot 3^{0} \cdot 5^{1} \cdot 13^{1} = 65$
$0$	$0$	$2$	$0$	$2^{0} \cdot 3^{0} \cdot 5^{2} \cdot 13^{0} = 25$
$0$	$0$	$2$	$1$	$2^{0} \cdot 3^{0} \cdot 5^{2} \cdot 13^{1} = 325$
$0$	$1$	$0$	$0$	$2^{0} \cdot 3^{1} \cdot 5^{0} \cdot 13^{0} = 3$
$0$	$1$	$0$	$1$	$2^{0} \cdot 3^{1} \cdot 5^{0} \cdot 13^{1} = 39$
$0$	$1$	$1$	$0$	$2^{0} \cdot 3^{1} \cdot 5^{1} \cdot 13^{0} = 15$
$0$	$1$	$1$	$1$	$2^{0} \cdot 3^{1} \cdot 5^{1} \cdot 13^{1} = 195$
$0$	$1$	$2$	$0$	$2^{0} \cdot 3^{1} \cdot 5^{2} \cdot 13^{0} = 75$
$0$	$1$	$2$	$1$	$2^{0} \cdot 3^{1} \cdot 5^{2} \cdot 13^{1} = 975$

$t_{1}$	$t_{2}$	$t_{3}$	$t_{4}$	$2^{t_{1}} \cdot 3^{t_{2}} \cdot 5^{t_{3}} \cdot 13^{t_{4}}$
$1$	$0$	$0$	$0$	$2^{1} \cdot 3^{0} \cdot 5^{0} \cdot 13^{0} = 2$
$1$	$0$	$0$	$1$	$2^{1} \cdot 3^{0} \cdot 5^{0} \cdot 13^{1} = 26$
$1$	$0$	$1$	$0$	$2^{1} \cdot 3^{0} \cdot 5^{1} \cdot 13^{0} = 10$
$1$	$0$	$1$	$1$	$2^{1} \cdot 3^{0} \cdot 5^{1} \cdot 13^{1} = 130$
$1$	$0$	$2$	$0$	$2^{1} \cdot 3^{0} \cdot 5^{2} \cdot 13^{0} = 50$
$1$	$0$	$2$	$1$	$2^{1} \cdot 3^{0} \cdot 5^{2} \cdot 13^{1} = 650$
$1$	$1$	$0$	$0$	$2^{1} \cdot 3^{1} \cdot 5^{0} \cdot 13^{0} = 6$
$1$	$1$	$0$	$1$	$2^{1} \cdot 3^{1} \cdot 5^{0} \cdot 13^{1} = 78$
$1$	$1$	$1$	$0$	$2^{1} \cdot 3^{1} \cdot 5^{1} \cdot 13^{0} = 30$
$1$	$1$	$1$	$1$	$2^{1} \cdot 3^{1} \cdot 5^{1} \cdot 13^{1} = 390$
$1$	$1$	$2$	$0$	$2^{1} \cdot 3^{1} \cdot 5^{2} \cdot 13^{0} = 150$
$1$	$1$	$2$	$1$	$2^{1} \cdot 3^{1} \cdot 5^{2} \cdot 13^{1} = 1950$

$t_{1}$	$t_{2}$	$t_{3}$	$t_{4}$	$2^{t_{1}} \cdot 3^{t_{2}} \cdot 5^{t_{3}} \cdot 13^{t_{4}}$
$2$	$0$	$0$	$0$	$2^{2} \cdot 3^{0} \cdot 5^{0} \cdot 13^{0} = 4$
$2$	$0$	$0$	$1$	$2^{2} \cdot 3^{0} \cdot 5^{0} \cdot 13^{1} = 52$
$2$	$0$	$1$	$0$	$2^{2} \cdot 3^{0} \cdot 5^{1} \cdot 13^{0} = 20$
$2$	$0$	$1$	$1$	$2^{2} \cdot 3^{0} \cdot 5^{1} \cdot 13^{1} = 260$
$2$	$0$	$2$	$0$	$2^{2} \cdot 3^{0} \cdot 5^{2} \cdot 13^{0} = 100$
$2$	$1$	$0$	$1$	$2^{2} \cdot 3^{0} \cdot 5^{2} \cdot 13^{1} = 1300$
$2$	$1$	$0$	$0$	$2^{2} \cdot 3^{1} \cdot 5^{0} \cdot 13^{0} = 12$
$2$	$1$	$0$	$1$	$2^{2} \cdot 3^{1} \cdot 5^{0} \cdot 13^{1} = 156$
$2$	$1$	$1$	$0$	$2^{2} \cdot 3^{1} \cdot 5^{1} \cdot 13^{0} = 60$
$2$	$1$	$1$	$1$	$2^{2} \cdot 3^{1} \cdot 5^{1} \cdot 13^{1} = 780$
$2$	$1$	$2$	$0$	$2^{2} \cdot 3^{1} \cdot 5^{2} \cdot 13^{0} = 300$
$2$	$1$	$2$	$1$	$2^{2} \cdot 3^{1} \cdot 5^{2} \cdot 13^{1} = 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 = p_{1}^{s_{1}} \cdot p_{2}^{s_{2}} \cdot \dots \cdot p_{n}^{s_{n}}$ , нужно найти значение выражения $(s_{1} + 1) \cdot (s_{2} + 1) \cdot \dots \cdot (s_{n} + 1)$ . О количестве наборов переменных $t_{1,} t_{2}, \dots, t_{n}$ мы можем судить по величине записанного выражения.

Покажем на примере, как это вычисляется. Определим, сколько будет натуральных делителей у числа $3 900$ , которое мы использовали в предыдущей задаче. Каноническое разложение мы уже записывали: $3 900 = 2^{2} \cdot 3 \cdot 5^{2} \cdot 13$ . Значит, $s_{1} = 2, s_{2} = 1, s_{3} = 2, s_{4} = 1$ . Теперь подставим значения $s_{1}, s_{2}, s_{3}$ и $s_{4}$ в выражение $(s_{1} + 1) \cdot (s_{2} + 1) \cdot (s_{3} + 1) \cdot (s_{4} + 1)$ и вычислим его значение. Имеем $(2 + 1) \cdot (1 + 1) \cdot (2 + 1) \cdot (1 + 1) = 3 \cdot 2 \cdot 3 \cdot 2 = 36$ . Значит, это число имеет всего $36$ делителей, являющихся натуральными числами. Пересчитаем то количество, что у нас получилось в предыдущей задаче, и убедимся в правильности решения. Если учесть и отрицательные делители, которых столько же, сколько и положительных, то получится, что у данного числа всего будет $72$ делителя.

Пример 4

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

Решение

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

$\begin{matrix} 84 \\ 42 \\ 21 7 1 \end{matrix} \begin{matrix} 2 \\ 2 \\ 3 7 \end{matrix}$

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

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

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

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

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

Пример 5

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

Решение

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

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

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

Далее выясним, сколько положительных делителей есть у десяти. Разложим его на простые множители и получим $2^{0} \cdot 5^{0} = 1, 2^{0} \cdot 5^{1} = 5, 2^{1} \cdot 5^{0} = 2$ и $2^{1} \cdot 5^{1} = 1^{0}$ . Значит, все натуральные общие делители исходного числа – это $1, 2, 5$ и $10$ , а всего их четыре.

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

Пример 6

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

Решение

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

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

Считаем:

НОД $(90, 45, 315, 585) = 3^{2} \cdot 5 : (2 + 1) \cdot (1 + 1) = 6$ .

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

Курсовая работа по математике

от 5 дней/ от 2160 р.

Реферат по математике

от 1 дня/ от 840 р.

Решение задач по математике

от 1 дня/ от 150 р.