Поиск чисел с заданным количеством делителей.

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

Навигация по странице.

Все делители числа, их нахождение

Дальнейшее изложение подразумевает хорошее владение информацией статьи делители и кратные числа . Мы будем говорить лишь о поиске всех делителей (). Этого вполне достаточно, так как одно из свойств делимости утверждает, что множество делителей целого отрицательного числа −a совпадает со множеством делителей a (которое будет положительным). Напомним также, что число 0 имеет бесконечно много делителей, и нахождение всех делителей нуля не представляет интереса.

положительными делителями простого числа a являются лишь единица и само это число. Следовательно, любое простое число a имеет четыре делителя, среди которых два положительных и два отрицательных: 1 , −1 , a и −a . Например, число 11 – простое, оно имеет всего четыре делителя 1 , −1 , 11 и −11 . Еще пример. Число 367 тоже простое, все его делители – это числа 1 , −1 , 367 и −367 .

Интереснее проходит поиск всех делителей составных чисел. Теоретическая основа этого процесса заключается в следующей теореме.

Теорема.

Пусть известно каноническое разложение числа на простые множители , которое имеет вид , тогда все положительные (натуральные) делители числа a – это числа вида d=p 1 t 1 ·p 2 t 2 ·…·p n t n , где t 1 =0, 1, …, s 1 , t 2 =0, 1, …, s 2 , …, t n =0, 1, …, s n .

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

С одной стороны, по определению делимости число a делится на любое такое число d , так как существует такое целое число q=p 1 (s 1 −t 1) ·p 2 (s 2 −t 2) ·…·p n (s n −t n) , что a=d·q .

С другой стороны, всякое число d , которое делит a , имеет указанный вид, так как в силу свойств делимости оно не может иметь других простых множителей, кроме p 1 , p 2 , …, p n , а показатели этих множителей не могут превышать s 1 , s 2 , …, s n соответственно.

Из рассмотренной теоремы следует алгоритм нахождения всех положительных делителей данного числа . Чтобы найти все делители числа a нужно:

• получить его каноническое разложение на простые множители вида a=p 1 s 1 ·p 2 s 2 ·…·p n s n ;
• вычислить все значения выражения p 1 t 1 ·p 2 t 2 ·…·p n t n , в которых числа t 1 , t 2 , …, t n принимают независимо друг от друга каждое из значений t 1 =0, 1, …, s 1 , t 2 =0, 1, …, s 2 , …, t n =0, 1, …, s n .

Обычно наибольшую трудность представляет именно процесс перебора всех возможных комбинаций значений чисел t 1 , t 2 , …, t n . Сейчас мы последовательно рассмотрим решения нескольких примеров нахождения всех делителей чисел, откуда будут понятны все тонкости этого процесса.

Пример.

Найдите все делители числа 8 .

Решение.

Получить разложение на простые множители числа 8 не составляет труда: 8=2·2·2 . В канонической форме это разложение выглядит так: 8=2 3 . То есть, в нашем случае a=8 , p 1 =2 , s 1 =3 .

Тогда все делители числа 8 представляют собой значения выражения p 1 t 1 =2 t 1 , в котором t 1 принимает значения 0 , 1 , 2 и 3 (3 – последнее значение, так как s 1 =3 ). Итак, при t 1 =0 имеем 2 t 1 =2 0 =1 , при t 1 =1 имеем 2 t 1 =2 1 =2 , при t 1 =2 имеем 2 t 1 =2 2 =4 , наконец, при t 1 =3 имеем 2 t 1 =2 3 =8 .

Весь процесс нахождения делителей удобно проводить, заполняя таблицу следующего вида:

Таким образом, 1 , 2 , 4 и 8 – это все положительные делители числа 8 . Отрицательными делителями числа 8 являются −1 , −2 , −4 и −8 .

Ответ:

±1 , ±2 , ±4 , ±8 – все делители числа 8 .

Рассмотрим более сложный пример нахождения всех делителей числа a , в нем разложение числа уже будет содержать два простых множителя.

Пример.

Перечислите все натуральные делители числа 567 .

Решение.

Сначала разложим на простые множители число 567 :

Каноническое разложение числа 567 на простые множители имеет вид 567=3 4 ·7 . Теперь для нахождения всех натуральных делителей числа 567 заставим t 1 и t 2 пробегать независимо друг от друга значения 0 , 1 , 2 , 3 , 4 и 0 , 1 соответственно, при этом будем вычислять значения выражения 3 t 1 ·7 t 2 . Все эти действия удобно поводить, заполняя следующую таблицу:

Ответ:

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

Еще немного усложним пример.

Пример.

Найдите все положительные делители числа 3 900 .

Решение.

Разложив число 3 900 на простые множители, получим его каноническое разложение 3 900=2 2 ·3·5 2 ·13 . Все положительные делители найдем, вычисляя значения выражения 2 t 1 ·3 t 2 ·5 t 3 ·13 t 4 при t 1 =0, 1, 2 , t 2 =0, 1 , t 3 =0, 1, 2 , t 4 =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=p 1 s 1 ·p 2 s 2 ·…·p n s n , равно значению выражения (s 1 +1)·(s 2 +1)·…·(s n +1) . Величина записанного выражения дает количество всех возможных наборов переменных t 1 , t 2 , …, t n , где t 1 =0, 1, …, s 1 , t 2 =0, 1, …, s 2 , …, t n =0, 1, …, s n .

Приведем пример. Вычислим число натуральных делителей числа 3 900 из последнего примера, рассмотренного в предыдущем пункте. Мы выяснили, что 3 900=2 2 ·3·5 2 ·13 , тогда s 1 =2 , s 2 =1 , s 3 =2 , s 4 =1 . Осталось вычислить значение выражения (s 1 +1)·(s 2 +1)·(s 3 +1)·(s 4 +1) при данных значениях s 1 , s 2 , s 3 и s 4 , которое и даст нам искомое число натуральных делителей. Получаем (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=2 2 ·3·7 . Тогда число положительных делителей равно (2+1)·(1+1)·(1+1)=12 . Следовательно, число всех делителей равно 2·12=24 .

Ответ:

Число 84 имеет 24 делителя.

Инструкция

Чаще всего, нужно разложить число на простые множители. Это числа, которые делят исходное число без остатка, и при этом сами могут делиться без остатка только на само себя и единицу (к таким числам 2, 3, 5, 7, 11, 13, 17 и т.д.). Причем, закономерности в ряду не найдено. Возьмите их из специальной таблицы или найдите при помощи алгоритма, который называется «решето Эратосфена».

Числа, имеющие более двух делителей, называются составными. Какие же числа могут быть составными?
Так как числа делятся на 2 нацело, то все четные числа , кроме числа 2, будут составными. Действительно, при делении 2:2 двойка делится саму на себя, то есть имеет только два делителя (1 и 2) и является простым числом.

Посмотрим, есть ли у четного числа еще каки-либо делители . Разделим его сначала на 2. Из коммутативности операции умножения очевидно, что получившееся частное также будет делителем числа . Затем, если получившееся частное будет целым, разделим опять на 2 уже это частное. Тогда получившееся в результате новое частное y = (x:2):2 = x:4 тоже будет делителем исходного числа . Аналогично, и 4 будет делителем исходного числа .

Продолжая эту цепочку, обобщим правило: последовательно делим сначала а потом получившееся частные на 2 до тех пор, пока -либо частное не станет равно нечетному числу. При этом все получившиеся частные будут делителями этого числа . Кроме этого делителями этого числа будут и числа 2^k где k = 1...n, где n - число шагов этой цепочки.Пример: 24:2 = 12, 12:2 = 6, 6:2 = 3 - нечетное число. Следовательно, 12, 6 и 3 - делители числа 24. В этой цепочке 3 шага, следовательно, делителями числа 24 будут также числа 2^1 = 2 (уже известно из четности числа 24), 2^2 = 4 и 2^3 = 8. Таким образом, числа 1, 2, 3, 4, 6, 8, 12 и 24 будут делителями числа 24.

Однако не для всех четных чисел эта может дать все делители числа . Рассмотрим, например, число 42. 42:2 = 21. Однако, как известно, числа 3, 6 и 7 также будут делителями числа 42.
Существуют делимости на числа . Рассмотрим важнейшие из них:
Признак делимости на 3: когда сумма цифр числа делится на 3 без остатка.
Признак делимости на 5: когда последняя цифра числа 5 или 0.
Признак делимости на 7: когда результат вычитания удвоенной последней цифры из этого числа без последней цифры делится на 7.
Признак делимости на 9: когда сумма цифр числа делится на 9 без остатка.
Признак делимости на 11: когда сумма цифр, занимающих нечётные места, либо равна сумме цифр, занимающих чётные места, либо от неё на число, делящееся на 11.
Существуют также признаки делимости на 13, 17, 19, 23 и другие числа .

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

Источники:

• Признаки делимости

Из четырех основных математических действий наиболее ресурсоемкой операцией является деление. Его можно осуществлять вручную (столбиком), на калькуляторах различных конструкций, а также при помощи логарифмической линейки.

Инструкция

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

Если числа не делятся друг на друга, возможны две ситуации. В первой из них одна цифра или сочетание из нескольких цифр будет повторяться бесконечно. Тогда продолжать вычисление бессмысленно - достаточно взять эту цифру или цепочку из цифр в период. Во второй ситуации какой-либо закономерности в частного не удастся. Тогда прекратите деление, добившись желаемой точности результата, а последний округлите.

Для деления одного числа на другое с использованием калькулятора с арифметической (как простейшего, так и инженерного) нажмите кнопку сброса, введите делимое, нажмите кнопку деления, введите делитель, а затем нажмите кнопку со знаком равенства. На калькуляторе с формульной записью производите деление аналогичным образом, с учетом того, что клавиша со знаком равенства может носить , например, Enter или Exe. Современные приборы этого типа являются двухстрочными: набирается в верхней строке, а результат отображается в нижней более крупными цифрами. Используя клавишу Ans, этот результат можно использовать в следующем вычислении. Во всех случаях результат автоматически округляется в пределах разрядной сетки калькулятора.

На калькуляторе с обратной польской записью вначале нажмите кнопку сброса, затем введите делимое и нажмите клавишу Enter (вместо этой надписи на ней может быть стрелка, направленная вверх). Число окажется в ячейке стека. Теперь введите делитель и нажмите клавишу со знаком деления. Произойдет деление числа из стека на число, которое отображалось до этого на индикаторе.

Логарифмическую линейку используйте в тех случаях, когда точность требуется небольшая. Уберите из обоих чисел , а затем от каждого из них возьмите по два старших разряда. На шкале A найдите делитель, а затем совместите его с делимым на шкале B. Затем найдите на последней единицу - прямо над ней на шкале A будет расположено частное . Местоположение запятой в нем определите тем же способом, что и столбиком.

Источники:

• Порядок деления столбиком
• частные числа это

Школьники часто встречают среди заданий по математике такую формулировку: "найдите наименьшее общее кратное чисел". Этому обязательно нужно научиться делать, чтобы выполнять различные действия с дробями с неодинаковыми знаменателями.

Нахождение наименьшего общего кратного: основные понятия

Чтобы понять, как вычислять НОК, следует определиться в первую очередь со значением термина "кратное".

Кратным числу А называют такое натуральное число, которое без остатка делится на А. Так, числами кратными 5 можно считать 15, 20, 25 и так далее.

Делителей конкретного числа может быть ограниченное количество, а вот кратных бесконечное множество.

Общее кратное натуральных чисел - число, которое делится на них без остатка.

Наименьшее общее кратное (НОК) чисел (двух, трех или больше) - это самое маленькое натурально число, которое делится на все эти числа нацело.

Чтобы найти НОК, можно использовать несколько способов.

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

Например, кратные числа 4 можно записать так:

К (4) = {8,12, 16, 20, 24, ...}

К (6) = {12, 18, 24, ...}

Так, можно увидеть, что наименьшим общим кратным чисел 4 и 6 является число 24. Эту запись выполняют следующим образом:

НОК (4, 6) = 24

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

Вам понадобится

• Для этого вам понадобится листок бумаги или калькулятор.

Инструкция

Разложите каждое сложное число на произведение простых или множителей. Например, 60 и 80, где 60 - равно 2*2*3*5, а 80 - 2*2*2*2*5, проще это можно записать с помощью . В данном случае будет выглядеть как два во второй , умноженное на пять и три, а второй - произведение двух в четвертой и пяти.

Теперь выпишите общие для обоих чисел . В нашем варианте - это два и пять. Однако в других случаях это число может быть одно, два или три цифры и даже . Далее нужно поработать . Выберите наименьшую у каждого из множителей. В примере это два во второй степени и пять в первой.

В завершении просто нужно перемножить получившиеся цифры. В нашем случае все предельно просто: два в , умноженное на пять, равно 20. Таким образом, число 20 можно назвать наибольшим общим делителем для 60 и 80.

Видео по теме

Обратите внимание

Помните, что простым множителем является число, которое имеет только 2 делителя: единица и само это число.

Полезный совет

Кроме данного метода можно также пользоваться алгоритмом Евклида. Полное его описание, представленное в геометрической форме, можно найти в книге Евклида "Начала".

Связанная статья

Нередко можно встретить такие уравнения, в которых неизвестен . Например 350: Х = 50, где 350 - делимое, Х - делитель, а 50 - частное. Для решения этих примеров необходимо произвести определенный набор действий с теми числами, которые известны.

Вам понадобится

• - карандаш или ручка;
• - лист бумаги или тетрадь.

Инструкция

Составьте простое уравнение, где неизвестное, т.е. Х - это количество детей, 5 - это число конфет, полученных каждым ребенком, а 30 - это количество сладостей, которое было куплено. Таким образом вы должны получить : 30: Х = 5. В этом математическом выражении 30 называется делимым, Х - делителем, а получившееся частное равно 5.

Теперь приступайте к решению. Известно: чтобы найти делитель, нужно делимое разделить на частное. Получается:Х = 30: 5;30: 5 = 6;Х = 6.

Сделайте проверку, подставив в уравнение получившееся число. Итак, 30: Х = 5, вы нашли неизвестный делитель, т.е. Х = 6, таким образом: 30: 6 = 5. Выражение верно, а из этого следует, что уравнение решено . Разумеется, при решении примеров, в которых фигурируют простые числа, проверку выполнять необязательно. Но когда уравнения из , трехзначных, четырехзначных и т.д. чисел, обязательно проверяйте себя. Ведь это не отнимает много времени, но дает абсолютную уверенность в полученном результате.

Обратите внимание

Как решить задачу, если нет идеи? Нет универсального способа, позволяющего решать любые задачи. Но есть методика, дающая возможность продвинуться и в трудных ситуациях, тем более, в лёгких заданиях, которые предлагаются в тестах ЦТ. Эту методику описывает великий мастер эвристики Д. Пойа. Абутуриенту полезно с ней.
А ниже приводятся эвристические указания к решению задач первой темы курса для абитуриента. Разумеется, ими не следует пользоваться, если не сделано попыток решения более трудных для вас заданий.
Задачи.
№2. Простые числа имеют ровно два делителя. А какие числа имеют ровно 3 делителя?
Начните с числового эксперимента. Подметьте особенность чисел, имеющих три делителя. Обобщите и докажите.
№6. Найдите наименьшее натуральное число, большее десяти, которое при делении на 24, 45 и 56 давало бы в остатке 1.
Если х даёт при делении на n остаток 1, то число х-1 делится на n?
№7. Лист картона со сторонами 54 см и 36 см надо разрезать без отходов на равные квадраты. Найдите площадь наибольшего квадрата, который можно получить из этого листа.
Если сделать рисунок так, чтобы квадраты покрыли прямоугольник соответствующим образом, то идея о длине стороны наибольшего квадрата должна появиться. С каким математическим понятием это связано?
№10. Найдите два натуральных числа, зная, что их сумма равна 85, а наименьшее общее кратное равно 102.
Если НОК искомых чисел равен 102, то они должны быть делителями числа 102. Но их тогда можно все выписать...
№13. Трехзначное число оканчивается цифрой 3. Если ее перенести в начало записи числа, то полученное число будет на 27 больше первоначального. Найти это число.
Записать искомое число в стандартном виде: 100a 10b c, c=3.
№20. Задумано целое положительное число. К его записи приписали справа цифру 7 и из полученного числа вычли квадрат задуманного. Разность уменьшили на 75% и ещё вычли задуманное число. В окончательном результате получили 4. Какое число задумано?
Если задуманное число назвать n, то какое число получим, если к его поразрядной записи приписать 7? Можете поэксперементировать?
№30. Решить в натуральных числах уравнение: а) (х-2у)(2х-1+у)=11; в) (х+3у-2) 2 +(у-4) 2 =29; д) 55х 2 -12ху-91у 2 =59; ж) 4x 3 -2y 3 -z 3 =0.
а) Произведение каких натуральных чисел равно 11?.. в) Сумма квадратов каких целых чисел даёт 29?.. д) Идея из пункта а). ж) Здесь интересно, это для олимпиадников. Во-первых, одно решение (одна тройка чисел x, y, z) сразу видна. Будем искать ненулевые решения. Заметим, что z 3 - чётное число (если перенести другие слагаемые вправо). Следовательно, z - чётно. Тогда его можно записать как 2n, где n - целое. Подставим это вместо z в уравнение... . Порассуждайте в таком духе и дальше.
№32. Найти все тройки целых чисел, которые удовлетворяют неравенству

Ясно, что преобразование неравенства ничего хорошего не даст. Тогда надо, как обычно, наблюдать его структуру, искать какие-то особенности и зависимости. Случаен ли подбор коэффициентов в подкоренных выражениях? Попробуем сложить подкоренные выражения... . Результат будет интересен. Тогда, учитывая, что эти выражения - натуральные числа, сделаем вывод о том, что... . Дальше будет дело техники.
№33. При каких целых значениях n дроби: б) (2n+7)/(n+1) принимает целое значение?
.

Можно видеть теперь, при каком условии значение выражения станет целым числом.
№34. У натурального числа ровно 6 натуральных делителей. Сумма этих делителей равна 104. Найдите это число.
Как устроено число n, у которого 6 делителей? Если разложить его на простые множители, то сколько их? Когда разложение выглядит так n=pq, p ≠ q, то у него 4 делителя. А если n=pqr при различных сомножителях, то делителями являются 1, p, q, pq, pr, qr, pqr. То есть их больше шести... . Найдите самостоятельно нужное разложение. А потом используйте условие и работайте с полученным равенством.

Любое составное число с может быть записано в виде произведения с = ab, причем ни один из делителей не равен 1 и каждый из них меньше, чем с ; например,

72 = 8 9, 150 = 10 15.

При разложении числа с на множители один из них, и даже оба (а и b ) могут оказаться составными. Если а - составное, то разложение на множители можно продолжить:

