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

Сумма натуральных делителей

Сумма натуральных делителей (С) — величина, которая для каждого натурального числа показывает, чему равна сумма всех его натуральных делителей.

С точки зрения математики С является мультипликативной арифметической функцией: для любых натуральных и взаимно простых a и b справедливо свойство мультипликативности С(a • b) = С(a) • С(b).

Другая, похожая величина — это сумма S(n) собственных делителей числа, меньших чем исходное число n (число 1, являющееся делителем любого числа, входит в эту сумму). Она отличается от С(n) на величину самого числа n: S(n) = С(n) — n. Вычисление S позволяет разбить множество натуральных чисел на 3 группы: совершенные числа — натуральные числа, равные сумме своих меньших делителей; избыточные числа — для которых сумма S(n) больше числа; недостаточные числа — для которых сумма S(n) меньше числа.

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

Сумма делителей числа – это сумма всех натуральных чисел, на которые данное число делится без остатка. Например, сумма делителей числа 12 равна 1 + 2 + 3 + 4 + 6 + 12 = 28. Найти сумму делителей числа может быть полезно в решении различных математических задач и создании определенных алгоритмов. В данной статье мы рассмотрим несколько простых шагов, которые помогут вам быстро найти сумму делителей числа и приведем несколько примеров.

Первый шаг в поиске суммы делителей числа – найти все делители данного числа. Для этого нужно разложить число на простые множители и найти все возможные комбинации. Например, для числа 12 простые множители – это 2 и 3. Таким образом, все делители числа 12: 1, 2, 3, 4, 6 и 12.

Второй шаг – сложить все найденные делители. В нашем примере сумма делителей числа 12 равна 1 + 2 + 3 + 4 + 6 + 12 = 28. В качестве упражнения вы можете попробовать найти сумму делителей для других чисел.

Например, найдите сумму делителей чисел 20 и 48.

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

Если вы хотите найти сумму всех делителей конкретного числа, то следуйте этим простым шагам.

Шаг 1: Разложите число на простые множители.

Например, если вам нужно найти сумму всех делителей числа 30, то разложите его на простые множители: 2, 3 и 5.

Шаг 2: Найдите все возможные комбинации множителей, включая 1 и само число.

Если мы возьмем наш пример числа 30, то все возможные комбинации это: 1,2,3,5,6,10,15 и 30.

Шаг 3: Сложите все найденные комбинации.

В нашем примере мы получаем сумму: 1+2+3+5+6+10+15+30=72.

Шаг 4: Полученная сумма является суммой всех делителей числа.

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

Зачем нужно находить сумму делителей числа

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

• Теория чисел: нахождение суммы делителей числа позволяет выявить свойства чисел, например, определить совершенное число, которое равно сумме своих делителей.
• Криптография: при построении криптографических алгоритмов особое значение имеют простые числа и их свойства, в том числе сумма и количества делителей.
• Программирование: в задачах на программирование часто требуется вычислить сумму делителей числа, например, при поиске всех дружественных чисел или при проверке числа на простоту.

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

Простые шаги для нахождения суммы делителей числа

Найдем сумму делителей числа 24. Простые шаги:

1. Найдем все делители числа 24. Делители — это числа, которые делят число без остатка. Для числа 24 делителями будут числа 1, 2, 3, 4, 6, 8, 12, 24.
2. Сложим все найденные делители: 1 + 2 + 3 + 4 + 6 + 8 + 12 + 24 = 60.

Теперь рассмотрим более подробно, как находить делители числа:

1. Найдем максимальный делитель числа. Для этого нужно найти корень квадратный из данного числа. Например, для числа 24 корень квадратный из 24 равен примерно 4.89. Максимальный делитель будет равен 4.
2. Найдем все делители числа от 1 до максимального делителя. Для числа 24 это будут числа от 1 до 4. Для каждого такого числа проверяем, является ли оно делителем числа 24. В данном случае 1, 2, 3 и 4 являются делителями 24.
3. Найдем оставшиеся делители числа от максимального делителя до самого числа. Для числа 24 это будут числа от 5 до 24. Для каждого из чисел проверяем, является ли оно делителем числа 24. В данном случае делителями будут числа 6, 8, 12 и 24.

