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

Русская и советская математические школы выдвинули из своей среды многих выдающихся представителей теории чисел — науки о закономерностях чисел. Начиная с XVIII века, когда в Петербурге работал Леонард Эйлер, Россия дала миру яркие таланты — П. Л. Чебышева, А. А. Маркова, Г. Ф. Вороного и многих других, внесших в развитие теории чисел неоценимый вклад. Советский период в развитии теории чисел связан с именами И. М. Виноградова, Л. Г. Шнирельмана, А. Я. Хинчина, А. О. Гельфонда, Ю. В. Линника и ряда других ученых, закрепивших за нашей страной славу крупнейшего поставщика теоретико-числовых открытий.

Брошюра А. М. Полосуева приоткрывает перед читателем тайны методов исследования в элементарной теории чисел. То, что сообщает брошюра,— лишь первые шаги, но и они требуют от читателя определенных усилий для отчетливого ознакомления с ними. Я убежден, что брошюра будет с интересом и пользой прочтена читателями нашей серии и побудит некоторых из них обратиться к изучению более специальной литературы.

Б. В. ГНЕДЕНКО.

академик АН Украинской ССР

ВВЕДЕНИЕ

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

Всякий, кто изучал высшую математику, не мог не заметить, что она распадается на несколько основных разделов — геометрия, математический анализ, теория функции комплексного переменного, теория чисел и т. д. Эти разделы отличаются один от другого своей проблематикой и своими методами исследования. Однако полностью отделить один раздел от другого невозможно и порой бывает трудно провести резкую границу между ними. Тесная связь между различными разделами математики позволяет использовать результаты и методы одного из них для решения проблем другого. Так, например, в теории чисел — древнейшем разделе математики,— основным объектом изучения которой являются свойства натуральных чисел, широко используются методы теории функций комплексного переменного, алгебры, геометрии, теории вероятностей, и в зависимости от того, какой метод исследования является доминирующим в решении тех или Иных числовых проблем, говорят о теории чисел аналитической, алгебраической или геометрической. К элементарной теории чисел относят те числовые проблемы, которые решаются чисто арифметическими средствами, то есть без привлечения средств математического анализа, геометрии, комплексного переменного. Конечно, такое деление теории чисел на разделы нельзя считать абсолютным: имеется немало числовых проблем, решение которых получено впервые аналитическими методами, а впоследствии выяснилось, что их можно решить и методами чисто арифметическими.

В данной брошюре мы расскажем о некоторых теоретико-числовых функциях, которые являются не только вспомогательным средством описания многих числовых фактов, но и объектом изучения. Речь пойдет о следующих функциях: т (и) — число делителей числа п; <р (п) — число чисел ряда 1, 2, . . ., п, взаимно простых с и; [х] — целая часть числа х; {х} — дробная часть числа х. Методы, которыми пользовались при исследовании излагаемых здесь свойств функций или при решении числовых проблем, тесно связанных с ними,— в основном аналитические, хотя и включают в себя некоторые геометрические и алгебраические факты.

Введем понятие числовой функции. Для этого напомним общее определение функции, принятое в современной математике.

Пусть X и Y — два каких-нибудь множества чисел. Элементы множества X будем обозначать буквой х, элементы множества Y — буквой у. Если существует правило, по которому каждому элементу х множества X можно поставить в соответствие элемент у множества Y, то соответствие х —► у называют функцией и обозначают так: у = f (х), где буква f указывает на наличие названно-

го правила. Множество X называется областью определения, множество У — областью изменения функции.

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

Из введенного определения следует, что числовых функций можно построить сколько угодно. Например, элементарные функции £^х, Sl’nx, tgx являются числовыми, если их аргумент принимает натуральные значения.

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

• 1. ЧИСЛО ДЕЛИТЕЛЕЙ

Из школьного курса арифметики известны четыре действия над целыми числами — сложение, вычитание, умножение и деление. Первые три действия выполнимы всегда, то есть над любыми двумя целыми числами можно производить действия сложения, вычитания, умножения, причем в результате получим опять целое число. Действие же деления одного числа на другое не всегда выполнимо в том смысле, что в результате деления одного целого числа на другое частное от деления не всегда оказывается целым числом. В силу этого сразу же возникает масса вопросов: каковы признаки делимости одних целых чисел на другое, сколько существует делителей данного целого числа и т. д.?

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

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

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

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