Система задач 3.4.
1. Используя список простых чисел Мерсенна, найдите четвертое и пятое совершенные числа.
§ 5. Дружественные числа
Дружественные числа также входят в наследство, доставшееся нам от греческой нумерологии. Если у двух людей имена были таковы, что их числовые значения удовлетворяли следующему условию: сумма частей (делителей) одного из них равнялась второму числу, и наоборот, то считалось, что это свидетельствует об их духовной близости. В действительности греки знали всего лишь одну пару таких чисел, а именно:
220 = 22 • 5 • 11, 284 = 22 • 71.
Суммами их делителей являются соответственно
1 + 2 + 4 + 5 +10 + 20 + 11 + 22 + 44 + 55 + 110 = 284,
1 + 2 + 4 + 71 + 142 = 220.
Эта пара дружественных чисел оставалась единственной известной до тех пор, пока Пьеру Ферма не удалось найти следующую пару:
17 296 = 24 • 23 • 47, 18 416 = 24 • 1151.
Поиски пар дружественных чисел чрезвычайно удобно вести с помощью ЭВМ. Для каждого числа n при помощи машины определяются все делители этого числа (≠ n) и их сумма m. После этого производится такая же операция с числом m. Если при этом вновь получается первоначальное число n, то пара чисел (n, m) оказывается дружественной. Недавно этим способом в Йельском университете на ЭВМ IBM 7094 были проверены все числа до одного миллиона. В результате была получена коллекция из 42 пар дружественных чисел; некоторые из них оказались ранее неизвестными. Все пары дружественных чисел до 100 000 приведены в табл. 2. При помощи этого метода, как нетрудно видеть, одновременно «вылавливаются» и совершенные числа. Если возникает желание продолжать поиски дальше, то, конечно, это можно сделать, но придется затратить большое количество машинного времени.
Таблица 2
Дружественные числа до 100 000
В действительности мы очень мало знаем о свойствах пар дружественных чисел, однако, можно на основе наших таблиц высказать несколько предположений. Например, отношение одного из них к другому, по-видимому, должно все больше и больше приближаться к 1 по мере того, как они увеличиваются. Из таблицы видно, что эти числа бывают либо оба четными, либо оба нечетными, но не было найдено случая, когда одно число четно, а другое нечетно, хотя поиски дружественных чисел такого вида были проведены среди всех чисел n ≤ 1 3 000 000 000.
ГЛАВА 4 НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ И НАИМЕНЬШЕЕ ОБЩЕЕ КРАТНОЕ
§ 1. Наибольший общий делитель
Откровенно говоря, мы надеемся, что многое в этой главе окажется для вас знакомым.
В ней рассматриваются понятия, с которыми вы познакомились в школе, как только научились обращаться с обыкновенными дробями. Единственным оправданием включения этого материала является желание освежить его в вашей памяти. Мы также надеемся, что приведенное изложение материала явится более систематическим, чем то, к которому вы привыкли.
Возьмем некоторую дробь а/b, отношение двух целых положительных чисел а и b. Обычно мы стараемся привести ее к простейшему виду, т. е. мы стараемся сократить множители, общие для а и b.
Эта операция не изменяет значения дроби, например,
24/36 = 8/12 = 2/3.
Общим делителем двух натуральных чисел а и b называется натуральное число d, которое является множителем как числа а, так и числа b, т. е.
a = d • а1, b = d • b1.
Если число d — общий делитель чисел а и b, то он также делит числа а + b и а — b, так как
а + b = а1d + b1d = (а1 + b1) d,
а — b = а1d — b1d = (а1 — b1) d.
Когда известны разложения чисел а и b на простые множители, нетрудно найти все их общие делители. Выпишем эти два разложения на простые множители:
а = р1α1 • … • рrαr, b = р1β1 • … • рrβr. (4.1.1)
Здесь мы договариваемся записывать разложения чисел а и b так, как если бы они имели одинаковые простые множители
р1, p2…, рr