О. ОРЕ - Приглашение в теорию чисел
Любое целое число, которое является произведением двух целых чисел, можно было бы назвать прямоугольным числом. Когда две стороны прямоугольника имеют одну и ту же длину, то такое число является квадратным числом, или квадратом. Некоторые числа нельзя представлять в виде прямоугольных чисел иначе, как тривиальным способом — в виде цепочки точек, лежащих в одном ряду. Например, пять может быть представлено как прямоугольное число лишь единственным способом, взяв одну сторону равной единице, а другую — пяти (рис. 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-е пятиугольное число выражается формулой
pn = ½ (3n2 — 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 (n2 - n) — n2 + 2n.
§ 5. Магические квадраты
Если вы играли в «шафлборд»[1], вы можете вспомнить, что девять квадратов, на которых вы размещаете свои фишки, занумерованы числами от 1 до 9, расположенными так, как на рис. 7. Здесь числа в каждом столбце и в каждой строчке, а также в каждой из диагоналей, дают при сложении одно и то же число 15.
Рис. 7.
В общем случае магическим квадратом является расположение чисел от 1 до n2 в виде квадрата так, что числа в каждом столбце, строчке и диагонали дают одинаковую сумму s, называемую магической суммой.
Пример магического квадрата с 42 = 16 числами изображен на рис. 8. Магическая сумма для него равна 34.
Рис. 8.
Для каждого числа n существует только одна магическая сумма s, которую легко найти. Так как сумма чисел в каждом столбце равна s, а столбцов — n, то сумма всех чисел в магическом квадрате равна ns.
Но сумма всех чисел от 1 до n2 равна
1 + 2 +… + n2 = ½ (n2 + 1) n2,
что следует из формулы для суммы n членов арифметической прогрессии. Так как
n s = ½ (n2 + 1) n2,
то
s = ½ n (n2 + 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.
Вначале покажем, что центральное число y2 должно равняться 5. Из формулы (1.5.1) следует, что при n = 3 магическая сумма s равна 15. Просуммируем теперь числа во второй строке, втором столбце и обеих диагоналях. В эту сумму каждое число, кроме числа y2, входит по одному разу; число у2 входит четыре раза, так как оно содержится в каждой из четырех сумм. Поэтому, так как каждая сумма равна s, то
4s = 4 × 15 = 60 =
= x2 + y2 + z2 + y1 + y2 + y3 + x1 + у2 + z3 + z1 + y2 + x3 = Зy2 + x1 + x2 + x3 + y1 + y2 + y3 + z1 + z2 + z3 =
= 3y2 + 1 + 2 +… + 9 = 3y2 + 45.
Следовательно,
Зy2 = 60–45 = 15 и y2 = 5.
В таблице
x1 y1 z1
x2 5 z2
x3 y3 z3
число 9 не может стоять в углу, так как, если, например, x1 = 9, то z3 = 1 (потому что s = 15), т. е. мы получили бы таблицу
9 y1 z1
x2 5 z2
x3 y3 1
Каждое из четырех чисел y1, z1, x2, х3 должно быть меньше шести, так как y1 + z1 = х2 + х3 = 6. Но у нас осталось лишь три числа, меньших шести, а именно: 2, 3 и 4. Таким образом, получилось противоречие. Отсюда мы делаем вывод, что число 9 должно находиться в середине строки или столбца, поэтому наш квадрат может быть записан так:
x1 9 z1
x2 5 z2
x3 1 z3
Число 7 не может быть в одной и той же строке с числом 9, так как тогда сумма чисел в этой строке была бы больше пятнадцати; точно так же число 7 не может быть в одной и той же строке с числом 1, так как тогда оставшееся в этой строке число должно было бы быть также семеркой. Таким образом, 7 не может находиться в углу, и мы можем считать, что наш квадрат имеет следующий вид:
