Глава X. ПРОСТЫЕ ЧИСЛА

§ 1. ЧТО И КАК ИЗУЧАЕТ ТЕОРИЯ ЧИСЕЛ

Целые числа.

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

И теперь в самых разнообразных вопросах практической деятельности людям приходится постоянно встречаться с целыми числами. Целые числа отражают множество количественных соотношений в природе; во всех вопросах, связанных с дискретным, целые числа являются необходимым математическим аппаратом.

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

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

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

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

Одним из основных вопросов теории чисел является исследование делимости одного числа на другое: если результатом деления целого а на целое (не равное нулю) является целое число, т. е. если

(а, b, с — целые), то говорят, что а делится на или что делит а. Если же в результате деления целого а на целое получается дробь, то говорят, что а не делится на На практике с вопросами делимости чисел приходится сталкиваться постоянно. Свойства делимости чисел играют важную роль в некоторых вопросах математического анализа. Если, например, разложение функции по целым степеням х

таково, что все нечетные коэффициенты, т. е. коэффициенты с номерами, не делящимися на 2, равны нулю, т. е. если

то функция удовлетворяет условию

такая функция называется четной функцией, и график ее симметричен относительно оси ординат. Если в разложении (2) равны пулю все четные коэффициенты, т. е. коэффициенты с номерами, делящимися на 2, иначе говоря, если

то

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

Геометрический вопрос о возможности построения правильного -угольника при помощи циркуля и линейки оказывается зависящим от арифметической природы числа

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

Простыми числами являются, следовательно, числа

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

где — некоторые простые и целые числа, не меньшие единицы, причем представление в форме (4) является единственным.

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

Наличие в теории чисел трудных задач в соединении с тем, что целое число является простейшим и ясным математическим понятием, самым тесным образом связанным с объективной реальностью, приводит к тому, что при изучении глубоких вопросов теории чисел появляются новые идеи и развиваются мощные методы, имеющие зачастую значение не только в теории чисел, но и в других; разделах математики. Так, например, громадное влияние на все развитие математики оказала идея бесконечности натурального ряда чисел, отражающая бесконечность материального мира в пространстве и во времени. Большое значение имеет факт упорядоченности членов натурального ряда. Изучение действий над целыми числами приводит к понятию алгебраической операции, играющему основную роль в ряде разделов математики.

Большое значение в математике имеет сложившееся прежде всего на арифметическом материале понятие алгорифма — процесса решения задачи, основанного на повторном выполнении строго определенного предписания; в частности, в машинной математике роль алгорифма является фундаментальной. Особенности алгорифмического решения задачи можно четко проследить на примере алгорифма Эвклида для нахождения общего наибольшего делителя двух натуральных чисел а и

Пусть Делим а на и находим неполное частное и, если не является делителем а, остаток

Далее, если делим на

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

тогда как раз и будет общим наибольшим делителем а и Действительно, если два целых числа имеют общий делитель то при целых к число также будет делиться на . Предположим, что общий наибольший делитель а и равен 8. Из равенства видно, что будет делителем из (52) следует, что будет делителем из — что является делителем Но само является общим делителем а и так как из видно, что есть делитель из — что есть делитель Поэтому совпадает с задача нахождения общего наибольшего делителя а и решена. Мы имеем здесь определенный, однотипный для любых a и b процесс, заведомо ведущий нас к искомому результату, — это характерный пример алгорифма.

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