В табличной форме нахождение суммы делителей числа будет выглядеть следующим образом:

Делитель	24/делитель	Целое
1	24/1	24
2	24/2	12
3	24/3	8
4	24/4	6
6	24/6	4
8	24/8	3
12	24/12	2
24	24/24	1

Затем складываем все полученные значения в столбце «Целое»:

24 + 12 + 8 + 6 + 4 + 3 + 2 + 1 = 60

Примеры задач на нахождение суммы делителей числа

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

Пример 1

Найдите сумму всех делителей числа 12.

Решение:

12 можно представить в виде произведения простых множителей: 12 = 2 2 × 3 1 . Тогда сумма делителей числа 12 будет равна (2 0 + 2 1 + 2 2 ) × (3 0 + 3 1 ) = 1 + 2 + 4 + 3 + 6 + 12 = 28.

Пример 2

Найдите сумму всех делителей числа 16.

Решение:

16 можно представить в виде произведения простых множителей: 16 = 2 4 . Тогда сумма делителей числа 16 будет равна (2 0 + 2 1 + 2 2 + 2 3 + 2 4 ) = 1 + 2 + 4 + 8 + 16 = 31.

Пример 3

Найдите сумму всех делителей числа 105.

Решение:

105 можно представить в виде произведения простых множителей: 105 = 3 1 × 5 1 × 7 1 . Тогда сумма делителей числа 105 будет равна (3 0 + 3 1 ) × (5 0 + 5 1 ) × (7 0 + 7 1 ) = 1 + 3 + 5 + 7 + 15 + 21 + 35 + 105 = 192.

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

Факторизация чисел и сумма неизвестных делителей. Часть IV

Возможность единственного представления составного нечетного натурального числа (СННЧ) N в виде произведения степеней простых (кроме 2) чисел составляет существо основной теоремы арифметики (ОТА). Для больших чисел, содержащих в своей записи и более цифр, эта возможность, а точнее задача не получила приемлемого для практики (за обозримое время) решения до наших дней. Кратко эту задачу называют задачей факторизации больших чисел(ЗФБЧ). Ее формулировка проста и известна уже несколько тысячелетий: для заданного натурального числа N = pq найти все его нетривиальные делители.

При заданном значении СННЧ N что можно узнать о его делителях? Практически ни о числе, ни составе делителей в теории чисел нет теорем. Поэтому ЗФБЧ до сегодняшнего дня является практически нерешаемой. Известен переборный алгоритм решения ЗФБЧ методом решета о котором мной написаны прочие статьи цикла под спойлером. Имеется зацепка в виде суммы σ(N) = N +p +q +1 делителей N для подступа к ее решению, минуя решета и связанные с ними проблемы.

Так в Г 2± – модели НРЧ в клетке () всегда лежит сумма делителей N, если само число N помещено в клетке (). Кроме этого, в клетке () лежит значение функции Эйлера СННЧ N, если его собственные делители простые числа.

В теории чисел известны две формы представления (моделей) числа: аддитивная и мультипликативная на основе ОТА. Эти формы (при аддитивном представлении числа суммой членов отрезка непрерывной последовательности нечетных чисел) тесно связаны. Число слагаемых в сумме равно меньшему делителю, а среднее слагаемое — большему. Это не так, если аддитивная форма представляет произвольное разбиение числа на части. Например, в 1-ом случае 105 =33+35+37 =3·35 и 105 = 60+40 +5 ≠3·40 — во 2-ом.

Поводом для написания этой работы послужило стремление автора познакомить читателей с подходом к задаче факторизации чисел на основе факта, открытого автором при изучении модели натурального ряда чисел (НРЧ), а также с результатом Л. Эйлера,

, который состоит в том, что для произвольного СННЧ N можно вычислить сумму σ(N) его делителей, не располагая значениями самих делителей. Это положение граничит с мистикой, но оказывается такое возможно при наличии качественных моделей НРЧ и отдельного числа.

