On odd perfect numbers.pdf Введение. Постановка задачи Совершенное число (др.-греч. аргбцО^ теХею^) - натуральное число, равное сумме всех своих собственных делителей (т.е. всех положительных делителей, отличных от самого числа). Совершенные числа образуют последовательность: 6, 28, 496, 8128, 33550336, 8589869056, 137438691328, ... (последовательность A000396 в OEIS). По мере того как натуральные числа возрастают, совершенные числа встречаются всё реже. Алгоритм построения чётных совершенных чисел описан в IX книге Начал Евклида, где было доказано, что число 2P-1(2P-1) является совершенным, если число M = 2P-1 является простым (так называемые простые числа Мерсенна) [1]. Числа Мерсенна получили известность в связи с эффективным тестом простоты Люка - Лемера, благодаря которому простые числа Мерсенна давно удерживают лидерство как самые большие известные простые числа, однако неизвестно, бесконечно ли множество этих чисел. Впоследствии Леонард Эйлер доказал, что все чётные совершенные числа имеют вид, указанный Евклидом, но нечётных совершенных чисел до сих пор не обнаружено, однако не доказано и то, что их не существует. Известно, что нечётное совершенное число, если оно существует, имеет не менее 2800 (!) различных простых делителей [2]. Также известно, что нечётных совершенных чисел нет в интервале [1,., 102500]. Поиском нечётных совершенных чисел занимается проект распределённых вычислений OddPerfect.org. Таким образом, возникает гипотеза о том, что нечётных совершенных чисел не существует. Займёмся проверкой этой гипотезы. §1. Необходимое условие Пусть S - некоторое натуральное число, тогда по основной теореме арифметики имеем о a a 1 й„ S = P11 • P22 ••• Pn-11 • Pn" , где Pi - простые числа, a - некоторые натуральные числа, a > 1, n - количество сомножителей числа S (здесь и далее i = 1,...,n). Если pn> pn-1 >...> p1, то такое представление единственно и называется каноническим. Сумма всех положительных делителей S равна D = (1 + p + pp2 + ...+ p^1 )(1 + p2 + p22 + ...+ pa22 )-(i + Pn + pl +... + pann) или, с учётом формулы для суммы геометрической прогрессии, d p+a1 -1 p}+a2 -1 p;an -1 (pI - 1) (2 -1) (pn -1) . Пусть S - совершенное число. Из определения совершенного числа следует S=(1+p+p2 +...+pa1)-(1+pn+pi+...+pan)-s , p1+a1 - 1 pl + a2 -1 pl + an - 1 или --^-----^-= 2 . (1) (p - (pi - 1)p? (pn - 1)pan Уравнение (1) - это диофантово уравнение с неопределенным числом неизвестных (содержащее 2n неизвестных, значение n - количество сомножителей некоторого числа не фиксировано). §2. О системах уравнений, эквивалентных формуле (1) Перепишем равенство (1) в следующем виде: p^ - 1 = 2 (2 - 1) p^2 ... (pn - 1)pan (p - 1)pa p2+a2 -1 pl:an -1 Обозначим 4 aj j Q = 2(pi -1)*pa2 (pn -1)*pa/ = 2п(pj - 1)p. 1 1+a2 i „1+a„ л 1 1 p2+a2 -1 pl:an -1 J=1 pl;aJ -1 Рассмотрим следующее уравнение: p11+a1 -1 --= q1. (2) (p - 1)p1a1 Согласно равенству (1), Qi = qi, i = 1,...,n. Очевидно, что 2 > q1 > 1. При ai > 1 и p(i) < pi (p(i) - i-е по счёту простое число, i = 1,...,n) выполняются неравенства 1+a,- -t < p> i -1 < p> pt +1 < p (i+1) p (i +1)-1 i=1 (p-1 )pa pi-1 Из уравнения (2) с учётом того, что 1 < a1 < получаем неравенства p1 . = 1 > q1 > Л±1 = 1 + ± > 1; p -1 p -1 p p Из последнего неравенства следует, что 1 ■> Pi -1 ^ --т +1 > Р{. q -1 - - ^P1 - 1 7 q -1 P1 q-1 P1-1 q1-1 Значит, из формулы (2) при 1 < а1 < получаем неравенства 1 1 1 -> q -1- +1 > P1 - (3) q -1 1 q1-1 Поскольку p1 - натуральное число, то оно определяется однозначно: 1 - - целое, если q1-1 P1 =1 q -1 +1, если - - - нецелое. . q1-1 q1 -1 q -1_ С учётом определения функции «потолок» получаем более удобную запись этого условия: 1 P1 =-1 . q -1 Для показателя степени а1 из того же уравнения (2) получаем следующую зависимость: а = ~1п(Я\ - P1 (q1 -1)) 1 l"( P1) Таким образом, при заданном рациональном числе q1 натуральные значения р1 и а1 определяются однозначно. Аналогично получаются значения pi и ai для i = 2,...,п. Заметим, что значение (Р1 -1)Р/ = P11 _= р -jpi^pld 1 1 + (Р1 + •••Р11 ) 1 1 q-1 р1a1 -1 -1 р? -1 1 + Р1 + ... р1 (Р1 -1)pl1 может быть целым только при а1 = 1. Поскольку, согласно уравнению (1), Qi = qi, i = 1,...,п, то, заменив значения qt на Qi, получаем систему из 2п уравнений с 2п неизвестными: a = -l"(Q1 - Р1 (Q1 -1)) -1; 1 l"( Р1) 1 - 2, Р1 = Q1 -1 (4) - Р (n), an - 1 Pn = Qn -1 ln( Pn ) где (P1 -1) pl (-1 -1) pou (p+1 - 1)рГ++1 (Pn -1)pl Й = 2 1+a 1 P1 1 -1 1+ a, P1-1i ^ 1 + Li, P1+1i+ p: an -1 n\i = 2П ^ 1 j=1 Pj ' -1 (- 1)р?. г=r , n. Очевидно, что если некоторый набор чисел {pi, ai, i = 1,...,n} удовлетворяет системе (4), то он будет также являться решением уравнения (1). Заметим, что возможна прямая подстановка всех неизвестных в каждое из уравнений системы (4), что даёт систему уравнений от одной переменной вида f (p ) = 0; i =1,...,n, 1 fn, (at ) = 0, () но уже при малых значениях n запись этих уравнений сверхгромоздка, их «этажность» растёт как ~nn. Из теории систем алгебраических уравнений известно, что в общем случае (без ограничений на целостность показателей степеней ai и простоту чисел p) при данном n система уравнений (*) имеет конечное число решений, если выполнены два условия: 1) каждое из уравнений системы (*) имеет конечное число решений (при n = 2 это не так); 2) отсутствуют эквивалентные между собой уравнения. Рассмотрим теперь уравнение (1) с точки зрения понятия «делимость». Число (1 + p1 + pj2 +... + p^) может делиться только на те простые числа, которые являются сомножителями числа S и, возможно, ещё на число 2, очевидно также, что оно не делится на число p1, т.е. l+a1 1 n\1 (, Л (1+p + p? +...+pa1)=p-= ■ p1) Y\p;(u), v 7 (p-1) J=T J где 5(a1, p1) формально определяется так: Г 0, если p1 = 2, 5(a1, p1 ) = 2 одно и только одно из чисел 2S(a', pi) равно 2, остальные равны 1), a(1j) - некоторое неотрицательное число (параметр). Следовательно, получаем следующую формальную систему уравнений: l+a1 1 n\1 (1 ,) p_-1 = О^, p )ТГpa J • • (p 1) 2 П ' 1+a 1 1 (5) n1+an 1 n-1 , n = 2«(an, pn )TTpfj); Ya(',J )= at; i = 1,..., n. (p -1) 11 J ^ _ \Pn 4 J=1 J=1 С учётом того, что разложение натуральных чисел на множители определяется однозначно, система уравнений (5) является системой c 2n уравнениями и с 2n неизвестными (не с (n2+n) неизвестными). Числа a(lj) однозначно определяются некоторой функцией факторизации F(pbabi, j) и считаются параметрами. Вычисление этих параметров является проблемой факторизации (разложения на множители) и сама эта задача намного сложнее исходной. Из системы (5) непосредственно следует, что ln (1 + 25 1(1+25(ai, pi )(p - 1)п j --1; i = 1,...,n, ln(pi) относительно значений pt получаем алгебраические уравнения степени ai+1, следовательно, неизвестные p и a могут быть выражены через параметры a(1,3) в явном виде. Система уравнений (5) при данном n также имеет конечное число решений, если в ней отсутствуют тождества и эквивалентные между собой уравнения. Таким образом, совместно две неэквивалентные системы (4) и (5) дают 4n уравнений при 2n неизвестных, что явно избыточно для вычисления значений p1 и a 1 при больших n (хотя и связано с существенными практическими трудностями) и ставит вопрос о разрешимости уравнения (1) при этих значениях n. §3. О показателе степени в системе уравнений (4) Рассмотрим уравнение ln (q - q-1 J 1 1 - ln -1 q -1 ^ q -1 (6) a = - 1 ln q -1 q -1 при q e Q; 2 > q > 1. Эта функция имеет бесконечно много разрывов второго рода (бесконечных) слева в точках q = ^у^ (I e N). Ниже приведён график (приблизительный: без учёта окрестностей точек разрыва и особенностей представления чисел с плавающей запятой в вычислительных системах) этой функции при 1 < q < 2. a 15 10 Покажем, что если предел an при qn^+1 существует, то он равен 1. Поскольку (в силу определения функции «потолок») 1 1 1 Рг _1 > Рг +1 > Р,+1 > Р,+1 _1 > Рг+1 +1 . Рг _ 1 (Рг _ 1) Ра Р, Рг+1 _ 1 (Р, +1 _ 1) Р,^ Р, +1 рПап _ 1 v2, или -=-> р1; Р1 _ 1 П2 _ 1 1+а1 л f 1+ 1-1- tli 1 Р2 2 _1 (Р1 _ 4 (Р2 _ ^Р? У \ п_1 Р1 1 _1 > 2^1 +--■ ==-> Р2 и т.д. .ШМ- _ 1 > р,1+а1 _ 1 В общем случае 1+- 1 -к+1 ■> pk; к = 1,...,n _ 1, (7) 2Пк-1 (Р, _ 1)Р/ _ 1 11/=1 1+ a, Р, ' _ 1 к_1 (p, _ 1) paJ причём необходимо Lk = 2^ j+ -- > 1. ,=1 Р/^ _1 Заметим, что это условие выполняется для всех достаточно больших значений Pi независимо от значений а, (поскольку для них значение Lk сколь угодно близко к 2), значит, существует лишь конечный набор значений {p,, i = 1,...,k-1}, при которых оно, возможно, неверно либо значение Lk не является минимальным. Таким образом, значения простых чисел pk ограничены. Например, поскольку при Pi>p(i) верны неравенства > CftziMl > Рi _1 1+а, Л „ Р, i _1 p, > P (i)_ 1 p(( 1 >р, +1 то из формулы (7) последовательно получаем 1 +--j=- > p2; 1 +--р=- > p3; 1 +--,==-> p4, если p3 > 17 и т.д. n_|_1 ..... Только значение pn не ограничено неравенством (7). С другой стороны, значение pn определяется из системы (4) при известных значениях pi,...,pn-1, а1,..., an-1 однозначно по формуле pn = -1-, значит, pn < -1--+1. Fn Qn _ 1 n Qn _1 Пусть значенияp, i = 1,...,n-1, заданы, множество {Х} - некоторый произвольный набор натуральных чисел, меньших n, и множество {aX} - набор показателей степеней с этими индексами. Заметим, что выполняется неравенство lim Q = 2 lim П (1+1М. = 2 П (Р1 -1 )*ni ,1 {axn W1=1 p!+ a1 _ 1 {n_!}^X} p!+a1 _ 1 fx\ Pi (поскольку сомножители p, здесь несокращаемы, кроме случая p, = 2). Значит, существует инфимум inf Qn (наибольшая нижняя грань) множества дискретных значений Qn, такой, что inf Qn>1 при некоторых значениях a, (включая несобственное значение + 1, то р1 = 2 либо (р21 + а2)/2 -1 (Р2 -1) 1+/1 1 чаем -1-= р/2 . Если а2 = 1, то (Р -1) Р1+а1 -1 L-1 = р2 = 2 р/1 -1; р11+а1 -1 = 2 р/ +1 - Д - 2 р/ +1; р + 2 р/1 = р/ +1 + 2, (Р1 -1) значит, 2 делится на р1. Таким образом, во всех случаях р1 = 2 . ) = 1, т.е. а2 = 1 = 1, т.е. а2 = 1 или р2 +1 = 2 р11. С учётом второго уравнения полу- Из аналогичных соображений приходим к выводу, что случай 2s(ai' Pl) = 2 невозможен (по условию p2 > 3), кроме случая pj = 2, p2 = 3, ах = а2 = 1. Подстановка значения pj = 2 в систему (5) при n = 2 в итоге даёт ту же формулу: S2 = 2ai(2ai+1 -1) , где 2"1 -1 и ах +1 - простые. Заметим, что при pj = 2 также следует обратное: n = 2 (согласно Л. Эйлеру), поэтому при n > 2 можно считать, что pj > 3 .

Скачать электронную версию публикации