Читаем Приглашение в теорию чисел онлайн бесплатно

Перевод с английского

Л. А. САВИНОЙ и А. П. САВИНА

Библиотечка "Квант", выпуск 3

МОСКВА «НАУКА»

ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ

1980

Имя О. Оре (1899–1968) хорошо известно у нас в стране. Две его книги по теории графов, переведенные на русский язык (О. Оре. Теория графов. — М.: Наука, 1968 и Графы и их применение. — М.: Мир, 1965) были тепло встречены читателями в СССР. С большим интересом был принят и перевод его книги о Нильсе Абеле (О. Оре. Замечательный математик Нильс Хенрик Абель. — М.: Физматгиз, 1961.)

Предлагаемая читателю книга О. Оре «Приглашение в теорию чисел» относится к чрезвычайно редкостному типу научно-популярных книг. Как правило, научно-популярные книги по математике имеют своей целью научить читателя чему-либо или дать ему представление о той или иной ветви математики. О. Оре не ставит перед собой ни той, ни другой задачи. Его цель — заинтересовать читателя математикой (а читателем предполагается школьник 13–17 лет), привить ему вкус к этой древней, но вечно юной науке.

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

Написанная просто и доступно, эта книга (за исключением нескольких страниц) может быть легко прочитана школьником начиная с 5–6 класса. Поскольку этот перевод адресован в первую очередь школьникам, то переводчики сочли необходимым полностью сменить рекомендуемую литературу на книги, доступные этой категории читателей.

Теория чисел — это ветвь математики, имеющая дело с целыми положительными числами

1, 2, 3…,

которые также называют натуральными числами.

Археология и история учат нас, что человек рано начал считать. Сначала он научился складывать числа, потом, много позже, умножать и вычитать их. Деление чисел было необходимым для распределения на равные части кучи яблок или улова рыбы. Эти действия над числами называются вычислениями. В некоторых случаях последовательность вычислений называют «калькуляцией». Это слово происходит от латинского calculus, означающего «маленький камень», поскольку римляне пользовались морской галькой при вычислениях на своих счетных досках.

Как только люди немного научились считать, этот процесс стал приятным времяпровождением для многих людей, склонных к абстрактному теоретизированию. Знания о числах накапливались в течение многих веков, порождая интерес к новым исследованиям, которые в свою очередь приумножали эти накопления. И сейчас, в современной математике, мы имеем величественную конструкцию, известную как теория чисел. Некоторые части этой теории все еще составляют простые игры с числами, а другие относятся к наиболее трудным и сложным разделам математики.

Некоторые следы размышлений о числах в давние времена можно обнаружить в суеверных предрассудках, связанных с числами. Среди чисел есть «счастливые», которым нужно отдавать предпочтение и радоваться при встрече с ними, и «несчастливые», которых нужно остерегаться, как дурного глаза. Мы обладаем обширными сведениями о нумерологии в античной Греции, мыслях и предрассудках, связанных с символическим значением различных чисел. Например, нечетные числа, большие единицы, символизировали мужское начало, а четные — женское; таким образом, число 5 — сумма первого мужского и первого женского чисел — символизировало супружество или союз.

Желающие познакомиться с более развитой «теорией» магических чисел могут сделать это, прочтя восьмую книгу «Республики» Платона. Такая «наука» мало что дает в смысле математических идей, но она содержит умение обращаться с числами и их свойствами. Как мы дальше увидим, некоторые замечательные проблемы в теории чисел, до сих пор занимающие умы математиков, берут свое начало из греческого учения о магических числах.

До сих пор у нас нет оснований считать себя выше предрассудков, связанных с числами. Вероятно, у каждого есть знакомые, которые ни за что не посадят за стол 13 гостей, а как мало в гостиницах США этажей и комнат с номером 13. По существу, мы не знаем, откуда взялись подобные «табу» на числа. Существует множество всевозможных объяснений, но большинство из них совершенно безосновательны. Например, в «Библии» записано, что на Тайной вечере было 13 гостей, разумеется, тринадцатым был Иуда. Если же заметить, что многие предметы считаются дюжинами, а число 13 дает «чертову дюжину», т. е. лишний предмет, то это соображение имеет больший реальный смысл.

В «Библии», особенно в «Ветхом Завете», особую роль играет число 7, в древнегерманском фольклоре часто встречаются числа 3 и 9, индусы же, как видно из их мифологии, неравнодушны к числу 10.

Примером ранней теории чисел может служить задача Пифагора. Как мы знаем, в прямоугольном треугольнике длины сторон удовлетворяют соотношению Пифагора

z² = x² + y², (1.3.1)

где z — длина гипотенузы. Это дает возможность в прямоугольном треугольнике вычислить длину одной стороны, если известны две другие. Между прочим, то, что эту теорему назвали в честь греческого философа Пифагора, не совсем справедливо: она была известна вавилонянам почти за 2000 лет до Пифагора.