а = a 1 a 2 , с = a 1 a 2 b .

Примерами этого могут служить рассмотренные выше числа

72 = 2 4 9, 150 = 2 5 15.

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

Таким образом мы показали, что

Каждое целое число, большее 1, является простым числом или произведением простых чисел.

Последовательное разложение числа на множители может быть выполнено многими способами. При этом можно использовать таблицу делителей. Сначала найдем наименьшее простое число р 1 , делящее число с , так что с = р 1 с 1 . Если с 1 - составное число, то по таблице делителей найдем наименьшее простое число р 2 , делящее с 1 , так что

c 1 = р 2 с 2 , c = p 1 p 2 с 2 .

Затем найдем наименьший простой делитель числа с 2 и т. д.

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

Этот результат мы можем кратко выразить следующим образом:

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

Возможно, что вы так часто слышали об этой так называемой «основной теореме арифметики» и пользовались ею, что она представляется вам очевидной, но это совсем не так. Эта теорема может быть доказана несколькими различными способами, однако ни один из них не тривиален. Здесь мы приведём доказательство, используя способ «от противного», который часто называют его латинским названием reductio ad absurdum (приведением к абсурду). Этот способ заключается в следующем: предположив ложность теоремы, которую нужно доказать, показывают, что это предположение приводит к противоречию.

