Досконалі числа • Євген Єпіфанов • Науково-популярні завдання на «Елементах» • Математика

Власний дільникнатурального числа - це будь-який дільник, крім самого цього числа. Якщо число дорівнює сумі своїх дільників, воно називаєтьсядосконалим. Так, 6 = 3 + 2 + 1 - це найменше з усіх досконалих чисел (1 не в рахунок), 28 = 14 + 7 + 4 + 2 + 1 - це ще одне таке число.

Досконалі числа були відомі ще в давнину і цікавили вчених у всі часи. У «Початках» Евкліда доведено, що й просте число має вигляд 2n– 1 (такі числа називають простими числами Мерсенна), то число 2n–1 (2n- 1) - досконале. А у XVIII столітті Леонард Ейлер довів, що будь-яке парне досконале число має такий вигляд.

Спробуйте довести ці факти та знайти ще пару-трійку досконалих чисел.

Підказка 1

а) Щоб довести твердження з «Початок» (що якщо просте число має вигляд 2n– 1, то число 2n–1 (2n– 1) ) - Довершене), зручно розглянути сигма-функцію, яка дорівнює сумі всіх позитивних дільників натурального числаn. Наприклад,σ(3) = 1 + 3 = 4, аσ(4) = 1 + 2 + 4 = 7. Ця функція має корисну властивість: вонамультиплікативна, тобтоσ(ab) =σ(a)σ(b); рівність виконується для будь-яких двох взаємно простих натуральних чиселaіb(взаємно простиминазиваються числа, які не мають спільних дільників). Цю властивість можна спробувати довести чи прийняти на віру.

За допомогою сигма-функції доказ досконалості числаN= 2n–1 (2n– 1) зводиться до перевірки того, щоσ(N) = 2N. Для цього стане в нагоді мультиплікативність цієї функції.

б) Інший шлях рішення не використовує жодних додаткових конструкцій на кшталт сигма-функції. Він спирається лише визначення досконалого числа: треба виписати все дільники числа 2n–1 (2n– 1) і знайти їх суму. Повинне вийти це число.

Підказка 2

Доводити, що будь-яке парне досконале число - це ступінь двійки, помножена на просте число Мерсенна, також зручно за допомогою сигма-функції. НехайN— якесь парне досконале число. Тодіσ(N) = 2N. ПредставимоNякN= 2k·m, деm— непарне число. Томуσ(N) =σ(2k·m) =σ>(2k)σ(m) = (1 + 2 + . + 2k)σ(m) = (2k+1 – 1)σ(m).

Виходить, що 2·2k·m= (2k+1 – 1)σ(m). Отже, 2k+1 - 1 ділить твір 2k+1 ·m, а оскільки 2k+1 - 1 і 2k+1 взаємно прості, тоmмає ділитися на 2k+1 – 1. Тобтоmможна записати у виглядіm= (2k+1 - 1) ·M. Підставивши цей вираз у попередню рівність і скоротивши на 2k+1 – 1, отримаємо 2k+1 ·M=σ(m). Тепер до закінчення доказу залишається лише один, хоч і не найочевидніший, крок.

У підказках міститься значна частина доказів обох фактів. Заповнимо тут кроки, що бракують.

1. Теорема Евкліда.

а) Спочатку треба довести, що сигма-функція дійсно мультиплікативна. Насправді, оскільки кожне натуральне число однозначно розкладається на прості множники (це твердження називають основною теоремою арифметики), достатньо довести, щоσ(pq) =σ(p)σ(q), деpіq- різні прості числа. Але досить очевидно, що в цьомувипадкуσ(p) = 1 +p,σ(q) = 1 +q, аσ(pq) = 1 +p+q+pq= ( 1 +p) (1 +q).

