Вальтер боро приглашает на охоту
В заключение я предлагаю вам отправиться на охоту за дружественными числами, вооружившись методом, существенно отличающимся от методов Эйлера. Речь идет об одном рецепте, по которому из уже известных дружественных чисел можно изготовить новые, значительно превосходящие исходные по величине.
Хотите получить свою собственную пару дружественных чисел? Тогда следуйте методу немецкого математика Вальтера Боро (р. 1945 г.):
1) Возьмите пару дружественных чисел вида
А = а · u и B = a · s,
где s – простое число. Например,
А = 220 = 22 · 55 и В = 284 = 22 · 71,
где s = 71 – простое число.
2) Проверьте, является ли число
p = u s 1
простым. В нашем случае p = 55 71 1 = 127 – простое.
3) Если да и если не окажется, что а делится на р, то при n = 1, 2, 3, … справедливо следующее правило:
если оба числа
q1 = (u 1) · рn – 1 и q2=(u 1) · (s 1) · pn – 1
– простые, то числа
B1= A · pn · q1 и B2 = a · pn · q2
– дружественные.
Итак, при n = 1 числа
q1 = (55 1) · 1271 – 1 = 7111 = 13 ·547
q2 = (55 1) · (71 1) · 1271 – 1 = 512 063 = 97 · 5 279
не являются простыми.
Но уже при n = 2 мы получаем простые q1 и q2:
q1 = (55 1) · 1272 – 1 = 903 223
q2 = (55 1) · (71 1) · 1272 – 1 = 65 032 127,
а значит и дружественную пару
B1 = 220 · 1272 · 903 223 и В2 = 22 · 1272 · 65 032 127.
Великий охотник – леонард эйлер
Время отмерило еще 100 лет, когда на математическом небосклоне засияла звезда гения Леонарда Эйлера (1707–1783). С присущей ему основательностью и энергией включился Эйлер в начавшуюся охоту – поиск дружественных чисел. Эйлер получил утверждение, очень похожее на правило Сабита, но более общее.
Эйлер искал дружественные числа и совершенно иного вида, чем его предшественники, в частности нечетные. Среди его «трофеев» оказались и пары нечетных дружественных чисел вида
а · p · q и а · r
где р, q, r – простые числа. Например:
(32· 7 · 13) · 5 · 17 и (32· 7 · 13) · 107;
(34 · 5 · 11) · 29 · 89 и (34 · 5 · 11) · 2699.
Попробуйте самостоятельно найти собственные делители каждого из этих чисел и убедиться в том, что это действительно пары дружественных чисел.
В своих мемуарах «О дружественных числах» и «О сумме делителей» Эйлер излагает пять (!) различных методов выявления дружественных чисел. С примерным терпением и восхитительной виртуозностью он выполняет вычисления и преподносит изумленным современникам, занимающимся той же проблемой примерно с таким же увлечением, но безрезультатно, обильную добычу: ровно 59 пар дружественных чисел. И это в короткий период – с 1747 года по 1750 год!
Выход европейцев
Независимо от ибн аль-Банна, спустя более чем 300 лет, в 1636 году, эту же пару открыл Пьер Ферма (1601–1665). Вскоре появилась третья «добыча», третья пара:
9 363 584 и 9 437 056,
в результате изысканий выполненных Рене Декартом (1596–1650) в 1638 году.
О датах и обстоятельствах этих двух открытий имеются самые точные сведения. Хотя и в то время проблема обмена новыми знаниями еще не была решена – издание книг занимало длительное время, а математических журналов не существовало, – тем не менее, дело обстояло значительно лучше, чем во времена Пифагора.
Ученые письменно сообщали о своих открытиях французскому математику, физику, философу и богослову Марену Мерсенну (1588–1648), который на протяжении первой половины XVII века был по существу координатором научной жизни Европы, ведя активную переписку практически со всеми видными учёными того времени.
Такое извещение было равноценно письму, отправляемому в настоящее время в редакцию математического журнала. Ферма и Декарт также написали Мерсенну, который в предисловии к своей ближайшей книге назвал их открытия крупными достижениями гениальных математиков.
Наше время
С наступлением эры вычислительной техники возник новый метод, о котором Эйлер не мог и помышлять, – перебирать все числа подряд, пока хватит машинного времени. Как отнеслись к этому грубому натиску конкурентов тонкие искусные ловцы, охотящиеся за числами подобно Эйлеру, Пуле и Ли?
Трудно передать их чувства. Представьте себе страстного рыболова-любителя, неожиданно замечающего у ручья людей, которые просто осушают русло и затем спокойно собирают рыбу! Впрочем, при этом обнаружилось, что рыболовы удили весьма успешно и выловили почти всю рыбу, так что «браконьерам» досталась лишь довольно скромная добыча.
К настоящему времени счёт в коллекции дружественных чисел пошёл на миллионы. Из этой коллекции ровно 13 пар дружественных чисел размещаются на отрезке [1; 100 000]:
220 и 284,
1 184 и 1 210,
2 620 и 2 924,
5 020 и 5 564,
6 232 и 6 362,
10 744 и 10 856,
2 285 и 14 595,
17 296 и 18 416,
63 020 и 76 084,
66 928 и 66 992,
67 095 и 71 145,
69 615 и 87 633,
79 750 и 88 730.
Дружественные числа продолжают скрывать множество тайн. Пока неизвестно, конечно или бесконечно множество пар дружественных чисел. Может случиться так, что это никогда не станет известно. Впрочем венгерский математик Пауль Эрдёш (1913–1996) доказал, что дружественные числа имеют плотность 0, т.е. их доля среди чисел, не превосходящих х, стремится к 0 с ростом х.
На сентябрь 2007 года было известно 11 994 387 пар дружественных чисел. Все они состоят из чисел одной чётности. Существует ли чётно-нечётная пара дружественных чисел, неизвестно. Также неизвестно, существуют ли взаимно простые дружественные числа, но если такая пара дружественных чисел существует, то, согласно расчетам, их произведение должно быть больше 1067.
И, наконец, неизвестно существует ли общая формула, позволяющая описать все пары дружественных чисел.
Общительные числа
В XX веке математики обобщили понятие дружественных чисел и занялись поиском дружественных рядов или общительных чисел – замкнутых циклов из трех и более чисел. Например, в тройке чисел
1 945 330 728 960; 2 324 196 638 720; 2 615 631 953920
делители первого числа в сумме дают второе число, делители второго в сумме дают третье число, а делители третьего числа в сумме дают первое число. А вот – пятёрка общительных чисел:
12 496, 14 288, 15 472, 14 536, 14 264.
Самый длинный из известных циклов найден в 1918 году и состоит из 28 чисел:
14316, 19116, 31704, 47616, 83328, 177792, 295488, 629072, 589786, 294896, 358336, 418904, 366556, 274924, 275444, 243760, 376736, 381028, 285778, 152990, 122410, 97946, 48976, 45946, 22976, 22744, 19916, 17716.
Примеры:
Ниже приведены все пары дружественных чисел, меньших 100 000.
- 220 и 284 (Пифагор, около 500 дон. э.)
- 1184 и 1210 (Паганини, 1860)
- 2620 и 2924 (Эйлер, 1747)
- 5020 и 5564 (Эйлер, 1747)
- 6232 и 6368 (Эйлер, 1750)
- 10744 и 10856 (Эйлер, 1747)
- 12285 и 14595 (Браун, 1939)
- 17296 и 18416 (Ибн ал-Банна, около 1300, Фариси, около 1300, Ферма, Пьер, 1636)
- 63020 и 76084 (Эйлер, 1747)
- 66928 и 66992 (Эйлер, 1750)
- 67095 и 71145 (Эйлер, 1747)
- 69615 и 87633 (Эйлер, 1747)
- 79750 и 88730 (Рольф (Rolf), 1964)
Происхождение дружественных и совершенных чисел
Следующие 200 лет
По словам немецкого математика Вальтера Боро, дальнейшую историю поисков дружественных чисел можно сравнить с охотой за экзотическими бабочками:
найти новый экземпляр чрезвычайно трудно, но если вооружиться правильной методикой и необходимыми познаниями и проявить ловкость и настойчивость, то иногда все же удается его поймать (если к тому же еще и повезет). Очарование такой охоты и радость при каждой удаче, очевидно, и побуждали Эйлера не довольствоваться тремя, четырьмя примерами, а искать все новые и новые числа.
Следующим математиком после Эйлера, кто пополнил коллекцию дружественных чисел, но только одной парой, был наш выдающийся соотечественник Пафнутий Львович Чебышёв (1821–1894), в 1851 году, а за ним – и тоже только одной парой, в 1866 году, – шестнадцатилетний итальянец Николо Паганини, тезка великого скрипача. Он «изловил» вторую – по величине – пару дружественных чисел:
1 184 и 1 210.
Математический мир был потрясён – эту пару, ближайшую к 220 и 284, проглядели все знаменитые математики, изучавшие дружественные числа!
Но превзойти Эйлера по количеству новых «пойманных экзотических бабочек» никому из математиков не удавалось на протяжении 200 лет, вплоть до середины ХХ века.
Первым побил рекорд Эйлера бельгиец Поль Пуле – 62 новые пары к 1948 году – причем свою монографию Пуле озаглавил так: «La chasse aux nombres» («Охота за числами»).
Следующей рекордной «добычи» достиг американец Элвин Дж. Ли – 300 пар за период с 1968 по 1972 годы. И хотя он оперировал методами Эйлера, в несколько усовершенствованной форме, но при этом пользовался помощью ЭВМ, предшественников современных компьютеров.
Совершенные и дружественные числа
История совершенных и дружественных чисел восходит к глубокой древности. Ими интересовались пифагорейцы, которые стремились выразить на языке чисел всё на свете, включая понятия справедливости (см. предыдущий урок), совершенства и дружбы.
называется число, равное сумме всех своих делителей, исключая само это число. Первые два совершенных числа – это 6 и 28:
6 = 1 2 3,
28 = 1 2 4 7 14.
В «Началах» Евклида приводится теорема (вероятно, пифагорейского происхождения), позволяющая искать последующие совершенные числа: если число p = 2n – 1 простое, то число 2n – 1p совершенное. Доказательство состоит в следующем. У числа 2n – 1p делители такие:
1, 2, 22, 23, …, 2n – 1,
p, 2p, 22p, 23p, …, 2n – 1p.
Поскольку 1 2 22 23 … 2n – 1 = 2n – 1 = p, то сумма делителей числа 2n – 1p, кроме его самого, равна (2n – 1) (2n – 1 – 1) p = p 2n – 1p – p = 2n – 1p, таким образом, число 2n – 1p совершенное.
Так, например, если n = 2, то p = 2n – 1 = 22 – 1 = 4 – 1 = 3 – простое, и 2n – 1p = 2 ∙ 3 = 6 – совершенное;
если n = 3, то p = 2n – 1 = 23 – 1 = 8 – 1 = 7 – простое, и 2n – 1p = 22 ∙ 7 = 4 ∙ 7 = 28 – совершенное;
если n = 4, то p = 2n – 1 = 24 – 1 = 16 – 1 = 15 – составное;
если n = 5, то p = 2n – 1 = 25 – 1 = 32 – 1 = 31 – простое, и 2n – 1p = 24 ∙ 31 = 16 ∙ 31 = 496 – совершенное;
если n = 6, то p = 2n – 1 = 26 – 1 = 64 – 1 = 63 – составное;
если n = 7, то p = 2n – 1 = 27 – 1 = 128 – 1 = 127 – простое, и 2n – 1p = 26 ∙ 127 = 64 ∙ 127 = 8128 – совершенное.
Ямвлих (III–IV вв.) отметил, что любое четное совершенное число имеет вид 2n – 1 (2n – 1),
где (2n – 1) – простое (строго доказал это Л. Эйлер в XVIII в.).
Первые четыре совершенных числа (6, 28, 496 и 8128 – соответственно, при n = 2, 3, 5, 7) были известны уже древнегреческому математику Никомаху из Герасы (I–II вв.).
Редкость совершенных чисел служила некоторым средневековым авторам для иллюстрации того положения, что совершенство вообще редко встречается в жизни.
Пятое совершенное число было найдено лишь в XV в. Оно соответствует n = 13 и равно 33 550 336.
Видна некоторая закономерность: совершенные числа получаются при простых n. Это не случайно. Дело в том, что если n составное, то число (2n – 1) тоже составное. В самом деле, пусть n = kl, тогда 2n – 1 = 2kl – 1 = (2k – 1) (2k (l – 1) 2k (l – 2) … 1). А значит, при составных n число 2n – 1 (2n – 1) не будет совершенным.
Верно ли обратное – то есть при всяком ли простом n число (2n – 1) является простым? До XVI в. многие так думали, пока не было обнаружено, что это не так: (211 – 1) = 2047 = 23 ∙ 89. Соответственно, и число 2n – 1 (2n – 1) при n = 11 не совершенно.
Возникла серьезная проблема: при каких простых n числа (2n – 1) являются простыми (а числа 2n – 1 (2n – 1), соответственно, – совершенными)? Этой проблемой занимались многие математики, в т. ч. Марен Мерсенн, по имени которого числа вида (2n – 1) называются «числами Мерсенна» и обозначаются Mn. Мерсенн заявил (не вполне ясно, как он к этому пришел), что простыми будут числа вида (2n – 1), соответствующие n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 и 257, а составными – числа, соответствующие всем остальным n до 267, однако в случаях n = 67 и 257 он ошибся: это было обнаружено только в XX в. С другой стороны, в 1883 русский священник Иван Михеевич Первушин обнаружил, что, вопреки Мерсенну, число M61 простое; в начале XX в. оказалось, что простыми являются и числа M89 и M107. А вот насчет n = 127 Мерсенн был вполне прав, и соответствующее число 2126 (2127 – 1) совершенно (это двенадцатое совершенное число, в его записи больше 75 цифр).
В настоящее время обнаружено (с помощью компьютеров) больше 30 совершенных чисел; начиная с 34-го они соответствуют семизначным n. Развитой теории на эту тему пока не существует, известно только несколько общих закономерностей.
Открытым остается вопрос о том, существуют ли нечетные совершенные числа. Пока удалось определить лишь некоторое количество условий, которым эти числа должны удовлетворять, если они вообще существуют.
называются такие два числа, что сумма делителей первого (кроме его самого) равна второму, а сумма делителей второго (опять же кроме его самого) равна первому. Согласно позднейшему преданию, Пифагор некогда сказал, что считать своим другом следует «того, кто является моим вторым Я, как числа 220 и 284».
Попробуйте проверить, что числа 220 и 284 действительно дружественные.
| Решение |
220 = 2 ∙ 2 ∙ 5 ∙ 11; делители 220 – это 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110, 220; 1 2 4 5 10 11 20 22 44 55 110 = 284; 284 = 2 ∙ 2 ∙ 71; делители 284 – это 1, 2, 4, 71, 142, 284; 1 2 4 71 142 = 220. |
Арабский математик IX в. Сабит ибн Корра написал «Книгу о нахождении дружественных чисел легким способом». Его способ похож на описанное в «Началах» Евклида правило нахождения совершенных чисел. А именно, если числа p = 3 ∙ 2n – 1, q = 3 ∙ 2n – 1 – 1 и
r = p q pq простые, то числа М = 2npq и N = 2nr дружественные.
| Доказательство |
У числа M = 2npq делители такие: 1, 2, 22, 23, …, 2n, p, 2p, 22p, 23p, …, 2np, q, 2q, 22q, 23q, …, 2nq, pq, 2pq, 22pq, 23pq, …, 2npq. Сумма делителей числа M, кроме его самого, равна (1 2 22 23 … 2n – 1) (1 p q pq) 2n (1 p q) = = (2n – 1) ( 1 p q pq) 2n (1 p q) = = 2n (p q pq) 2n – (1 p q pq) 2n (1 p q) = = 2nr – (1 p) (1 q) 2n (2 p q) = = N – 9 ∙ 22n – 1 9 ∙ 22n – 1 = N. У числа N = 2nr делители такие: 1, 2, 22, 23, …, 2n, r, 2r, 22r, 23r, …, 2nr. Сумма делителей числа N, кроме его самого, равна (1 2 22 23 … 2n – 1) (1 r) 2n = (2n – 1) (1 r) 2n = = (2n – 1) (1 p q pq) 2n = 2npq 2n (1 p q) – (1 p q pq) 2n = = M 2n (2 p q) – (1 p) (1 q) = M 9 ∙ 22n – 1 – 9 ∙ 22n – 1 = M. |
Примером на правило Ибн Корры являются уже упомянутые числа 220 и 284 (в этом случае n = 2). Следующую пару дружественных чисел 17 296 и 18 416 (n = 4) обнаружил арабский математик Ибн ал-Банна (XIII–XIV вв.) из Марокко, а затем, независимо, П. Ферма. Третью пару 9 363 584 и 9 437 056 (n = 7) открыл Р. Декарт. В отличие от евклидова правила для совершенных чисел, правило Ибн Корры не универсально, а также не очень полезно: оказывается, помимо указанных трех случаев оно не дает никаких новых дружественных чисел при n < 20 000.
В XVIII в. Л. Эйлер разработал новые методы поиска дружественных чисел и нашел еще 61 их пару, в том числе нечетных (например, 69 615 и 87 633). Сейчас известно более тысячи пар, в том числе четыре пары четырехзначных чисел и восемь – пятизначных. Интересно, что вторую по возрастанию пару, 1184 и 1210, открыл в 1866 г. школьник Н. Паганини (однофамилец великого музыканта). Неизвестно, существуют ли смешанные пары из четных и нечетных чисел, конечно или бесконечно число пар и т. д.
