Дружественные числа

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

История

Первое упоминание дружественных чисел встречается в античной математике. Древнегреческие философы и математики, в частности пифагорейцы, придавали числам мистическое значение. Они считали, что числа обладают свойствами, отражающими гармонию мира. Пара (220, 284) была известна ещё пифагорейцам (около VI века до н. э.). По легенде, Пифагор на вопрос «Что такое друг?» ответил: «Тот, кто является вторым я, как числа 220 и 284». Согласно античным представлениям, эти числа символизировали идеальную дружбу и взаимность.

В Средние века интерес к дружественным числам возродился в арабском мире. Арабский математик Сабит ибн Курра (IX век) сформулировал теорему, позволяющую находить некоторые пары дружественных чисел. Его правило, известное как «теорема Сабита ибн Курры», гласит: если для некоторого целого числа n > 1 числа p = 3·2ⁿ⁻¹ − 1, q = 3·2ⁿ − 1 и r = 9·2²ⁿ⁻¹ − 1 являются простыми, то числа 2ⁿ·p·q и 2ⁿ·r образуют дружественную пару. С помощью этой теоремы были найдены пары (220, 284) при n = 2, (17296, 18416) при n = 4 и (9363584, 9437056) при n = 7.

В Европе в эпоху Возрождения и Нового времени дружественные числа изучали такие математики, как Пьер Ферма, Рене Декарт и Леонард Эйлер. Ферма в 1636 году открыл пару (17296, 18416), а Декарт в 1638 году — пару (9363584, 9437056). Эйлер в XVIII веке систематизировал поиск и опубликовал список из 61 пары дружественных чисел, хотя некоторые из них оказались ошибочными. В XIX веке были найдены новые пары, в том числе с помощью компьютеров в XX веке. К началу XXI века известно более 12 миллионов пар дружественных чисел, однако их полный перечень не составлен, и вопрос о бесконечности множества таких пар остаётся открытым.

Определение и свойства

Формальное определение

Пусть σ(n) — функция суммы всех положительных делителей числа n, включая само число. Тогда собственные делители числа n — это все делители, кроме n, и их сумма равна σ(n) − n. Два различных натуральных числа a и b называются дружественными, если: σ(a) − a = b и σ(b) − b = a. Из этого следует, что σ(a) = σ(b) = a + b.

Основные свойства

• Наименьшая пара дружественных чисел — (220, 284). Делители числа 220: 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110. Их сумма: 1+2+4+5+10+11+20+22+44+55+110 = 284. Делители числа 284: 1, 2, 4, 71, 142. Их сумма: 1+2+4+71+142 = 220.
• Все известные дружественные числа — чётные. Существование нечётной пары дружественных чисел не доказано, но и не опровергнуто; это одна из нерешённых проблем теории чисел.
• Дружественные числа могут быть как равными (совершенные числа), так и различными. Совершенное число — это число, равное сумме своих собственных делителей (например, 6, 28). Если бы в определении дружественных чисел не требовалось различие чисел, то каждое совершенное число образовывало бы пару с самим собой, но по определению пара должна состоять из двух разных чисел.
• Дружественные числа не обязательно взаимно просты. Например, в паре (220, 284) наибольший общий делитель равен 4.

Известные пары

Ниже приведены несколько первых пар дружественных чисел (в порядке возрастания меньшего числа):

Примечательно, что вторая по величине пара (1184, 1210) была пропущена многими математиками и открыта лишь в 1866 году итальянским школьником Б. Никколо Паганини.

Методы поиска

Теорема Сабита ибн Курры

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

Алгоритмический перебор

С развитием вычислительной техники поиск дружественных чисел стал осуществляться путём перебора всех чисел в заданном диапазоне. Для каждого числа n вычисляется сумма его собственных делителей s(n). Если s(n) > n и s(s(n)) = n, то пара (n, s(n)) является дружественной. Этот метод позволяет находить пары до произвольно больших чисел, но требует значительных вычислительных ресурсов. Например, к 2023 году были найдены пары с числами, превышающими 10¹⁰⁰.

Использование факторизации

Для ускорения вычислений применяется разложение чисел на простые множители. Сумма делителей числа n = p₁ᵃ¹·p₂ᵃ²·...·pₖᵃᵏ вычисляется по формуле: σ(n) = (p₁ᵃ¹⁺¹ − 1)/(p₁ − 1) · (p₂ᵃ²⁺¹ − 1)/(p₂ − 1) · ... · (pₖᵃᵏ⁺¹ − 1)/(pₖ − 1). Это позволяет эффективно вычислять суммы делителей для больших чисел.

Связанные понятия

• Совершенные числа — числа, равные сумме своих собственных делителей. Являются частным случаем дружественных чисел, если допустить равенство чисел в паре.
• Общительные числа — циклы из трёх и более чисел, где каждое число равно сумме собственных делителей предыдущего. Например, (12496, 14288, 15472, 14536, 14264) — цикл из 5 чисел.
• Квазидружественные числа — пары чисел, где сумма собственных делителей каждого числа на единицу больше другого числа. Например, (48, 75): σ(48) − 48 = 75 + 1, σ(75) − 75 = 48 + 1.
• Содружественные числа — пары, где сумма собственных делителей каждого числа равна другому числу, но числа могут быть равны (совершенные числа) или различны.

Нерешённые проблемы

• Бесконечность множества дружественных чисел. Неизвестно, существует ли бесконечно много пар дружественных чисел. Хотя известно более 12 миллионов пар, доказательства бесконечности нет.
• Существование нечётных дружественных пар. Ни одна нечётная пара не найдена, и не доказано, что их не существует. Если нечётная пара существует, то оба её числа должны быть больше 10¹⁰⁰ по современным оценкам.
• Плотность дружественных чисел. Неизвестно, как часто встречаются дружественные числа среди натуральных чисел. Предполагается, что их доля стремится к нулю с ростом чисел, но точные оценки отсутствуют.

Применение

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

Интересные факты

• В античной культуре считалось, что амулеты с числами 220 и 284 приносят дружбу и любовь. Такие амулеты дарили друг другу в знак верности.
• Пара (220, 284) упоминается в Библии (Книга Бытия, 32:14) как количество козлов и овнов, принесённых в дар Иаковом, хотя это, вероятно, совпадение.
• В 1747 году Леонард Эйлер опубликовал список из 61 пары, но впоследствии некоторые из них были признаны ошибочными. Эйлер использовал метод, основанный на теореме Сабита ибн Курры, но с обобщениями.
• Самая большая известная пара дружественных чисел (по состоянию на 2023 год) содержит числа с более чем 100 000 десятичных знаков.

Источники

• Эйлер Л. «Введение в анализ бесконечных» (1748).
• Гарднер М. «Математические головоломки и развлечения» (1959).
• Оре О. «Теория чисел и её история» (1948).
• Сайт OEIS (On-Line Encyclopedia of Integer Sequences): последовательность A002025 (дружественные числа).
• Кнут Д. «Искусство программирования. Том 2. Получисленные алгоритмы» (1997).