Тепер завершимо доказ першого факту: якщо просте число має вигляд 2n– 1, то числоN= 2n–1 (2n– 1) – досконале. Для цього достатньо перевірити, щоσ(N) = 2N(оскільки сигма-функція - це сумавсіхдільників числа, тобто сумавласнихдільників плюс саме число). Перевіряємо:σ(N) =σ(2n–1 (2n– 1)) =σ(2n–1 )σ(2n– 1) = (1 + 2 + . + 2n–1 )·((2n– 1) + 1) = (2n– 1)·2n= 2N. Тут було використано, що якщо 2n– 1 — просте число, тоσ(2n– 1) = (2n- 1) + 1 = 2n.

б) Доведемо остаточно і друге рішення. Знайдемо всі власні дільники числа 2n-1 (2n- 1). Це 1; ступеня двійки 2, 2 2 . 2n-1; просте числоp= 2n- 1; а також дільники виду 2m·p, де 1 ≤m≤n– 2. Підсумовування всіх дільників тим самим розбивається на підрахунок сум двох геометричних прогресій Перша починається з 1, а друга - з числа p ; у обох знаменник дорівнює 2. За формулою суми елементів геометричної прогресії сума всіх елементів першої прогресії дорівнює 1+2+. + 2n–1 = (2n– 1)/2 – 1 = 2n– 1 (і це дорівнюєp). Друга прогресія даєp·(2n–1 – 1)/(2 – 1) =p·(2n– 1 – 1). Отже, виходитьp+p·(2n–1 – 1) = 2n–1 ·p- те, що треба.

Швидше за все, Евклід не був знайомий із сигма-функцією (та й взагалі з поняттям функції), тому його доказ викладено дещоіншою мовою та ближче до рішення з пункту б). Воно міститься в пропозиції 36 з IX книги "Початок" і доступне, наприклад, тут.

2. Теорема Ейлера.

Перш ніж доводити теорему Ейлера, зазначимо ще, що якщо 2n- 1 - просте число Мерсенна, тоnтакож має бути простим числом. Справа в тому, що якщоn=km— складова, то2 km– 1 = (2k)m- 1 ділиться на 2k- 1 (оскільки виразx m- 1 ділиться наx- 1, це одна з формул скороченого множення). І це суперечить простоті числа 2n– 1. Зворотне твердження — «якщоn— просте, то 2n– 1 також просте» — не так: 2 11 - 1 = 23 · 89.

Повернемося до теореми Ейлера. Наша мета — довести, що будь-яке парне досконале число має вигляд, який отримав Євклід. У підказці 2 було намічено перші етапи докази, і залишилося зробити вирішальний крок. З рівності 2k+1 ·M=σ(m) випливає, щоmділиться наM. Але m ділиться також і на само себе. У цьомуM+m=M+ (2k+1 – 1)·M = 2k+1 ·M=σ(m). Це означає, що числоmне має інших дільників, крімMіm. Отже,M= 1, аm— просте число, яке має вигляд 2k+1 – 1. ТодіN= 2k·m= 2k(2k+1 - 1), що й потрібно.

Отже, формули доведено. Застосуємо їх, щоб знайти якісь досконалі числа. Приn= 2 формула дає 6, а приn= 3 виходить 28; це перші два досконалі числа. За властивістю простих чисел Мерсенна, нам потрібно підібрати таке простеn, що 2n- 1 буде також простим числом, а складовіnможна взагалі не розглядати. Приn= 5 вийде 2n- 1 = 32 - 1 = 31, це нам підходить. Ось і третє досконале число - 16 · 31 = 496. Про всяк випадок перевіримо його досконалість явно. Випишемо всі власні дільники 496: 1, 2, 4, 8, 16, 31, 62, 124, 248. Їхня сума дорівнює 496, так що все гаразд. Наступне досконале число виходить приn= 7, це 8128. Відповідне просте число Мерсенна дорівнює 27 - 1 = 127, і досить легко перевірити, що воно дійсно просте. А ось п'яте досконале число виходить заn= 13 і дорівнює 33 550 336. Але перевіряти його вручну вже дуже втомлює (проте це не завадило комусь відкрити його ще в XV столітті!).

Післямова