Доказательство . Предположим, что наша теорема о единственности разложения на множители неверна. Тогда должны существовать числа, имеющие по крайней мере два различных разложения на простые множители. Выберем из них наименьшее и обозначим его через с 0 . Для небольших чисел, скажем, меньших 10, истинность теоремы можно установить прямой проверкой. Число с 0 имеет наименьший простой множитель р 0 , и мы можем записать:

c 0 = p 0 d 0 .

Так как d 0 < c 0 , то число d 0 единственным образом раскладывается на простые множители. Отсюда следует, что разложение числа c 0 на простые множители, содержащее число р 0 , единственно.

А так как, по предположению, имеется по крайней мере два разложения числа c 0 на простые множители, то должно быть разложение, не содержащее число р 0 . Наименьшее простое число в этом разложении мы обозначим через р 1 и запишем

c 0 = p 1 d 1 . (3.1.1)

Так как p 1 > p 0 , то d 1 < d 0 и, следовательно, p 0 d 1 < c 0 . Рассмотрим число

c 0 " = c 0 - p 0 d 1 = (p 1 - p 0) d 1 . (3.1.2)

Так как оно меньше, чем число c 0 , то оно должно раскладываться на простые множители единственным способом; при этом простые множители числа c 0 состоят из простых множителей чисел p 1 - p 0 и d 1 . Так как число c 0 делится на p 0 , то из выражения (3.1.2) следует, что число c 0 " также делится на p 0 . Следовательно, p 0 должно быть делителем либо числа d 1 , либо p 1 - p 0 . Но любой простой делитель числа d 1 больше, чем p 0 , так как p 1 - наименьшее простое число в разложении (3.1.1). Таким образом, остается единственная возможность: p 0 должно быть делителем числа p 1 - p 0 и, следовательно, оно делит p 1 . Итак, мы пришли к противоречию, потому что p 1 является простым числом и не может делиться на другое простое число p 0 .

Выше мы отмечали, что единственность разложения числа на простые множители совсем не очевидна. В действительности, существуют «арифметики», в которых аналогичная теорема не выполняется. Простейшим примером такой арифметики может служить арифметика четных чисел

2, 4, 6, 8, 10, 12…

