ГЛАВА V. РАЗБИЕНИЕ ЧИСЕЛ НА СЛАГАЕМЫЕ И МЕТОДЫ ЛИУВИЛЛЯ

§ 1. Точечные диаграммы, теорема Эйлера-Лежандра.

Классическая теория чисел, изложенная в предыдущих главах, основывается в значительной степени на образовании целых чисел из простых множителей путем умножения и потому может быть названа мультипликативною. В настоящей главе мы рассмотрим другую, гораздо менее разработанную часть теории чисел, изучающую составление чисел путем сложения и которую поэтому можно назвать аддитивной теорией чисел. Собственно говоря, преждевременно называть эту область исследований «теорией», так как в ней отсутствуют еще общие методы и общие точки зрения, характеризующие всякую теорию; состояние ее во многом напоминает состояние классической теории чисел до появления "Disquisitiones Arithmeticae" Гаусса.

Начало этой части теории чисел положено знаменитыми исследованиями Эйлера, изложенными в мемуаре "De partitione numerorum" (см. 17, т. I, стр. 73) и известными под названием теорем о разбиениях (partitio numerorum). Эйлер получил свои теоремы аналитически, выводя различные соотношения между степенными рядами и приравнивая затем в полученных равенствах коэфициенты при одинаковых степенях переменного. В этом параграфе будут изложены арифметические доказательства главнейших теорем Эйлера.

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

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

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

получаем следующие числовые функции: количество представлений в виде суммы равных или неравных целых положительных слагаемых в произвольном числе (например, для числа 6 имеем: . В обозначении этой функции ставим черточку наверху для отличия от функции Мёбиуса см. § 2 гл. I); количество представлений в виде суммы таких же слагаемых, как и в предыдущем случае; количество представлений в виде суммы неравных положительных нечетных слагаемых и количество представлений суммою равных или неравных положительных нечетных слагаемых. Все эти величины (так называемые аддитивные числовые функции) обладают многими замечательными свойствами, изложенными в этом и следующих параграфах. Обозначая левую часть второй формулы (2) через Эйлер получает для этой функции соотношение откуда выводит

Сравнение коэфициентов при в обеих частях этого равенства дает такую теорему:

1) Количество представлений числа суммою равных или неравных целых положительных слагаемых равно количеству представлений суммою равных или неравных слагаемых, взятых из ряда чисел

Символически можно записать эту теорему так:

причем обозначает количество разбиений, характеризованных в скобках после буквы Аналогично получается теорема (в формулировке этой и следующих теорем настоящего параграфа под словом "слагаемое" нужно понимать везде "целое положительное слагаемое"):

2) Число представлений [большего, чем суммой неравных слагаемых равно числу представлений суммой любого числа равных или неравных слагаемых, взятых из ряда Далее, доказав тождество

Эйлер получает для всякого или

3) Всякое число представляется суммою неравных слагаемых столькими же способами, сколькими оно представляется суммою равных или неравных нечетных слагаемых.

Еще одна важная теорема хотя не формулирована Эйлером явно, но вытекает из нижеприведенной его формулы. Желая доказать открытое им рекуррентное соотношение для суммы делителей (см. ниже, теорема 20), Эйлер в мемуаре "Demonstratio theorematis circa ordinem in summis divis-orum observati" доказывает соотношение

представляющее одну из самых употребительных формул современной теории эллиптических функций. В показателях правой части формулы (5) стоят пентагональные числа (см. примечания к гл. IV); значения их для первых номеров суть д. Сравнивая коэфициенты при в обеих частях (5), получаем следующую теорему, называемую теоремой Эйлера-Лежандра:

Теорема 19. Разность между количествами представлений данного числа в виде суммы четного и нечетного числа слагаемых равна нулю, если непентагональное число, и равна если есть пентагональное число .

Для арифметического доказательства приведенных теорем служит простой и наглядный метод точечных диаграмм, употреблявшийся английскими учеными школы Сильвестра. Пусть дано разбиение числа на слагаемые изобразим это разбиение в виде точек на плоскости, расположенных в строках, причем в первую строку поставим точек, во вторую точек строку точек. Начальные точки строк поставим в одном вертикальном столбце и расстояния между соседними точками как по горизонтальным, так и по вертикальным линиям возьмем одинаковыми. Систему точек, расположенных таким образом, назовем диаграммой, соответствующей разбиению например, на фиг. 1 слева изображена диаграмма, соответствующая разбиению числа 13 на слагаемые Очевидно, что в каждой диаграмме любой столбец не длиннее столбцов, стоящих слева от него; кроме того, если

диаграмма соответствует разбиению числа на неравные слагаемые, то количества точек в двух соседних столбцах либо равны, либо отличаются на единицу.

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

Фиг. 1.

Очевидно, что получится диаграмма разбиения числа на равные или неравные слагаемые, причем каждое слагаемое имеет одно из значений Обратно, взяв диаграмму любого разбиения на равные или неравные слагаемые, не превышающие обратим строки ее в столбцы и, приписав слева столбец, состоящий из точек, получим диаграмму некоторого разбиения на равных или неравных слагаемых. На фиг. 1 слева изображена диаграмма разбиения числа на слагаемых а справа — соответствующая диаграмма разбиения на слагаемые не превышающие 4. Итак, разбиения, стоящие в левой и правой частях равенства (4), приведены во взаимно однозначное соответствие, и, следовательно, количества этих разбиений равны между собою, что и требовалось доказать. Аналогично доказывается и теорема 2).