Определенным стимулом явилась также публикация Пшеннова А.В. в Интернете, где приводится некоторый фактический материал по делителям чисел и их суммам. Конечно,
основной причиной является наблюдение, сделанное автором самостоятельно, при изучении созданной и разрабатываемой им оригинальной модели натурального ряда чисел (НРЧ). Приведу краткое описание модели, которая ранее уже рассматривалась здесь.

Таблица М — Модель (плоскостная) натурального ряда чисел

Символами в модели обозначены соответственно номера строк и столбцов.

В модели использовано известное положение о том, что в любой клетке СННЧ N = а·b представимо разностью квадратов двух целых чисел () разной четности, которые выбираются специальным образом, т.е. и а, b играют роль диагоналей, пересекающихся в этой клетке модели.

Сущность наблюдения в Г 2± – модели НРЧ (таблица М) состоит в следующем. Располагая в модели координатами клетки, легко определяются значения чисел в них, но обратная задача трудно решаемая. Допускаем, что координаты клетки заданного СННЧ N известны.

Сумму делителей числа N из клетки () обозначают σ(N). Cумма σ(N) этих двух (а, b) неизвестных нетривиальных делителей, а также тривиальных делителей 1 и самого N, определяется (вычисляется) в модели, как значение числа в другой клетке с координатами (), в то время как само число N помещается в клетке (), что легко показывается. Установлены, сформулированы и доказаны две новые теоремы.

Теорема 1. Если в клетке () Г 2± – модели НРЧ содержится СННЧ N = а·b, где а,b -собственные делители играют роль номеров короткой и длинной диагоналей, пересекающихся в этой клетке, то в строке ниже под этой клеткой в клетке () содержится сумма σ(N) делителей СННЧ N. (положение N задано, а и b неизвестны).

Доказательство. Значение любой клетки Г 2± – модели НРЧ по основному соотношению модели равно , где в скобках соответственно приведено произведение — номеров диагоналей длинной и короткой, пересекающихся в этой клетке и выполняющих роль делителей N=аb. Под клеткой со значением N помещается клетка, значение в которой равно произведению диагоналей, увеличенных на 1, т.е. (а+1)(b+1)=а·b+а+b+1=σ(N), раскрывая скобки, получаем сумму делителей. Этим доказательство завершается.

В этом равенстве а·b+1=N+1, а разность σ(N)-N-1=а+b — есть сумма только собственных делителей N. Названные зависимости легко могут быть выражены через переменные модели (), так как а = () и b=(), тогда .
Здесь же отметим и еще одно наблюдение для которого справедлива следующая

Теорема 2. Если в клетке () Г 2± – модели НРЧ содержится СННЧ N = а·b, где а,b -собственные делители играют роль номеров короткой и длинной диагоналей, пересекающихся в этой клетке и являющиеся простыми нечетными числами, то в строке выше над этой клеткой в клетке () содержится функция Эйлера φ(N) СННЧ N. Положение N задано, а и b неизвестны.

Доказательство. Здесь повторяется положение предыдущей теоремы, но для клетки выше изменяются знаки. Над клеткой со значением N помещается клетка, значение в которой произведение номеров диагоналей, уменьшенных на 1, т.е. φ(N)=(а-1)(b-1) = а·b -а-b+1. Этим равенством доказательство теоремы завершено.
Результаты обеих теорем (показано ниже) могут быть применены в атаках на шифр RSA.

Из второй теоремы следует, если а и b простые нечетные числа-нетривиальные делители числа N, то произведение φ(N) = (а – 1)( b – 1) и разность являются теоретико-числовой функцией Эйлера для составного числа N.
Приведем вид решетчатой функции σ(N) суммы делителей в зависимости от числа N. По оси ординат расположим числа N, а по оси абсцисс σ(N) сумму их делителей (1≤N≤1000).

На графике отчётливо просматриваются несколько наклонных линий из точек, имеющих сходство с прямыми, например, нижняя линия соответствует суммам делителей простых чисел. Верхняя граница – это наиболее сложные числа (имеющие наибольшее количество делителей) — это не прямая, но и не парабола. Возможно – это показательная функция вида ().

При решении задачи факторизации совсем не обязательно сразу получать все степени простых чисел. Можно пойти путем нахождения вначале лишь одного единственного делителя (второй получается, как частное при выполнении деления). Этот единственный делитель может быть и составным числом, как впрочем, и частное от деления числа N на него. После этого оба найденные делителя (числа меньшей разрядности) подвергаются процедуре дальнейшей факторизации до ее полного завершения.

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

Этот факт служит подтверждением правильности найденного решения.
Чтобы количественно почувствовать и оценить зависимость σ(N) – суммы делителей от числа N покажем последовательность таких сумм для первых ста натуральных чисел N (см. таблицу 1):

Таблица 1. Суммы σ(N) делителей натуральных чисел, полученные Эйлером.

Из приведенных весьма ограниченных данных видим, что для простых чисел σ(N)=N+1, что некоторые различные числа (46, 55, 71) имеют совпадающие значения σ(N) = 72, а некоторые N не являются суммами делителей ни одного из натуральных чисел.

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

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

Делителями N являются все числа, для которых . Ясно, что σ(N) представляет собой сумму всех таких чисел при различных значениях показателей .

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

Ясно, что существуют составные натуральные числа, образованные произведением всего лишь двух простых чисел (RSA числа). Это, вообще говоря, частный для теории чисел случай, но очень важный для практики. В общем случае оба делителя а и b – составные числа. Для лучшего понимания идеи такого алгоритма факторизации ниже приведем числовые примеры, рассматриваемые в рамках приведенной Г 2± – модели НРЧ (табл. М).

Пример 1. Найти разложение заданного составного натурального числа N на множители а и b, если а и b неизвестны, а их сумма σ(N)=а + b известна.

Данная задача может быть сведена к нахождению решения системы двух алгебраических уравнений с двумя неизвестными. Чтобы исключить тривиальные решения (делители) вычтем их из заданной σ(N) суммы делителей .

В рассматриваемом примере решением задачи факторизации числа N являются значения а и b, удовлетворяющие замкнутой системе двух алгебраических уравнений:
,
.

Здесь σ(N) обозначает сумму всех делителей N, которая полагается известной, а вычисляется и представляет собой сумму лишь двух нетривиальных делителей простых или составных чисел. Как находить значения таких сумм σ(N) и будет показано позже.

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

Таким образом, задача факторизации числа в рассматриваемой ситуации будет успешно решена, если для числа N предварительно будет определена σ(N) сумма делителей.

Пример 2 (числовой с двумя простыми делителями). Задано N = a·b = 301, для которого известна клетка () его размещения в Г 2± – модели НРЧ. Требуется определить cумму всех делителей σ(N) числа N, вычислить функцию Эйлера и факторизовать N.

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

Уже отмечалось, что для простого числа q сумма σ(q)=q+1 равна сумме делителей q и 1. Поэтому при

Располагая моделью Г 2± этот результат получается вычислением в одной клетке. Находим , сумма неизвестных а и b делителей Находим делители Покажем как связаны делители и координаты клетки

Наконец, вычислим значение функции Эйлера
Ответ: корни уравнения-делители N реализуют факторизацию. Проверка N = a∙b = 43∙7 = 301,

Убедимся, что в терминах переменных сумма делителей совпадает с вычисленной

Вычислим при найденных значениях a и b, функцию Эйлера
. Значения функции Эйлера, вычисленные двумя способами, совпали.

Пример 3 (числовой с одним простым и одним составным делителем). Задано N = 147, для которого сумма всех делителей σ(N) = σ(147) = 1+3+7+21+49 +147= 228. Но для четырех делителей числа N сумма равна 1 + а + b + 147, σ(N) = 176. Здесь а=21 и b=7 неизвестные делители, формирующие значение N. Требуется факторизовать число N.

Решение. Находим .
Корни найдены Установим связь корней с переменными .
Ответ: Корни уравнения . Проверка a∙b = 21∙7 = 147

В этом примере один из делителей а=21 оказался составным числом, но именно это число и является слагаемым в сумме делителей, что видим в модели (табл. М строки 14,15; столб. 7) .

В примерах 2 и 3 рассмотрены задачи, в которых в качестве исходных данных задано число N и клетка его размещения. Требовалось факторизовать число N, т.е. отыскать делители. Для факторизации привлекалась модель НРЧ и в ее клетках отыскивалась сумма делителей σ(N) и функция Эйлера φ(N), когда делителей (собственных) было всего два и они оба были простыми числами.

Существует симметричная относительно исходных данных задача, в которой известна сумма N+1 кратных делителей N = pq и клетка в Г 2± – модели НРЧ с координатами (), в которой лежит кратное целому числу sN произведение . Само число N лежит в последней клетке строки x1 с кратным произведением в Г 2- – модели НРЧ. Требуется факторизовать составное число N.

Пример 4. Заданы составное число N=pq =77, сумма , коэффициенты целые числа, координаты клетки () с кратным произведением числа . Требуется факторизовать N, т.е. определить p и q делители N.

Решение. По координатам клетки легко определяется значение в ней . Далее определяем произведение коэффициентов делителей в сумме . Получаем для двух неизвестных p и q замкнутую систему из двух уравнений:
,
.
Введем новые обозначения неизвестных . Перепишем систему.
,
.
Решение. .
Последнее слагаемое в квадратном уравнении необходимо сделать квадратом числа 39. Для этого добавим в левую и правую части уравнения число . Тогда получаем или и окончательно или

Пример 5. Если – различные простые числа, то σ(N) для различных их комбинаций имеет формулы:

Пользуясь этими соотношениями, можно записать

Пусть по формуле конечного числа членов геометрической прогрессии приходим к равенству

Следующий результат в виде ряда для σ(N) получил Л. Эйлер, который записал сомножители N в многочленном представлении и раскрыл скобки в произведении многочленов
=
.

Ряд Эйлера

Этот ряд обеспечивает вычисление суммы делителей составного числа N, не зная ни числа делителей, ни их значений.

Аналогичный результат получен в рамках исследования Г 2± – модели НРЧ (Теоремы 1 и 2)

Пример 6. Необходимо вычислить σ(360), при известном каноническом разложении на множители числа. По формулам теории чисел это легко вычисляется.

Эта задача по формулам не решается, если для N отсутствует каноническое разложение.
Ряд Эйлера позволяет свести задачу к решению системы алгебраических уравнений как в примерах 2 и 3. Но возникает ряд проблем, хотя и преодолимых. Привлечение модели НРЧ (табл. М) снимает часть затруднений, но создает свои.

Описание и использование ряда Эйлера при расчетах σ(N)

Пусть задано нечетное число N, которое требуется факторизовать, и известно, что N = pq, где p и q простые числа. Делителями N кроме p и q являются также 1 и само число N. Если известна сумма p + q = σ(N), то, как показано ранее, задача факторизации легко решается. Далее поясним как находятся значения σ(N) без знания делителей.

Рассмотрим две числовые последовательности: а) натуральных чисел;
б) нечетных чисел.
а)1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 3738…
б) 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49……

вторая последовательность начинается не 1, а числом 3.

Сольем эти две последовательности в одну, обозначив ее s, чередуя числа из последовательностей а) и б), а также выполним нумерацию элементов s сформированного ряда.

Таблица 2 – Совмещенные последовательности ряда нечетных и натуральных чисел.

Нечетные номера получают элементы из натурального ряда, а четные – из ряда нечетных чисел (при начале отсчета элементов s от единицы и наоборот, если начать отсчет номеров от нуля).

Использование ряда s предполагает возможность вычисления любого его элемента по текущему номеру или восстановление текущего номера по известному значению элемента ряда. Анализ ряда s показывает, что для элементов нечетного ряда их значение на единицу больше текущего номера, а значения элементов из натурального ряда равны половине увеличенного на единицу порядкового номера. Следующие примеры проясняют эти утверждения.

Пример 7. Порядковый номер элемента ряда s равен 30. Определить значение s(30).
Так как 30 ≡ 0(mod2), т.е. номер – четное число, то s(30) принадлежит ряду б) нечетных чисел и равно s(30) = 30 + 1 = 31.

Пример 8. Порядковый номер элемента ряда s равен 37. Определить значение s(37).
Определяем четность номера 37 ≡ 1(mod2). Номер нечетный, следовательно, число с этим номером принадлежит натуральному ряду а) и его значение
s(37) = (37 + 1)/2 = 19.

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

Пример 9. Значение элемента ряда s = 13. Определить порядковые номера для s-1(13).
Если s принадлежит натуральному ряду чисел, то его номер является нечетным числом и большим из двух возможных.
Таким образом, №натур(s) = 2s – 1 = 2∙13 – 1 = 25.

Если s принадлежит ряду нечетных чисел, то его номер – четное число и определяется по формуле № нечетн(s) = s – 1 = 13 – 1 = 12. Это меньший номер из двух. Оба номера связаны простым соотношением
№натур(s) – № нечетн(s) = (2s – 1) – (s –1)= s = 25 – 12 = 13.

Разность номеров равна значению s. Таким образом, поведение элементов ряда s, т.е. значения и занимаемые позиции устанавливаются достаточно простыми соотношениями.
Как этими фактами можно воспользоваться при решении задачи факторизации?
Оказывается, ряд s является рядом разностей смежных элементов другого ряда k(i), открытого Эйлером, и по известному ряду s ряд k(i) можно восстановить.

Таблица 3 – Последовательность нумерованных чисел k(i) ряда Эйлера

k(1) =1, k(2) = k(1) + s(1) = 2, k(3) = k(2) + s(2) = 2 + 3 = 5,
k(4) = k(3) + s(3) = 5 + 2 = 7, k(5) = k(4) + s(4) = 7 + 5 = 12 и т. д… в общем виде
k(i + 1) = k(i) + s(i), i = 1(1)…, k(1) = 1.

Ряд k(i) был открыт Л. Эйлером, который указал на его применимость к решению задачи определения сумм делителей натуральных чисел в формуле:
σ(N)=σ(N-k(1))+σ(N-k(2))-σ(N-k(3))-σ(N-k(4))+σ(N-k(5))+σ(N-k(6))-σ(N-k(7))-
-σ(N–k(8))+= … = σ(N-1)+σ(N-2)-σ(N-5)-σ(N-7)+σ(N-12)+σ(N-15)-σ(N-22)-σ(N–26)+ …

При выполнении расчетов σ(N) для аргумента функции σ(N) вычисляются разности
N — k(i), если σ(N) обозначает любой член этой последовательности, а σ(N — 1),
σ(N — 2), σ(N — 5)… предшествующие члены, то σ(N) всегда можно получить по нескольким предыдущим членам:
σ(N)= σ(N — 1)+ σ(N — 2)- σ(N — 5)- σ(N — 7)+ σ(N — 12)+σ(N — 15)- σ(N — 22)- σ(N – 26)+ …

Знаки «+» и «–» в правой части формулы попарно чередуются.
Возникают еще вопросы. Когда необходимо ограничить бесконечный ряд, остановиться? Как определить значение в точке останова?

Остановка происходит при получении отрицательного или нулевого значения аргумента в некотором слагаемом. Последняя разность при вычислениях N — k(i) может оказаться отрицательной при N < k(i) или нулевой при N = k(i). В первом случае останавливаются на предпоследнем значении аргумента, а во втором – нулевое значение заменяется на N.

Вычисления функции σ(N — k(i)) с аргументами, определяемыми с использованием ряда k(i), с учетом знаков при суммировании обеспечивает нахождение суммы делителей N без знания значений самих делителей. Наличие такой суммы приводит к решению задачи факторизации чисел вида N = ab, где а и b – делители N.

Эйлеру не удалось найти доказательство открытой им закономерности и те, к кому он обращался ничего подсказать ему не смогли, но он был глубоко убежден в правильности открытого закона и опубликовал его. Почитать об этом можно в [10]. В модели (табл. М) я привожу формулировку и доказательство теорем о σ(N) и φ(N), которые несколько перекрывают результат Эйлера (он не говорит ничего о значениях функции φ(N), которая лежит строкой выше).

Закон образования ряда чисел 1, 2, 5, 7, 12, 15…, которые необходимо вычитать из рассматриваемого числа N, станет ясен, если рассмотреть их последовательные разности:
Числа:1, 2, 5, 7, 12, 15, 22, 26, 35, 40, 51, 57, 70, 77, 92, 100…
Разности: 1, 3, 2, 5, 3, 7, 4, 9, 5, 11, 6, 13, 7, 15, 8…

В самом деле, в ряде разности обнаруживаются два ряда: поочередно через один элемент все натуральные числа 1, 2, 3, 4, 5, 6, 7… и остаются после этого только нечетные числа 3, 5, 7, 9 11…они выделены жирным шрифтом между числами натурального ряда.

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

Пример 10. Вычислить сумму делителей числа N = 20. Начальные условия для формулы Эйлера имеют вид: σ(1) = σ(0) =1, σ(2) = σ(1) + σ(0) = 1 + 2 = 3, …
Решение: σ(20) = σ(19) + σ(18) — σ(15) — σ(13) + σ(8) + σ(5) =
=20 + 39 – 24 – 14 + 15 + 6 = 42.

Формула содержит лишь шесть слагаемых, так как в седьмом аргумент 20 – 22 = –2 получает отрицательное значение и процесс вычислений обрывается. Для поиска новых возможностей изучения натуральных чисел мы продолжаем экспериментировать и часть материалов приводим ниже.

