Кошки монастыря святого Эдмондсбери

— О монастыре святого Эдмондсбери, — начал однажды отец Питер, — рассказывают, что как-то в давние времена его одолели мыши. Дабы искоренить это зло, доброму тамошнему аббату пришлось распорядиться, чтобы в святую обитель доставили кошек со всей округи. Записи свидетельствуют, что к концу года каждая кошка уничтожила одинаковое число мышей и что всего их было уничтожено ровно 1 111 111 штук. Как вы думаете, сколько кошек собрали в монастыре?
— Мне думается, что всех мышей съела одна кошка, — сказал брат Бенджамин.
— Брат мой! Я же сказал «сколько кошек».
— Хорошо, — настаивал Бенджамин, — тогда, наверное, 1 111 111 кошек съело по одной мыши.
— Нет, — возразил отец Питер после того, как монахи вволю насмеялись, — я сказал «мышей»; я хочу лишь добавить, что каждая кошка уничтожила больше мышей, чем всего было кошек. Мне сказали, что здесь все основано просто на делении чисел, но я не знаю ответа на эту загадку.
Правильный ответ сохранился в летописи монастыря, но там не сказано, как его получили.

Ответ

Вы наверняка знаете, что целые числа бывают простыми и составными. Далее: 1 111 111 не может быть простым числом, ибо если бы оно было таковым, то единственными возможными ответами оказались бы те, что предложил брат Бенджамин и отверг брат Питер. Точно так же оно не может разлагаться в произведение более двух простых сомножителей, ибо тогда решение оказалось бы не единственным. И действительно, 1 111 111 = 239 х 4649 (оба сомножителя простые); поскольку каждая кошка уничтожила больше мышей, чем всего было кошек, то кошек было 239 (см. введение).

В общем случае данная задача состоит в нахождении делителей (если они имеются) чисел вида (10n - 1)/9

Люка в своей книге «Занимательная арифметика» приводит несколько удивительных таблиц, которые он позаимствовал из арифметического трактата под названием «Талкис», принадлежащего арабскому математику и астроному Ибн Албанна, жившему в первой половине XIII века. В Парижской национальной библиотеке имеется несколько манускриптов, посвященных «Талкис», и комментарий Алкаласади, который умер в 1486 г. Среди таблиц, приведенных Люка, есть одна, где перечислены все делители чисел указанного вида вплоть до n - 18. Кажется почти невероятным, что арабы того времени могли найти делители при n = 17, приведенные во введении к настоящей книге. Но Люка утверждает, что они имеются в «Талкис», хотя выдающийся математик читает их по-другому, и вероятно, что их открыл сам Люка. Это, разумеется, можно было бы проверить, обратившись непосредственно к «Талкис», но во время войны сделать это оказалось невозможно.
Трудности возникают исключительно в тех случаях, когда n — простое число. При n = 2 мы получаем простое число 11. Для n = 3, 5, 11 и 13 делители соответственно равны (3 х 37), (41 х 271), (21 649 х 513 239) и (53 х 79 х 265 371 653). Здесь приведены уже делители для n = 7 и 17. Делители в случаях n = 19, 23 и 37 неизвестны, если они вообще имеются1. При n = 29 делителями будут (3191 х 16 763 х 43 037 х 62 003 х 77 843 х х 839 397); при n = 31 одним из делителей будет 2791; при и = 41 два делителя имеют вид (83 х 1231).
Что же касается четных n, то следующая любопытная последовательность сомножителей, несомненно, заинтересует вас. Числа в скобках — простые.


Или мы можем записать делитель иначе:


В приведенных выше двух таблицах n имеет вид 4m + 2. Когда n имеет вид 4m, делители можно записать следующим образом2:


При n = 2 мы получаем простое число 11; при n = 3 делителями будут 3 х 37; при n = 6 они имеют вид 11 х 3 х 37 х 7 х 13; при n = 9 получается 32 х 37 х 333 667. Следовательно, мы знаем, что делителями при n = 18 будут 11 х 32 х 37 х 7 х 13 х 333 667, тогда как остающийся множитель — составной и может быть представлен в виде 19 х 52 579. Это показывает, как можно упростить работу в случае составного n.

1 О. Хопп сообщает, что его исследования случая n = 19 позволяют утверждать, что соответствующее число — простое. Он представил свое доказательство в Лондонское математическое общество, и специально назначенная комиссия признала доказательство верным и окончательным (Proccedings of Lowd. Math. Soc. от 14 февраля 1918 г.).

2 Во избежание недоразумений следует отметить, что во всех приведенных здесь таблицах допускается небрежность в обозначениях. Так, запись n = 4 = (11) x (110) означает, что при n = 4 число вида (10n - 1)/9 разлагается на множители (11) x (110)