О. ОРЕ - Приглашение в теорию чисел

Запишем сумму этих делителей

1 + 2 +… + 2 р -1+ q (1 + 2 +… + 2 р -1),

которая равна

(1 + 2 +… + 2 р -1)( q + 1) = (1 + 2 +… + 2 р -1) 2 р

Если вы не помните формулы для суммы членов геометрической прогрессии,

S = 1 + 2 +… + 2 р -1,

то умножьте эту сумму на 2:

2 S = 2 + 2 2+… +2 р -1+ 2 р ,

а затем, вычтя S , получите

S = 2 p — 1 = q .

Таким образом, сумма всех делителей числа Р есть

2 p q = 2 • 2 p -1 q,

а сумма всех делителей, кроме самого числа Р = 2 p -1 q , равна

2 2 p -1 q — 2 p -1 q = 2 p -1 q = Р.

Итак, наше число является совершенным.

Из этого результата следует, что каждое простое число Мерсенна порождает совершенное число. В § 2 второй главы говорилось, что известно всего 23 простых числа Мерсенна, следовательно, мы знаем также и 23 совершенных числа. Существуют ли другие виды совершенных чисел? Все совершенные числа вида (3.4.1) являются четными, можно доказать, что любое четное совершенное число имеет вид (3.4.1). Остается вопрос: существуют ли нечетные совершенные числа? В настоящее время мы не знаем ни одного такого числа, и вопрос о существовании нечетных совершенных чисел является одной из самых знаменитых проблем теории чисел. Если бы удалось обнаружить такое число, то это было бы крупным достижением. Вы можете поддаться соблазну найти такое число, перебирая различные нечетные числа. Но мы не советуем этого делать, так как по последним сообщениям Брайена Такхермана из IBM [7] Американская фирма, выпускающая вычислительное оборудование. ( Прим. перев. ) (1968), нечетное совершенное число должно иметь по крайней мере 36 знаков.

Система задач 3.4.

1. Используя список простых чисел Мерсенна, найдите четвертое и пятое совершенные числа.

Дружественные числа также входят в наследство, доставшееся нам от греческой нумерологии. Если у двух людей имена были таковы, что их числовые значения удовлетворяли следующему условию: сумма частей (делителей) одного из них равнялась второму числу, и наоборот, то считалось, что это свидетельствует об их духовной близости. В действительности греки знали всего лишь одну пару таких чисел, а именно:

220 = 2 2• 5 • 11, 284 = 2 2 • 71.

Суммами их делителей являются соответственно

1 + 2 + 4 + 5 +10 + 20 + 11 + 22 + 44 + 55 + 110 = 284,

1 + 2 + 4 + 71 + 142 = 220.

Эта пара дружественных чисел оставалась единственной известной до тех пор, пока Пьеру Ферма не удалось найти следующую пару:

17 296 = 2 4 • 23 • 47, 18 416 = 2 4 • 1151.

Поиски пар дружественных чисел чрезвычайно удобно вести с помощью ЭВМ. Для каждого числа n при помощи машины определяются все делители этого числа (≠ n ) и их сумма m . После этого производится такая же операция с числом m . Если при этом вновь получается первоначальное число n , то пара чисел ( n, m ) оказывается дружественной. Недавно этим способом в Йельском университете на ЭВМ IBM 7094 были проверены все числа до одного миллиона. В результате была получена коллекция из 42 пар дружественных чисел; некоторые из них оказались ранее неизвестными. Все пары дружественных чисел до 100 000 приведены в табл. 2. При помощи этого метода, как нетрудно видеть, одновременно «вылавливаются» и совершенные числа. Если возникает желание продолжать поиски дальше, то, конечно, это можно сделать, но придется затратить большое количество машинного времени.

Таблица 2

Дружественные числа до 100 000

В действительности мы очень мало знаем о свойствах пар дружественных чисел, однако, можно на основе наших таблиц высказать несколько предположений. Например, отношение одного из них к другому, по-видимому, должно все больше и больше приближаться к 1 по мере того, как они увеличиваются. Из таблицы видно, что эти числа бывают либо оба четными, либо оба нечетными, но не было найдено случая, когда одно число четно, а другое нечетно, хотя поиски дружественных чисел такого вида были проведены среди всех чисел n ≤ 1 3 000 000 000.

Откровенно говоря, мы надеемся, что многое в этой главе окажется для вас знакомым.

В ней рассматриваются понятия, с которыми вы познакомились в школе, как только научились обращаться с обыкновенными дробями. Единственным оправданием включения этого материала является желание освежить его в вашей памяти. Мы также надеемся, что приведенное изложение материала явится более систематическим, чем то, к которому вы привыкли.

Возьмем некоторую дробь а/b , отношение двух целых положительных чисел а и b . Обычно мы стараемся привести ее к простейшему виду, т. е. мы стараемся сократить множители, общие для а и b .

Эта операция не изменяет значения дроби, например,

24/36 = 8/12 = 2/3.

Общим делителем двух натуральных чисел а и b называется натуральное число d , которое является множителем как числа а , так и числа b , т. е.

a = d • а 1, b = d • b 1.

Если число d — общий делитель чисел а и b , то он также делит числа а + b и а — b , так как

а + b = а 1 d + b 1 d = ( а 1+ b 1) d ,

а — b = а 1 d — b 1 d = ( а 1— b 1) d .

Когда известны разложения чисел а и b на простые множители, нетрудно найти все их общие делители. Выпишем эти два разложения на простые множители:

а = р 1 α 1• … • р r α r , b = р 1 β 1• … • р r β r . (4.1.1)

Здесь мы договариваемся записывать разложения чисел а и b так, как если бы они имели одинаковые простые множители

р 1, p 2…, р r

но с условием, что мы допускаем возможность использования показателя степени, равного 0. Например, если p 1 делит число а , но не делит число b , мы полагаем, что в формуле (4.1.1) β 1= 0. Таким образом, если

а = 140, b = 110, (4.1.2)

то

а = 2 2 • 5 1 • 7 1 • 11 0, b = 2 1• 5 1• 7 0• 11 1. (4.1.3)

Из формулы (4.1.1) следует, что любой делитель d числа а может иметь простыми множителями только числа p i , которые встречаются в числе а и каждое из них содержится в степени δ i , не превосходящей соответствующей степени α i в числе а . Аналогичные условия имеют место и для любого делителя d числа b . Поэтому общий делитель d чисел а и b может иметь в качестве простых множителей только числа p i , которые встречаются одновременно в числах а и b , а степень δ i числа p i в d не может превосходить меньшей из двух степеней: α i и β i .