Приведём далее экспериментальный материал (список, который был получен с помощью программы для ЭВМ. Для нахождения делителей числа N, программа делила число N на другое число, не превосходящее корня из N, и, если результат деления был равен целому числу, то оба числа записывались как делители N. Ниже приведен фрагмент (таблица 4) списка чисел в интервале 1 < N < 1000 и их делителей

Таблица 4 – Делители натуральных чисел (фрагмент)

Теперь посмотрим, все ли натуральные числа являются суммой делителей какого-либо числа, и есть ли такие числа, суммы делителей которых равны (в первых двух сотнях) друг другу.

Далее приведена таблица 5: ее элемент [[N, σ(N)]]=[[4, 7]](на втором месте обозначения сумма делителей, а на первом число с данной суммой делителей) … [[1, 1]], [2], [5] (т.е. для чисел 2, 5 нет такого числа с суммой делителей равной двум или пяти). Если несколько чисел имеют одинаковые суммы делителей, то значения для таких сумм повторяются нужное число раз для чисел 14, 15 и 23 сумма делителей равна 24: [14,24]; [15,24]; [23,24].

Таблица 5. Числа от 1 до 200, совпадающие с суммами делителей разных чисел и не являющиеся такими суммами.

Теперь вычислим σ(N) суммы делителей всех чисел из диапазона
1< N < 1000 (которые тоже были получены с помощью программы, делители N из таблицы 4 просто суммировались). Как можно увидеть в таблице есть такие числа, которые не являются суммой делителей ни одного числа и так же есть такие числа, которые являются суммой делителей не одного, а нескольких чисел.

Таблица 6 – Суммы делителей σ(N) натуральных чисел 1< N<1000.

Жирным шрифтом выделены квадраты чисел. Подчеркиванием выделены кубы чисел.

1. Ферма П. Исследования по теории чисел и диофантову анализу. – М.: Наука, 1992. – 320 с.
2. Евклид, Начала Евклида, т.1–3, М–Л.,1948–1950.
3. Euler, Opera Omnia, ser.1, vol. 2, p. 241-253.
4. Ваулин А.Е. и др. Фундаментальные структуры натурального ряда чисел.//Сб.тр. 7-го Международного симпозиума. – М.: РУСАКИ, 2006. – с.456-459.
5. Ваулин А.Е. Новый метод факторизации больших чисел в задачах анализа и синтеза двух-ключевых криптографических алгоритмов. Ч.1.// Информация и космос .№3, 2005, 74 –78с.
6. Ваулин А.Е. Новый метод факторизации больших чисел в задачах анализа и синтеза двух-ключевых криптографических алгоритмов. Ч.2.//Информация и космос. №4, 2005,104 –112с.
7. Василенко О.Н. Теоретико–числовые алгоритмы в криптографии.–М.: МЦНМО,2003.–328с.
8. Дэвенпорт Г. Высшая арифметика. – М.: Наука, 1966. – 176с.
9. Ноден П., Китте К. Алгебраическая алгоритмика (с упражнениями и решениями). – М.: Мир, 1999. – 720с.
10. Пойя Д. Математика и правдоподобные рассуждения.– М.: Наука, 1975. – 464с.
11. Пойя Д. Математическое открытие. – М.: Наука, 1970.–
12. Эндрюс Г. Теория разбиений. – М.: Наука, 1982. – 256с.
13. Пшеннов А.В.

Найти делители числа

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

Онлайн калькулятор нахождения делителей числа

Калькулятор работает следующим образом: укажите величину, задайте параметр, нажмите Рассчитать. Для очистки полей используйте кнопку Очистить.

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

Определения

Напомним: делимое — то, что делим; делитель — то, на что делим; частное — результат деления.

• Делителем натурального числа a называют такое натуральное число b, на которое a делится без остатка.

10 : 5 = 2, где 5 — делитель

• Кратным называют такое число a, которое делится на число b без остатка. Частая задача — нахождение наименьшего общего кратного (НОК).

9 : 3 = 3, где 9 — кратное

• Простое число — это число, которое делится без остатка только на единицу и на само себя. Составное — имеющее больше этих двух делителей.

7 : 1 = 7, 7 : 7 = 1, т.е. 7 — простое

4 : 1 = 4, 4 : 4 = 1, 4 : 2 = 2, т.е. 4 — составное

• Признаки делимости — это набор правил, позволяющих быстро оценить делимость на определенное число.
• Наибольшим общим делителем (НОД) для двух целых чисел a и b называется наибольший из их общих делителей. Аналогичное определение можно вывести для наименьшего общего делителя.

Делители числа 12 — 12, 6, 4, 3, 2, 1; числа 9 — 9, 3, 1. Соответственно, НОД — 3.

Делители числа

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

Для натурального числа:

• Разложите число на множители.
• Выпишите все не повторяющиеся множители.

Простые делители числа:

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

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

Находим делители 18, для этого раскладываем на множители:

• 18 = 18 · 1
• 18 = 9 · 2
• 18 = 6 · 3
• 18 = 2 · 9
• 18 = 1 · 18

Выписываем не повторяющиеся делители: 1, 2, 6, 9, 18.

Находим простые делители 18, для этого раскладываем на простые множители:

• 18 = 2 · 3 · 3

Выписываем не повторяющиеся простые делители: 2, 3.

• Напишите делители числа 12. Указать только простые делители.

Как решить: раскладываем на множители 12 =1 · 12 = 2 · 2 · 3 = 6 · 2. Получаем полный список, на что делится 12 — это 1, 2, 3, 4, 6, 12. Простые из них те, что делятся только на себя и на единицу, то есть 2 и 3.

• Найдите общие делители 12 и 15.

Решение. Сначала вычислим для 12 — получаем 1, 2, 3, 4, 6, 12. Затем запишем для 15 — это 1, 3, 5, 15. Общие делители — 1 и 3.

Сумма делителей числа

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

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

Находим делители 32, для этого раскладываем на множители:

• 32 = 32 · 1
• 32 = 16 · 2
• 32 = 8 · 4
• 32 = 4 · 8
• 32 = 2 · 16
• 32 = 1 · 32

Выписываем не повторяющиеся делители: 1, 2, 4, 8, 16, 32. Находим сумму делителей: 1 + 2 + 4 + 8 + 16 + 32 = 63.

Чтобы найти простые делители, раскладываем величину на простые множители: 32 = 2 · 2 · 2 · 2 · 2. Находим сумму простых делителей — 2.

• На что делится 15. Найдите сумму простых делителей.

Как решить: раскладываем на простые множители 15 = 5 · 3. Находим сумму простых делителей: 5 + 3 = 8 .

• Найти сумму делителей числа 27.

Решение. Сначала разложим 27 на множители: 27 = 1 · 27 = 3 · 9 = 9 · 3 = 27 · 1. Находим сумму делителей: 1 + 3 + 9 + 27 = 40.