Иногда все длины сторон x, y, z в (1.3.1) выражаются целыми числами. Простейший случай,

x = 3, y = 4, z = 5, (1.3.2)

был найден на вавилонских глиняных табличках. Этому случаю можно дать следующее истолкование. Предположим, что у нас есть веревочное кольцо с узелками или метками, расположенными на равных расстояниях и делящими кольцо на 12 частей. Тогда, если мы растянем кольцо на трех колышках, вбитых на поле, так, чтобы получился треугольник со сторонами 3 и 4, то третья сторона будет иметь длину 5, а противоположный ей угол будет прямым (рис. 1). Часто можно прочесть в книгах по истории математики, что именно этот метод построения прямого угла использовался египетскими землемерами или «натягивателями веревки» при размежевании полей по окончании разлива Нила. Однако вполне возможно, что это один из мифов, которых так много в истории науки; у нас нет документов, подтверждающих это предположение.

Рис 1.

Существует много других целочисленных решений уравнения Пифагора (1.3.1), например,

х = 5, у = 12, z = 13,

х = 7, у = 24, z = 25,

x = 8, у = 15, z = 17.

Далее мы покажем, как можно получить все такие решения. Способ находить их был известен древним грекам, а возможно, и вавилонянам.

Если даны два целых числа, x и y, то всегда можно найти соответствующее число z, удовлетворяющее уравнению (1.3.1), но вполне возможно, что z будет иррациональным числом. Если же потребовать, чтобы все три числа были целыми, то тогда возможности существенно ограничиваются. Греческий математик Диофант (время его жизни точно не известно, приблизительно 200 г. нашей эры) написал книгу Arithmetica («Арифметика»), в которой рассматриваются подобные задачи. С этого времени задача нахождения целочисленных или рациональных решений уравнений называется задачей Диофанта, а диофантов анализ — важная часть современной теории чисел.

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

1. Попытайтесь найти другое решение уравнения Пифагора в целых числах.

2. Попытайтесь найти решения уравнения Пифагора, в которых гипотенуза на единицу больше, чем больший из двух катетов.

В теории чисел мы часто встречаемся с квадратами, т. е. такими числами, как

3² = 9, 7² = 49, 10² = 100,

и аналогично с кубами, т. е. такими числами, как

2³ = 8, 3³ = 27, 5³ = 125.

Рис. 2.

Этот геометрический образ рассматриваемой операции с числами является частью богатого наследства, оставленного древнегреческими мыслителями. Греки предпочитали думать о числах, как о геометрических величинах: произведение с = аb рассматривалось как площадь с прямоугольника со сторонами a и b. Также можно было рассматривать a•b как число точек в прямоугольной таблице с а точками на одной стороне и b точками на другой. Например, 20 = 4•5 есть число точек в прямоугольной таблице на рис. 2.

Любое целое число, которое является произведением двух целых чисел, можно было бы назвать прямоугольным числом. Когда две стороны прямоугольника имеют одну и ту же длину, то такое число является квадратным числом, или квадратом. Некоторые числа нельзя представлять в виде прямоугольных чисел иначе, как тривиальным способом — в виде цепочки точек, лежащих в одном ряду. Например, пять может быть представлено как прямоугольное число лишь единственным способом, взяв одну сторону равной единице, а другую — пяти (рис. 3).

• • • • •

Рис. 3.

Такие числа греки называли простыми числами. Точка, взятая в одном экземпляре, не рассматривалась как число. Число 1 явилось тем кирпичом, из которого строились все остальные числа. Таким образом, 1 не была для них и не считается сейчас простым числом.

Можно было бы рассматривать точки, равномерно заполняющие не только прямоугольники и квадраты, но и другие геометрические фигуры. Последовательные треугольные числа изображены на рис. 4.

Рис. 4.

В общем случае n-е треугольное число задается формулой

Т_n = ½ n (n+1), n = 1, 2, 3… (1.4.1)

У этих чисел масса интересных свойств: например, сумма двух последовательных треугольных чисел является квадратом

1 + 3 = 4, 3 + 6 = 9, 6 + 10 = 16 и т. д. (1.4.2)

Обобщением треугольных чисел и квадратов явились многоугольные числа. Метод их получения проиллюстрируем на примере пятиугольных чисел. Для этого рассмотрим рис. 5.

Рис. 5.

Глядя на него, легко найти несколько первых пятиугольных чисел,

1, 5, 12, 22, 35. (1.4.3)

Можно показать, что n-е пятиугольное число выражается формулой

p_n = ½ (3n² — n). (1.4.4)

Шестиугольные числа, и вообще k-угольные числа, аналогично определяются с помощью правильного k-угольника, и мы не будем больше тратить времени на их обсуждение. Фигурные числа, особенно треугольные, пользовались большой популярностью при изучении чисел в конце эпохи Возрождения, после того как греческая теория чисел проникла в Западную Европу. И сейчас их можно иногда встретить в статьях по теории чисел.

