Вступление
В этой статье мы рассмотрим некоторые особенности нечетных чисел и их делителей, а также выделим некоторые подклассы нечетных чисел, среди которых точно не содержатся совершенные числа. И, конечно же, позанимаемся доказательством того, почему это именно так :)
Давайте начнем с нужной нам терминологии и небольшой предыстории.
1. Совершенные числа
Определение
Натуральное число N называется совершенным, если сумма всех его делителей, отличных от самого N, равна N.
Сумму делителей числа N, отличных от N, будем для удобства обозначать S(N).
Примеры
6 — совершенное число, потому что делители числа 6 — это 1, 2, 3 и 6, причем 6=1+2+3 (последний делитель, 6, мы не рассматриваем по определению). То есть S(6) = 1+2+3 = 6.
10 же, наоборот, НЕ является совершенным числом, так как делители 10 — это 1, 2, 5 и 10, но S(10) = 1+2+5 = 8, а не 10.
Вот первые (наименьшие) 5 совершенных чисел:
6 = 1+2+3
28 = 1+2+4+7+14
496 = 1+2+4+8+16+31+62+124+248
8128 = 1+2+4+ ... +2032+4064
33550336 = 1+2+4+ ... +16775168
2. Нерешенные вопросы о совершенных числах
Если посмотреть на приведенные примеры совершенных чисел, можно заметить, что они все четны. На самом деле человечеству пока что неизвестно ни одного нечетного совершенного числа. Но и не доказано, что их нет. Известно лишь, что если нечетное совершенное число есть, то оно превышает 10 в степени 1500.
Также, открытым является и вопрос о том, бесконечно ли множество четных совершенных чисел. Но в этой статье мы не будем останавливаться на этом пункте.
3. Подробнее о нечетных совершенных числах
Поговорим теперь о некоторых классах нечетных чисел и поймем, почему эти классы не содержат совершенных чисел.
i. Простые нечетные числа
По определению, простые числа делятся только на 1 и на себя. То есть, если p — простое число, то S(p) = 1 < p. То есть, простые числа не являются совершенными.
ii. Степени простых нечетных чисел
Предположим, что p — простое число. Пусть N — степень p.
Этот случай тоже не очень трудный:
(При переходе, обозначенном звездочкой, мы воспользовались формулой суммы геометрической прогрессии)
iii. Немного жести :)
Пусть нечетное N>1 не делится на некоторое нечетное простое число p. Кстати, обозначать это будем так:
Попробуем выразить сумму делителей произведения Np, то есть посмотреть, что происходит с S(Np), и как оно соотносится с S(N). Во-первых, заметим, что все делители числа N также являются делителями числа Np. То есть,
S(Np) = S(N) + новые делители
Во-вторых, N не входило в S(N), но появляется в S(Np). То есть,
S(Np) = S(N) + N + еще что-то
Ну а в-третьих, теперь не хватает лишь таких делителей, которые содержат p как множитель. А это как раз все делители N, помноженные на p (кроме самого Np), то есть pS(N). (Здесь даже учтено, что нет слагаемого Np, так как в S(N) нет N)
Итак, итоговая формула такова:
или, после небольшого преобразования:
Теперь вспомним, что тема поста — совершенные числа :)
То есть вообще-то нам бы было хорошо, если бы S(Np) = Np. Ну или наоборот, доказать, что этого не бывает, например. Итак, поработаем с равенством S(Np) = Np. Ах да.. Волшебные слова.. Кхе-кхм. ПРЕДПОЛОЖИМ! что существует нечетное N>1, простое нечетное p, такие что!
Распишем S(Np) по формуле (1), а затем преобразуем полученное равенство:
Так как p нечетно, то cуществует некоторое целое k такое, что p=2k+1. Подставим данное выражение для p в наше равенство:
Посмотрим на четность/нечетность некоторых выражений. Покажем, для начала, что k не может быть нечетным. В самом деле, допустим, что k нечетно. Тогда правая часть равенства (2) будет нечетна (N нечетно, k нечетно, а произведение двух нечетных чисел тоже нечетно), а левая обязательно будет четной, потому что скобка (k+1) точно четна (раз само k нечетно), а произведение любого целого числа (например, S(N) ) на четное дает в результате тоже четное число. Но левая и правая части должны быть равными. Два числа разной четности не могут быть равны, и полученное противоречие приводит нас к выводу, что k может быть только четным (мы предполагали, что оно нечетное и получили противоречие).
Итак, что же из этого следует? Что теперь правая часть равенства (2) четна, а следовательно и левая должна быть четной. НО! k+1 явно нечетно, если k четно. Это может означать лишь одно. S(N) должно быть четным. Без этого условия наше равенство (2) оказывается неверным и Np не является совершенным числом.
** передышка **
Давайте остановимся на минутку и поймем, что это означает в контексте темы статьи. Мы хотим найти как можно больше нечетных чисел, про которые можно будет с уверенностью сказать: "это число не является совершенным". Если задуматься, мы только что получили инструмент генерации таких чисел. Посмотрите, если вдруг встретилось нечетное число N>1 такое, что S(N) нечетно, то можно взять любое простое p, на которое N не делится, и тогда число Np точно не будет совершенным.
Например, пусть N=5. Тогда S(N)=S(5)=1. (5 делится только на 1 и на 5, которая не в счет). Как видим, S(N)=1 нечетна, а значит, можно взять любое простое число, кроме 2 (потому что 2 четно) и 5 (потому что N делится на 5), например p=3, или p=7, или p=11, помножить его на N=5 и вуаля! получим число, которое, согласно нашим рассуждениям не будет совершенным. То есть не являются совершенными числа:
Заметьте, простых чисел бесконечно много, то есть этот список (и это только с пятеркой!) можно продолжать сколь угодно долго.
Back to hardcore
Заключительная выкладка будет посвящена следующему вопросу:
Пусть N>1, N нечетно. Как определить, является ли S(N) четным?
Зная ответ на этот вопрос мы сможем легко строить такие N.
Итак, приступим. Разложим N на простые сомножители.
Теорема 1.
Доказательство.
ч.т.д.
Эта формула чем-то похожа на формулу (1) и выводится тоже примерно так же (можете убедиться в этом сами в качестве упражнения).
Теорема 2.
Доказательство.
Представим число N в виде произведения:
В этом случае применима формула (3):
Лемма 1. Если S(M) нечетно, то и S(N) нечетно.
Доказательство леммы.
Индукция по r.
База индукции: при r=1 получаем уже доказанную Теорему 1.
Индукционный шаг:
Лемма доказана.
Лемма 2. Если S(M) четно, то S(N) четно тогда и только тогда, когда четно r.
Доказательство леммы.
Индукция по r.
База индукции: при r=1 получаем уже доказанную Теорему 1.
Индукционный шаг:
Лемма доказана.
Для завершения доказательства самой теоремы 2 осталось лишь заметить, что
Действительно сумма делителей (кроме самого p) степени n простого нечетного числа p состоит из n нечетных слагаемых.
Вот и получается, что если все степени простых чисел в разложении N четны, то можем применить m-1 раз лемму 2 к изначальному числу
последовательно достраивая это число до N.
Если же какая-то из степеней будет нечетной, то на соответствующем шаге мы получим нечетную сумму делителей и далее уже применяем лемму 1 достраивая число до N.
ч.т.д.
Заключение.
Итак, чтобы построить какое-нибудь нечетное несовершенное число, совсем не обязательно перебирать все нечетные числа и искать сумму их делителей. Достаточно составить произведение из степеней простых нечетных чисел, причем так, чтобы хотя бы один из показателей этих степеней был нечетным, а затем домножить это число на простое нечетное, на которое изначальное не делится :)
Надеюсь было интересно :D