Нахождение всех делителей числа, число делителей числа.
Материал этой статьи про нахождение всех делителей числа. Сначала доказана теорема, которая задает вид всех общих делителей данного числа, после чего рассмотрены примеры нахождения всех делителей. Дальше показано, как вычисляется число делителей числа. В заключение подробно разобраны примеры нахождения всех общих делителей нескольких чисел и их количества.
Все делители числа, их нахождение
Дальнейшее изложение подразумевает хорошее владение информацией статьи делители и кратные числа. Мы будем говорить лишь о поиске всех делителей целых положительных чисел (натуральных чисел). Этого вполне достаточно, так как одно из свойств делимости утверждает, что множество делителей целого отрицательного числа −a совпадает со множеством делителей противоположного числа a (которое будет положительным). Напомним также, что число 0 имеет бесконечно много делителей, и нахождение всех делителей нуля не представляет интереса.
положительными делителями простого числа a являются лишь единица и само это число. Следовательно, любое простое число a имеет четыре делителя, среди которых два положительных и два отрицательных: 1, −1, a и −a. Например, число 11 – простое, оно имеет всего четыре делителя 1, −1, 11 и −11. Еще пример. Число 367 тоже простое, все его делители – это числа 1, −1, 367 и −367.
Интереснее проходит поиск всех делителей составных чисел. Теоретическая основа этого процесса заключается в следующей теореме.
Теорема.
Пусть известно каноническое разложение числа на простые множители, которое имеет вид a=p1s1·p2s2·…·pnsn, тогда все положительные (натуральные) делители числа a – это числа вида d=p1t1·p2t2·…·pntn, где t1=0, 1, …, s1, t2=0, 1, …, s2, …, tn=0, 1, …, sn.
Доказательство.
С одной стороны, по определению делимости число a делится на любое такое число d, так как существует такое целое число q=p1(s1−t1)·p2(s2−t2)·…·pn(sn−tn), что a=d·q.
С другой стороны, всякое число d, которое делит a, имеет указанный вид, так как в силу свойств делимости оно не может иметь других простых множителей, кроме p1, p2, …, pn, а показатели этих множителей не могут превышать s1, s2, …, sn соответственно.
Из рассмотренной теоремы следует алгоритм нахождения всех положительных делителей данного числа. Чтобы найти все делители числа a нужно:
- получить его каноническое разложение на простые множители вида a=p1s1·p2s2·…·pnsn;
- вычислить все значения выражения p1t1·p2t2·…·pntn, в которых числа t1, t2, …, tn принимают независимо друг от друга каждое из значений t1=0, 1, …, s1, t2=0, 1, …, s2, …, tn=0, 1, …, sn.
Обычно наибольшую трудность представляет именно процесс перебора всех возможных комбинаций значений чисел t1, t2, …, tn. Сейчас мы последовательно рассмотрим решения нескольких примеров нахождения всех делителей чисел, откуда будут понятны все тонкости этого процесса.
Пример.
Найдите все делители числа 8.
Решение.
Получить разложение на простые множители числа 8 не составляет труда: 8=2·2·2. В канонической форме это разложение выглядит так: 8=23. То есть, в нашем случае a=8, p1=2, s1=3.
Тогда все делители числа 8 представляют собой значения выражения p1t1=2t1, в котором t1 принимает значения 0, 1, 2 и 3 (3 – последнее значение, так как s1=3). Итак, при t1=0 имеем 2t1=20=1, при t1=1 имеем 2t1=21=2, при t1=2 имеем 2t1=22=4, наконец, при t1=3 имеем 2t1=23=8.
Весь процесс нахождения делителей удобно проводить, заполняя таблицу следующего вида:
Таким образом, 1, 2, 4 и 8 – это все положительные делители числа 8. Отрицательными делителями числа 8 являются −1, −2, −4 и −8.
Ответ:
±1, ±2, ±4, ±8 – все делители числа 8.
Рассмотрим более сложный пример нахождения всех делителей числа a, в нем разложение числа уже будет содержать два простых множителя.
Пример.
Перечислите все натуральные делители числа 567.
Решение.
Сначала разложим на простые множители число 567:
Каноническое разложение числа 567 на простые множители имеет вид 567=34·7. Теперь для нахождения всех натуральных делителей числа 567 заставим t1 и t2 пробегать независимо друг от друга значения 0, 1, 2, 3, 4 и 0, 1 соответственно, при этом будем вычислять значения выражения 3t1·7t2. Все эти действия удобно поводить, заполняя следующую таблицу:
Ответ:
1, 3, 7, 9, 21, 27, 63, 81, 189 и 567 – все натуральные делители числа 567.
Еще немного усложним пример.
Пример.
Найдите все положительные делители числа 3 900.
Решение.
Разложив число 3 900 на простые множители, получим его каноническое разложение 3 900=22·3·52·13. Все положительные делители найдем, вычисляя значения выражения 2t1·3t2·5t3·13t4 при t1=0, 1, 2, t2=0, 1, t3=0, 1, 2, t4=0, 1.
Ответ:
1, 2, 3, 4, 5, 6, 10, 12, 13, 15, 20, 25, 26, 30, 39, 50, 52, 60, 65, 75, 78, 100, 130, 150, 156, 195, 260, 300, 325, 390, 650, 780, 975, 1 300, 1 950, 3 900 - все положительные делители числа 117 000.
Число делителей числа
Число положительных делителей данного числа a, каноническое разложение которого имеет вид a=p1s1·p2s2·…·pnsn, равно значению выражения (s1+1)·(s2+1)·…·(sn+1). Величина записанного выражения дает количество всех возможных наборов переменных t1, t2, …, tn, где t1=0, 1, …, s1, t2=0, 1, …, s2, …, tn=0, 1, …, sn.
Приведем пример. Вычислим число натуральных делителей числа 3 900 из последнего примера, рассмотренного в предыдущем пункте. Мы выяснили, что 3 900=22·3·52·13, тогда s1=2, s2=1, s3=2, s4=1. Осталось вычислить значение выражения (s1+1)·(s2+1)·(s3+1)·(s4+1) при данных значениях s1, s2, s3 и s4, которое и даст нам искомое число натуральных делителей. Получаем (2+1)·(1+1)·(2+1)·(1+1)=3·2·3·2=36. Следовательно, число 3 900 имеет 36 натуральных делителей. Если мы пересчитаем все делители числа 3 900, полученные в предыдущем примере, то убедимся, что их количество действительно равно 36. Число всех делителей (и положительных и отрицательных) числа 3 900 равно 36·2=72, так как число 3 900 имеет 36 положительных делителей, и, следовательно, 36 отрицательных, противоположных каждому из положительных делителей.
Пример.
Найдите число делителей числа 84.
Решение.
Разложим 84 на простые множители:
Таким образом, каноническое разложение имеет вид 84=22·3·7. Тогда число положительных делителей равно (2+1)·(1+1)·(1+1)=12. Следовательно, число всех делителей равно 2·12=24.
Ответ:
число 84 имеет 24 делителя.
Нахождение всех общих делителей чисел и их количества
Из свойств наибольшего общего делителя следует, что множество делителей данных целых чисел совпадает со множеством делителей НОД этих чисел. Это утверждение относится как к двум числам, так и к трем, и к большему их количеству. Таким образом, чтобы найти все общие делители данных чисел, нужно определить НОД этих чисел и найти все его делители.
Рассмотрим решения примеров, в которых находятся все общие делители некоторых чисел.
Пример.
Найдите все натуральные общие делители чисел 50 и 140, а также их количество.
Решение.
Сначала нам нужно найти наибольший общий делитель чисел 50 и 140, для этого воспользуемся алгоритмом Евклида: 140=50·2+40, 50=40·1+10, 40=10·4, то есть, НОД(50, 140)=10.
Теперь определим все положительные делители числа 10. Его разложение на простые множители имеет вид 10=2·5. Тогда 20·50=1, 20·51=5, 21·50=2 и 21·51=10 – все делители числа 10. Следовательно, числа 1, 2, 5 и 10 – это все положительные общие делители чисел 50 и 140, количество этих делителей равно 4.
Ответ:
1, 2, 5 и 10 – это все натуральные делители чисел 50 и 140, их количество равно 4.
Пример.
Определите число всех положительных общих делителей четырех чисел 90, 45, 315 и 585.
Решение.
Сначала найдем НОД с помощью разложения чисел на простые множители. Так как 90=2·3·3·5, 45=3·3·5, 315=3·3·5·7 и 585=3·3·5·13, то НОД(90, 45, 315, 585)=3·3·5=32·5. Количество всех искомых положительных общих делителей исходных четырех чисел равно количеству всех положительных делителей НОД этих чисел. Вычислим количество делителей НОД(90, 45, 315, 585)=32·5, оно равно (2+1)·(1+1)=6.
Ответ:
6.
Список литературы.
- Виленкин Н.Я. и др. Математика. 6 класс: учебник для общеобразовательных учреждений.
- Виноградов И.М. Основы теории чисел.
- Михелович Ш.Х. Теория чисел.
- Куликов Л.Я. и др. Сборник задач по алгебре и теории чисел: Учебное пособие для студентов физ.-мат. специальностей педагогических институтов.