Перші два досконалих числа - 6 і 28 - були відомі з незапам'ятних часів. Евклід (і ми слідом за ним), застосувавши доведену нами формулу з «Початок», знайшов третє та четверте досконалі числа — 496 і 8128. Тобто спочатку було відомо лише два, а потім чотири числа з гарною властивістю «бути рівними сумі своїх дільників ». Більше таких чисел виявити не могли, та й ці, на перший погляд, нічого не поєднувало. В епоху давнини люди були схильні вкладати містичний сенс у таємничі та незрозумілі явища, тому й досконалі числа набули особливого статусу. Піфагорійці, які сильно вплинули на розвиток науки і культури того часу, також посприяли цьому. "Все є число", - говорили вони; число 6 у тому вченні мало особливими магічними властивостями. А ранні тлумачі Біблії пояснювали, що світ був створений саме на шостий день, тому що число 6 — найдосконаліша серед чисел, бо вона перша серед них. Також багатьом здавалося невипадковим, що Місяць робить оберт навколо Землі приблизно за 28 днів.

П'яте досконале число - 33550336 - було знайдено тільки в XV столітті. Ще майже через півтора століттяіталієць Катальді знайшов шосте і сьоме досконалі числа: 8 589 869 056 і 137 438 691 328. Їм відповідаютьn= 17 іn= 19 у формулі Евкліда. Зверніть увагу, що рахунок йде вже на мільярди, і страшно навіть уявити, що всі обчислення були зроблені без калькуляторів та комп'ютерів!

Повернемося до парних досконалих чисел. Дев'яте число було знайдено 1883 року сільським священиком з Пермської губернії І. М. Первушиним. У тому числі 37 цифр. Таким чином, до початку XX століття було знайдено лише 9 досконалих чисел. У цей час з'явилися механічні арифметичні машини, а в середині століття – перші комп'ютери. З їхньою допомогою справа пішла швидше. Наразі знайдено 47 досконалих чисел. Причому лише перші сорок відомі порядкові номери. Ще про сім чисел поки що точно не встановлено, які вони за рахунком. Здебільшого пошуком нових мерсенівських простих (а з ними і нових досконалих чисел) займаються учасники проекту GIMPS (mersenne.org).

У 2008 році учасниками проекту було знайдено перше просте число, в якому більше 10 000 000 = 107 цифр. За це вони отримали приз $100 000. Грошові призи 150 000 і 250 000 доларів також обіцяні за прості числа, що складаються з більш ніж 108 і 109 цифр відповідно. Передбачається, що із цих грошей отримають винагороду і ті, хто знайшов менші, але ще не відкриті прості числа Мерсенна. Щоправда, на сучасних комп'ютерах перевірка чисел такої довжини на простоту займе роки, і це, мабуть, справа майбутнього. Найбільше просте число на сьогодні дорівнює 243112609 - 1. Воно складається з 12 978 189 цифр. Зазначимо, що завдяки тесту Люка-Лемера сильно спрощується перевірка на простоту чисел Мерсенна: не потрібно намагатися знайти хоча б один дільникчергового кандидата (це дуже трудомістка робота, яка для таких великих чисел практично нездійсненна зараз).

У скоєних чисел є кумедні арифметичні властивості:

• Кожне парне досконале число є також трикутним числом, тобто у вигляді 1 + 2 + . +k=k(k+ 1)/2 для деякогоk.
• Кожне парне досконале число, крім 6, є сумою кубів послідовних непарних натуральних чисел. Наприклад, 28 = 1 3 + 3 3 , а 496 = 1 3 + 3 3 + 5 3 + 7 3 .
• У двійковій системі числення досконале число 2n-1 (2n- 1) записується дуже просто: спочатку йдутьnодиниць, а потім -n- 1 нулів (це випливає з формули Евкліда). Наприклад, 610 = 1102, 2810 = 111002, 3355033610 = 11111111111111000000000002.
• Сума чисел, зворотних усім дільникам досконалого числа (саме число тут також бере участь), дорівнює 2. Наприклад, 1/1 + 1/2 + 1/4 + 1/7 + 1/14 + 1/28 = 2.

---