Теорему 3) также можно доказать при помощи диаграмм, но еще проще следующее ее доказательство. Из элементарной арифметики известно, что каждое целое число представляется единственным способом по системе счисления с основанием целое т. е. в виде причем "цифры" имеют значения из ряда При получается, что каждое число может быть представлено единственным способом в виде суммы нескольких различных степеней двойки. Пусть теперь

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

т. е. разбиение на четные или нечетные слагаемые которые будут, очевидно, различны. Обратно, если дано разбиение на различные слагаемые то представим каждое из них в виде нечетное) и соединим все слагаемые с одним и тем же положив сумму этих слагаемых равной получим разбиение на нечетные слагаемые, причем различны и слагаемое входит в разбиение раз. Итак, число разбиений на неравные (четные или нечетные) слагаемые равно числу разбиений на равные или неравные нечетные слагаемые, что и требовалось доказать.

Обращаясь к доказательству теоремы 19 Эйлера-Лежандра методом диаграмм, возьмем диаграмму какого-нибудь разбиения на неравные слагаемые и через последнюю точку первой строки этой диаграммы проведем прямую под углом 45° к горизонтальному направлению (см. на фиг. 2 слева); эту линию будем называть иосоь линией диаграммы. Пусть число точек диаграммы, лежащих на косой линии, k — число точек в последней строке диаграммы. Все диаграммы, соответствующие разбиениям на неравные слагаемые, разделим на два класса: к первому классу отнесем те диаграммы, в которых ко второму — те, в которых Условимся называть особенными те диаграммы первого класса, в которых и последняя точка последней строки лежит на косой линии, и те диаграммы второго класса, в которых и последняя точка последней строки лежит на косой линии. Особенные диаграммы первого класса соответствуют разбиениям вида к , особенные диаграммы второго класса — разбиениям вида Отсюда ясно, что когда разбиваемое число и непентагональное, то особенных диаграмм вовсе нет. Если же то это равенство вполне определяет целое число и в этом случае существует только одна особенная диаграмма, принадлежащая к первому классу, когда и ко второму, когда число строк в этой диаграмме равно Докажем теперь, что неособенные диаграммы первого и второго классов можно привести во взаимно однозначное соответствие. Возьмем неособенную диаграмму первого класса и, уничтожив ее последнюю строку, прибавим принадлежащие ей к точек к к первым строкам. Тогда получим диаграмму, на косой линии которой будет к точек, а в последней строке больше к точек; эта диаграмма будет, следовательно, II класса и притом неособенная. В самом деле, если косая линия полученной диаграммы заканчивается на ее последней строке, то эта строка содержит не менее точек. На фиг. 2 слева помещена неособенная диаграмма I класса соответствующая разбиению числа а справа — полученная из нее указанным путем неособенная диаграмма II класса. Обратно, возьмем любую неособенную диаграмму II класса и I точек ее косой линии поместим снизу диаграммы в виде последней строки. Тогда получим

новую диаграмму, косая линия которой содержит не менее I точек, а последняя строка I точек и которая будет, следовательно, диаграммой I класса и притом неособенной. В самом деле, если косая линия новой диаграммы кончается на ее последней строке, то в этой косой линии будет не менее точек. Таким образом неособенные диаграммы I и II классов приведены во взаимно однозначное соответствие; притом числа строк двух соответствующих диаграмм отличаются всегда на единицу.

Фиг. 2.

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

В близком отношении к теореме Эйлера-Лежандра стоит знаменитая теорема Эйлера о сумме делителей числа (§ 2 гл. I) (см. Эйлер 1Т, т. I, стр. 234):

Теорема 20. Для всякого имеем

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

Рассмотрим всевозможные представления в виде причем 2 а есть сумма неравных слагаемых положительные числа; сумма может и отсутствовать. На все эти представления распространим сумму вычисление этой суммы двояким способом и дает формулу (7).

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

неравные слагаемые. Применяя теорему 19, находим для выражение Чтобы найти другое выражение для разобьем все представления на три категории: 1) представления, в которых не встречается среди слагаемых суммы 2 а и вместе с тем представления, в которых встречается среди слагаемых суммы представления, в которых не встречается среди слагаемых и Возьмем какое-нибудь представление первой категории отняв от члена присоединим его как слагаемое к сумме полученное представление, которое можно изобразить так: принадлежит, очевидно, ко второй категории. Обратно, из каждого представления второй категории обратным действием можно получить представление первой категории. Итак, представления первой и второй категорий находятся в простом взаимно однозначном соответствии; замечая, что члены суммы для соответствующих представлений, взаимно уничтожаются, можем сказать, что часть суммы распространенная на представления первых двух категорий, равна нулю. Рассмотрим какое-нибудь представление третьей категории так как не встречается среди слагаемых , то представление можно рассматривать как разбиение на неравных слагаемых. Обратно, из каждого разбиения на слагаемых получим представлений третьей категории, приняв последовательно равным Эти представлений третьей категории дадут в сумме члены откуда ясно, что вся сумма равна берется по всем разбиениям на различные слагаемые, число которых и по теореме Сравнивая два выражения для получим формулу (7).

Сам Эйлер доказал формулу (7) логарифмическим диференцированием тождества (5). Формула (7) позволяет вычислять последовательно значения функции не прибегая к разложению чисел на простые множители.