Некоторые из них могут быть разложены на два четных множителя, а другие - нет; последние мы называем чётно-простыми числами . Это числа, которые делятся на 2, но не делятся на 4:

2, 6, 10, 14, 18….

Очевидно, что каждое четное число либо является четно-простым, либо записывается в виде произведения чётно-простых чисел. Но такое разложение на чётно-простые числа не всегда будет единственным. Например, число 420 может быть разложено на четно-простые числа различными способами:

420 = 6 70 = 10 42 = 14 30.

Система задач 3.1.

1. Найдите разложение на простые множители каждого из чисел 120, 365, 1970.

2. Проделайте то же самое для чисел, указанных в задаче 1 системы задач 2.1 (стр. 25).

3. Запишите все разложения числа 360 на чётно-простые числа.

4. В каких случаях четные числа обладают единственным разложением на четно-простые множители?

Разложим на множители какое-нибудь число, скажем, 3600. Это разложение

3600 = 2 2 2 2 3 3 5 5

может быть записано как

3600 = 2 4 3 2 5 2 .

Вообще при разложении числа n на множители аналогично можно собирать одинаковые простые множители в виде степеней и записывать

n = p 1 α 1 p 2 α 2 …. р r α r , (3.2.1)

где p 1 , p 2 …. р r - различные простые множители числа n , причем число p 1 входит α 1 раз, p 2 входит α 2 раз и т. д.

Если мы знаем вид (3.2.1) для числа, то мы сможем тотчас же ответить на некоторые вопросы об этом числе.

Например, если мы захотим, то можем узнать, какие числа делят число n . Возьмем для примера рассмотренное выше число 3600. Предположим, что число d является одним из его делителей, т. е.

3600 = d d 1 .

Приведенное разложение на простые множители показывает, что единственными числами среди множителей числа d будут лишь 2, 3, 5. Кроме того, число 2 может содержаться не более 4 раз, а числа 3 и 5 не более, чем по 2 раза каждое. Итак, мы видим, что возможными делителями числа 3600 будут числа вида

d = 2 δ 1 3 δ 2 5 δ 3 ,

при этом показатели степени могут принимать значения:

δ 1 = 0, 1, 2, 3, 4;

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

(4 + 1) (2 + 1) (2 + 1) = 5 3 3 = 45.

Для любого числа n , разложение которого на простые множители дается формулой (3.2.1), положение точно такое же. Если число d является делителем числа n , т. е.

n = d d 1

то единственными простыми числами, на которые может делиться число d , будут только те, которые делят число n , а именно: p 1 …, р r . Таким образом, мы можем записать разложение числа d на простые множители в виде

d = p 1 δ 1 p 2 δ 2 …. р r α r , (3.2.2)

Простое число p 1 может содержаться не более α 1 раз, как и в самом числе n ; аналогично - для p 2 и других простых чисел. Это значение для числа δ 1 мы можем выбрать α 1 + 1 способом:

δ 1 = 0, 1…, α 1 ;

аналогично и для других простых чисел. Так как каждое из α 1 + 1 значений, которые может принимать число δ 1 , может сочетаться с любым из α 2 + 1 возможных значений числа δ 2 и т. д., то мы видим, что общее число делителей числа n задается формулой

τ(n ) = (α 1 + 1) (α 2 + 1)… (α r + 1). (3.2.3)

Система задач 3.2.

1. Сколько делителей имеет простое число? Сколько делителей имеет степень простого числа р α ?

2. Найдите количество делителей у следующих чисел: 60, 366, 1970, вашего почтового индекса.

3. Какое натуральное число (или числа), не превосходящее 100, имеет наибольшее количество делителей

Существует единственное число n = 1, которое имеет только один делитель. Числами с ровно двумя делителями являются простые числа n = р : они делятся на 1 и на р . Наименьшим числом, имеющим два делителя, является, таким образом, р = 2.

Исследуем числа, имеющие ровно 3 делителя. В соответствии с (3.2.3) имеем

3 = (α 1 + 1) (α 2 + 1)… (α r + 1).

Так как 3 - простое число, то справа может существовать лишь один множитель, не равный 1. Отсюда r = 1, a α 1 = 2. Таким образом,

n = p 1 2 .

Наименьшим числом с 3 делителями является n = 2 2 = 4. Это соображение, примененное к общему случаю, когда число делителей q является простым числом, позволяет получить, что

q = α 1 + 1, т. е. α 1 = q - 1 и n = р 1 q -1 ;

наименьшим из таких чисел является

n = 2 q -1 .

Рассмотрим следующий случай, когда существует ровно 4 делителя. Тогда соотношение

4 = (α 1 + 1) (α 2 + 1),

возможно только тогда, когда

α 1 = 3, α 2 = 0 или α 1 = α 2 = 1.

Это приводит к двум возможностям:

n = p 1 3 , n = p 1 p 2 ;

наименьшее число с 4 делителями - это n = 6.

В том случае, когда имеется 6 делителей, должно выполняться соотношение

6 = (α 1 + 1) (α 2 + 1),

что возможно лишь тогда, когда

α 1 = 5, α 2 = 0 или α 1 = 2, α 2 = 1.

Это дает две возможности:

n = p 1 5 , n = p 1 2 p 2 ;

при этом наименьшее значение имеет место в последнем случае, когда

p 1 = 2, p 2 = 3, n =12.

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

Существуют таблицы, указывающие количество делителей для различных чисел. Они начинаются следующим образом:

Вы легко можете ее самостоятельно продолжить.

Будем говорить, что натуральное число n является сверхсоставным , если количество делителей у каждого числа, меньшего n , меньше, чем количество делителей у числа n . Глядя на нашу небольшую таблицу, мы видим, что

являются первыми пятью сверхсоставными числами. О свойствах этих чисел известно еще очень мало.

Система задач 3.3.

1. Взвод из 12 солдат может маршировать 6-ю различными способами: 12 × 1, 6 × 2, 4 × 3, 3 × 4, 2 × 6, 1 × 12. Какую наименьшую численность должны иметь группы людей, которые могут маршировать 8, 10, 12 и 72 способами?

2. Найдите наименьшие натуральные числа, имеющие: а) 14 делителей, б) 18 делителей ив) 100 делителей.

3. Найдите два первых сверхсоставных числа, следующих за числом 12.

4. Охарактеризуйте все натуральные числа, количество делителей которых является произведением двух простых чисел.

Нумерология (или гематрия, как ее иногда еще называют) была распространенным увлечением у древних греков. Естественным объяснением этому является то, что числа в Древней Греции изображались буквами греческого алфавита, и поэтому каждому написанному слову, каждому имени соответствовало некоторое число. Люди могли сравнивать свойства чисел, соответствующих их именам.

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

Наименьшим совершенным числом является 6:

За ним следует число 28:

496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248.

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

6 = 2 3 = 2(2 2 - 1),

28 = 2 2 7 = 2 2 (2 3 - 1),

496 = 24 31 = 2 4 (2 5 - 1).

Это наталкивает нас на гипотезу:

Число является совершенным, если оно представляется в виде

Р = 2 p -1 (2 p - 1) = 2 р q , (3.4.1)

q = 2 p - 1

является простым числом Мерсенна.

Этот результат, известный еще грекам, несложно доказать. Делителями числа Р , включая само число Р , очевидно, являются следующие числа:

1, 2, 2 2 …, 2 р-1 ,

q , 2q , 2 2 q …, 2 р-1 q .

Запишем сумму этих делителей

1 + 2 +… + 2 р -1 + q (1 + 2 +… + 2 р -1),

которая равна

(1 + 2 +… + 2 р -1)(q + 1) = (1 + 2 +… + 2 р -1) 2 р

Если вы не помните формулы для суммы членов геометрической прогрессии,

S = 1 + 2 +… + 2 р -1 ,

то умножьте эту сумму на 2:

2S = 2 + 2 2 +… +2 р -1 + 2 р ,

а затем, вычтя S , получите

S = 2 p - 1 = q .

Таким образом, сумма всех делителей числа Р есть

2 p q = 2 2 p -1 q,

а сумма всех делителей, кроме самого числа Р = 2 p -1 q , равна

2 2 p -1 q - 2 p -1 q = 2 p -1 q = Р.

Итак, наше число является совершенным.

Из этого результата следует, что каждое простое число Мерсенна порождает совершенное число. В § 2 второй главы говорилось, что известно всего 23 простых числа Мерсенна, следовательно, мы знаем также и 23 совершенных числа. Существуют ли другие виды совершенных чисел? Все совершенные числа вида (3.4.1) являются четными, можно доказать, что любое четное совершенное число имеет вид (3.4.1). Остается вопрос: существуют ли нечетные совершенные числа? В настоящее время мы не знаем ни одного такого числа, и вопрос о существовании нечетных совершенных чисел является одной из самых знаменитых проблем теории чисел. Если бы удалось обнаружить такое число, то это было бы крупным достижением. Вы можете поддаться соблазну найти такое число, перебирая различные нечетные числа. Но мы не советуем этого делать, так как по последним сообщениям Брайена Такхермана из IBM (1968), нечетное совершенное число должно иметь по крайней мере 36 знаков.

Система задач 3.4.

1. Используя список простых чисел Мерсенна, найдите четвертое и пятое совершенные числа.

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

220 = 2 2 5 11, 284 = 2 2 71.

Суммами их делителей являются соответственно

1 + 2 + 4 + 5 +10 + 20 + 11 + 22 + 44 + 55 + 110 = 284,

1 + 2 + 4 + 71 + 142 = 220.

Эта пара дружественных чисел оставалась единственной известной до тех пор, пока Пьеру Ферма не удалось найти следующую пару:

17 296 = 2 4 23 47, 18 416 = 2 4 1151.

Поиски пар дружественных чисел чрезвычайно удобно вести с помощью ЭВМ. Для каждого числа n при помощи машины определяются все делители этого числа (≠ n ) и их сумма m . После этого производится такая же операция с числом m . Если при этом вновь получается первоначальное число n , то пара чисел (n, m ) оказывается дружественной. Недавно этим способом в Йельском университете на ЭВМ IBM 7094 были проверены все числа до одного миллиона. В результате была получена коллекция из 42 пар дружественных чисел; некоторые из них оказались ранее неизвестными. Все пары дружественных чисел до 100 000 приведены в табл. 2. При помощи этого метода, как нетрудно видеть, одновременно «вылавливаются» и совершенные числа. Если возникает желание продолжать поиски дальше, то, конечно, это можно сделать, но придется затратить большое количество машинного времени.

Таблица 2

Дружественные числа до 100 000

В действительности мы очень мало знаем о свойствах пар дружественных чисел, однако, можно на основе наших таблиц высказать несколько предположений. Например, отношение одного из них к другому, по-видимому, должно все больше и больше приближаться к 1 по мере того, как они увеличиваются. Из таблицы видно, что эти числа бывают либо оба четными, либо оба нечетными, но не было найдено случая, когда одно число четно, а другое нечетно, хотя поиски дружественных чисел такого вида были проведены среди всех чисел n ≤ 1 3 000 000 000.

Примечания:

Аликвотные дроби - дроби вида 1/n; в древности было принято всякую дробь представлять в виде суммы аликвотных дробей. Например, 5/12 = 1/12 + 1/3. (Прим. перев .)

Американская фирма, выпускающая вычислительное оборудование. (Прим. перев. )

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

Вам понадобится

• - таблица простых чисел;
• - признаки делимости чисел;
• - калькулятор.

Инструкция

• Чаще всего, нужно разложить число на простые множители. Это числа, которые делят исходное число без остатка, и при этом сами могут делиться без остатка только на само себя и единицу (к таким числам относятся 2, 3, 5, 7, 11, 13, 17 и т.д.). Причем, никакой закономерности в ряду простых чисел не найдено. Возьмите их из специальной таблицы или найдите при помощи алгоритма, который называется «решето Эратосфена».
• Начинайте подбирать простые числа, на которые делится данное число. Частное снова делите на простое число и продолжаете этот процесс до тех пор, пока в качестве частного не останется простое число. Затем просто посчитайте количество простых делителей, прибавьте к нему число 1 (которое учитывает последнее частное). Результатом будет количество простых делителей, которые при умножении дадут искомое число.
• Например, количество простых делителей числа 364 найдите таким образом:364/2=182
  182/2=91
  91/7=13Получите числа 2, 2, 7, 13, которые являются простыми натуральными делителями числа 364. Их количество равно 3 (если считать повторяющиеся делители за один).
• Если же нужно найти общее количество всех возможных натуральных делителей числа, воспользуйтесь его каноническим разложением. Для этого по описанной выше методике разложите число на простые множители. Затем запишите число как произведение таких множителей. Повторяющиеся числа возведите в степени, например, если трижды получали делитель 5, то запишите его как 5³.
• Записывайте произведение от наименьших множителей к наибольшим. Такое произведение и называется каноническим разложением числа. Каждый множитель этого разложения имеет степень, представленную натуральным числом (1, 2, 3, 4 и т.д.). Обозначьте показатели степени при множителях а1, а2, а3, и т.д. Тогда общее количество делителей будет равно произведению (a1 + 1)∙(a2 + 1)∙(a3+1)∙…
• Например, возьмите то же число 364: его каноническое разложение 364=2²∙7∙13. Получите а1=2, а2=1, а3=1, тогда количество натуральных делителей этого числа будет равно (2+1)∙(1+1)∙(1+1)=3∙2∙2=12.