Проводя анализ такого геометрического представления чисел, можно получить несколько простых соотношений. Остановимся лишь на одном примере. Уже давно было известно, что складывая последовательно нечетные числа, мы все время будем получать квадраты, например,

1 + 3 = 4, 1 + 3 + 5 = 9, 1 + 3 + 5 + 7 = 16 и т. д.

Чтобы доказать это соотношение, достаточно лишь взглянуть на рис. 6, на котором изображены последовательно вложенные квадраты.

Рис. 6.

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

1. Докажите по индукции общую формулу (1.4.1) для треугольных чисел.

2. Докажите формулу (1.4.4) для пятиугольных чисел.

3. Докажите, что произвольное k-угольное число выражается формулой

½ k (n² - n) — n² + 2n.

Если вы играли в «шафлборд»[1], вы можете вспомнить, что девять квадратов, на которых вы размещаете свои фишки, занумерованы числами от 1 до 9, расположенными так, как на рис. 7. Здесь числа в каждом столбце и в каждой строчке, а также в каждой из диагоналей, дают при сложении одно и то же число 15.

Рис. 7.

В общем случае магическим квадратом является расположение чисел от 1 до n² в виде квадрата так, что числа в каждом столбце, строчке и диагонали дают одинаковую сумму s, называемую магической суммой.

Пример магического квадрата с 4² = 16 числами изображен на рис. 8. Магическая сумма для него равна 34.

Рис. 8.

Для каждого числа n существует только одна магическая сумма s, которую легко найти. Так как сумма чисел в каждом столбце равна s, а столбцов — n, то сумма всех чисел в магическом квадрате равна ns.

Но сумма всех чисел от 1 до n² равна

1 + 2 +… + n² = ½ (n² + 1) n²,

что следует из формулы для суммы n членов арифметической прогрессии. Так как

n  s = ½ (n² + 1) n²,

то

s = ½ n (n² + 1). (1.5.1)

Таким образом, если число n задано, то число s определено. Магические квадраты могут быть построены для любого числа n, которое больше 2; читатель легко может убедиться, что их не существует для n = 2.

Во времена средневековья странные свойства этих квадратов считались волшебными и поэтому магические квадраты служили талисманами, защищающими тех, кто их носил, от многих несчастий. Часто воспроизводится магический квадрат, присутствующий на знаменитой гравюре Альбрехта Дюрера «Меланхолия» (она помещена на фронтисписе нашей книги). Этот квадрат воспроизведен с большим увеличением на рис. 9; при этом мы получили также возможность увидеть, как во времена Дюрера изображались цифры. Средние числа в последней строке изображают год, — 1514, в котором, как мы знаем, была создана эта гравюра. Возможно, что Дюрер, положив в основу именно эти числа, нашел остальные методом проб и ошибок. Можно доказать, что при n = 3 имеется лишь один магический квадрат, а именно квадрат, изображенный на рис. 7. Докажем этот факт. Для этого напишем числовой квадрат 3 × 3 в общем виде

x1  y1  z1

x2  y2  z2

x3  y3  z3

и выясним, какими могут быть эти девять чисел.

Рис. 9.

Вначале покажем, что центральное число y₂ должно равняться 5. Из формулы (1.5.1) следует, что при n = 3 магическая сумма s равна 15. Просуммируем теперь числа во второй строке, втором столбце и обеих диагоналях. В эту сумму каждое число, кроме числа y₂, входит по одному разу; число у₂ входит четыре раза, так как оно содержится в каждой из четырех сумм. Поэтому, так как каждая сумма равна s, то

4s = 4 × 15 = 60 =

= x₂ + y₂ + z₂ + y₁ + y₂ + y₃ + x₁ + у₂ + z₃ + z₁ + y₂ + x₃ = Зy₂ + x₁ + x₂ + x₃ + y₁ + y₂ + y₃ + z₁ + z₂ + z₃ =

= 3y₂ + 1 + 2 +… + 9 = 3y₂ + 45.

Следовательно,

Зy₂ = 60–45 = 15 и y₂ = 5.

В таблице

x1  y1  z1

x2   5  z2

x3  y3  z3

число 9 не может стоять в углу, так как, если, например, x₁ = 9, то z₃ = 1 (потому что s = 15), т. е. мы получили бы таблицу

9  y1  z1

x2  5  z2

x3  y3  1

Каждое из четырех чисел y₁, z₁, x₂, х₃ должно быть меньше шести, так как y₁ + z₁ = х₂ + х₃ = 6. Но у нас осталось лишь три числа, меньших шести, а именно: 2, 3 и 4. Таким образом, получилось противоречие. Отсюда мы делаем вывод, что число 9 должно находиться в середине строки или столбца, поэтому наш квадрат может быть записан так:

x1  9  z1

x2  5  z2

x3  1  z3