Г. Н. БЕРМАН

Число и наука о нем

Г. Н. БЕРМАН

ЧИСЛО И НАУКА О НЕМ

Общедоступные очерки по арифметике натуральных чисел

Издание третье

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

МОСКВА 1960

ОТ ИЗДАТЕЛЬСТВА

Первое издание книги «Число и наука о нем» вышло в свет в 1948 г. (кроме того, в 1949 г. был отпечатан дополнительный тираж). Второе издание книги вышло в 1954 г. после смерти автора Георгия Николаевича Бермана (последовавшей 9 февраля 1949 г.). При подготовке настоящего третьего издания к печати Издательство внесло в текст книги некоторые уточнения и исправления.

Георгий Николаевич Берман Число и наука о нем

Редактор И. Е. Морозова. Техн. редактор И. Ш. Аксельрод.

Обложка, титул, заставки и концовки художника В. А. Селенгинского. Корректор К. Н. Мартынкина

Сдано в набор 29/V I960 г. Подписано к печати 30/111 1960 г. Бумага 84X1081/я*. Физ. печ. л. 5,125. Условн. печ. л. 8,4. Уч.-изд. л. 7,7/.

Т-01063. Тираж 40 000. Цена 2 р. 45 к. С 1/1 1961 г. 25 к. Заказ № 929.

Государственное издательство физико-математической литературы. Москва, Ленинский проспект, 15.

Ленинградский Совет народного хозяйства. Управление полиграфической промышленности. Типография № I «Печатный Двор» имени А. М. Горького. Ленинград, Гатчинская, 26.

Памяти НИКОЛАЯ БОРИСОВИЧА ГОФМАНА, павшего смертью храбрых

ИЗ ПРЕДИСЛОВИЯ АВТОРА К ПЕРВОМУ ИЗДАНИЮ

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

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

Автор благодарит всех, кто содействовал написанию и опубликованию этой книги. Особенно благодарен автор проф. А. Ф. Берманту, внимательно прочитавшему рукопись и давшему ряд ценных указаний.

Москва 1947 г.

ВВЕДЕНИЕ

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

человек знакомится с ними еще в дошкольном возрасте. И все же, несмотря на свою привычность и повседневность, натуральные числа обладают многими свойствами, далеко не общеизвестными. Существует целая наука —теория чисел, — которая занимается их изучением. Наука эта обладает интересной особенностью: задачи ее кажутся простыми и понятными; о результатах ее можно рассказать всякому достаточно грамотному человеку. Но путь решения задач, способы достижения результатов порою очень трудны и сплошь да рядом недоступны даже лучшим математикам. Недаром крупнейший немецкий математик Гаусс (1777—1855) говорил, что арифметика—царица математики. Он имел в виду, разумеется, не элементарную арифметику, а именно теорию чисел, которую называют иначе высшей арифметикой и на дальнейшее развитие которой оказали большое влияние труды самого Гаусса.

Натуральных чисел бесконечно много: среди них нет наибольшего. Нам это кажется ясным. В самом деле, какое бы большое число мы ни взяли, если мы прибавим к нему единицу, то получим число еще большее. Эта бесконечность числового ряда создает значительные трудности при логическом обосновании арифметики.

В этой книжке основы арифметики (аксиомы и простейшие правила) не рассматриваются.

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

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

Учением о простых числах занимались лучшие русские математики: Чебышев, Золотарев и другие. В двадцатом веке самые крупные, самые блестящие результаты в этой области были получены советскими математиками: Л. Г. Шнирельманом и особенно академиком И. М. Виноградовым. Об этих результатах будет рассказано в последней главе этой книжки.

ГЛАВА I

НАША СИСТЕМА СЧИСЛЕНИЯ

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

Наша нумерация использует для записи чисел десять различных знаков. Девять из них служат для обозначения первых девяти натуральных чисел (1, 2, 3, 4, 5, 6, 7, 8, 9), десятый не обозначает никакого числа; он представляет собою просто пробку, «пробельный материал» при записи чисел. Значок этот называют нулем и обозначают 0.

Итак, мы имеем девять значков для обозначения первых девяти чисел и десятый значок — нуль—«позиционную пробочку»*). Значки эти называются цифрами.

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

*) О слове «позиционная» см. примечание на стр. 9.

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

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

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

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

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

Записать какое-нибудь число, например «пятьдесят семь», пользуясь десятью основными значками и некоторыми связующими словами, можно хотя бы так: «5 единиц второго разряда и 7 простых единиц». Но такой способ записи громоздок. Удобнее и короче было бы записывать числа без помощи слов, одними знаками (цифрами). И в самом деле, мы записываем число «пятьдесят семь» так: 57. Эти две цифры, поставленные рядом, обозначают сумму двух чисел: правое (в нашем примере 7) дает число простых единиц, а левое (5) — число единиц второго разряда (десятков). Если написаны три цифры подряд, крайняя правая обозначает простые единицы, следующая (средняя) — единицы второго разряда (десятки), а крайняя левая — единицы третьего разряда, т. е. сотни; значит, 238 обозначает сумму двух сотен, трех десятков и восьми единиц. Вообще, из двух написанных рядом цифр левая выражает единицы, в десять раз большие, чем правая. Не только сама цифра, но и ее место,

ее позиция*) имеют значение. Поэтому нашу нумерацию называют позиционной нумерацией.

Напишем по нашей нумерации число «сто два». Здесь одна единица третьего разряда (сотня) и две простые единицы. Записать это так: «12» — нельзя: ведь так записывается число «двенадцать». Писать «1 2», оставляя место для отсутствующего разряда, неудобно; можно подумать, что здесь широко написанное число «двенадцать» или просто два числа: «один» и «два». Как, далее, отличить в записи следующие числа: «двенадцать» и «сто двадцать»; где оставлять при этом пустое место? Для устранения этих неудобств и введена «позиционная пробка» — цифра нуль. Ее пишут на месте отсутствующего разряда. С ее помощью числа «двенадцать», «сто два» и «сто двадцать» напишутся по-разному (12; 102; 120).

Позиционная десятичная нумерация известна была индусам полторы тысячи лет назад (а может быть, и раньше); в Европу ее занесли арабы, вторгшиеся в Испанию в VIII веке нашей эры. Арабская нумерация распространилась по всей Европе и, будучи проще и удобнее остальных систем счисления, о которых речь будет в следующей главе, быстро их вытеснила. До сих пор наши цифры принято называть арабскими. Впрочем, за 1000 лет все цифры, кроме единицы и девятки, сильно изменились. Приводим для сравнения наши (называемые «арабскими») и настоящие арабские цифры:

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

*) Слово «positio» (позйцио) значит по-латыни «положение».

сотни, тысячи, десятки тысяч, сотни тысяч) очень древни и у разных народов звучат по-разному. Думать о происхождении этих названий — дело филолога, а не математика. Слово «миллион» сравнительно недавнего происхождения. По-итальянски millione (миллионэ) есть увеличительное от mille (мйлле), что значит «тысяча». По-русски ему могло бы соответствовать несуществующее слово «тысячища». Придумал слово «миллион» известный венецианский путешественник XIII в. Марко Поло, которому нехватило обыкновенных чисел, чтобы рассказывать о необычайном изобилии людей и богатств далекой Небесной Империи*). Теперь миллионами, десятками и сотнями миллионов называют единицы седьмого, восьмого и девятого разрядов. Тысяча миллионов называется биллионом или миллиардом, а далее, для построения числовых наименований, единых во всем мире, используются латинские числительные. Чтобы лучше понять, как строятся названия этих числовых гигантов, вспомним, что каждые три разряда образуют класс: простые единицы, десятки и сотни образуют первый класс; тысячи, их десятки и сотни — второй класс; миллионы — третий класс, биллионы — четвертый и т. д.

Чтобы назвать единицу какого-нибудь класса, начиная с четвертого, надо уменьшить номер класса на два и к полученному числу, названному по-латыни, прибавить окончание «иллион». Так, единица пятого класса называется «триллион», потому что 5 — 2 = 3, а 3 по-латыни très (трэс); в сложных же словах très переходит в tri (звучит так же, как наше «три»). Возьмем единицу двадцать второго класса. Это будет, как нетрудно сообразить, единица 64-го разряда (единице двадцать второго класса предшествует 21 класс, т. е. 21X3 = 63 разряда). Значит, запишется это число так:

Как же его назвать? От номера класса отнимаем двойку: 22 — 2 = 20; двадцать по-латыни viginti (вигйнти); значит, наше число следует назвать «вигинтиллион».

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

*) Так в старину называли Китай.

миллионами нулей. Впрочем, и записать такое число практически невозможно.

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

Позвольте, позвольте, — перебьет читатель: а физика, а астрономия? Ведь за большими числами даже кличка установилась: «астрономические» числа!

Терпенье, читатель! Сейчас будет речь и об «астрономических» числах. Но раньше приведем таблицу наименований единиц высоких разрядов не столько для пользы (польза от нее, как мы скоро увидим, невелика), сколько для удовлетворения любопытства.

1 000 000 000 (единица 10 разряда или 4 класса) — биллион, 1 000 000 000 000 ( » 13 » »5» ) — триллион, 1 000 000 000 000 000 ( » 16 » »6» ) — квадриллион, 1000 000 000 000 000 000 ( » 19 » »7 » ) — квинтиллион.

Далее следуют: секстиллион, септиллион, октиллион, нониллион, дециллион, ундециллион и т. д.

В некоторых странах, например во Франции, биллионом называют не тысячу, а миллион миллионов, т. е. единицу 13-го разряда; триллионом называют миллион этих «крупных» биллионов (наш квинтиллион) и так далее, считая классы не по три, а по шесть разрядов. Это несколько упрощает наименование больших чисел.

Поговорим теперь об «астрономических числах»; причем, прежде чем забираться на небо, поищем их на земле. Чему равны, например, поверхность, объем и масса земного шара? Заглянув в учебник географии, находим:

Поверхность земного шара— 509 000 000 км2,

Объем » » — 1 070 000 000 000 км8,

Масса » » —6 000 000 000 000 000 000 000 тонн.

Последнее число (масса) представляет собою 6 единиц 22-го разряда, т. е. шесть секстиллионов.

Все эти числа обладают одной особенностью; это — числа «круглые», оканчивающиеся нулями. Разумеется, ни поверхность, ни объем Земли не могут быть выражены таким «круглым» числом квадратных и кубических километров.

«Круглота» здесь кажущаяся. Ведь все геодезические измерения на земной поверхности — приближенные, хотя и производятся очень тщательно; поэтому и числа для поверхности и объема земного шара суть числа приближенные.

Рассмотрим внимательнее число 509 000 000 (пятьсот девять миллионов). Шесть нулей справа не обозначают здесь отсутствия тысяч и низших разрядов. Этих разрядов мы либо не знаем, либо сознательно не пишем, так как такая точность нам не нужна. Мы округляем результат, мы говорим : число квадратных километров земной поверхности складывается из пятисот девяти миллионов и какого-то числа тысяч, сотен, десятков и единиц, но какого именно — точно не указываем.

В практической жизни при счете предметов, которых очень много, например жителей какой-либо страны или красных кровяных телец в крови человека, а также при измерении различных величин удается определить только первые 3 — 4 верные цифры результата. При точнейших измерениях современной физики, которые сопровождаются предосторожностями, превосходящими самые смелые выдумки технической фантазии, удается получить семь, в редчайших случаях — восемь верных цифр; если получается целое число больше чем с восемью цифрами, то приходится дописывать на конце нули. Значит, любое большое число, данное практически, можно записать как произведение не более чем восьмизначного (а чаще—трех-четырехзначного) числа на «единицу с нулями»*) (например, поверхность земли 509 000 000 км2 можно записать так: 509 X 1 000 000 или 509-1 000 000). Числа до миллиарда нетрудно и назвать и записать; следовательно, все дело в том, чтобы рационально записывать и называть числа, изображаемые единицей с большим числом нулей.

Тут нам на помощь приходит понятие степени. Число, изображаемое единицей с нулями, является степенью десяти. Например, сто есть вторая степень десяти (100 = 102), тысяча — третья степень десяти (1000=103). Вообще, число, изображаемое единицей с нулями, представляет собою такую степень десяти, сколько у него нулей; это можно записать следующим образом:

*) Так коротко называют число, которое имеет первую цифру 1, а все остальные — нули, например 10, 100, 1000, 10 000 000 и т. д.

Можно сказать и так: единица я-го разряда представляет собою (п—1)-ю степень десяти (например, миллион — единица 7-го разряда — равняется 106).

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

6 000 000 000 000 000 000 000 тонн.

Теперь мы его можем записать так 6-1021 тонн, а назвать: «шесть на десять в двадцать первой» (подразумевается: степени). Это и коротко и удобно.

Чтобы привыкнуть к этой системе обозначений и названий, рассмотрим несколько примеров.

После первой мировой войны 1914—1918 гг. в ряде стран, в том числе и у нас, была хозяйственная разруха, сопровождавшаяся обесцениванием денег. Приходилось выпускать огромные массы бумажек все более и более высокой номинальной стоимости. Это явление, называемое инфляцией, сопровождалось у нас несколько раз деноминацией, т. е. выпускались деньги сравнительно невысокой номинальной стоимости, причем объявлялось, что один рубль нового выпуска равняется сотне или тысяче рублей предыдущего. Эти деноминации приводили к тому, что на денежных знаках не приходилось печатать очень большие числа: дальше миллионов дело не шло. Но в Германии, где инфляция не сопровождалась деноминацией, существовали боны и даже почтовые марки необычайно высокого номинального достоинства: в десятки и сотни миллиардов марок. На рис. 1 читатель видит несколько почтовых марок с «астрономической» номинальной стоимостью. Высший номинал почтовой марки,

Рис. 1.

выпущенной в Германии, — пятьдесят миллиардов, т. е. 5 • 1010 марок; боны бывали еще более высокого достоинства.

Классическим примером числового гиганта является награда, которую, если верить старинной легенде, потребовал себе изобретатель шахматной игры. Он, гласит предание, просил за первую клетку доски одно зерно риса, за вторую — два, за третью — четыре и т. д., за каждую последующую — в два раза больше, чем за предыдущую. Эта скромная на вид просьба оказалась невыполнимой: все житницы мира не могут вместить риса, затребованного хитрым изобретателем. Действительно, за первую клетку ему следовало получить одно зерно, т. е. 2—1. За первую и вторую ему следовало 1 -{- 2 = 3 = 2 • 2 — 1 зерно. За первые три клетки 1 ~\- 2 -{-—[- 4 = 7 = 2-2-2 — 1 зерен. Мы видим, что за некоторое число а первых клеток придется отдать

Значит, за все 64 клетки изобретателю причитается 264 — 1 зерен*). Число 2е4 легче всего вычислить, пользуясь сочетательным свойством умножения: ведь 264 есть произведение 64 двоек; их можно соединить в 4 группы: из 20, из 20, из 20 и из 4 двоек; мы получим:

Вычислить 210=1024 нетрудно. Помножив 1024 на себя, получим 220 = 1 048 576. Следовательно,

Остается сделать скучное, но не трудное умножение. Окончательно получим:

Число это читается так: восемнадцать квинтиллионов четыреста

*) Читатели, знакомые с прогрессиями, сообразят, что числа зерен, приходящиеся на каждую клетку, образуют геометрическую прогрессию со знаменателем 2, т. е. ~ 1, 2, 4,..., 203. Сумма членов такой прогрессии равна

сорок шесть квадриллионов семьсот сорок четыре триллиона семьдесят три биллиона семьсот девять миллионов пятьсот пятьдесят одна тысяча шестьсот пятнадцать. Оно приблизительно равно 18*1018 (читается так: «восемнадцать на десять в восемнадцатой»).

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

Ответом этой задачи служит не наивное число 999 и не внушительное 9" или 999, а «трёхэтажный» гигант 99. Запись его с помощью нашей системы счисления приблизительно такова: 4 • 10369 693 099 (четыре на десять в триста шестьдесят девять миллионов шестьсот девяносто три тысячи девяносто девятой; его и по сокращенному способу назвать трудно!):

(я« — знак приближенного равенства).

Рядом с таким числом исполином «астрономические» числа кажутся жалкими карликами. Рассмотрим, например, расстояние до самых далеких небесных объектов — галактик, доступных современным телескопам. Галактики — это грандиозные звездные системы, состоящие из миллиардов звезд; они так далеки, что свет от них до нас доходит почти в 1 миллиард лет; это значит, что они отстоят от нас почти на 1022 километров.

Итак, расстояние до галактик, доступных современным телескопам, равно Юп км или 10м • 10в= 10тсм (в 1 км содержится 100 000= \ 0*см). В физике все длины принято выражать в сантиметрах, поэтому и мы выразили это расстояние в сантиметрах. Это число нетрудно назвать: ведь 1027 равно одной единице двадцать восьмого разряда или одной единице десятого класса. Отнимая от десяти два, получим восемь (см. стр. 10 — как называть большие числа). Значит, название нашей единицы должно происходить от латинского octo (восемь), т. е. расстояние до галактик, доступных современным телескопам, равно одному октиллиону сантиметров.

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

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

ГЛАВА II

КАК СЧИТАЛИ НАШИ ПРЕДКИ?

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

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

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

Вот японские иероглифы, изображающие числа:

Еще более замысловаты китайские иероглифы:

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

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

Римские цифры общеизвестны; вот они:

Знаки эти, собственно, не цифры, а заглавные латинские буквы: «и», «вэ», «икс», «эль», «це», «де» и «эм». Но они играли роль цифр: с их помощью римляне могли записать любое число до миллиона. Вот как это делалось. Два и три записывались соответственно так: II, III (т. е. две единицы, три единицы). Четыре записывалось IV: единица, поставленная слева, «отнималась» от пяти. Наоборот, единицы, по-

ставленные справа, прибавлялись: пять, шесть, семь и восемь записывались так:

V, VI, VII, VIII.

Далее приходилось вводить значок X. Девять записывалось следующим образом: IX (от десяти отнимается единица), а десять, одиннадцать и т. д. так:

X, XI, XII, XIII, XIV.

Пятнадцать получалось комбинированием значков десятки и пятерки: XV; двадцать, тридцать — с помощью десяток:

XX, XXX.

Для сорока и выше приходилось вводить знак L. Сорок один, например, писали так: XLI (десять отнимается, а единица к пятидесяти прибавляется). Для девяноста использовался знак сотни С, именно, 90 записывалось так: ХС. Заметим, что 49 и 99 писали не так: XLIX, XCIX, а так: IL, 1С. Сто два писалось СП, триста семьдесят четыре — CCCLXXIV и т. д. Большое число, например 29 635, записывали следующим образом:

XXIXmDCXXXV

(маленькая буква т*) обозначала тысячи).

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

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

*) Начало латинского слова mille (мйлле) — тысяча.

Вот славянские цифры:

Числа одиннадцать, двенадцать,. . . записывались соответственно так: Xi,gl, . . .; двадцать один, двадцать два,. . . — К A, KB . . . и т. д. Титло ставилось только над одной из цифр. Порядок цифр при записи числа был такой же, как в его устном названии. Мы говорим, например, «пятнадцать» (по славянски — пятьнадесять), — называя вперед цифру единиц, потом десяток. Славяне так и писали: €|эт. е. впереди писали пятерку, а за нею десяток. Наоборот, в числе «двадцать три» мы сперва называем десятки, потом единицы; у славян это отражалось в письме: писали кг. Место цифры, ее положение в числе не имело значения.

С помощью этих знаков легко записывались большие числа. Число 29 946 записывалось, например, таким образом: *ка й[л\5 (знак # обозначал тысячи). С помощью повторения знака # можно было записывать очень большие числа. Вот как, например, записывалось число 20 178 073: *рои5г«

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

Скажем несколько слов о названиях чисел в древней Руси. Числа до тысячи назывались почти так же, как сейчас*). Десять тысяч называлось «тьма», и число это считалось столь огромным, что тем же словом обозначалось всякое неподдающееся учету множество. В более позднее время (XVI—XVII вв.) появилась своеобразная система наименования чисел, так называемое «великое словенское число»; в этой системе числа до 999 999 называются почти так же, как теперь. Слово «тьма» обозначает не десять тысяч, а миллион. Кроме того, появляются следующие названия: «тьма тем» или «легион» (т. е. миллион миллионов или по теперешнему триллион, т. е. 1012); легион легионов («леодр»), который мы теперь должны записать с помощью единицы с 24 нулями (септиллион — Ю24); наконец, леодр леодров («ворон»), т. е. по нынешнему 1048. Про это число наши предки говорили, что «более сего несть разумевати». Впрочем, иногда (рукопись XVII в.) упоминалась еще «колода», равная десяти «воронам» (1049), но при этом оговаривалось, что «сего числа несть больше»**).

Позиционная нумерация возникла, по-видимому, в древнем Вавилоне. Там она приняла такую своеобразную форму, что о ней стоит поговорить подробнее; это будет сделано немного дальше. От вавилонян позиционная нумерация перешла к индусам.

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

*) Была небольшая разница в произношении: например, один назывался «един», двадцать — «двадесять» и т. д.

**) См. брошюру проф. А. В. Васильева — «Целое число» или книгу В. Беллюстина «Как постепенно дошли люди до настоящей арифметики».

Три тысячи лет назад индусы уже пользовались хорошо разработанной нумерацией, хотя в памятниках того времени и не упоминаются числа, большие 100 000. В позднейших произведениях индийской письменности встречаются значительно большие числа — до ста квадриллионов (1017). В одной из сравнительно «молодых» легенд о Будде (ей меньше тысячи лет) говорится, что он знал названия чисел до 10В4. Впрочем, индусы, по-видимому, не представляли себе ясно бесконечности натурального ряда, они полагали, что существует какое-то наибольшее число, известное только богам. Доказательство бесконечности числового ряда — заслуга древнегреческих ученых.

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

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

На рубеже XIX и XVIII вв. (до нашей эры) произошло слияние двух народов: сумерийцев и аккадян. Каждый из этих народов имел достаточно развитую торговлю, весовые и денежные единицы. Правда, торговля была мелкая, считать приходилось немного, и разработанной нумерации ни один из этих народов не имел. Единицей веса у сумерийцев была «мина» (приблизительно кг). Денежной единицей служила мина серебра. У аккадян основная единица — «шекель» — была в шестьдесят раз меньше (разумеется, не точно, а приблизительно в шестьдесят раз, но примитивные весы того времени не улавливали разницы). После слияния этих народов «имели хождение» обе системы единиц: минами и шекелями пользовались так, как мы теперь пользуемся килограммами и граммами. А в денежном обращении мины и шекели

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

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

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

Для десяти был особый знак <J • Запись чисел второго десятка тоже понятна:

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

сотни. Например, числа 37 и 54 запишутся так:

Числа восьмого и девятого десятков записываются довольно громоздко; но в них ведь не было надобности. Числа, большего пятидесяти девяти, благодаря наличию трех единиц, вавилонянам записывать вообще не приходилось.

Первоначально мины обозначались более крупными значками, чем шекели. Например, 20 мин 37 шекелей записывалось так:

В более поздние времена все знаки записывались совершенно одинаково, и только положение знака показывало, какие единицы он обозначает. Например, 2 таланта 13 мин 41 шекель записывалось так:

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

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

обозначает не обязательно 1 талант 23 мины 15 шекелей — совершенно так же записывается отвлеченное число, содер-

жащее одну единицу третьего, 23 единицы второго и 15 единиц первого разряда, причем единицы каждого последующего разряда в шестьдесят раз крупнее единиц предыдущего. Запись

обозначает, по нашему,

Аналогично записываются четырех-, пяти-, вообще многозначные числа. Например, запись

обозначает

Наибольшее число, которое встречается в вавилонских «рукописях», равно 608 + 10-607. Вавилонская нумерация — вполне разработанная нумерация с основанием 60 — шестидесятиричное счисление.

Как же обозначали вавилоняне нуль? Как записывали они число 3605, равное 1 • 60а + 5, т. е. содержащее одну единицу третьего, пять единиц первого и совсем не содержащее единиц второго разряда? Они в течение сотен лет вовсе не пользовались знаком разделения. В нужных случаях они оставляли между цифрами более широкий промежуток:

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

Теперь 3605 записывают так:

а 65 так:

— смешать их больше нельзя.

Однако, введя «позиционную пробку» в середине чисел, вавилоняне так и не додумались ставить ее на конце. И до самого падения вавилонской культуры числа «единица», «шестьдесят», «три тысячи шестьсот» записывались одинаково: Y* Записывать шестьдесят так: ^ § вавилонянам не приходило в голову. Только индусы, заимствовавшие у них позиционную нумерацию, научились правильно использовать знак нуля и, введя вместо шестидесяти основание десять, дали счислению его современную форму.

Вавилонская (шестидесятиричная) система счисления удержалась до сих пор при измерении углов и времени. Шестую часть окружности делят на 60 градусов, градус на 60 минут, минуту на 60 секунд. Точно так же час делится на 60 минут, минута на 60 секунд, подобно тому, как талант делился на 60 мин., а мина на 60 шекелей. Скажем, кстати, несколько слов о происхождении названий «минута» и «секунда». Минута (minuta) значит по-латыни: «маленькая»; а секунда (secunda) значит: «вторая». Минуты это были «partes minutae primae» (партэс минутэ прймэ) — «впервые малые части», а секунды — «partes minutae secundae» (пертэс минутэ секундэ) — «вторые малые части» градуса или часа.

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

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

Почти четыре тысячи лет назад в Вавилоне возникла позиционная нумерация. В Индии она приняла форму позиционной десятичной нумерации с применением «позиционной пробки» — нуля. У индусов эту систему записи чисел заимствовали арабы, ставшие в VIII — IX вв. н. э. одним из самых культурных народов мира. От арабов переняли ее европейцы (отсюда — название: арабские цифры).

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

ГЛАВА III

ДЛЯ ЧЕГО И КАК АРХИМЕД СЧИТАЛ ПЕСОК?

В III в. до н. э. на острове Сицилия жил математик совершенно исключительной одаренности. И сейчас, более чем через две тысячи лет после его кончины, имя его известно любому школьнику. Это был Архимед. Замечательный геометр, механик, физик и военный инженер, он оставил среди своих многочисленных творений удивительное сочинение по арифметике. Называется оно «Псаммит или исчисление песку в пространстве, равном шару неподвижных звезд».

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

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

*) Архимед опирается здесь на воззрения выдающегося древнегреческого астронома Аристарха Самосского (конец IV в. — 1-я половина III в. до н. э.), полагавшего, что Солнце неподвижно и находится в центре сферы неподвижных звезд, что Земля обращается по окружности, в центре которой находится Солнце.

АРХИМЕД

Один из античных бюстов, считавшихся изображением Архимеда.

по-нашему 150-107 км*). Это — в десять раз больше среднего расстояния от Земли до Солнца, для которого современные измерения дают приблизительно 150-106 км. Таким образом, радиус сферы неподвижных звезд, в пересчете на наши меры, Архимед принимал равным 15 • 1012 км, что значительно превосходило даже аристархов радиус сферы неподвижных звезд. Это примерно в три раза меньше фактического расстояния до ближайшей к нам звезды. Значит, принятый Архимедом радиус сферы неподвижных звезд примерно в 650 миллионов раз меньше, чем расстояние до галактик, доступных нашим современным телескопам.

Теперь нетрудно вычислить объем «шара неподвижных звезд». Он равен

Остается подсчитать, сколько в этот объем можно вместить песчинок. Архимед считал, что в объеме макового зерна может вместиться мириада (10 000) песчинок (иными словами, он рассматривал весьма тонкий песок — легкую пыль). Поперечник макового зерна он считал равным одной сороковой части дюйма***), т. е. по-нашему мм.

Считая, для простоты, что зерно имеет форму кубика, мы видим, что в одном кубическом миллиметре содержится 8 маковых зерен или 80 000 песчинок; в кубическом метре — в 109 (в биллион) раз больше, т. е. 8-1013, а в кубическом километре — еще в 109 больше, т. е. 8 • 1013-109 = 8 • 1022 песчинок. Остается перемножить число кубических километров «шара неподвижных звезд» (135-10а8) и число песчинок в одном кубическом километре (8-1022). Это даст, примерно, 1063 песчинок — число и по нашим современным масштабам громадное.

Мы без труда решили архимедову задачу. Но во времена Архимеда не было названий для чисел, больших десяти тысяч,

*) Греческая стадия равнялась приблизительно 150 метрам. От слова «стадия» происходит «стадион» первоначально—разделенная на стадии дорожка, на которой состязались бегуны. Слово «мириада» значит десять тысяч. Слов для обозначения чисел, больших чем 10000, в греческом языке не было.

**) Мы считаем, для простоты расчетов, я = 3. Эта неточность не влияет на существо результата.

***) Греческий дюйм равнялся приблизительно 2 см.

не было десятичной системы счисления, не было знака показателя, не было разработанных правил действий. Заслуга Архимеда именно в том, что он выдумал, как называть большие числа и как производить с ними вычисления (при вычислениях он пользовался только свойствами арифметической и геометрической прогрессий, которые и в то время были известны). Это вычисление очень интересно, но говорить о нем в нашей небольшой книжке нет возможности*). Мы рассмотрим только архимедову систему счисления.

Для первого десятка тысяч, т. е. до первой мириады, Архимед использует существовавшие тогда греческие числительные. Далее он называет числа до мириады мириад подобно тому, как мы называем числа до тысячи тысяч. Так число 85 643 911 Архимед назовет: «восемь тысяч пятьсот шестьдесят четыре мириады три тысячи девятьсот одиннадцать». Все числа от единицы до мириады мириад он называет «числами первыми». Простую единицу он называет «единицей чисел первых», а мириаду мириад единиц чисел первых — «единицей чисел вторых». Итак, «единица чисел вторых» — это 108. Теперь нетрудно назвать числа до мириады мириад «единиц чисел вторых», т. е. по-нашему до 1016. Это число Архимед называет «единицей чисел третьих» и т. д. Мы видим здесь позиционную систему счисления с основанием 108, но разработаны только названия, а не написание чисел, в котором Архимед для решения своей задачи не нуждался. Единица каждого разряда у Архимеда в 108 раз больше единицы предшествующего разряда.

Таким образом можно дойти до единицы любых чисел вплоть до мириадо-мириадных. Единица п-х чисел будет равна, как легко сообразить, 108(п !) (например, единица десятых чисел—108(10_1) = 107'2; единица сто двадцать четвертых чисел—ю8(124_1) = 10984 и т. д.). Счет можно довести до мириады мириад чисел мириадо-мириадных, т. е. до ! 08.108( юо 000 000-D = 108. ш Этих чисел Архимеду вполне достаточно для решения его задачи. Мы видели, в самом деле, что решением служит 1063= 107« 108(81), т. е. тысяча мириад единиц чисел восьмых.

*) Интересующиеся с удовольствием прочтут сами «Псаммит», который, начиная с 1824 г., неоднократно издавался в русском переводе. Последнее издание: «Исчисление песчинок (Псаммит)», перевод Г. Н. Попова, М.—Л., 1932 г.

Но Архимед на этом не останавливается. Как мы, кроме единиц различных разрядов, вводим единицы различных классов, так он вводит числа различных периодов. Все числа до 108*108 он называет числами первого периода. Мириаду мириад чисел мириадо-мириадных он называет «единицей первых чисел второго периода». Затем вводятся вторые, третьи числа и т. д. до мириадо-мириадных чисел второго периода. Мириада мириад мириадо-мириадных чисел второго периода (Ю2*8,108) образует единицу первых чисел 3-го периода. Единицей первых чисел четвертого периода будет число 103'8*108. Вообще единицей первых чисел я-го периода будет число ю^-1)*8*108, а единицей т-х чисел я-ro периода — число io^-1)*8,l°8+m,8-m. Так Архимед доходит до мириады мириад мириадо-мириадных чисел мириадо-мириадного периода, т. е. до числа 108,101в. На этом Архимед останавливается. Но продолжить его путь нетрудно. Вслед за периодами можно ввести какие-нибудь циклы или периоды второго порядка и т. д.

Архимедову систему счисления удобно представить в форме следующей таблицы:

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

Как было показано на стр. 14, изобретатель шахматной игры потребовал

18 446 744 073 709 551 615

зерен. Разобьем это число на «архимедовы разряды», т. е. на группы по 8 цифр

1844 6744 0737 0955 1615.

Здесь, очевидно, тысяча восемьсот сорок четыре единицы третьих чисел, шесть тысяч семьсот сорок четыре мириады семьсот тридцать семь единиц вторых чисел, девятьсот пятьдесят пять мириад тысяча шестьсот пятнадцать единиц первых чисел. Это название немногим длиннее нашего (восемнадцать квинтиллионов... и т. д., см. стр. 14).

Для числа 99° хватило бы чисел первого периода. Но число 1010 будет уже равняться единице чисел пять тысяч мириад первых (5000 0001-х) периода тринадцатого.

Вот какое удобное орудие счета создал Архимед две тысячи двести лет тому назад!

ГЛАВА IV

НЕ ДЕСЯТКАМИ, А ПЯТКАМИ ИЛИ ДЮЖИНАМИ

При современном состоянии науки нельзя, по-видимому, придумать систему счисления, которая была бы удобнее позиционной. Но в основу позиционной системы счисления можно ставить разные числа.

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

Есть, впрочем, одна система счисления, настолько своеобразная, ее преимущества перед десятичной в одних вопросах и недостатки в других так резко бросаются в глаза, что стоит ее рассмотреть подробнее. Это — двоичная система, или система при основании 2. Ей будет посвящена следующая глава. А в этой главе поговорим о позиционных недесятичных системах вообще и научимся переходить от одной из таких систем к другой.

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

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

систему с основанием пять. Эта система использует для записи всех чисел только пять знаков — цифр: знаки для чисел «одно», «два», «три», «четыре» и позиционную пробку — знак для нуля. Для обозначения этих первых четырех чисел и нуля можно воспользоваться хотя бы нашими цифрами: 1, 2, 3, 4, О, но напечатанными жирным шрифтом.

Число «пять», являющееся одним «пятком», т. е. одной единицей второго разряда, придется записать так: 10 (как наше «десять»), поставив на месте отсутствующих простых единиц нуль.

Запишем по пятеричной системе число 387 (триста восемьдесят семь; обычный, светлый шрифт указывает на обычную, десятичную запись). Прежде всего выясним, сколько в нашем числе пятерок (единиц второго разряда) и сколько простых единиц. Чтобы это узнать, поделим 387 на пять. Частное даст число пятерок, остаток — число простых единиц:

Итак, в нашем числе 2 простые единицы и 77 единиц второго разряда. Но каждые пять единиц второго разряда составляют единицу третьего разряда; очевидно, в семидесяти семи единицах второго разряда содержится некоторое количество единиц третьего разряда. Чтобы найти его, повторяем операцию деления: делим 77 на 5:

Остаток (2) дает число единиц второго разряда, частное же — число единиц третьего. Ищем, сколько в пятнадцати едини-

Рис. 2.

цах третьего разряда содержится единиц разряда четвертого:

15:5 = 3.

Пятнадцать единиц третьего разряда состоят целиком из единиц четвертого разряда. Отсутствие остатка указывает, что «свободных» единиц третьего разряда нет. Что касается трех единиц четвертого разряда, то ясно, что в них содержаться единицы высших разрядов не могут. Значит, число 387 состоит из трех единиц четвертого разряда, не содержит вовсе единиц третьего разряда, содержит две единицы второго и две единицы первого разрядов, т. е. может быть записано так: 3022. Все действия могут быть сгруппированы вместе:

Напечатанные жирным шрифтом числа (остатки и последнее частное) нужно еще переписать в обратном порядке.

Решим теперь обратную задачу. Пусть число дано в пятеричной системе: 2341. Найти его десятичное выражение.

Подумаем, что обозначает каждая из цифр этого числа. Стоящая справа единица обозначает просто 1. Стоящая на втором (справа) месте четверка обозначает четыре пятка, т. е. 4-5; следующая за ней тройка обозначает три «пять раз взятых пятка», т. е. 3 • 52; наконец, крайняя левая двойка обозначает 2 • 53. Следовательно,

Заметим, что и написанное по десятичной системе число, например 3208, может быть дано в аналогичной форме: 3 • 103 + 2 -10'2 + 0-10 + 8. (В 3-м слагаемом этого выражения (0-10) множитель «нуль» есть число целое, но не натуральное.)

Вообще, если в основание системы счисления положено число т, то abcdk*) обозначает:

*) Здесь, в отличие от принятой в алгебре записи, выражение abcdk обозначает не произведение чисел a, b, ct d и kt a число, записанное в некоторой позиционной системе счисления с помощью цифр а, bt ct dt k.

В нашем быту остались кое-какие пережитки счета дюжинами. Английский фут, как и русский, делится на 12 дюймов. Ряд товаров упаковывается в тару дюжинами, а для дюжины дюжин в торговле имеется специальное наименование — гросс. Надо сказать, что двенадцатеричная система счисления в некотором отношении лучше десятичной: двенадцать имеет четыре целых делителя (не считая 1 и самого числа 12): 2, 3, 4, 6, тогда как 10 — только два (2 и 5). Поэтому при двенадцатеричной системе было бы больше «круглых» чисел, а это позволило бы установить больше сокращенных приемов выполнения действий. Но в общем выигрыш был бы невелик.

В двенадцатеричной системе счисления, кроме нуля и цифр от одного до девяти, пришлось бы ввести еще цифры для обозначения десяти и одиннадцати. Обозначим условно эти цифры значками X и А. Запишем, например, число 1443 по двенадцатеричной системе:

Последнее частное равно десяти, остатки: нуль и три. Следовательно, 1443 = ХОЗ.

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

В какой системе счисления она справедлива?

Внимательно приглядываясь к выполнению действий, мы замечаем, что 2 4 дают какое-то число, оканчивающееся

единицей*). Но «два» и «четыре» дадут «шесть», как бы мы их ни записывали. Значит, знака для числа «шесть» в этой системе счисления нет. Но цифру 4 (четыре) мы в данной записи находим. Следовательно, система счисления может быть либо пятеричной, либо шестеричной. Записав число «шесть» в обеих этих системах, получим 11 (пятеричная) и 10 (шестеричная). Следовательно, в указанном примере, где 2 + 4 дает число, оканчивающееся единицей, система счисления — пятеричная. Вот еще легкий пример: в какой системе счисления 3X3=10? Читатель сообразит, что это возможно только при основании девять.

Не всегда, однако, по виду действия можно однозначно установить, в какой системе счисления справедлива запись. Например, равенство 122X3 = 366 справедливо в любой системе счисления с основанием, большим шести.

Но случается и так, что но «жалким остаткам» какого-либо действия удается не только установить систему счисления, в которой произведена запись, но и восстановить действие. Вот пример: пусть известны лишь некоторые цифры действия (остальные заменены звездочками):

По какой системе счисления это написано? Как восстановить пропущенные цифры?

Смотрим прежде всего на последние цифры множимого и множителя и на последнюю цифру результата. Мы видим, что число «четыре» (дважды два) в этой системе счисления оканчивается единицей, т. е. для него нет специального знака. Это возможно только при основаниях, не превосходящих четырех, т. е. при основаниях 2, 3 или 4. При основании «2» число «четыре» (квадрат основания) запишется так: 100; при основании «3» число «четыре» запишется так: 11 (т. е. 31 + 1). Наконец, при основании «4» число «четыре» (само основание) запишется так: 10. Значит, искомым основанием

*) Предполагается, что цифры обозначают те же числа, что и в нашей системе счисления, т. е. что 1 есть знак для единицы, 2 — для числа «два» и т. д.

может быть только число «три». «Три» и будет ответом на первый вопрос задачи,

Обозначив далее вторую цифру множимого через х и учитывая единицу в уме, получим, что 2л;+ 1 дает число, оканчивающееся нулем; это возможно только при лг=1*). Точно так же найдем, что первая цифра множимого равна единице. Значит, множимое равно 112, т. е. числу «четырнадцать».

Левая цифра множителя при умножении на два дает число, оканчивающееся единицей. Но 2-0 = 0; 2-1=2; 2-2 = 11. Значит, эта цифра может равняться только двум, множитель равен 22 (восемь) и все действие запишется так:

Для проверки запишем 112 в троичной системе счисления:

Получается как раз 11011.

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

*) X может равняться 0, или 1, или 2 (ведь система-то счисления — троичная). Но 2 0 -f 1 = 1; 2 • 1 + 1 = 10; 2 • 2 + 1 = 12. Значит, X должен равняться 1.

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

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

При маленьком основании и таблица сложения и таблица умножения значительно проще, чем у нас. Вот эти таблицы при основании «3»:

Ясно, что заучить эти таблицы значительно проще, чем наши.

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

ГЛАВА V

АРИФМЕТИКА, В КОТОРОЙ НЕ НУЖНО СЧИТАТЬ

Система счисления, в основание которой положено число «два», обладает многими замечательными свойствами и заслуживает того, чтобы на ней задержаться. В ней используются только два знака для записи чисел: знак для единицы (1) и позиционная пробка — нуль (0).

В этой главе, как и в предыдущей, числа, изображенные по двоичной системе, будут напечатаны жирным шрифтом, а числа, записанные по десятичной — обыкновенным.

Для единицы мы имеем знак 1. Число «два», будучи основанием системы счисления, станет единицей второго разряда и запишется так: 10. Число «три», состоящее из единицы второго разряда (два) и простой единицы, запишется так: 11. «Четыре» является квадратом двух, т.е. единицей третьего разряда, поэтому оно запишется так: 100. Что касается числа восемь, равного двум в кубе, то его придется записать, как нашу тысячу: 1000.

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

Начнем со сложения. Сложим, например, 10110 и 1101 (т. е. 22 и 13).

Напишем эти числа одно под другим, как при обычной записи:

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

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

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

Запись, сравнительно с нашей, десятичной, очень громоздка. Но действие выполняется автоматически.

Вычитание производится проще всего, если пользоваться «правилом дополнения». Десятичным дополнением данного числа называется разность между ближайшей

большей степенью десяти («единицей с нулями») и данным числом. Так, например, десятичным дополнением числа 7 будет 3, числа 89 — число 11, для числа 6385 десятичным дополнением будет 3615, для числа 580 —число 420. Чтобы найти дополнение, нужно все цифры данного числа вычесть из девяток, а последнюю (не считая нулей на конце) — из десяти. Теперь нетрудно заменить вычитание сложением: вместо того чтобы вычитать какое-либо число из данного, достаточно прибавить к последнему десятичное дополнение вычитаемого и вычесть степень десяти. Например, вычитая 5833 из 11021, расположим действие так:

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

т. е. 101001000. Это и есть двоичное дополнение числа 11010111000.

Умея находить двоичные дополнения, мы сумеем автоматически выполнять вычитание. Вычтем, например, 11011 из 1 110001:

Находим двоичное дополнение вычитаемого. Получим:

Заменяем теперь вычитание сложением:

В десятичной системе запись вычитания этих же чисел будет короче: 113—27=86.

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

Таблица умножения в двоичной системе счисления имеет следующий вид:

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

Перемножим, например, числа 111001101 и 1101101:

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

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

Самым трудным из арифметических действий является, несомненно, деление. Всякий помнит, вероятно, каким сложным ему казалось деление в детстве. Да и взрослый человек вряд ли испытает особое удовольствие, деля, например, 8 663 545 198 на 87 995. В средние века деление считалось столь трудной операцией, что людям, искусным в этом действии, давалась ученая степень.

А в двоичной системе счисления и деление выполняется совершенно автоматически! Правда, простота и автоматичность покупаются здесь ценою чрезвычайно громоздкой записи. В качестве примера разделим 11011101 на 10 111. Действие располагаем так же, как при обычном делении, но каждый раз под делимым будем подписывать не произведение делителя на соответствующую цифру частного, а двоичное дополнение этого произведения (при этом нули спереди можно и не зачеркивать):

В частном получается 1001 и в остатке 1110. Справа дано выполнение деления этих же чисел в обычной (десятичной) записи. Сразу видно, что двоичная система практически неприменима потому, что запись очень громоздка. Но что-то считать, что-то пробовать, что-то замечать — здесь совершенно не приходится.

На необычайную простоту и своеобразие двоичной системы счисления первым из европейцев обратил внимание знаменитый философ и математик Г. В. Лейбниц (1646—1716). Но китайцам она, по-видимому, была известна значительно раньше.

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

Большинство применений двоичной системы основано на следующем ее свойстве: во всех остальных системах счисления нужно указывать, сколько единиц каждого разряда входит в состав данного числа (например, называя или записывая число девятьсот пятьдесят один, мы отмечаем, что оно содержит девять сотен, пять десятков и одну единицу); в двоичной же системе единица любого разряда может либо присутствовать (тогда непременно в единственном числе), либо отсутствовать. Нет надобности говорить, что в двоичном разложении некоторого числа имеется столько-то единиц третьего разряда, столько-то второго, столько-то первого. Достаточно сказать: есть единица третьего разряда, нет — второго, есть — первого. Этим число вполне определено: в рассмотренном примере мы имеем число 101 =5. Чему, например, равно число, в котором есть единица десятого разряда, нет — ни девятого, ни восьмого, ни седьмого, есть — шестого и пятого, нет — четвертого и всех низших? Ответ получается сразу: это будет число 1000 110 000, т. е. 560.

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

Любое число может быть представлено в виде суммы нескольких членов этого ряда. Например, 19 равно сумме первого, второго и пятого чисел ряда (номера членов проставлены под ними); сто равно сумме третьего, шестого и седьмого членов и т. д. Действительно, всякое число можно записать в двоичной системе счисления: тогда единицы укажут на присутствующие, а нули — на отсутствующие члены этой прогрессии (19=10011, 100=1 100100).

Теперь нетрудно объяснить следующий фокус с угадыванием числа. Вы предлагаете товарищу задумать какое-нибудь число от 1 до 31, затем даёте ему картонную табличку, изображенную на рис. 3, и предлагаете, не показывая вам таблицу, сказать, в каких строчках имеется число. Как только он назовет номера строк, вы сейчас же называете задуманное число.

Составлена эта таблица очень просто. В первой строке помещены все те числа (от 1 до 31), в двоичной записи которых на первом справа месте стоит единица (т. е. все нечетные числа). Во второй строке помещены те числа, в двоичном разложении которых на втором месте справа стоит единица. Число «три», например, которое в двоичной системе счисления записывается так: 11, помещено и в первую и во вторую строку, так как у него и первая справа и вторая цифра — единицы. Так же построены и остальные строки. В последней, пятой строке помещены все те числа (в пределах от 1 до 31), у которых на пятом месте двоичного разложения стоит единица, т. е. числа от 16 до 31.

Пусть, например, задумано число 29. Загадывающий видит это число в первой, третьей, четвертой и пятой строках. Назвав вам эти строки, он тем самым невольно указывает, что в двоичное разложение задуманного числа входят единицы первого, третьего, четвертого и пятого разрядов. Вы знаете, что единицами этих разрядов в двоичной системе счисления служат числа 1, 4, 8 и 16 (они выписаны в первом столбце каждой строки). Теперь легко восстановить почти мгновенно задуманное число: нужно только сложить в уме эти несколько небольших чисел, что и даст 29,

Рис. 3.

Для выполнения следующего эффектного фокуса нужно научиться быстро запоминать несколько двузначных чисел (т. е. количество цифр, соответствующее двум телефонным номерам; запомнить сразу два телефонных номера нетрудно, тем более, что держать их в памяти придется всего несколько минут). Фокус состоит в следующем. Вы предлагаете товарищу нарисовать квадратик из 5X5 клеток и расставить в его клетках произвольным образом крестики. Затем в течение полуминуты смотрите внимательно на квадрат и возвращаете его товарищу. Через пять минут вы беретесь нарисовать напамять расположение крестиков, и это вам удается сразу. Окружающим кажется, что это очень просто, но предложите любому в течение полуминуты запомнить расположение крестиков в квадрате: можете быть уверены, что никто этого не сможет сделать.

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

Считайте, что крестики это — единицы, а пустые клетки — нули. Тогда на каждую строку можно смотреть как на число, записанное по двоичной системе. В нашем примере мы имеем следующие числа:

(нули, стоящие впереди единиц, пропущены). Прочитать эти числа легко, вот они:

При некотором навыке этот перевод из двоичной системы в десятичную выполняется почти мгновенно. Остается запомнить серию чисел: 12—22—07—25—10. На перевод из двоичной системы в десятичную и на запоминание этой серии достаточно после небольшой тренировки полуминуты.

Через пять минут, когда расположение крестов у всех исчезло из памяти, вы продолжаете помнить серии чисел: 12—22—07 и 25—10 (как бы два телефонных номера). По этим числам можно сразу восстановить первоначальную таблицу: нужно только написать их одно под другим в двоичной системе счисления и заменить единицы крестиками.

Эта возможность использовать двоичную систему счисления в качестве приема запоминания квадратных таблиц применяется в шифровальном деле и в конспиративном письме. Как это осуществляется, подробно рассказано в книге Я. И. Перельмана «Живая математика»*).

Читатель обратит внимание на то, что во всех наших рассуждениях есть одна нестрогость. Мы несколько раз употребляли выражение: «всякое число (целое) можно записать в позиционной системе счисления с любым основанием». Верно ли это? Рассуждения, которыми мы пользовались в предыдущей главе, записывая одно и то же число при различных основаниях, показывают, что, по-видимому, — верно. Более основательно этот вопрос будет разобран дальше, в конце главы VI (стр. 63); там возможность изображения любого числа в позиционной системе с любым основанием будет строго доказана.

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

*) Физматгиз, М., 1959 г.

ГЛАВА VI

ОБЩАЯ МЕРА

Сложение и умножение — два прямых действия — обладают следующим важным свойством: эти действия всегда выполнимы в целых числах. Точнее говоря, если даны два любых натуральных числа, то всегда можно найти натуральное число, равное их сумме, и натуральное число, равное их произведению. Иначе обстоит дело в случае двух обратных действий: вычитания и деления. Не всегда можно найти натуральное число, равное разности двух данных натуральных чисел (например, не существует натурального числа, равного 5 — 8 или 6 — 6). Точно так же, не всегда удается найти натуральное число, равное частному двух натуральных чисел (например, не существует натурального числа, равного 5:8). Но между вычитанием и делением есть существенная разница. Узнать, вычитается ли одно натуральное число из другого, очень просто. Существует один единственный универсальный «признак вычитаемости»: если число Ь больше числа а или равно ему, то из а нельзя вычесть Ь, т. е. нельзя найти натуральное число, равное (а — Ь). Наоборот, при делении часто бывает нелегко узнать, делится число а на b или нет (т. е. будет ли частное у натуральным числом или нет).

Но этого мало. Из любого натурального числа, кроме единицы, можно вычитать некоторые другие натуральные числа (именно — все числа, меньшие его). При этом различных возможных вычитаемых у числа N будет всегда ровно N—1 (например, для числа 5 «возможными вычитаемыми» будут числа 1, 2, 3, 4, т. е. всего N—1=5—1 = 4 числе).

В случае же деления дело обстоит гораздо сложнее. Существует число, имеющее только один дели гель, — это единица; существуют числа, имеющие два делителя: единицу и самого себя (таковы числа 2, 3, 5, 7 и другие). Наконец, существуют числа, имеющие больше двух делителей: так, например, число 6 имеет четыре делителя (1, 2, 3 и 6). Числа, имеющие ровно два делителя, обладают многими замечательными свойствами. Их называют простыми или первоначальными числами.

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

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

Если существует натуральное число л, равное частному от деления числа а на Ь, т. е. такое, которое при умножении на b дает а, то говорят, что а кратно b или что а делится на Ь. Число b называют делителем числа а. Так, например, 6 кратно двум; 15 делится на 5 и т. д. Тот факт, что b является делителем а, записывают в виде формулы следующим образом:

а = Ьп, где п — натуральное число.

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

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

Теорема 1. Если а делится на b, а Ь в свою очередь делится на с, то а делится на с.

Теорема 2. Если алгебраическая сумма (т. е. сумма или разность) нескольких чисел равна нулю или делится на число Л/, и все слагаемые, кроме одного,- о котором ничего не известно, кратны N, то и это слагаемое тоже делится на N.

Теорема 3. Если произведение двух целых чисел а нЬ делится на число ту не имеющее с а общих делителей (кроме единицы, разумеется), то b делится на т.

Первые две теоремы совершенно ясны. Если 36 делится на 9, а 9 в свою очередь делится на 3, значит, и 36 должно разделиться на 3. Точно так же, если 3 — х—9 + 81 = О, то ясно, что X должен быть кратным трем. Доказывать эти теоремы нужно не для того, чтобы убедить кого-то в их справедливости, а для того, чтобы показать их связь с еще более простыми предложениями. Читатель докажет их без труда. Что касается третьей теоремы, то она, несмотря на кажущуюся простоту, доказывается более сложно. Мы к ней еще вернемся (на стр. 62—63).

Прежде чем итти дальше, задержимся немного на делении с остатком. Если умножение на целое число можно рассматривать как повторное сложение, то деление естественно рассматривать как повторное вычитание. Чтобы разделить, например, 20 на 5, будем вычитать 5 из 20: после первого вычитания получим 15, после второго —10, после третьего —5, после четвертого получим нуль (" при рассмотрении вопросов делимости удобно к натуральным числам присоединить число нуль, рассматривая, таким образом, все целые неотрицательные числа,). Итак, здесь возможны четыре последовательных вычитания; это и значит, что частным от деления 20 на 5 является число 4; кому приходилось считать на счетах или на арифмометре, тому этот взгляд на деление покажется особенно естественным. Нетрудно сообразить, что количество повторных вычитаний равно числу, которое при умножении на делитель (т. е. на повторное вычитаемое) дает делимое (исходное число).

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

отношениях исключительного, числа. Никакое число нельзя делить на 0. Действительно, чему может быть равно а : 0 при а Ф 0? Никакому числу такое частное равняться не может; ведь всякое число, умноженное на нуль, даст 0, а не а. Если же мы нуль попробуем делить на нуль, то в качестве частного сможем взять любое число, ибо любое число при умножении на 0 дает 0. Ввиду этих обстоятельств в математике делить на нуль «строго воспрещается». Напротив, сам нуль можно делить на какое угодно число (не равное нулю), причем частным всегда будет нуль. Говоря о делении целых, но не обязательно натуральных чисел, мы приходим к выводу, что нуль делится на любое не равное нулю целое число без остатка, потому что 0:а = 0, а нуль считается целым числом. На этом основании принято говорить, что нуль есть кратное любого числа.

Повторное вычитание оказывается применимым и тогда, когда делимое не является кратным делителя*). В этом случае последнее вычитание приведет не к нулю, а к некоторому числу, меньшему делителя, — к так называемому остатку. Будем, например, делить 17 на 5 способом последовательного вычитания. Вычитаем 5 из 17 первый раз — получаем 12, вычитаем второй раз — получаем 7, вычитаем третий раз — получаем 2. Дальше вычитать невозможно. Значит, частным от деления 17 на 5 будет 3 (число последовательных вычитаний), а в остатке получится число 2.

Последовательное вычитание числа Ъ из числа а, при котором получается частное п и остаток г, можно «перевести на язык формул», записав его так:

*) Слово «делитель» имеет в арифметике два значения. Во-первых, делителем называют число, на которое делят другое число. Когда мы пишем а : bt то Ь называем делителем, даже если не знаем, что а должно разделиться на него (т. е. и в том случае, когда й \ Ь не есть целое). С другой стороны, всякое число, кратное которого равно а, мы называем делителем а даже и в том случае, когда непосредственно о делении нет речи. В последнем случае вместо слова «делитель» употребляют иногда слово «множитель». Например, выражения: «разложить данное число на простые множители» и «найти все простые делители данного числа» — значит по существу одно и то же. Эта двусмысленность при внимательном отношении к делу никогда не ведет к путанице.

приведение подобных членов дает: а — bn = r или а — г = = Ьпу что формулируется следующим образом: если из числа а, которое при делении на b дает остаток г, вычесть этот остаток, то разность а — г будет делиться на Ь.

Более важно такое расположение членов в нашей формуле:

Это — основная формула, определяющая деление с остатком. При этом существенно, что г меньше Ь. Если г равняется нулю, то деление выполняется нацело. Чтобы не исключать и этого случая, мы в нашу последнюю формулу подставим и знак равенства (г = 0), присоединив его к знаку неравенства. Формула будет выглядеть так:

Из хода рассуждений ясно, что числа лиг определяются по числам а и b единственным образом. Иными словами, если даны два числа а и bt причем а ^> bf то единственным образом определяются частное п и остаток г; остаток этот неотрицателен (т. е. положителен или равен нулю) и всегда меньше делителя.

Оставим теперь современные учебники арифметики и посмотрим, как две с лишним тысячи лет назад подходил к вопросу о делимости один из крупнейших греческих математиков— Евклид. В своем сочинении «Начала», состоящем из 13 частей («книг»), он подвел итог математическим знаниям того времени и систематизировал их. «Начала» Евклида были так хорошо разработаны, что до самого недавнего времени, всего 100 лет назад, в школах Англии геометрию изучали прямо по книге Евклида, как по учебнику. В основном «Начала» были посвящены именно геометрии, но в них рассматривались и арифметические вопросы: пятая книга была посвящена теории пропорций, десятая — классификации иррациональных величин, а седьмая, восьмая и девятая — арифметике целых чисел. В «Началах», между прочим, рассматривается разыскание общей меры двух отрезков и родственное ему разыскание общего наибольшего делителя двух целых чисел. Тот прием нахождения общего наибольшего делителя двух чисел, которым мы пользуемся в настоящее время, так и называется алгоритмом Евклида*).

*) Алгоритмом называется правило, которое позволяет автоматически решать какой-нибудь математический вопрос, выполнять определенное вычисление и т. д.

Общею мерой двух отрезков называют такой третий отрезок, который на каждом из данных укладывается целое число раз. Найдем, например, общую меру отрезков AB и CD на рис. 4. Отложим меньший отрезок CD на большем AB от точки А столько раз, сколько окажется возможным. Если CD уложится некоторое число раз без остатка, то он, очевидно, и будет общею мерой. Если же, как на нашем рисунке, останется некоторый остаток D3ß, то придется искать общую меру меньшего из данных отрезков (CD) и остатка (D3£), т. е. на CD откладывать от точки С один за другим отрезки, равные D^B. На рис. 4 отрезок D^B откладывается на CD ровно четыре раза. Сам отрезок CD укладывается на AB три раза с остатком, равным D^B. Значит, D$B укладывается на AB ровно 4 - 3 + 1 = 13 раз. Итак, D$B укладывается целое число раз и на AB (13 раз) и на CD (4 раза). Он и есть общая мера этих отрезков.

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

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

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

Рис. 4.

от отрезков такая общая мера у целых чисел всегда существует: именно число 1, которое «укладывается» целое число раз в любом целом числе. Но, кроме единицы, пара чисел может иметь и другие «общие меры». Например, 6 и 20 имеют «общею мерой» число 2: оба они делятся на два.

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

Общим наибольшим делителем двух данных чисел называется наибольшее число, на которое делятся оба этих числа. Если общий наибольший делитель двух чисел равен единице, то числа эти называются взаимно-простыми. Например, 8 и 9— числа взаимно-простые. Точно так же взаимно-простыми будут числа 12 и 35. Вот как определяет взаимно-простые числа сам Евклид: «Если из двух неравных целых чисел последовательно меньшее вычитается из большего и остаток до тех пор не измеряет точно предыдущего, пока он не равен единице, то данные числа суть числа между собою взаимно-простые».

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

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

Пусть даны два натуральных числа а и из которых а больше Ь\ требуется найти их общий наибольший делитель. По Евклиду, нужно из большего вычитать меньшее до тех пор, пока не получится остаток; вместо этого мы просто разделим а на Ь\ при этом получится некоторое частное т1 и некоторый остаток rt, что мы можем записать так:

Остаток гх меньше, чем Ь. Может случиться, что b точно разделится на этот остаток. Тогда правая часть написанного равенства, как сумма двух чисел, делящихся на гь сама будет делиться на rt, а значит, и равное ей число а тоже разделится на rv Остаток гх будет общим делителем чисел

а и b. С другой стороны, переписав наше равенство так: гх = а — ЬтХ, мы видим, что всякий делитель чисел а и b будет делителем числа /у, следовательно, этот делитель будет не больше гу а это как раз и значит, что гх будет общим наибольшим делителем чисел а и Ь.

Пусть, например, а = 24, £=16. Поделив 24 на 16, получим в частном \(ml=l), а в остатке 8(^ = 8). Но 8 есть делитель 16. Значит 8 и будет общим наибольшим делителем чисел 16 и 24. Действительно, проверим это. Вот все делители чисел 16 и 24:

Наибольшим из общих делителей чисел 16 и 24 является, как мы и нашли, число 8.

Но может случиться, что меньшее из данных чисел b не делится на /у Прежде чем разобрать этот случай, обратим внимание на одно важное обстоятельство. Допустим, что а при делении на b дает остаток /у Мы уже видели, что на математическом языке этот факт записывается так:

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

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

Вооруженные этой теоремой, вернемся к рассмотрению того случая, когда при делении а на b получается остаток гу на который b точно не разделится. Тогда придется при делении b на Т\ найти второе частное т% и второй остаток г2. Именно это и имеет в виду Евклид, когда говорит о после-

довательном применении повторного вычитания (по-нашему, деления с остатком). Значит, получатся уже два равенства:

При этом новый остаток г2 будет меньше нового делителя, т. е. первого остатка rv Таким образом, получается важный результат: r%<^rv

Будем применять этот прием последовательно, как нам советует Евклид. Разделим гх на га. Получим новое очередное частное тъ и новый остаток г3, обязательно меньший, чем г2:

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

В самом деле, мы видели, что первый остаток гх меньше числа Ь. Второй остаток г2 меньше rt и так далее, т. е.

Все эти числа — b> rt, г2, г3,... — целые и положительные, и каждое из них по крайней мере на единицу меньше предшествующего, так что они все различны. Но различных целых положительных чисел, меньших Ьу существует не так уже много: всего b—1. Следовательно, рано или поздно наши деления с остатком закончатся, и последнее деление будет уже без остатка.

Обозначим число последовательных делений с остатком буквою п:

следующее, «эн плюс первое» деление непременно будет выполняться нацело:

Теперь ко всем полученным равенствам применим только что найденную теорему об общем наибольшем делителе (стр. 58). Из первого равенства мы видим, что общий наибольший делитель чисел а и b равен общему наибольшему делителю чисел Ъ и rt. Но этот общий наибольший делитель равен, в силу второго равенства, общему наибольшему делителю чисел Т\ и г2. Итак, общий наибольший делитель чисел а и Ь равен общему наибольшему делителю чисел гх и г2. Рассмотрев третье равенство, убедимся, что он равен общему наибольшему делителю чисел г2 и г3. Дойдя последовательно до п-то равенства, убедимся, что общий наибольший делитель чисел а и b равен общему наибольшему делителю чисел гп_\ и гп. Но гя_1, как мы видели, делится без остатка на гп. Значит, тп является общим наибольшим делителем чисел гп_х и тю и, следовательно, общим наибольшим делителем чисел а и Ь. Значит, евклидов алгоритм действительно ведет к цели.

Как расположить действия при практическом вычислении общего наибольшего делителя, видно из следующего примера. Найдем общий наибольший делитель чисел а = 729 и £ = 522.

Начинаем действие ближе к правому краю листа:

В этом примере выполнять деления приходится п + 1 = = 5 раз. Четвертый остаток (У4 = 9) и есть общий наибольший делитель чисел 729 и 522.

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

бывают важны последовательные частные; мы эти вопросы рассматривать здесь не будем*).

Вернемся к столбику равенств, с которыми мы имели дело при разыскании общего наибольшего делителя. Вот этот столбик:

Здесь а и Ь — два данных числа (а больше чем Ь\ ти т2 и т. д. — последовательные частные, г1у г2 и т. д. — последовательные остатки.

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

(все равенства мы перенумеровали). Подставим теперь в равенство (1) выражение для гпЛ из равенства (2); мы получим:

или

Последний остаток гп, являющийся общим наибольшим делителем чисел а и Ь, выражается через числа гЛ_а и гд_3, причем коэффициентами при г„_2 и гл_3 в этом выражении

*) Последовательные частные нужны, например, при разложении данного числа в непрерывную дробь, где тоже применяется алгоритм Евклида.

являются целые числа (положительные или отрицательные). Обозначим эти числа через Ах и Вх:

Тогда последнее равенство запишется так:

Перейдем теперь к равенству (3) нашего столбика (оно фактически не написано и заменено точками, но читатель без труда восстановит его). Это равенство выражает гЛ_2 через гл_3 и гл..4. Подставляя его в выражение для гп и делая приведение подобных членов, мы получим:

где А2 и В2— опять некоторые целые числа (положительные или отрицательные). Повторяя эту операцию п раз, мы дойдем, наконец, до соотношения

(*)

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

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

Вот первое применение равенства (*).

Рассмотрим два взаимно-простых числа а и m (т. е. таких, что их общий наибольший делитель равен единице). Предположим, что произведение ab данного числа а и некоторого целого числа b делится на т. Что можно сказать о делимости b на т?

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

1 = Аа + Вт

(гп в нашем случае равен единице, потому что а и m — взаимно-простые!)

Оба члена правой части делятся на т: первый — потому что ab делится на m по условию, а второй — содержит множитель m явно. Следовательно, и левая часть, т. е. число Ь, разделится на т.

Мы получили доказательство теоремы третьей, о которой говорилось в начале этой главы (стр. 53).

С последовательным делением — правда, несколько иного рода — мы уже встречались при переводе числа из одной системы счисления в другую (стр. 37). Там, в отличие от евклидова алгоритма, все делители были одинаковы. Остановимся на этом делении несколько подробнее.

Предположим, что нам дано какое-нибудь число а и основание системы счисления т. Само число а может быть задано в какой-либо иной системе счисления, записано римскими цифрами или дано еще как-нибудь иначе. Возникает принципиальный вопрос: можно ли число а записать в позиционной системе с основанием т? Как это делать практически, мы знаем; все примеры, с которыми приходилось сталкиваться в главах IV и V, как будто подтверждают такую возможность. Остается рассмотреть вопрос с общей, теоретической точки зрения — доказать теорему в общем виде.

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

Частное пх показывает, сколько в числе a содержится групп по m единиц, т. е. единиц второго разряда. Остаток гх дает число свободных единиц первого разряда. Если число щ меньше основания системы счисления, то задача решена: наше число состоит из я, единиц второго и гх единиц первого разряда и запишется так:

n1r1*).

Если же пх больше /я, то повторяем ту же операцию: делим пх на m и получаем в частном какое-то число п± и в остатке га.

Умножив обе части последнего равенства на Ъ, получим:

*) Здесь, как и в главе IV (см. стр. 37), щгх обозначает не произведение чисел щ и гu а просто две рядом написанные цифры, как, например, цифры 3 и 5 в числе 35.

Частное показывает число единиц третьего разряда, а остаток— число единиц второго. Если щ меньше ту то задача решена: искомая запись числа а в системе с основанием m будет выглядеть так:

(т. е. п2т2 + г^т + гх). Если же щ больше, чем /я, то снова повторяем деление.

Но число а — данное, вполне определенное. Если мы рассмотрим ряд степеней целого числа т, большего единицы, именно: т> tri*, m*,..., то в этом ряду обязательно найдется степень с таким показателем — назовем его q, — что тЯ будет больше, чем а. Значит, после q последовательных делений на m наши деления закончатся, и мы получим единственное, вполне определенное представление числа а в позиционной системе с основанием т. Это мы и хотели доказать.

ГЛАВА VII

УРАВНЕНИЯ, КОТОРЫМИ ЗАНИМАЕТСЯ АРИФМЕТИКА

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

Рассмотрим следующую простую задачу.

В артели было несколько квалифицированных рабочих и несколько чернорабочих. Каждый квалифицированный рабочий получил за проделанную работу 210 р., а каждый чернорабочий—150 р. Всего артель получила 1740 р. Сколько в артели было квалифицированных рабочих и сколько чернорабочих?

Уравнение этой задачи составляется очень просто: если квалифицированных рабочих было х, а чернорабочих у, то первые получили 210лг, а последние — 150у рублей. Сумма этих количеств должна равняться общему заработку артели; это сразу дает уравнение:

или, по сокращении на 30,

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

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

С точки зрения алгебры вопрос ясен: уравнение имеет бесчисленное множество решений; каждому произвольно взятому числу X соответствует определенное число у, которое вычисляется по формуле

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

Таким образом, из бесконечного множества решений уравнения 1х+Ьу = Ь% нас интересуют только такие пары значений X и у> когда оба неизвестных являются натуральными числами (легко видеть, что при лг = 0 или у = 0 второе неизвестное получается дробным, а потому нулевые решения можно не рассматривать). Это позволит выделить некоторое определенное решение и довести задачу до конца.

Будем давать неизвестному х целые значения и вычислять соответствующие значения у. Проб придется сделать не так уж много, потому что при лг^>8 второе неизвестное станет отрицательным, а такое решение нас не устраивает. Составляем табличку:

Только при х = 4 второе неизвестное получает целое положительное значение (у = 6). При любом другом значении х число у будет либо дробным, либо отрицательным. Следова-

тельно, задача имеет одно единственное, вполне определенное решение:

квалифицированных рабочих было 4; чернорабочих » 6.

Дополнительное условие (целочисленность и положительность решения) заменило нам второе уравнение.

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

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

Такого рода исследование неопределенных уравнений носит название неопределенного анализа. Оно называется также диофантовым анализом по имени замечательного греческого математика — Диофанта, жившего в III в. н. э. в городе Александрии (больше о его жизни ничего не известно). Диофант оставил книгу, на которой воспитывались творцы современной теории чисел. Нужно заметить, что он занимался разысканием не только целых, но и рациональных (т. е. целых и дробных) решений неопределенных уравнений. Решением неопределенных уравнений в целых числах и исследованием полученных решений стали значительно позже заниматься индусы. Впрочем, трудно сказать, когда впервые возник неопределенный анализ; во всяком случае, в XII в. н. э. у индийского математика Бхаскара мы встречаем вполне

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

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

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

Задача первая. Требуется пятирублевку разменять полтинниками*), двугривенными и пятачками так, чтобы всего было 20 монет.

Составляем уравнение. Пусть х — число пятачков, у — число двугривенных, z — число полтинников. Тогда общая сумма, равная 500 копеек, выразится так: Ъх + 20j> +50z; с другой стороны, по условию, х+у + z = 20. Больше никаких данных нет. Следовательно, решение задачи сводится к решению в целых числах системы:

Число неизвестных (три) больше числа уравнений (два); значит, система уравнений — неопределенная. Сократив первое уравнение на 5 и вычтя из него второе, получим единственное уравнение с двумя неизвестными:

Остается решить это уравнение в целых числах. Но приглядываясь к нему внимательнее, мы видим, что при любых целых значениях у и z левая часть уравнения должна делиться на 3; правая же часть (80) на 3 не делится. Следовательно, не существует таких целых у н z, которые удовлетворяли бы нашему уравнению. Это — пример неопределенного уравнения, неразрешимого в целых числах. Поэтому неразрешима и при-

*) Полтинник — монета в 50 копеек.

ведшая к нему задача. Разменять пятирублевку двадцатью монетами указанного достоинства невозможно.

Задача вторая. Найти натуральное число, которое при делении на 3 дает остаток 2, а при делении на 5— остаток 3.

Обозначим искомое число через х. Если частное от деления X на 3 обозначим через у, а частное от деления на 5— через z, то получим (см. стр. 53):

По смыслу задачи х, у и z должны быть целыми (больше того — натуральными) числами. Значит, нужно решить в целых числах неопределенную систему уравнений.

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

Найдя все целые положительные значения у или z из этого уравнения, сразу получим и все целые положительные значения X,

Из уравнения dz — Зд/ +1 = 0 находим:

Одно решение очевидно: при z = 1 получим

и z и у получаются целые. Им соответствует решение х = 8.

Найдем все остальные решения. Для этого введем вспомогательное неизвестное и, полагая z = 1 + il Мы получим:

т. е. или

Правая часть последнего уравнения при любом целом у делится на 3. Значит, и левая должна делиться на 3. Но число 5—взаимно-простое с числом 3; поэтому и должно разделиться на 3*), т. е. иметь вид 3«, где п — целое неотрицательное число. В этом случае у будет равняться

т. е. тоже целому числу. Итак, z = 1 + и = 1 + Зя, откуда

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

где п — целое число (положительное или нуль):

Проверка показывает, что все эти решения годятся**).

Задача третья. Куплены дыни по 7 р. и арбузы по 4 р. за штуку, всего на сумму 53 р. Сколько куплено дынь и сколько арбузов?

Одно уравнение составляется сразу; вот оно:

(через X обозначено число дынь, а через у — арбузов).

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

*) Вспомним теорему третью предыдущей главы (стр. 51).

**) Все решения этой задачи образуют неограниченно продолжаемую арифметическую прогрессию с первым членом 8 и разностью 15:

8, 23, 38. 53. 68, 83, ...

Даем X значения от 1 до 7 (при лг^>7 для у получатся отрицательные значения). Вычисляем соответствующие значения у:

Получаются два решения задачи:

Во всех остальных случаях хотя бы одно из неизвестных дробно или отрицательно. Следовательно, задача имеет два решения: либо куплено 3 дыни и 8 арбузов (это стоит 3 • 7+8М = 53 р.), либо 7 дынь и 1 арбуз (это стоит 7 • 7+ 1-4, т. е. тоже 53 р.).

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

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

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

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

ах+Ьу = с. (*)

Здесь а, Ь, с — данные целые (положительные или отрицательные) числа; х и у— неизвестные, но принимающие только целые значения (тоже — положительные, отрицательные или нуль).

Рассмотрим прежде всего случай, когда неопределенное уравнение неразрешимо (как в разобранной выше задаче первой на стр. 68).

Найдем общий наибольший делитель чисел а и Ь. Обозначим его через d (если а и b — взаимно-простые числа, то d равно 1). Тогда а будет равно произведению d на некоторое целое число m, a b — произведению того же d на целое число п:

а = md\ b — nd.

При этом тип обязательно будут числами взаимнопростыми. В самом деле, если бы они в свою очередь имели общий делитель /г, не равный единице, то произведение kd было бы делителем и числа а, и числа b, а потому d не было бы наибольшим делителем этих двух чисел.

Каковы бы ни были целые числа х и у, левая часть уравнения (*) должна делиться на d, потому что оба слагаемых ах и by на него делятся. Значит, и правая часть этого уравнения должна делиться на d. Отсюда можно сделать такой вывод: если свободный член неопределенного уравнения не делится на общий наибольший делитель коэффициентов при неизвестных, то уравнение (*) неразрешимо. В задаче первой на стр. 66 мы пришли к уравнению

здесь общий наибольший делитель коэффициентов равен 3; свободный же член (80) на 3 не делится; следовательно, уравнение неразрешимо. Мы видели, что задача первая действительно не имеет решений.

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

(*)

числа а и b не только целые, но и взаимно-простые. Уравнения первой степени называют иначе линейными уравнениями*). Уравнения, все члены которых имеют одинаковое измерение, т. е. одинаковую сумму показателей при неизвестных, называют однородными. Например, уравнения х* -f* 2ху =у~\ х* +у* = Злгу2 будут однородными. Однородные уравнения обладают многими интересными свойствами и решаются они обычно проще неоднородных. В случае линейных уравнений однородным будет уравнение, не содержащее свободного члена, который является членом нулевого измерения. Например, уравнения

будут однородными; уравнения же

— неоднородные.

Рассмотрим два уравнения:

*) Это название происходит оттого, что в аналитической геометрии (отдел, с которого обычно начинают изучение высшей математики) уравнение ах~{-Ьу = с изображает прямую линию.

У этих уравнений одинаковые коэффициенты при неизвестных. В этом случае второе уравнение называют однородным уравнением, соответствующим первому (неоднородному) уравнению. Занимаясь линейным неопределенным уравнением ах+Ьу = с, естественно сначала рассмотреть однородное уравнение, т. е. положить с = 0:

а X + by = 0.

Удобнее записать это уравнение так:

ах = by*).

Решить его очень просто. Раз правая часть (by) делится на by значит и левая (ах) должна делиться на Ь. Но а — число взаимно-простое с Ь\ следовательно, х должен быть кратным b (вспомним теорему третью предыдущей главы на стр. 53). Итак,

x = brij

где п — любое целое число.

Чтобы найти у, мы подставляем найденное выражение для X в уравнение ах = Ьу. Получим:

abn = by, откуда у = ап. Здесь п должно быть непременно то же самое, что в выражении для X.

Следовательно, решение нашего однородного уравнения имеет вид:

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

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

*) Читателю, быть может, не нравится, что вместо ах = — by мы написали ах = by. По существу, конечно, сделано следующее. Сначала написано ах = — by. Затем положено: Ьх = — Ь, что дает ах = Ьху. Наконец, Ьи обозначающее совершенно произвольное число, заменено буквою Ь,

С однородными неопределенными уравнениями нередко приходится иметь дело и в современной технике. В качестве примера приведем вопрос о числе зубцов у зубчатых колес. Для плавной работы пары сцепленных зубчатых колес необходимо, чтобы числа их зубцов были обратно пропорциональны числам оборотов каждого из колес в единицу времени. Например, если одно из колес делает 50, а другое — 80 оборотов в минуту, то число X зубцов первого колеса должно относиться к числу у зубцов второго, как 80 к 50; это записывается так:

Получилось однородное уравнение, которое легко решается в целых числах. По формулам (**)

где п — любое целое число.

Переходим теперь к неоднородным неопределенным уравнениям первой степени, т. е. к уравнениям вида

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

будет общим, а решение

полученное из предыдущего при я = 3, — частным.

Предположим, что путем подбора удалось найти одно (частное) решение уравнения ах+Ьу = с, т. е. найти два целых числа х0 и у0> удовлетворяющих соотношению

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

Подставляя эти выражения в уравнение ах + by = с, мы получим:

Раскроем скобки и перегруппируем иначе члены:

Вычитая из этого равенства тождество axQ +by0 = с, получим:

Это — однородное уравнение, соответствующее неоднородному уравнению ах+Ьу = с. Его решение мы можем написать по формулам (**) сразу; вот оно:

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

Такой вид должно иметь любое решение уравнения ах -{-by = с. С другой стороны, подставив найденные значения X и у в наше уравнение (*), мы убедимся, что при любом п они ему удовлетворяют. В самом деле:

а это число равно с, так как х0 и у0 удовлетворяют уравнению (*).

Следовательно, мы нашли общее решение неоднородного уравнения.

*) Здесь перед b стоит знак «минус», которого не было в формулах (**), потому что рассматриваемое уравнение имеет вид не ah = bv, a au = — bv\ у коэффициента b стоит знак «минус».

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

Каким же образом найти числа х0 и у0, г. е. хотя бы одно решение неопределенного уравнения (*)? Практически, если коэффициенты a, b и с этого уравнения невелики, то лучше всего просто подобрать это решение, давая одному из неизвестных, например х, последовательно значения О, 1, 2, 3,..., пока и для второго, у, не получится целое значение; мы так уже поступали при решении задачи третьей (стр. 71). Если же коэффициенты эти велики, то приходится в той или иной форме использовать алгоритм Евклида. Так, по существу, поступали уже индусы, так же поступают и современные математики. Как применить алгоритм Евклида к решению уравнения (*), лучше всего будет видно на числовом примере.

Требуется решить уравнение

Найдем сначала какое-нибудь частное решение этого уравнения.

Постараемся свести данное уравнение к уравнению с меньшими коэффициентами. С этой целью делим больший коэффициент (331) на меньший (169). Получаем в частном 1 и в остатке 162. Значит,

Наше уравнение можно теперь преобразовать так:

Введем вспомогательное неизвестное, — прием, которым мы уже пользовались, — именно, положим

(1)

Получим уравнение с меньшими коэффициентами:

Заметим, что вспомогательное неизвестное z вошло в равенство (1), связывающее z со старыми неизвестными

X и у, с коэффициентом 1. То же самое можно сказать и о неизвестном у, входившем в исходное уравнение с меньшим по абсолютной величине коэффициентом.

Повторяем с полученным уравнением снова тот же прием: делим его больший коэффициент при неизвестном на меньший; иными словами, делим меньший коэффициент исходного уравнения (169) на первый остаток (162). Получим в частном 1 и в остатке 7, т. е. 169z = 162z + 7z. Наше уравнение переписывается так:

Вводим новое вспомогательное неизвестное, полагая

(2)

[Обратим внимание на то, что в уравнении (2) и и (новое неизвестное), и х (то старое неизвестное, которое в предыдущем уравнении имело меньший коэффициент) имеют коэффициентом единицу!] Мы получим:

Делим снова больший коэффициент на меньший, т. е. делим первый остаток исходного уравнения (162) на второй остаток (7); в частном получится 23, а в остатке 1. Следовательно, 162н = 7 • 23м + w, и наше уравнение примет вид

Введем последнее вспомогательное неизвестное, положив

(3)

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

Наше уравнение примет теперь особенно простой вид

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

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

Последнее уравнение (it+7v — 5) дает нам:

При любом целом v будет целым и и. Положив v равным, например, нулю, получим н = 5. Теперь остается пройтись «снизу вверх» по всем равенствам, отмеченным номерами (3), (2), (1). При этом каждое подлежащее определению неизвестное будет иметь коэффициентом единицу (мы все время обращали внимание на это обстоятельство!). Поэтому все неизвестные, в том числе х и у, будут целыми числами. В нашем примере мы получим:

Итак, частным решением нашего уравнения будег:

Мы уже видели, как найти общее решение этого уравнения. Для этого мы рассматриваем соответствующее однородное уравнение

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

здесь я = 331, £=169. Поэтому [см. формулы (**) на стр. 74] общим решением неоднородного уравнения 331лг — — 169y = б будет:

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

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

Мы уже говорили, что первой книгой о неопределенных уравнениях было сочинение Диофанта (III в. н. э.). Есть основания полагать, что за 500 лет до Диофанта Архимед умел решать такие уравнения. В средние века ими занимались индусы и отчасти арабы. В Европе первым стал изучать целочисленные решения неопределенных уравнений французский математик Баше де-Мезириак, издатель и комментатор сочинений Диофанта (начало XVII в.).

Уже Диофант наряду с линейными уравнениями (уравнениями первой степени) рассматривал квадратные и кубические неопределенные уравнения. Решение их, как правило, сложно. Остановимся на одной задаче, ставшей классической.

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

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

*) Такой упрощенный путь решения неопределенного уравнения дан, например, во II части учебника алгебры Киселева и в книге Я. Перельмана «Занимательная алгебра».

и у, а длину гипотенузы — через z> то получим:

Это — неопределенное уравнение (уравнение одно, а неизвестных три). Оно однородное, второй степени. Одно его решение известно всем: катеты — 3 и 4, а гипотенуза — 5 единиц («египетский треугольник»). Но знание частного решения позволяет решить полностью только линейные уравнения. Здесь же для полного решения придется искать какой-то искусственный прием.

Будем искать три числа xt yt z, удовлетворяющие пифагорову*) уравнению и не имеющие ни одного общего множителя, кроме 1**). Важно найти именно эти решения, потому что из любого «взаимно-простого» решения xQ, у0, z0 сейчас же получается серия составных решений пх0, пу0, nzQt где п — любое целое число. Обратно: если найдем какое-нибудь «составное» решение р> q, г, то, полагая р = ах0, q = ay0y r = az0y где а — общий наибольший делитель чисел /?, q и rf подставив axQt ayot az0 в уравнение и сократив его на dly убедимся, что x0i yQf z0 образуют «взаимно-простое» решение. Таким образом, найдя все «взаимно-простые» решения, мы будем знать и все вообще решения пифагорова уравнения.

Но если Х, у и z — взаимно-простые числа, то они не могут быть все три четными. Два из них тоже не могут быть четными, потому что тогда одна часть равенства будет делиться на 2, а другая нет. Все три нечетными быть не могут, потому что сумма двух нечетных чисел — четна. Следовательно, либо нечетны оба катета, либо нечетны один из катетов и гипотенуза.

Покажем, что оба катета не могут выражаться нечетными числами. Действительно, если один из них выражается числом 2q +1, а другой — числом 2р + 1 (где q и р — целые числа), то сумма их квадратов равна

*) Пифагор сам не занимался этим уравнением, но оно связано с теоремой Пифагора, и поэтому такое название уравнения оправдано.

**) Такие три числа называются взаимно-простыми. Мы видим, что это название применяется не только к паре чисел, как на стр. 57, но и к тройке, четверке и большему количеству целых чисел.

Эта сумма, очевидно, делится на 2 и не делится на 4. Но квадрат любого четного числа делится на 4, а квадрат любого нечетного не делится на 2. Следовательно, сумма квадратов двух нечетных чисел не может быть ни квадратом четного, ни квадратом нечетного числа, т. е. вообще не может быть квадратом целого числа.

Итак, если все три стороны прямоугольного треугольника выражаются взаимно-простыми целыми числами, то возможно только такое «распределение четности»: один из катетов — четное число, а другой катет и гипотенуза — нечетные.

Будем четный катет обозначать через лг, а нечетный — через у\ тогда мы вправе положить x = 2v, и наше уравнение запишется так: Av* +j/2 = z\ или так: 4v2 = z*—у\ или, наконец, так:

Сумма и разность двух нечетных чисел всегда четны. Положим поэтому

Нетрудно видеть, что и и t — числа взаимно-простые, причем одно из них четное, а другое нечетное. Действительно, выразив z и у через и и /, получим: z = u~\-ti у = и — t. Если бы и и t имели общий делитель, то его имели бы и z и у, что противоречит предположению об их взаимной простоте; точно так же и и t не могут быть одной четности, потому что тогда г, равный их сумме, был бы четным, что, как мы видели, невозможно.

Подставляя в уравнение 4v* — (z +y)(z—у) вместо суммы и разности неизвестных числа 2и и 2ty мы получим:

Но это возможно только в том случае, если и и t порознь являются квадратами, т. е. если н = а2; t = b*. Действительно, в произведение ut (равное квадрату числа v) все простые множители входят парами*). Если бы в и имелся какой-нибудь непарный множитель, то такой же множитель должен был бы быть и в /, чтобы в произведение ut = v* он вошел парой. А это невозможно, потому что числа и и /

*) Подробно о разложении на простые множители будет рассказано в главе XI (стр. 132).

взаимно-простые и общих множителей не имеют. Итак, в и все простые множители должны входить парами; то же можно сказать и про L Следовательно, и н, и t являются квадратами. Заметим еще, что в силу взаимной простоты и различной четности чисел н(=а*) и t(=b*) сами числа а и Ь тоже будут взаимно-простые и различной четности. Таким образом,

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

откуда

Следовательно, наиболее общее «взаимно-простое» решение пифагорова уравнения будет определяться формулами:

а все без исключения решения, как простые, так и составные, — формулами:

Здесь п — совершенно произвольное натуральное число, а а и Ь— целые числа, выбор которых ограничен лишь следующими условиями: 1) Ь больше а, 2) b и а — взаимно-простые, 3) b и а — различной четности.

Мы видим, что «выбор» получился больший, чем в тех случаях, которые мы до сих пор рассматривали. Оно и

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

Рассмотрим некоторые числовые решения пифагорова уравнения. Если п=1 (решения «взаимно-простые»), то мы получим следующий ряд решений:

Далее можно написать таблички для а = 4. а = 5 и т. д.

Умножая любую строку (т. е. все числа строки) каждой из табличек на произвольное натуральное число, мы получим новые серии решений. Например, умножая третью строку второй таблички последовательно на 2, 3, 4, получим следующие решения:

Никаких иных решений, кроме полученных этим путем из наших табличек, задача иметь не может.

После уравнения x*+y'à = z% естественно рассмотреть уравнения хд+у* = гь; х*+у1 = г1 и т. д. Математики XVI и начала XVII в. пытались решить эти уравнения в целых числах, но безуспешно.

П. ФЕРМА

Так обстояло дело до середины XVII в., когда француз Ферма, рассмотревший это уравнение в общем виде, т. е. в форме

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

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

На полях книги Диофанта Ферма сделал следующую надпись (на латинском языке): «Ни куб на два куба, ни квадрато-квадрат и вообще никакая, кроме квадрата, степень, не может быть разложена на сумму двух таких же; я нашел удивительное доказательство этому. Однако ширина полей не позволяет здесь его осуществить».

Эту теорему Ферма оставил недоказанной. И не только эту: Ферма формулировал много интересных теорем, но доказательства их не оставил. Он умышленно посылал теоремы своим знакомым без доказательства, тем самым предлагая им трудную задачу для решения. Современники часто с ними не справлялись, но в течение XVIII и XIX вв. все эти теоремы были доказаны. Все, кроме двух! Одна из них — только одна из всего богатого наследия Ферма — оказалась неверной*): один раз и этому гению изменило математическое чутье. А вторую, ту, которая была написана на полях книги Диофанта и о которой мы сейчас говорили, до сих пор не удалось ни доказать, ни опровергнуть.

*) О ней будет сказано дальше, см. стр. 124.

Лучшие математики пробовали на ней свои силы. Эйлер дал доказательства того, что уравнения хъ +Ул —z* и xi+yi = zi неразрешимы в целых числах, т. е. доказал теорему Ферма для я=3 и я = 4*). Лежандр и Дирихле доказали ее для п = 5, Ламэ—для я = 7. В середине прошлого века Куммеру с помощью трудной и тонкой теории удалось показать, что теорема Ферма может быть неверна лишь для некоторых исключительных значений я. Так, например, он доказал, что она верна для всех я, меньших 100**). Но полного доказательства ее справедливости он все же не дал.

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

*) Доказательство теоремы для я = 4 дал, по существу, сам Ферма.

**) В настоящее время она доказана для всех я, превышающих несколько тысяч.

ГЛАВА VIII

АРИФМЕТИКА, В КОТОРОЙ «ТРИЖДЫ ТРИ — ЧЕТЫРЕ»

Мы уже рассматривали (на стр. 39) арифметику, в которой 3X3=10. Это — система счисления при основании 9. Разумеется, и в этой, и во всякой другой системе счисления три раза повторенное число три будет равно девяти; но в девятиричной системе счисления само число девять, будучи единицей второго разряда, выглядит так: 10. Поэтому и получилась парадоксальная запись.

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

Рассмотрим уравнение

где а, Ь, с—целые числа, причем а и b — взаимно-простые. По существу, при решении важно найти только х. Тогда у определится сразу:

При этом X нужно искать с таким расчетом, чтобы выражение, которому равен у, было целым. Но это выражение, наверное, будет целым, если (ах — с) разделится на b или, иначе, если ах при делении на b даст остаток с.

(Действительно, если ах при делении на b дает остаток с, то это значит, что ах = Ьт + с\ отняв отсюда с, получим Ьт, очевидно, делящееся на Ь.)

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

Для начала предположим, что а=1. Это, очевидно, простейший случай, и отправляться нужно именно от него. Тогда наша задача примет вид: найти все числа лг, которые при делении на данное число b дают остаток с. Несмотря на кажущуюся простоту, такая постановка вопроса оказалась очень плодотворной. Ее развил и превратил в стройную систему Гаусс (1777—1855 гг.), которому удалось сделать на этом пути много важных открытий.

Итак, нас интересуют все числа, дающие при делении на некоторое определенное число данный остаток. Если, например, число, на которое делят [его называют модул ь*)], равно 7, а требуемый остаток равен 2, то искомыми числами будут:

2, 9, 16, 23 и т. д.

Они образуют неограниченно продолжаемую арифметическую прогрессию, первый член которой равен 2, а разность — 7.

Числа, дающие при делении на модуль равные остатки, называют равноостаточными или сравнимыми по этому модулю. Следовательно, числа 2, 9, 16, 23 и т.д. сравнимы друг с другом по модулю 7. Точно так же числа 1 и 27 сравнимы по модулю 13, число 103 сравнимо с 3 по модулю 10.

Понятие сравнения, введенное Гауссом, нашло такое широкое применение в математике, что для него пришлось ввести специальное обозначение (его придумал тот же Гаусс).

*) Слово «модуль» происходит от латинского modulus (модулюс), что значит «мерка»; употребляется оно обычно в смысле «делитель». Постоянные, которые входят в знаменатель различных физических и технических формул, часто называются модулями: например, модуль упругости и т. д.

К. Ф. ГАУСС

Если а и b при делении на m дают равные остатки, т. е. если а сравнимо с b по модулю т, то пишут

а = Ь (mod m);

читается это так: «а сравнимо с b по модулю /гс». Знак сравнения (=) напоминает знак равенства. Это не случайно: свойства сравнений похожи на свойства равенств.

Кроме сравнений, содержащих известные, данные числа, например 2 = 5(mod 3), 1000=1 (mod 37) и т. д., приходится рассматривать сравнения, содержащие неизвестные. При этом возможны три случая: либо сравнение справедливо при любых целых значениях входящих в него букв, либо оно справедливо только при некоторых, либо оно не может быть справедливым ни при каких значениях входящих в него букв. Например, сравнение ах = 2а (mod а) справедливо при любых целых х и а (ах и 2а оба дают при делении на а остаток, равный нулю; значит, они сравнимы). Напротив, сравнение 2лг = 3 (mod 5), справедливое при х — А (ибо 2-4 = 8 дает при делении на 5 остаток 3), не выполняется при jc = 5, потому что тогда 2х равно 10; это число делится на модуль 5 без остатка. Наконец, сравнение 2jc=l(mod2) не выполняется ни при каком целом х: левая часть его (2лг) делится на модуль, а правая — нет.

Решить сравнение, значит — найти все удовлетворяющие ему значения неизвестных (или доказать его невозможность). Сами значения неизвестных, удовлетворяющие сравнению, называются его решениями.

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

2jc -J— 3j/ = 5(mod 21) (сравнение первой степени с двумя неизвестными),

х*+5х—3 = 0(mod 3) (квадратное сравнение с одним неизвестным).

Рассмотрим простейшие свойства сравнений. Возьмем сравнение a = b (mod m) и попробуем «перевести» его на привычный нам язык равенств. Это нетрудно сделать. Ведь сравнение а = b (mod m) обозначает, что а — b делится на m без остатка, т. е. что а — b равно произведению m на произвольное целое число п. Обратно: если а — b = тп, где п—целое число, то при делении а на m и b на m получатся

одинаковые остатки. В самом деле, допустим, что при делении на m число а дает остаток гь а число b— остаток г9. Это значит, что имеют место равенства: а=рт+ гх\ b = qm-{- гъ где р, qt rt и г2— числа целые, а г, и га, кроме того, оба меньше т. Допустим, что гх^>г^ Вычитая второе равенство из первого, получим:

или

Следовательно, разность гх — г2 есть число, кратное т. Эта разность меньше т, потому что и уменьшаемое и вычитаемое — положительные числа, меньшие т\ значит, она может быть равна только нулю, и значит, г1 = /*2. Но равноостаточность а и b по модулю m записывается как раз так: c = b(moàm).

Итак, равенство а — Ь = тп (или а = Ь+ тп) и сравнение а = b (mod m) обозначают совершенно одно и то же. Где нужно, можно вместо равенства писать сравнение, где нужно—вместо сравнения равенство. То и другое выражают одну мысль, только, так сказать, на разных языках.

Покажем теперь, что сравнения по одному и тому же модулю можно складывать, вычитать и перемножать (левую часть — с левой, правую — с правой). Рассмотрим два сравнения:

Первое, как мы знаем, равносильно равенству а = тщ + Ь, а второе— равенству с = тщ + d\ сложив (или вычтя) эти равенства, мы будем иметь: а ± с = m (пх ± л2) b ± d\ переведя результат на язык сравнений, мы получим:

А это как раз и значит, что сравнения можно почленно складывать (и вычитать).

Если равенства а = тпх + b и с — тщ + d мы перемножим, то получим:

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

Это значит, что ас = bd (mod т\ т. е. что сравнения по одному и тому же модулю можно перемножать. Разумеется, складывать и перемножать можно не только два, но и любое число сравнений. Отсюда сейчас же получается следствие: сравнение, не содержащее неизвестных, можно возвести в любую степень*).

Так же просто можно показать, что к обеим частям сравнения можно прибавить, от обеих частей отнять одно и то же число и обе части умножить на одно и то же число*). Например, из a = b (mod m) следует a + с = b + с (mod m). Действительно, сложим сравнения

(первое дано, а второе — очевидно); получим

что и требовалось доказать.

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

(некоторый многочлен) = 0 (mod m). Например, сравнение

приводится к виду

сравнение

— к сравнению

и т. д. В частности, любое сравнение первой степени с одним неизвестным можно привести к виду

*) Умножение на выражение, содержащее неизвестное, как и в случае обыкновенных уравнений, может привести к посторонним решениям.

где û, i и m — заданные целые числа (m, кроме того, положительно).

Но в некотором отношении сравнения все-таки «хуже» равенств. Сокращать их на общий множитель можно не всегда. Рассмотрим этот вопрос внимательнее.

Сравнение 22=12 (mod 5), несомненно, справедливо: и 22 и 12 при делении на 5 дают остаток 2. Если мы разделим обе его части на 2, то получим 11=6 (mod 5); это тоже справедливо: и 11 и 6 при делении на 5 дают в остатке 1. Кажется все благополучно. Вот, однако, другой пример: 14 = 10 (mod 4); действительно, и 14 и 10 при делении на 4 дают в остатке 2. Если же мы разделим обе части сравнения на 2, то получим 7 = 5 (mod 4), что неверно: ведь 7 при делении на 4 дает остаток 3, а 5 — единицу. В чем же дело?

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

Сформулируем наши наблюдения в форме теорем и докажем их.

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

Пусть в сравнении

обе части делятся на d, а модуль не только не делится, но и взаимно-прост с d, т. е. не имеет делителей, общих с d и не равных 1. Из данного сравнения следует:

т. е. d (а — Ь) должно делиться на т. Но d, по условию, взаимно-просто с т. Следовательно, а — b должно делиться на nty т. е. должно иметь место сравнение a = b (mod m), что и требовалось доказать. И здесь приходится использовать теорему третью главы VI (на стр. 53).

Теорема вторая. Если обе части сравнения и модуль имеют общий множитель, то справедливо сравнение,

*) Вопрос читателю: может ли одна часть сравнения быть взаимно-простой с модулем, а другая — нет?

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

в котором обе части и модуль делятся на d. Переводим мысль, выраженную сравнением, на язык равенств:

Сокращение этого равенства на d дает:

а это, в переводе на язык сравнений, значит:

что и требовалось доказать.

Доказанная только что теорема объясняет, почему второй пример 14=10 (mod 4) привел нас при сокращении к абсурду. Обе стороны этого сравнения и его модуль (4) делятся на 2. Значит, нужно было не забыть сократить на 2 и модуль, что дало бы 7 = 5 (mod 2), а это, очевидно, справедливо (и 7, и 5 при делении на 2 дают в остатке 1).

Но если, с точки зрения возможности сокращения, сравнения «хуже» равенств, то у них есть и такие свойства, которые позволяют делать преобразования, невыполнимые в случае равенств. Вот важнейшее из этих свойств: к любой части сравнения можно прибавить, от любой части сравнения можно отнять любое число, кратное модулю.

Действительно, прибавим к обеим частям сравнения

(или отнимем от них) очевидное сравнение ст = 0 (mod m); мы получим:

аналогично можно было бы получить:

Посмотрим, какую пользу можно извлечь из этого свойства.

Возьмем сравнение

(1)

Вычтем из левой части 7х: это — число, кратное модулю. Мы получим:

Далее, из правой части вычтем число 14, тоже кратное модулю. Получим:

Сократив на 2 (модуль не делится на 2), мы получим совсем простое сравнение:

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

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

Задача первая. Найти остаток от деления числа 15325— 1 на 9.

Для решения этой задачи не нужно делать утомительное умножение и скучное деление. Рассуждаем так:

1530 делится на 9 (сумма его цифр делится на 9); следовательно, 1532 дает при делении на 9 остаток 2; это мы можем записать в форме сравнения

Мы знаем, что сравнения можно почленно перемножать; в частности, обе части сравнения можно возвести в одну и ту же степень. Возведем написанное сравнение в пятую степень; мы получим:

Вычтем из правой части 27 (число, кратное модулю):

Если теперь от обеих частей сравнения отнять по единице, то получится:

а это значит, что 15325— 1 дает при делении на 9 остаток 4. Наша задача решена.

Задача вторая. Найти последние две цифры числа 9е9-Рассмотрим сначала, каковы последние две цифры у первых десяти степеней девятки. Найти их просто:

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

Последнее число (910), оканчиваясь на 01, дает при делении на 100 в остатке единицу, что мы теперь умеем записать так:

Если мы возведем обе части этого сравнения в произвольную целую степень ру то увидим, что всякая степень числа 910, т. е. число 910р, будет сравнима с 1 по модулю 100.

Рассмотрим, далее, произвольную степень девяти 9^. Обозначим число десятков в N через ру число единиц — через q; иными словами, положим N=\0p +q. Мы только что доказали, что

Умножив обе части этого сравнения на 9q, получим слева:

а справа

Последнее равенство показывает, что любая степень девяти (N) сравнима по модулю 100 с такой степенью девяти, показатель которой (q) равен остатку от деления первоначально данного показателя на 10, т. е. обе эти степени девяти

имеют те же две последние цифры*). Таким образом, наша задача упрощается. Последние две цифры числа 9э9 обязательно должны быть те же, что и у числа 9а, где а — остаток от деления «двухэтажного» показателя 99 на 10. Но остаток от деления любого числа на 10 равен последней цифре десятичной записи этого числа. Для числа 99 он равен 9 (см. табличку степеней девятки, данную выше). Следовательно,

т. е. 9°9 и 99 имеют те же последние две цифры. Смотрим снова в табличку первых десяти степеней девятки: видим, что 99 оканчивается на 89. Значит, и 9эЭ оканчивается на 89.

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

Это сравнение показывает, что разность 7лг — 3 делится на 9, т. е. равна произведению 9 на некоторое целое число у:

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

Взглянем теперь на сравнения с совершенно новой точки зрения. Зададим какой-нибудь определенный модуль, например т = Ъ. При делении любого числа на 5 могут получиться следующие остатки: 0, 1, 2, 3 и 4. Все натуральные числа можно разбить на пять категорий, в зависимости от того, какой остаток получается при делении этих чисел на 5. Числа каждой категории образуют неограниченно продолжаемую арифметическую прогрессию с разностью, равной мо-

*) Если два числа сравнимы, т. е. равноостаточны по модулю 100, го это значит, очевидно, что у одного из них в десятичной записи те же последние две цифры, что и у другого.

дулю, т. е. в нашем примере — пяти. Вот эти пять прогрессий:

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

Все числа, входящие в состав написанных выше прогрессий (т. е. все без исключения числа натурального ряда), называются вычетами*) по модулю 5; каждый из этих вычетов может служить свободным членом сравнения х = а (mod 5), имеющего решения.

Если бы мы взяли сравнение второй степени, например,

то убедились бы, что некоторые числа, например а=\9 являются вычетами, потому что сравнение х*=\ (mod 3) имеет решения; другие числа, например 2, не являются вычетами: можно доказать, что сравнение х* = 2 (mod 3) совсем не имеет решений. Говорят, что 2 есть квадратичный невычет по модулю 3. Для сравнений первой степени каждое натуральное число есть вычет.

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

Взятые таким образом числа называются представителями классов по модулю пять, а их совокупность — полной системой вычетов по модулю 5.

*) Слово «вычет» должно напоминать о том, что при изучении целых чисел мы смотрим на деление, как на повторное вычитание.

Полная система вычетов по данному модулю обладает многими замечательными свойствами. Мы рассмотрим одно из них; чтобы оно стало нагляднее, сделаем еще упрощение. Именно, вместо взятых наудачу представителей классов, возьмем в качестве таковых наименьшие положительные вычеты, соответствующие различным классам. В нашем примере это будут числа: 1, 2, 3, 4, 5. Заменим последний вычет, равный модулю, сравнимым с ним по этому модулю числом 0. Получим следующую систему чисел:

1, 2, 3, 4, 0.

Будем над числами такой системы производить сложение, вычитание и умножение по обычным правилам, но каждый полученный результат заменять наименьшим положительным вычетом того же класса. Сложив, например, 3 и 4, мы получим 7; наименьший вычет класса, представителем которого служит 7, равен 2. Поэтому напишем: 3 4 = 2. Чтобы эта запись не слишком резала глаза, будем указывать модуль, по которому все числа были разбиты на классы. Будем писать: 3 + 4 = 2 (mod 5). Точно так же, помножив 2 на 3, получим 6; число 6 принадлежит первому классу по модулю 5; оно по этому модулю сравнимо с единицей. Поэтому будем писать: 2X3=1 (mod 5). Чтобы вычесть четыре из трех, заменим тройку ближайшим большим представителем того же класса — восьмеркой. Получим 8 — 4 = 4, или, по модулю 3,

3 — 4 = 4;

проверяем: если 3 — 4 = 4, то 4 + 4 (сумма разности и вычитаемого) должна равняться 3; и в самом деле, 4 + 4 равно 8, т. е. числу, сравнимому с 3 по модулю 5.

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

действия деления, а, во-вторых, и это главное, не с бесконечным множеством чисел, а только с . . . пятью!

Можно сделать своеобразные «счеты», наглядно иллюстрирующие эту арифметику. Вырежем из картона два кружка, один побольше, другой поменьше. На каждом из них в вершинах правильного вписанного пятиугольника напишем цифры 1, 2, 3, 4, 0, наложим меньший кружок на больший так, чтобы центры их совпали, и скрепим кружки кнопкой (рис. 5).

Рис. 5. Рис. 6.

Теперь для сложения двух чисел поступаем так: замечаем на большем кружке слагаемое и ставим против него нуль меньшего кружка. На меньшем кружке мысленно отмечаем второе слагаемое. Против него на большем кружке и будет сумма. Сложим, например, 2 и 4. Против двойки большего кружка ставим нуль малого (рис. 6). Четверке малого кружка соответствует единица большего. Значит, по модулю пять, 2 + 4=1.

Чтобы умножить 4 на 3, поступаем так. Сначала поставим оба кружка в исходное положение (т. е. чтобы одинаковые числа стояли друг против друга). Затем поворачиваем 3 раза (т. е. число раз, равное множителю) меньший кружок на угол, равный -g- окружности (здесь числитель равен множимому, а знаменатель — модулю), и смотрим, против какого числа большего кружка станет нуль меньшего (рис. 7). Видим, что он придется против двойки. Значит, в этой арифметике

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

Из этой таблицы умножения мы видим, что 3X3 = 4; мы нашли ту арифметику, которая была обещана в начале главы.

В наших примерах мы имели дело с системами чисел, в которых установлены только три действия: сложение, вычитание и умножение. Такие числовые системы называются в математике «кольцами». Совокупность всех целых чисел (положительных и отрицательных, включая нуль) тоже образует кольцо, но это кольцо содержит бесконечное множество элементов. Кольцом же является совокупность всех многочленов всевозможных степеней относительно единственной буквы X с целыми коэффициентами: сумма, разность и произведение многочленов подобного рода являются в свою очередь такими многочленами; деление же, напротив, приводит сплошь да рядом к алгебраическим дробям. Совокупность натуральных чисел не является кольцом, потому что

Рис. 7.

разность двух натуральных чисел может и не быть натуральным числом: например, 5—8 =—3, а «минус три» — число хотя и целое, но не натуральное.

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

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

Говоря о кольцах, мы упомянули вскользь о «кольце многочленов». Это выражение кажется бессмысленным, потому что мы сказали сейчас, что кольцом называют некоторую совокупность чисел, а многочлены числами не являются. Но дело в том, что к группам, кольцам и телам можно подойти шире, рассматривая не только системы чисел, но и системы любых вещей, знаков, величин, над которыми производятся какие-то действия. Изучением групп, колец и тел различной природы, т. е. систем с двумя, тремя или четырьмя действиями, независимо от вещей, из которых они построены, занимается высшая алгебра. Арифметика, напротив, в первую очередь интересуется свойствами самих чисел. Эта ее черта особенно ярко проявляется в учении о простых числах, которыми мы займемся в следующих главах.

ГЛАВА IX

РАЗДЕЛИТСЯ ИЛИ НЕТ?

От тел и колец, т. е. от вопросов, принадлежащих скорее алгебре, вернемся снова к арифметике: займемся признаками делимости. Признаки делимости на 2, 3, 4, 5, 6, 8, 9, 10, 25 всем известны. Заметим только, что в различных системах счисления признаки делимости выглядят по-разному. Вот, например, признак делимости на два: «на два делятся все числа, последняя цифра которых четна». Предположим, что мы пользуемся троичной системой счисления; в ней число «десять» записывается так: 101, т. е. оканчивается нечетной цифрой — единицей; тем не менее и в троичной, и в любой другой системе счисления число «десять» будет делиться на 2, потому что делимость на два есть внутреннее свойство числа десять, совершенно не зависящее от того, как это число записывать. Следовательно, признак делимости, имеющий место в десятичной системе, в другой системе счисления может оказаться неверным. Есть, разумеется, и такие предложения о делимости, которые справедливы в любой системе счисления, хотя бы, например, такая теорема: «Разность между кубом любого нечетного числа и самим числом делится на шесть»; ими мы займемся в следующей главе.

Остановимся сначала на хорошо знакомых вещах: рассмотрим признак делимости на 9. Он поможет нам лучше понять те методы, которыми пользуются при выводе всевозможных иных признаков делимости.

Признак делимости на 9 основывается на том, что всякое число, имеющее в нашей системе счисления вид единицы

с нулями (всякая степень десяти), дает при делении на 9 остаток 1. Действительно,

Первое слагаемое, составленное сплошь из девяток, очевидно, делится на 9. Поэтому в остатке от деления 10" на 9 будет обязательно единица.

Рассмотрим, далее, какое-нибудь произвольное число, например, 4351. Каждая тысяча дает при делении на 9 остаток единицу. Значит, четыре тысячи дадут остаток 4. Точно так же три сотни при делении на 9 дадут остаток 3, пять десятков — 5, да еще останется 1 (число единиц в данном числе). Следовательно,

Если бы «хвост» 4 3 + 5 + 1, представляющий собой «сумму цифр» данного числа, делился на 9, то и все число разделилось бы на 9. Отсюда вывод: если «сумма цифр» данного числа делится на 9, то и само число разделится на 9.

Слова «сумма цифр» мы взяли в кавычки, потому что, строго говоря, складывать цифры нельзя: ведь цифра — это значок, с помощью которого записывается число. Складываются, разумеется, числа, изображаемые отдельными цифрами данного многозначного числа; но для краткости условились говорить «сумма цифр».

Повторим то же рассуждение, пользуясь понятием сравнения. 10 при делении на 9 дает в остатке 1, т. е. 10 и 1 сравнимы по модулю 9:

Возводим обе части сравнения в произвольную степень т; получим:

Умножив обе части этого сравнения на любое число TV, получим:

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

Рассмотрим теперь число, составленное из цифр а, ... ..., k, /, т. е. число

Это — не произведение чисел а, /, a число, содержащее / единиц, k десятков и т. д. Его можно записать и так:

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

Сложим почленно эти сравнения. Слева мы получим.

т. е. данное нам число, а справа — сумму его цифр. Следовательно, любое число и сумма его цифр сравнимы но модулю 9, т. е. либо одновременно делятся на 9, либо нет.

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

В самом деле: и первоначальное, и «перевернутое» числа имеют одну и ту же сумму цифр; иными словами, они при делении на 9 дают одинаковые остатки, и, следовательно, их разность делится на 9. Но если эта разность делится на 9, то значит, на 9 в свою очередь делится и сумма ее цифр. Вам сказана сумма всех цифр, за исключением одной. Следовательно, зачеркнутая цифра должна дополнять названную вашим товарищем сумму до ближайшего кратного девяти.

Если, например, было написано число 2365, а после перестановки получилось 3652, то их разность будет 1287; разность эта, а значит, и сумма ее цифр 1 + 2 + 8 + 7 = 18 делятся на 9. Если зачеркнута цифра 2, то останутся цифры, дающие в сумме 1 +8+7=16. Услышав от товарища, что получилось 16, вы дополняете это число до ближайшего большего, кратного 9, т. е. до 18 (из кратных девяти: 1 • 9=9; 2-9=18; 3-9 = 27 и т. д.; ближайшим, большим шестнадцати будет 18). Получите, очевидно, 18—16 = 2, т. е. как раз зачеркнутую цифру. Если сумма незачеркнутых цифр сама окажется кратной девяти, то, очевидно, и зачеркнутая цифра должна быть кратной девяти, т. е. равняться или 9, или 0. В этом случае вам так и придется сказать: «зачеркнуто либо девять, либо нуль».

Займемся теперь признаком делимости на 11. Он основан на тех же соображениях, что и признак делимости на 9. Как 10; 100; 1000 и т. д. (т. е. единица с любым числом нулей) при делении на 9 дают в остатке единицу, точно так же 100; 10 000; 1 000 000 (вообще — единица, с четным числом нулей) при делении на 11 дают в остатке единицу*). Иными словами,

Рассмотрим теперь какое-нибудь число, например, 57 385. Разобьем его на грани по две цифры в каждой справа налево, как это делается при извлечении квадратного корня. При этом в крайней левой грани может получиться и одна цифра (что как раз имеет место в нашем примере: 5'73'85). Что представляет собой первая грань? — Пять десятков тысяч (5Х 10000). Каждый десяток тысяч даст при делении на 11 остаток 1, значит, пять десятков тысяч дадут при делении на 11 остаток 5. Следующая грань (73) представляет собой 73 сотни. Каждая сотня даст при делении на 11 остаток 1. Значит, 73 сотни дадут в остатке 73. Остается еще крайняя правая грань: 85. Значит, наше число равно

т. е. числу, делящемуся на 11 + «сумма граней». Отсюда получается следующее правило:

*) Предлагаем читателю доказать это.

Если сумма граней делится на 11, то и все число разделится на 11.

В нашем примере сумма граней равна 5+73 +85 = 163. Полученный результат не делится на 11; значит, и 57 385 не разделится на 11. Если при сложении граней получится большое число, то его в свою очередь можно разбить на грани и испытать их сумму; в нашем примере имеем: 163 = 1 '63. Складываем грани; 1 —|- 63 = 64 — не делится на 11; значит, и исходное число не делится на 11.

Еще пример:

563 035 делится на 11. Действительно, разбиение на грани дает 56'30'35 (здесь первая грань состоит из двух цифр). Складываем грани 56 + 30 35 = 121. Сумма граней делится на 11; значит, и 563 035 делится на 11.

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

Рассмотрим пример. Пусть дано число 8 230 541. На нечетных местах (считая справа) стоят цифры: 1 (на первом месте), 5 (на третьем), 3 (на пятом), 8 (на седьмом); складывая эти цифры, получим l+5+3 + 8=17. На четных местах стоят цифры: 4 (на втором), 0 (на четвертом), 2 (на шестом); их сумма равна 4 + 0 + 2 = 6. Разность 17 — 6 = 11 делится на 11. Значит, и число 8 230 541 разделится.

Пусть читатель подумает сам, как доказать этот признак делимости. Рассуждение будет особенно просто, если использовать понятие сравнения.

Рассмотрим задачу, связанную с признаками делимости на одиннадцать.

Задача. Написать наименьшее делящееся на 11 шестизначное число, первая цифра которого 7 и все цифры различны.

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

Пишем вслед за семеркой четыре цифры, начиная с нуля, в порядке их роста: 70 123. Ясно, что таким образом мы получим наименьшее число нужного нам вида. Остается приписать последнюю цифру так, чтобы все число разделилось на 11.

Сумма цифр, стоящих на нечетных местах (считая слева), равна 7 +1 + 3 = 11; сумма цифр, стоящих на четных местах, равна 2. Чтобы разность сумм цифр, стоящих на четных и нечетных местах, делилась на 11 или равнялась нулю, последняя цифра должна быть девяткой (7 -j— 1 + 3 = = 0+2 + 9). Значит, искомое число—701 239.

Совершенно аналогичен признак делимости на 37. Число 1000 и все его степени (т. е. числа, изображаемые единицей с числом нулей, кратным трем) дают при делении на 37 остаток, равный 1. Действительно, 999 делится на 37 (получается 27). Значит,

Если при испытании делимости на 11 мы разбивали число на грани по две цифры в каждой, то при испытании делимости на 37 приходится делить его на грани по три цифры в каждой, тоже справа налево. При этом в крайней левой грани могут получиться одна, две или три цифры. Если сумма граней делится на 37, то и все число разделится. Например, 25 012 делится на 37: разбивая на грани, получим 25*012; сумма граней равна 25+ 12 = 37.

Переходим к признакам делимости на 7 и на 13. Они основаны на том, что 1001 делится на 7 и на 13; кстати, 1001 делится и на 11, так что мы, мимоходом, получим третий признак делимости на 11.

Рассмотрим какое-нибудь число, например 357 285. Это число содержит 357 тысяч и 285 простых единиц. Его можно записать так: 357 000 + 285. Прибавим и отнимем от нашего числа число его тысяч, т. е. 357; от этого ничего не изменится; сделаем далее простые преобразования:

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

и числом его простых единиц*). Если эта разность делится на 7, 11 или 13, то и само число разделится. Заметим, что число тысяч может оказаться меньше числа простых единиц; тогда, разумеется, из большего вычитаем меньшее.

Рассмотрим число 208 824 525. В нем 208 824 тысячи и 525 простых единиц. Вычитаем из числа тысяч число единиц: 208 824 — 525 = 208 299. Нужно узнать, делится ли на 7, 11 или 13 это число. Повторяем наш прием. Теперь число единиц (299) больше числа тысяч (208). Вычитаем из большего меньшее: 299 — 208 = 91. Полученное число (91) делится на 7 и на 13, но не делится на 11. Значит, и 208 824 525 делится на 7 и на 13, но не делится на 11.

Со свойствами числа 1001 связан любопытный арифметический фокус. Предложите кому-нибудь написать какое угодно трехзначное число так, чтобы вы не видели, какое. Предложите, далее, приписать к этому числу справа такое же число (если, например, было задумано 167, то получится 167 167). Предложите разделить результат на 7. Все благополучно разделится, хотя, казалось бы, взятое наугад число вовсе не обязано делиться на 7. Результат предложите разделить на 11; снова все благополучно разделится! Наконец, последний результат предложите разделить на 13. Деление пройдет без остатка, и в результате получится первоначально задуманное число.

Секрет фокуса очень прост. Приписав справа от задуманного числа его самого, мы тем самым умножаем его на 1001 (если, например, задумано число 167, то будем иметь 167167 = 167 000 + 167 = 167 ( 1000 + 1 ) = 167.1001 ). Но 1001 = 7'1ЫЗ. Значит, разделив 167 167 последовательно на 7, 11 и 13, мы разделим его на 1001. Сперва мы умножили задуманное число на 1001, а потом разделили. Понятно, что все деления прошли благополучно, и в итоге получилось само задуманное число.

Мы говорили уже, что в разных системах счисления признаки делимости на одно и то же число — различны. Так, например, в системе счисления с основанием 3 число, оканчивающееся нечетной цифрой, может делиться на 2. Установим признак делимости на 2 в троичной системе счисления. Число 3 при делении на 2 дает остаток 1. То же

*) Имеются в виду не разряды, а классы тысяч и простых единиц.

можно сказать о любой степени трех, потому что всякая степень трех, не содержа множителем двойку, при делении на 2 дает в остатке единицу. Повторив те же рассуждения, которыми мы пользовались при выводе обычного признака делимости на 9, убедимся, что в троичной системе счисления на 2 делятся такие, и только такие, числа, сумма цифр которых делится на 2. Число 10 201*), например, сумма цифр которого равна четырем, должно делиться на 2. Действительно, число 10 201 равно 1 • 34 + 0 . 33+ 2 . 32 + 0 . 3 + + 1 = 81 + 18 + I = 100, а сто, очевидно, на 2 делится.

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

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

Обозначим основание искомой системы счисления буквой п. Число п, как основание системы счисления, запишется так: 10; его сумма цифр равна единице. Значит, п—1, разность между числом и его суммой цифр, должна делиться на а, что запишется следующим образом: п — 1 = та, где m — любое натуральное число (или нуль). Отсюда следует, что искомое основание п системы счисления должно равняться увеличенному на единицу кратному числа а:

Обратно: из этого равенства следует, что любая степень п при делении на а даст в остатке единицу. В самом деле, наше равенство выражает совершенно то же, что сравнение

возведя это сравнение в любую степень k, получим:

Но если любая степень основания системы счисления дает при делении на а в остатке единицу, то, повторив слово

*) Жирный шрифт, как и в главах IV и V, обозначает число, записанное в недесятичной, в данном случае в троичной, системе счисления.

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

Итак, наш признак делимости будет иметь место во всех системах счисления, основание которых на единицу больше произвольного кратного числа а. Например, делимость суммы цифр будет обеспечивать деление числа на 9 не только в десятичной (10 = 1 • 9 + 1 ), но и в девятнадцатиричной (19 = 2 - 9 + 1 ), и в двадцати«восьмиричной (28 = 3 • 9 + 1 ), и во всех системах с основанием, равным 9т+ 1. Ни в каких иных системах счисления этот признак делимости не будет иметь места.

Вот еще задача: найти наименьшее основание системы счисления, в которой имеют место следующие признаки делимости:

1°. Если сумма цифр некоторого числа делится на 5, то и само число разделится на 5.

2°. Если число, образованное двумя последними цифрами произвольного числа, делится на 7, то и само число разделится на 7.

Из предыдущей задачи мы знаем, что первому условию можно удовлетворить, взяв в качестве основания системы счисления число вида:

Займемся вторым условием. Если делимость некоторого числа на 7 обусловливается делимостью на 7 числа, образованного его двумя последними цифрами, то, значит, единица третьего разряда 100 = ri1 должна делиться на 7*); тогда и любое число единиц третьего разряда будет делиться на 7, и вопрос сведется к исследованию второго и первого разрядов. Итак, ла должно делиться на семь: п* = 7р. Чтобы правая часть равенства была точным квадратом, число р должно равняться 7, умноженному на точный квадрат: р = 7kl\ мы будем иметь л2 = 49&2 или n = 7k.

Для определения п получилось два линейных уравнения с тремя неизвестными:

*) Так, в десятичной системе счисления признак делимости на 4 или на 25 заключается в делимости на эти числа нашей единицы третьего разряда — сотни.

Приравнивая друг другу правые части, получим одно неопределенное линейное уравнение с двумя неизвестными:

Решать такие уравнения в целых числах мы умеем. Без особого труда найдем:

где t — любое целое число; следовательно, я = 21+49/. Наименьшее положительное значение п = 21 получится при / = 0.

Число 21 и будет ответом на нашу задачу. Наименьшим основанием системы счисления, в которой имеют место данные выше признаки делимости, является число 21.

Разобрав вопрос о связи признаков делимости с различными системами счисления, мы перейдем к таким теоремам о делимости чисел, которые от системы счисления не зависят.

ГЛАВА X

ЕЩЕ О ДЕЛИМОСТИ; «БОЛЬШАЯ» ТЕОРЕМА, КОТОРУЮ ЗОВУТ «МАЛОЙ»

Разбирая на стр. 81 задачу о пифагоровых треугольниках, мы были вынуждены использовать предложения, подобные следующему: «сумма или разность двух четных или двух нечетных чисел представляют собой числа четные». Эти предложения, несомненно, относятся к учению о делимости; но в отличие от признаков делимости, разобранных в предыдущей главе и существенно связанных с выбором системы счисления, здесь выбор системы счисления не играет никакой роли.

В качестве первого примера рассмотрим разность между квадратом нечетного числа и единицей, т. е. выражение т*— 1, где m — число нечетное. Нетрудно убедиться, что при любом (нечетном) m эта разность должна разделиться на 8. Действительно, она разлагается на множители:

Раз m — число нечетное, значит оба множителя в правой части будут четными, причем, очевидно, соседними четными числами, потому что разность между ними равна т+\ — — (т—1) = 2. Но из двух соседних четных чисел одно обязательно делится на 4*). Значит, один из множителей делится на 4, да еще второй введет двойку. Все произведение будет делиться на 2-4 = 8.

*) Действительно, если одно из них, будучи четным, не делится на 4, то при делении на 4 оно может давать в остатке только 2, т. е. иметь вид An + 2. Но четными соседями этого числа будут числа (4/1 + 2) ±. 2, т. е. An и An + 4; оба они кратны четырем.

Можно рассуждать и иначе: раз m по условию нечетное число, значит, его можно записать в виде 2A+1, где k — произвольное число (натуральное или нуль). Получим:

Из двух соседних чисел k и k + 1 одно обязательно четное. Значит, в состав нашего выражения, кроме коэффициента 4, войдет еще множитель, равный двум, т. е. в составе его будет множитель, равный 4-2 = 8, что мы и хотели доказать.

Давая в выражении п&—1 числу m различные натуральные значения, получим следующие числа, кратные восьми:

В качестве второго примера рассмотрим разность между кубом любого числа и самим числом. Эта разность, как нетрудно показать, делится на 6. Действительно, возьмем произвольное число т. Разность между кубом и самим числом равна тъ — т. Разлагая на множители, получим:

Иными словами, разность между кубом натурального числа и самим числом всегда представляет собой произведение трех стоящих подряд натуральных чисел. Из трех же стоящих подряд натуральных чисел по крайней мере одно — четное (делится на 2) и одно делится на 3*). Следовательно, разность между кубом натурального числа и самим числом делится на 2 • 3 = 6, что мы и хотели доказать.

В качестве третьего примера рассмотрим задачу, обошедшую все школьные олимпиады и конкурсы: «доказать, что выражение т* — 5/я3 + 4т при любом натуральном m делится на 120». Для m = 1 и т = 2 это очевидно, потому что при т=\ или 2 наш трехчлен равняется нулю, а нуль

*) Действительно, рассмотрим три числа, стоящие подряд: kt k + h Ä + 2. Первое имеет вид либо k = Зя, либо k = Зп + 1, либо k — 3n+2, потому что при делении на 3 возможны только такие остатки: 0,1,2. Если k = 3n, то вопрос ясен. Если £ = Зя+1, то k + 2 = Зп + 3 делится на 3. Если, наконец, k = Зп + 2, то k + 1 = = Зп + 3 тоже делится на 3. Во всех возможных случаях одно из трех стоящих подряд чисел оказывается кратным числа 3.

принято считать кратным любого числа, стало быть, и ста двадцати; поэтому будем считать, что т^>2. Сделаем следующие очевидные преобразования:

При любом m наш трехчлен разлагается на пять множителей, представляющих собой (при т, большем двух) пять последовательных натуральных чисел. В последовательности пяти натуральных чисел найдется по меньшей мере два соседних четных; значит, трехчлен будет делиться на 8. Далее, в последовательности пяти чисел имеется по крайней мере одно, делящееся на 3 (уже три первых множителя, как мы видели, обеспечивают делимость на 3). Наконец, соображениями, совершенно аналогичными тем, которые сделаны в примечании к предыдущему примеру, убеждаемся, что произведение пяти стоящих подряд натуральных чисел должно делиться на 5. Итак, наш трехчлен делится на взаимно-простые числа 8, 3 и 5; он разделится и на их произведение, т. е. на 120. Вот несколько различных значений m и соответствующих значений трехчлена:

Разобранные примеры, несмотря на некоторую искусственность, очень поучительны. Они подводят нас к двум любопытным теоремам. Прежде всего, мы видим, что разность тг — m делится на 3. Так же можно доказать, что /я8 — m делится на 5, хотя доказательство несколько громоздко. Непосредственно очевидно, что tri — m делится на 2. Напротив, tri — m может при некоторых m и не делиться на 4: именно, при т — 2 мы получим тк — /гс = 16 — 2=14, т. е. число, на 4 не делящееся. Возникает вопрос: при каких же именно значениях а разность та — m делится на показатель а при любом т, а

при каких — нет. Эту задачу решил уже знакомый нам Ферма. Ей будет посвящен конец настоящей главы.

Вторая теорема, к которой подводят наши примеры, состоит в следующем. Мы видели, что произведение трех последовательных натуральных чисел делится не только на 3 (это понятно), но и на 6, т. е. на произведение 1-2-3. Точно так же произведение пяти последовательных натуральных чисел делится не только на 5, но и на 120, т. е. на произведение 1-2-3-4-5. Читатель без всякого труда докажет, что произведение четырех последовательных натуральных чисел делится на 1-2-3-4 = 24. Оказывается, имеет место следующая общая теорема:

Произведение m последовательных натуральных чисел

делится без остатка на произведение m первых последовательных натуральных чисел, т. е. на

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

равно числу сочетаний из (k+m—1) элементов по m или же коэффициенту при (т+\)-м члене разложения бинома (a -{- by*m~l. Следовательно, это частное должно быть целым числом, т. е. k(k+1)... (k+m—1) должно делиться без остатка на 1-2-3... (т—\)т.

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

«Всякое число вида /г4+4, где я]>1, является составным».

Докажем эту теорему. Имеем:

При целом п оба множителя — целые числа. При л]> 1 ни один из них не равен 1 и, следовательно, n4+4 является числом составным. При п=\ мы имеем исключительный случай: /г4 + 4 = 1 * + 4 = 5 — число простое.

Простые числа занимают математиков буквально тысячелетия. Древние греки интересовались ими две с половиной тысячи лет тому назад. Многие пытались найти признаки, позволяющие по строению числа установить — простое оно или составное. Достичь некоторого успеха на этом пути удалось впервые Ферма. В 1640 г. ему удалось доказать теорему, которая так поразила и обрадовала его, что он написал по поводу ее открытия (в письме к Френиклю): «Меня озарило ярким светом».

В чем же состоит эта теорема Ферма?

Мы уже видели, что при любом m двучлен тъ — m делится на 3, двучлен т* — m делится на 5. Ферма показал, что при любом простом р двучлен тр — m делится на р, каково бы ни было число т. Этот скромный с виду результат привел к важным обобщениям и породил довольно значительную литературу; его считают одной из основных теорем теории чисел. И все же эту теорему называют «малой», в отличие от «великой теоремы Ферма», о которой было рассказано в конце главы VII.

Сам Ферма формулировал свою теорему не совсем так, как это было сделано выше. Выражение тр — m можно преобразовать, взяв m за скобку; получится т(тр'1—1). Если m кратно р, то теорема очевидна. Важен и интересен только тот случай, когда m не делится на р. Но в таком случае тир взаимно-просты, потому что только те числа могут иметь общие множители с простым числом pt которые ему кратны. В случае взаимно-простых тир должна делиться на р разность трх—1. Так и была сформулирована теорема самим Ферма: «Если р просто, a m не делится на р, то т?~х — 1 делится на р».

Эту же мысль можно выразить на языке сравнений. Раз тр~1 — 1 делится на р, значит, тр~1 и 1 сравнимы по

модулю р, что, как мы знаем, записывается так:

В этой форме теорема Ферма дается в современных курсах теории чисел.

Разберем несколько примеров. Положим т=2\ тогда в качестве р можно будет взять любое простое нечетное число, т. е. любое простое, за исключением самого числа 2. В следующей таблице даны значения ру 2Р-1, 2Р~1— 1 и показано, что 2Р~Х — 1 всегда содержит множителем р.

Если р не является простым числом (например, /7=15 = = 3-5), то число 2Р~1 — 1 не будет обязательно обладать этим свойством. Действительно, 215"1— 1 = 214— 1 = 16384 — — 1 = 16 383 не делится на 15. Точно так же m не должно делиться на р. Если при m = 2 мы возьмем в качестве р тоже 2, то у нас ничего не выйдет: 2*~! — 1 = 1 не делится на 2.

Вот еще примеры:

Мы видим, что m не обязано быть простым (например, в третьем столбце /w=10 = 2-5). Но оно не должно

делиться на р. Поэтому при m = 3 не рассматривается значение /? = 3, при т — Ь — значение р = Ь, при яг =10 — значения /7 = 2 и /? = 5. Читатель сам убедится путем подсчета, что в этих случаях утверждение теоремы не выполняется.

Переходим к доказательству теоремы Ферма. Начнем с того, что рассмотрим полную систему наименьших положительных вычетов числа р, т. е. все остатки, которые могут получиться при делении различных чисел на р (кроме остатка, равного нулю). Вот эти вычеты:

(1)

Помножим каждый из них на число т, не делящееся на р. Получим

(2)

Все эти числа различны, ни одно из них не равно нулю. Но этого мало: все они дают при делении на р разные остатки. Действительно, если am и Ьт, где а и b — различные числа из ряда (1), т. е. меньшие р, дают при делении на р одинаковые остатки, то разность am — bm = m(a— b) должна делиться на р. Число m взаимно-просто с р. Следовательно, а — b должно делиться на р. А это невозможно, потому что разность а — b не равна нулю и заведомо меньше р (и а, и b — положительные числа, меньшие р). Полученное противоречие показывает, что исходное предположение о возможности одинаковых остатков при делении чисел ряда (2) на р — неверно. Следовательно, все эти остатки различны, и так как их ровно р—1, то они равны числам ряда (1), т. е. 1, 2, 3, —1, только взятым в каком-то другом порядке.

Но это значит, что каждое число ряда (2) сравнимо по модулю р (равноостаточно) с одним, и только одним, из чисел ряда (1). Обозначим число из ряда (2), сравнимое с 1, через А19 число, сравнимое с 2, — через k% и т. д., число, сравнимое с р—1, — через kD_x. Получим следующий ряд сравнений:

Перемножим теперь все эти сравнения, что, как мы знаем, делать можно. Получим:

(*)

Переходим к центральному пункту доказательства. Числа ku kb ..., kp_x представляют собой все числа ряда (2), только взятые в другом порядке. Произведение их не зависит от порядка множителей; поэтому

Заменяя произведение в левой части сравнения (*) равной ему величиной, получим:

тр~1-1.2-3 ... (р— 1)= Ь2-3 ... (р— l)(mod/0.

Все члены произведения 1-2 ... (р—1) меньше первоначального простого числа р> а потому взаимно-просты с ним. Значит, сравнение можно на них сократить. Получится:

что и требовалось доказать.

Это доказательство можно изложить, не используя понятия сравнения, что и было сделано самим Ферма, жившим без малого за 200 лет до Гаусса — изобретателя теории сравнений. Такое доказательство очень громоздко. Существует любопытное доказательство теоремы Ферма, связанное с превращением простой дроби в периодическую десятичную. Но оно, во-первых, длинно, а во-вторых, не совсем подходит к теме этой книжки, посвященной целым числам*).

Для читателей, знакомых с биномом Ньютона, можно привести еще одно доказательство теоремы Ферма.

Напишем по формуле Ньютона, разложение двучлена (т+\у, где m — целое, а р — простое число:

Все коэффициенты бинома Ньютона, т. е. числа вида

числа целые. Мало того, все они,

*) Изложено оно в книге Радемахера и Теплица «Числа и фигуры», которая вообще очень интересна.

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

числа, стоящие в знаменателе, должны полностью сократиться с множителями числителя. Но р взаимно-просто со всеми числами 1, 2, 3,..., k. Значит, числа эти должны полностью сократиться с множителями произведения (р — \ )(р — 2) ... ... (р — k+ 1), а множитель р останется нетронутым. Итак,

Это равенство показывает нам следующее. Если при каком-нибудь значении m двучлен тр — m делится на р, то на р обязательно разделится и (т+\)р — (т + 1), т. е. такой же двучлен, но с основанием, на единицу большим (потому что из делимости вычитаемого и разности на некоторое число следует делимость на это число и уменьшаемого). Если т=\у то тр — m = 1 — 1=0 наверное делится на р (нуль делится без остатка на любое число). Значит, и (т+\)р — — (т-{-\\ т. е. 2Р—2, будет делиться на р, а отсюда, в свою очередь, будет следовать, что Зр—3 делится на р и т. д. до произвольного значения т*). Следовательно, тр—m при любом m и простом р делится на р («малая» теорема Ферма).

Эта теорема была открыта Ферма в связи со следующей задачей: он искал такие выражения, содержащие букву я, которые были бы простыми числами. В связи с этим Ферма формулировал любопытную «теорему», которая оказалась неверной (см. стр. 87). Вот эта «теорема».

Ферма рассматривал числа вида 2*п+\у где п — произвольное целое число. Вот какие числа он получил, полагая п равным 0, 1, 2, 3, 4:

*) Напомним, что подобное рассуждение называется полной математической индукцией.

Все числа в нижней строке этой таблички (3, 5, 17, 257, 65 537) — числа простые. Ферма утверждал, что и при больших значениях п получатся простые числа. При п = 5 Ферма получил число 4 294 967 297, которое он, Ферма, не сумел разложить на множители и думал, что оно тоже простое. Однако Эйлер, о котором речь будет дальше, убедился, что 4 294 967 297 делится на 641, т. е. не является простым числом. Таким образом, Эйлер показал, что Ферма ошибся*).

Это неверное предложение очень поучительно. Своеобразное «чутье» подсказывает талантливым математикам, в каком направлении вести исследование. Мы увидим в следующей главе, что числа Ферма, т. е. простые числа вида 2'2Л-|" Ь оказались весьма замечательными, и изучение их привело впоследствии к крупным открытиям. Далее математик работает подобно любому ученому-естественнику: он делает предположения (гипотезы), проверяет их путем наблюдения и своеобразного математического опыта, ищет аналогии и т. п. Но, получив результат путем догадки или опыта, математик обязан строго доказать его. В противном случае всегда остается опасение, что высказанное утверждение может оказаться ошибочным.

*) Легко разделить 4 294 967 297 на 641, когда заранее знаешь, что делить нужно именно на 641. Но делить десятизначное число на все простые числа подряд (а простых чисел уже в пределах первой сотни — двадцать пять штук), не имея при этом ни достаточно больших таблиц простых чисел, ни иных вспомогательных средств, — очень трудная работа.

ГЛАВА XI

ЭРАТОСФЕНОВО РЕШЕТО

В предыдущих главах нам нередко встречались простые, или первоначальные, числа. Мы говорили уже, что простым называется число, имеющее только два делителя: самого себя и единицу. Единица, имеющая только один делитель, к простым числам не причисляется. Числа 2, 3, 5, 7, И, очевидно, — простые. Напротив, числа 4, 6, 8, 9 — составные.

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

Как же найти все простые числа в пределах первой тысячи? Для этого поступают следующим образом: выписывают все числа от единицы до тысячи. Зачеркивают единицу (она не является простым числом). Затем подчеркивают число 2 и зачеркивают все числа, кратные двум (четные), т. е. все числа через одно; получается таблица такого вида:

Далее подчеркивают первое из оставшихся незачеркнутыми чисел (3) и зачеркивают все числа «через два на третье» (т. е. кратные трем); затем подчеркивают 5 (четыре уже за-

черкнуто) и зачеркивают все числа, кратные пяти («через четыре на пятое») и так далее. Получается следующая таблица:

Таким образом, мы вычеркнем все составные числа и получим таблицу простых чисел (она приложена в конце книги на стр. 163).

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

Приглядываясь к эратосфенову решету, мы замечаем, что в начале таблицы простые числа расположены гораздо гуще, чем, например, вблизи тысячи. Так, в первом десятке (от 1 до 10) мы встречаем четыре простых числа: 2, 3, 5, 7. А между простыми числами 997 и 1009 имеется одиннадцать составных чисел подряд. Если зайти достаточно далеко, то можно найти какой угодно длинный числовой промежуток, т. е. сколь угодно длинный ряд натуральных чисел, состоящий сплошь из чисел составных.

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

Это — очень большое число. Оно равно приблизительно 95-10158, т. е. значительно больше обычных «астрономических» чисел. (Но оно ничтожно мало рядом с числом 99в,

см. стр. 15.) Обозначим это число буквой А. Рассмотрим теперь ряд чисел*.

Это — серия из ста целых чисел подряд. Каждое из них — составное. Возьмем, например, первое из них, т. е. А+ 2; оно делится на 2. Действительно, А, имея по условию множителем 2, делится на 2. Само число 2 (второе слагаемое), очевидно, делится на 2. Следовательно, и сумма разделится на 2, т. е. будет числом составным. Точно так же А + 3 разделится на 3, A + 4 — на четыре и т. д.; наконец, A +101 разделится на 101, потому что в А входит множителем 101. Таким образом, все числа найденного нами ряда — числа составные, что мы и хотели доказать.

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

При этом, естественно, возникает мысль: может быть, начиная с некоторого числа, все числа являются составными? Может быть, существует лишь конечное, ограниченное количество простых чисел, а все остальное бесконечное множество чисел суть числа составные? Может быть, существует самое большое простое число? Что же это за число?

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

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

Итак, предположим, что существует наибольшее простое число. Обозначим его через р. Рассмотрим число, представляющее произведение всех простых чисел, т. е. число 2• 3• 5• 7• 11 ... р. Прибавив к этому числу единицу, по-

*) В настоящее время имеется много различных доказательств теоремы о бесконечности множества простых чисел.

лучим число 2-3-5.7-11 ... р+\, которое, конечно, гораздо больше, чем р.

Попытаемся разделить его на какое-либо простое число (мы предполагаем, что р самое большое простое число). Число 2-3'5-7-11 ... р+\ состоит из двух слагаемых. Первое слагаемое 2-3-5-7-11 .../?, как произведение всех простых чисел, делится на любое простое число, а второе слагаемое (единица) при делении на любое целое число, кроме единицы, дает в частном нуль и в остатке единицу; значит, и сумма 2-3-5-7-11 ... р+\ при делении на любое простое число даст в остатке единицу.

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

Значит, число 2-3-5-7-11 ... р+\ или само является простым, или делится на простое число, отличное от 2, 3, 5, 7, 11,..., р} и, значит, большее чем р. Таким образом, предположив, что р — наибольшее простое число, мы доказали, что существует простое число, еще большее. Это противоречие убеждает нас, что исходное предположение неправильно, т. е. что наибольшего простого числа быть не может: число простых чисел бесконечно.

Все простые числа, начиная с трех, можно разбить на две категории. Одни (например, 5, 13, 17) имеют вид 4/I+1; другие (например, 3, 7, 11) имеют вид An—1. Никакого иного вида нечетное число (а все простые числа, кроме числа 2, нечетны) иметь не может, так как при делении нечетного числа на 4 возможны остатки, равные только 1 или 3. Разумеется, не всякое число вида An ± 1 простое, но всякое простое число имеет один из этих видов. Спрашивается: в каждом ли из этих классов содержится бесконечное множество простых чисел, или же один из них конечен, а другой — нет? Оба они быть конечными, разумеется, не могут.

Исследование показало, что и тех и других чисел бесконечно много. Для чисел вида An +1 доказательство этого утверждения несколько громоздко, и мы ограничимся тем, что докажем бесконечность множества простых чисел вида An— 1.

Докажем предварительно следующее вспомогательное предложение (лемму): «Произведение нескольких чисел вида An +1 само есть число вида 4/z+l».

Рассмотрим два числа этого класса: Перемножим их:

где через k обозначено целое число 4ab+a+b. Мы видим, что произведение двух множителей вида 4п + 1 обязательно имеет тот же вид. Присоединяя третий, четвертый и т. д. множители, мы убедимся, что то же самое можно сказать о произведении любого числа таких множителей.

Перейдем теперь к теореме о числах вида 4п — 1 и применим к ней евклидов прием доказательства. Допустим противное— что простых чисел вида 4п— 1—конечное количество, например т. Обозначим их рь рь . . . , рт. Рассмотрим число

Оно должно иметь хотя бы один (простой) множитель вида 4п—1, потому что оно само имеет вид 4п—1, а произведение множителей вида 4/х + 1, как мы видели, должно иметь вид 4/1 + 1. Итак, среди простых множителей числа А должно быть некоторое р = 4п— 1. Но р не может равняться ни одному из чисел pt9 ръ . . ., pmf потому что ни на одно из этих чисел наше А не делится; это р — простое число вида 4п—1. Следовательно, числами рь рь . . рт не исчерпываются все простые числа вида 4п—1; а это противоречит нашему исходному предположению. Таким образом, простых чисел вида 4п — 1 бесконечно много.

Числа вида 4п — 1 образуют арифметическую прогрессию с первым членом 3 и разностью 4 (ч-З, 7, 11, 15, . . .). Доказанную только что теорему можно было бы сформулировать и так: в бесконечной арифметической прогрессии

содержится бесконечное же множество простых чисел.

Спрашивается, нет ли еще прогрессий, обладающих тем же свойством? Мы видели, что прогрессия с первым членом 1 и разностью 1 (сам натуральный ряд) содержит бесконечное количество простых чисел. То же самое говорилось (хотя мы и не доказывали этого) о прогрессии -Hl, 5, 9, 13, 17, 21, . . . , т. е. о числах вида 4п+1.

Вопрос о количестве простых чисел в той или иной арифметической прогрессии занимал многих математиков, особенно на рубеже XVIII и XIX столетий. Решил его полностью Лежен-Дирихле (1805—1859 гг.), который доказал, что любая арифметическая прогрессия, первый член и разность которой взаимно просты, содержит среди своих членов бесконечное множество простых чисел. Оговорка относительно взаимной простоты первого члена и разности очень существенна: если они имеют общий множитель, отличный от единицы, то, очевидно, все члены прогрессии будут содержать этот множитель и, следовательно, будут числами составными.

Изложить доказательство Дирихле элементарно — совершенно невозможно.

Упомянем, кстати, еще об одной проблеме, которая естественно возникает при внимательном рассмотрении эратосфенова решета и которая до сих пор не решена. Среди простых чисел встречаются «числа-близнецы», т. е. пары соседних нечетных чисел, являющихся одновременно простыми. Таковы, например, числа 5 и 7, числа 11 и 13, числа 17 и 19 и т. д. В начале «решета» подобные пары встречаются довольно часто, но по мере продвижения в область больших чисел, их становится все меньше и меньше. В первой сотне имеется 8 таких пар (3 и 5; 5 и 7; 11 и 13; 17 и 19; 29 и 31; 41 и 43; 59 и 61; 71 и 73); между числами 501 и 600 — только две пары (521 и 523; 569 и 571). Дальше они встречаются очень неравномерно, но в общем — все реже и реже, значительно реже, чем сами простые числа. Впрочем, известны и весьма солидные пары «близнецов», например 5 971 847 и 5 971 849. Спрашивается, будет ли среди этих пар последняя? Этого до сих пор не удалось установить. Мало того, до сих пор не намечено даже пути, следуя которому можно было бы приблизиться к решению этой проблемы.

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

чисел, что ее нередко называют «основной теоремой арифметики». Вот как она формулируется: «Всякое натуральное число разлагается единственным образом на простые множители». Докажем эту теорему.

Предварительно докажем вспомогательную теорему (лемму). Именно, докажем, что из делимости произведения kl на простое число р следует, что хотя бы один множитель (либо k, либо /, а может быть и оба) делится на р.

Действительно, число k либо делится на /?, — и тогда теорема доказана, — либо нет. Если k не делится на р, то числа кнр взаимно-просты, потому что k, не делясь на р, не содержит его в числе своих множителей, а р, будучи простым, никаких иных множителей, кроме единицы и самого р, не имеет. Но если k взаимно-просто с ру а произведение kl делится на pf то / должно делиться на р (теорема третья главы VI, стр. 53). Следовательно, / делится на р.

Эта лемма без труда распространяется на любое число множителей: если произведение ab.. .h делится на простое число ру то на него делится по крайней мере одно из чисел а, Л.

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

Что разложение возможно, это очевидно. Пусть дано некоторое число N. Если оно простое, то теорема доказана, ибо его можно считать собственным единственным простым множителем. Если же оно составное, то разделится на какое-то простое число ру меньшее чем N. В частном получится число Nlt тоже меньшее чем N. Если просто, то Л/=/?,Л^, и теорема доказана. Если же N\ не является простым числом, то оно разделится на некоторое простое число /?2, меньшее чем Ni9 и в частном получится JV2, тоже меньшее чем Л^. Числа Ni9 Л/2, iV3 и т. д. все время уменьшаются, и число их не может быть бесконечным. Поэтому дойдем до последнего частного — числа рт — уже простого, и получим представление числа N в виде произведения простых чисел рхр%. . ,рт.

Это все очень просто и почти очевидно. Существенной является вторая часть теоремы, именно утверждение, что разложение числа N на простые множители единственно. Пред-

положим, что нам удалось двумя путями разложить число Ы на простые множители: первый метод дал разложение

а второй — разложение

где все р и q— простые числа. Имеем, очевидно,

(*)

Левая часть этого равенства делится на рх\ значит, и правая, т.е. произведение qxq*...qs, на него разделится. Но в силу леммы один из множителей qXt q%,... ,qs должен разделиться на рх. Допустим, что qx делится на рх (мы всегда можем перенумеровать числа q именно таким образом). Число qXf будучи простым, делится только на единицу и на самого себя; следовательно,

Поделив обе части равенства (*) на px = qh получим:

Повторив это же рассуждение, получим:

а после нового сокращения придем к соотношению

Точно так же найдем, что ^3=/?3; qi=pi; ...\qs=pr. Следовательно, множителей q столько же, сколько множителей р> каждое q равно некоторому р, т. е. оба разложения числа N на простые множители — тождественны.

Как практически разлагать числа на простые множители, читатели помнят из школьного курса. Так, например, разложение числа 8316 на простые множители выполняется следующим образом:

Любое число N можно, таким образом, представить единственным образом в форме

где /?!, ръ.. ,,рт — простые числа, а а, ß, ..., X — некоторые показатели. Такое представление числа N иногда называют «каноническим разложением числа на сомножители».

Прежде чем расстаться с основной теоремой арифметики, сделаем еще одно замечание. Мы определили простое число как такое, которое не имеет делителей, кроме самого себя и единицы. Далее, мы доказали, что если произведение нескольких чисел делится на простое число, то на него непременно разделится хотя бы один из множителей (лемма к основной теореме). Можно было бы доказать теорему, обратную этой лемме, именно — доказать, что всякое число, на которое обязательно делится хотя бы один множитель делящегося на него произведения нескольких чисел, не имеет иных множителей, кроме единицы и самого себя. Поэтому именно последнее свойство можно принять за определение простого числа. Так часто и делают: именно, простым числом называют число, на которое произведение может делиться только в том случае, если на него делится один из множителей; а число, не имеющее иных делителей, кроме себя и единицы, называют неразложимым. Пользуясь этими терминами, мы можем лемму сформулировать так: «Всякое неразложимое число — просто»; а обратную ей теорему так: «Всякое простое число — неразложимо». Обе эти теоремы можно соединить в одну: термины «простое число» и «неразложимое число» — значат одно и то же.

Искушенный различными арифметическими сюрпризами читатель не станет спрашивать: «зачем было вводить два термина, если они обозначают одно и тоже?» Читатель чувствует, конечно, что здесь скрыт какой-то подвох. Ведь если есть «арифметики», в которых трижды три — четыре и 3-3= 10, то почему бы не быть и такой арифметике, в которой простые числа не являются неразложимыми, а неразложимые — простыми?..

Правда, такая арифметика кажется невероятной. Ведь именно лемма, смысл которой, по существу, и состоит в отождествлении понятий простоты и неразложимости, позволила нам доказать, что разложение любого числа на простые множители — единственно. Неужели возможны такие «арифметики», в которых одно и то же число разлагается на неразложимые

множители несколькими различными путями, т. е. имеет несколько канонических разложений?

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

Рассмотрим ряд всех четных положительных чисел, т. е. числа 2, 4, 6, 8, 10, 12, 14, 16, 18,...

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

В этой числовой системе некоторые числа имеют только два делителя (рассматриваются, разумеется, только четные делители). Таковы числа 6, 10, 14 и многие другие, делящиеся только на два и на себя. Любое число вида 4п+2 (где п — обычное натуральное число) будет в нашей системе иметь только два делителя. Числа такого вида и будут, с точки зрения этой системы, числами неразложимыми. Число 2, подобное единице в ряду натуральных чисел, имеет только один делитель (самого себя). Наконец, числа 4, 8, 12, 16, вообще числа вида 4я, имеют несколько делителей.

Пока аналогия с обычным натуральным рядом полная. Но дальше начинается расхождение. Рассмотрим число 420, принадлежащее к нашей системе (четное). Его можно двумя путями разложить на множители, неразложимые с точки зрения нашей системы. Действительно, имеем: 420 = 6*70 и 420= 14-30. Числа 6, 14, 30 и 70 неразложимы (ни одно из них не является произведением двух четных же чисел.) Следовательно, возможно два разложения числа 420 на неразложимые далее множители.

Какие же числа будут играть в нашей системе роль простых? Нетрудно сообразить, что это будут числа вида 2/?,

где р — простое число в обычном смысле (с точки зрения арифметики натурального ряда). Всякое простое число будет в нашей системе неразложимым. Но не всякое неразложимое будет простым. Числа 30, 42, 70, будучи неразложимыми, не будут простыми. Лемма, предшествующая основной теореме арифметики, для них не выполняется. Поэтому-то и получилась возможность разлагать число на неразложимые дальше множители несколькими способами.

Другим парадоксом этой числовой системы будет то, что не всякое число можно будет разложить на простые множители, т. е. представить в виде произведения чисел вида 2/7, где р — обычное первоначальное число. То же число 420, разложимое двумя путями на «неразложимые» множители, не может быть разложено на «простые» множители.

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

дает простые числа при любом п, не превосходящем 79. Например, при п = 0 мы получим Л =1601, при п=\ будет Л= 1523, при п = 2 будет Л = 1447, — все числа простые. Наконец, при п = 39 получим Л = 41, — тоже простое число. Далее, при значениях п от 40 до 79 получаются те же значения Л, но в обратном порядке: при л = 40будет Л =41,..., при п = 78 будет Л = 1523, при п =79 будет Л = 1601. Но при л = 80 формула «отказывается служить»! В этом случае получим:

Вот еще интересный пример*). Если в выражение

*) Этот пример указан мне проф. А. Ф. Бермантом.

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

Но формула «отказывается служить» при р = 37; при этом n=—y— = 45 812 984 491—число составное; оно разлагается на 2 простых множителя, именно:

В конце предыдущей главы мы говорили о знаменитой ошибке Ферма, связанной с «охотой за формулой», дающей простые числа. Ферма считал, что при любом целом неотрицательном п выражение 2*п + 1 дает простое число. Если математическое чутье обмануло Ферма в том отношении, что его утверждение оказалось неправильным, то во всяком случае оно подвело его к очень важной и интересной проблеме. Оказалось, что если и не все числа вида 2'2" +1 являются простыми, то те из них, которые просты, обладают рядом замечательных свойств. Мы уже говорили, что ими занимался Эйлер, который и обнаружил ошибку Ферма. Но самый любопытный результат, относящийся к этим числам, был получен Гауссом. Он связан с известной геометрической задачей — построением с помощью циркуля и линейки правильных многоугольников.

Уже в древности умели строить правильные трех-, четырех- и пятиугольники. Пользуясь возможностью делить любой угол пополам, без труда строили 8-, 16-, вообще 2Л-угольники; далее 6-, 12-, вообще 2п • 3-угольники, 10-, 20-, вообще 2п - 5-угольники. Отнимая от одной шестой части окружности одну десятую часть ее, получали одну пятнадцатую: т. е. строили правильный вписанный пятнадцатиугольник, а за ним 30-, 60-, вообще 2п • 15-угольники. Но все попытки

построить циркулем и линейкой правильный семи- или одиннадцатиугольник оканчивались неудачей.

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

Гаусс доказал следующую замечательную теорему: циркулем и линейкой можно построить только такие правильные многоугольники (с простым числом сторон), у которых число сторон есть «простое число Ферма», т. е. число вида 2*п + 1 (при тех значениях п, разумеется, при которых эта формула дает простое число, что, как мы знаем, осуществляется не всегда). При п = 2 получается правильный 17-угольник, при /2 = 3 — правильный 257-угольник. Если число сторон правильного многоугольника — простое, но не является числом Ферма, то его построение классическими средствами — циркулем и линейкой — невозможно. Правильные многоугольники с семью, с одиннадцатью, с тринадцатью сторонами построить циркулем и линейкой нельзя, а с 17 и 257 сторонами — можно!

Сам Гаусс, решив задачу в общем виде, дал разработанный до конца метод построения только для семнадцатиугольника. Следующими после 17 «числами Ферма» являются 257 и 65 537. Законченное построение многоугольника с 257 сторонами дал Ришело (оно занимает 80 страниц), а многоугольник с 65 537 сторонами построил (по гауссову же методу) Гермес (рукопись занимает довольно объемистый ручной чемодан и хранится в Геттингене). Теория чисел оказалась любопытнейшим образом связанной с геометрией.

После смерти Гаусса ему поставили в Геттингене памятник на пьедестале, имеющем форму правильной 17-угольной призмы.

ГЛАВА XII

ЧАСТО ИЛИ РЕДКО?

Рассматривая эратосфеново решето, мы видим, что сначала промежутки между последовательными простыми числами невелики, но по мере продвижения в ряду натуральных чисел они, как правило, становятся больше и больше. Иными словами, по мере движения вдоль ряда натуральных чисел простые числа встречаются все реже и реже (см. таблицу в конце этой книжки). Если среди чисел первого десятка мы находим четыре простых числа, то между 1001 и 1010 имеется только одно: 1009.

Евклид доказал, что простых чисел бесконечно много: как бы далеко мы ни зашли в натуральном ряду, нам будут попадаться простые числа. С другой стороны, «острова», состоящие сплошь из составных чисел, будут, как правило, становиться «длиннее», простые числа будут встречаться реже и реже. Каков же закон распределения простых чисел? Как узнать, например, сколько их содержится между 1 000 000 и 10 000 000, не пересчитывая их непосредственно? Эта задача принадлежит к числу труднейших, и до сего времени до конца она не решена. Сложность задач, связанных с распределением простых чисел, стала у математиков поговоркой. О ней знают и нематематики. Даже поэты упоминают о ней. Валерий Брюсов писал в одном из своих известных стихотворений:

... Но пред Эдипом загадка Сфинкса: Простые числа все не разгаданы . . .

Разберем пример, который позволит лучше освоиться с самой постановкой вопроса. Рассмотрим бесконечную

геометрическую прогрессию:

4fi, 2, 4, 8, 16. 32,

где каждое последующее число в два раза больше предыдущего. Число членов здесь бесконечно. Как же расположены эти числа по отношению к ряду всех натуральных чисел? Легко видеть, что вначале они «сидят» очень густо. В промежутке от 1 до 10 мы имеем четыре таких числа (1, 2, 4, 8). В промежутке от 30 до 40 мы имеем уже только одно (32). Наконец, в промежутке от 1025 до 2025 (промежуток в целую тысячу) нет ни одного числа нашего ряда. Нетрудно показать, что если зайти в натуральном ряду достаточно далеко, то можно найти сколь угодно длинный числовой промежуток («остров»), не содержащий ни одного члена нашей прогрессии.

Все это очень напоминает свойства простых чисел. Но есть и существенная разница. Закон распределения чисел ряда 1, 2, 4, 8, 16, ... в ряду натуральных чисел очень прост. Нетрудно написать формулу, позволяющую найти число членов этого ряда между двумя любыми натуральными числами. Действительно, число членов нашего ряда, не превосходящих числа M равно увеличенной на единицу целой части двоичного логарифма числа N (читатель, знакомый с логарифмами, сам докажет это).

Наоборот, закон распределения чисел ряда

2, 3, 5, 7, 11, 13, ...

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

998, 999, 1000, 1001,1002,1003,1004,1005,1006, 1007, 1008

следует промежуток

1009,1010,1011,1012,1013,1014, 1015, 1016,1017, 1018,1019

тоже из 11 чисел, содержащий три простых: 1009, 1013 и 1019.

Мы видели, что промежутки между простыми числами становятся все больше и больше и делаются в конце концов сколь угодно длинными. Но встречаются, и тоже достаточно

Л. ЭЙЛЕР

далеко, неожиданные «сгустки» простых чисел. По соседству с тысячей, например, вслед за промежутком в 11 составных следует серия из 11 чисел, из которых 3 простых. Значит, на 22 числа приходится три простых — более 13 процентов, что совсем не так уж мало! Далее, есть основания полагать, что в ряду натуральных чисел как угодно далеко встречаются пары соседних простых чисел — «числа-близнецы», о которых уже упоминалось в предыдущей главе. Поэтому наличие огромных «островов», свободных от простых чисел, почти ничего не дает нам для суждения о том, насколько часты последние среди всех натуральных чисел. И все-таки...

И все-таки уже Эйлер (1707—1783 гг.), замечательнейший математик XVIII столетия*), полагал, что простые числа встречаются «бесконечно реже, чем целые». Как понимать эти слова Эйлера? Они означают следующее: рассмотрим какое-нибудь натуральное число N, простое или составное. Рассмотрим все простые числа, не превосходящие Л/, т. е. числа

2, 3, 5, р

(если N простое, то последним в этом ряду будет само N=py в противном случае — некоторое число (простое), меньшее N). Допустим, что всего будет п простых чисел, не превосходящих N. Если, например, исходить из N=10, то простыми числами, меньшими чем 10, будут 2, 3, 5, 7; таких чисел будет всего 4; значит, в этом примере я = 4. Читатель сам подсчитает, что при N=19 п = 8; при N=30 п = = 10 и т. д.

Само число п мало что дает для интересующей нас задачи, но отношение ~ как раз и показывает, какую долю составляют простые числа, не превосходящие данного числа, по отношению ко всем натуральным числам, его не превосходящим. Отношение ^ вполне характеризует густоту, или, выражаясь научным языком, «плотность» простых чисел среди натуральных. В следующей таблице приведен ряд значений N

и соответствующих значений п и -^г. В последней строке

*) Эйлер более 30 лет жил и работал в России, являясь членом Петербургской Академии наук.

показано, какой процент составляет число п по отношению к n:

(Значок я^, поставленный перед некоторыми числами последней строки, заменяет слово «приблизительно»; например, я^17% читается: «приблизительно 17 процентов».) Мы видим, что «плотность», густота простых в ряду всех натуральных чисел становится меньше и меньше, если мы рассматриваем все большие и большие числовые промежутки.

Слова Эйлера о том, что простые числа встречаются бесконечно реже, чем целые, надо понимать так: если рассматривать очень большое количество n последовательных натуральных чисел, то отношение — будет очень малым числом; точнее, если мы выберем какое-нибудь очень малое значение для , например одну миллионную, одну миллиардную и т. д., то всегда можно будет найти такое большое натуральное число, что при всех значениях n, которые его превосходят, наше требование будет выполняться, т. е. ~ будет меньше, чем указанная малая дробь.

Эйлер доказал свое утверждение не вполне строго. Первое безупречное доказательство этого факта нашел французский математик А. М. Лежандр, опубликовавший его в 1798 г.

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

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

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

Л. ДИРИХЛЕ

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

Первую простую формулу, приближенно выражающую число простых чисел, меньших, чем заданное натуральное число N, дал Лежандр; он получил ее «путем подбора», причем она достаточно хорошо давала п для любых N, больших чем 1000 и меньших чем 400 000. (Во времена Лежандра таблицы простых чисел были составлены только до N=400 000; в наше время эратосфеново решето доведено до N= 9 000 000.)

Вот формула Лежандра:

причем берется, разумеется, целая часть неправильной дроби, вычисленной по этой формуле. Рассмотрим табличку, дающую соответствующие различным N значения п, вычисленные по формуле Лежандра и подсчитанные непосредственно по таблице:

N

10

100

1000

10 000

100 000

п по Лежандру .

8

28

171

1230

9587

п истинное . . .

4

25

168

1229

9592

Начиная с N=1000 «наблюденные» и вычисленные значения п очень близки друг к другу, причем уклонения получаются «двусторонние»: при некоторых значениях N «наблюденное» значение чуть больше вычисленного, при других — чуть меньше. Доказать справедливость формулы Лежандра в общем виде не удалось ни ему самому, ни другим математикам.

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

теорией чисел и, прилагая к ней последовательно методы анализа (в этом — его большая заслуга), получил ряд интересных результатов. Мы говорили уже, что он доказал справедливость Великой теоремы Ферма при п = Ъ и л=14 и что им же доказано наличие бесконечного множества простых чисел в любой арифметической прогрессии со взаимно-простыми первым членом и разностью. Им же были получены важные результаты в учении о неопределенных уравнениях второй степени. С легкой руки Дирихле*) математики разных стран начали применять аналитические методы к изучению натуральных чисел.

Французский математик Бертран, исходя из «опытов» с эратосфеновых решетом, высказал предположение, что между любым числом и числом, вдвое большим, имеется по крайней мере одно простое число. (Точнее, если 2х ]> 7, то между х и 2х — 2 всегда имеется простое число.) Он не сумел доказать это предложение, но, опираясь на него, доказал ряд важных теорем арифметики и алгебры. Предложение о том, что между числами х и 2х (при х^>\) имеется по крайней мере одно простое число, получило у математиков наименование «постулата Бертрана»**). Доказать постулат Бертрана удалось в 1852 г. Чебышеву.

Пафнутий Львович Чебышев (1821 — 1894 гг.) по справедливости считается гордостью русской науки. Полвека работал он в самых разнообразных областях математики и везде получил выдающиеся результаты. Но самое важное в его деятельности — то, что он ставил совершенно новые вопросы, быстро привлекавшие к себе внимание многих математиков, в первую очередь — его учеников. Он создал русскую математическую школу, представители которой до сих пор занимают ведущее положение в науке.

Чебышеву не удалось найти формулу, которая позволяла бы по данному N точно находить соответствующее значение «плотности» Мы говорили уже, что и теперь, спустя сто лет после работ Чебышева по теории чисел, эта задача

*) Дирихле первый стал систематически применять к изучению натуральных чисел методы анализа непрерывных величин. Но отдельные результаты на этом пути получили до него Эйлер и Гаусс.

**) Латинское слово postulatum (постулатум) значит «требование:». В старых руководствах формулировка аксиом обычно начиналась словами: «потребуем, чтобы...».

П. Л. ЧЕБЫШЕВ

считается неразрешимой (средствами современной науки, разумеется: наука будущего безусловно ее решит). Но Чебышев доказал, что при очень больших значениях N отношение ~ мало отличается от величины jj' , причем точность формулы тем больше, чем большие значения N рассматриваются. Такого рода формулы, справедливые только приблизительно, но дающие тем большую точность, чем больше значения входящих в них величин, носят название асимптотических формул. Значит, можно сказать, что Чебышев дал асимптотическую формулу для плотности распределения простых чисел. Ему же удалось дать асимптотическую формулу для вычисления самого числа п простых чисел, не превосходящих данного Л/, но в эту формулу входит знак интеграла, и мы приводить ее здесь не будем.

Чебышев справедливо считается создателем асимптотических законов распределения простых чисел. У него был, правда, предшественник, который чисто «опытным» путем — путем внимательного изучения эратосфенова решета — нашел те же формулы, но доказать их правильности он не сумел и не публиковал их. Это был Гаусс.

После открытия асимптотических формул стал вопрос об оценке их точности и о тех закономерностях, которые можно подметить в самом уклонении «наблюденных» значений числа п от вычисленных по этим формулам. Подобного рода вопросами занимались и сам Чебышев, и Адамар, и Ландау, а в последнее время — английские математики Гарди и Литтлвуд. Вопрос об отклонениях от формул Чебышева оказался чрезвычайно трудным. Но и здесь кое-что удалось сделать.

В приводимой здесь таблице в первой строке, отмеченной буквой N, даны значения натуральных чисел, а во второй, отмеченной буквой А, — соответствующие им значения для л, вычисленные по формуле Чебышева; наконец, в третьей строке — точные значения п

Мы видим, что разница между А и п с ростом N возрастает, но доля, которую эта разница составляет от числа /V, убывает и убывает быстро. При N=1000, например,

эти 10 составляют процента от тысячи. При N= 1 000 000 будем иметь:

(больше чем при N= 1000); но эти 130 по отношению ко всему рассматриваемому миллиону составляют лишь 0,013%— почти в 8 раз меньше, чем в случае 7V= 1000. Именно это отношение характерно для оценки качества приближенного соотношения. Мы видим, что для формулы Чебышева это отношение очень мало; стало быть, она хороша: чем больше рассматриваемые числа, тем эта формула лучше (асимптотический закон).

С другой стороны, мы замечаем, что А всегда больше я, и это справедливо не только для чисел, помещенных нами в табличку, но и для всех чисел Nt для которых были подсчитаны соответствующие им А и п. Казалось естественным ожидать, что формула Чебышева дает всегда несколько «завышенный» результат. До 1914 г. было много попыток доказать это утверждение, т. е. доказать, что А ^ п при любом N. Но в 1914 г. Литтлвуд показал, что существуют такие числа (такие значения TV), при которых п должно быть обязательно больше Л, причем в дальнейшем при еще больших значениях N будут встречаться и такие N, при которых А^>п, и такие, при которых п^> А; иными словами, уклонения от чебышевской формулы будут не только ничтожно малы, но будут носить совершенно случайный характер, давая результат, то чуть-чуть больший, то чуть-чуть меньший истинного.

Каково же то наименьшее натуральное число, для которого чебышевская формула дает результат, меньший чем нужно? Товарищ Литтлвуда по работе, математик Гарди, показал, что это число невероятно велико. Оно не меньше чем 10700. Казалось при этом, что подойти как-то ближе к этому числу невозможно. И только совсем недавно, в 1933 г., английскому математику Скьюзу удалось показать, что (если сделать некоторые дополнительные предположения) можно оценить то число, при котором впервые в числовом ряду чебышевская

формула дает результат, меньший истинного. Это число равно приблизительно 101о1°34.

Число, данное Скьюзом, значительно превосходит все ранее указанные числовые гиганты и в этом смысле его можно назвать «числом-рекордсменом». Именно, число 9э9, о котором говорилось в первой главе, и даже такое огромное число как 108,1°16, до которого дошел в своем «Псаммите» Архимед, очень и очень малы по сравнению со скьюзовским гигантом.

ГЛАВА XIII

ПРОБЛЕМА ГОЛЬДБАХА

В предыдущей главе мы познакомились с вопросом распределения простых чисел среди всех натуральных. Оказалось, что простые числа, расположенные сравнительно густо в начале натурального ряда, в дальнейшем встречаются все реже и реже, промежутки между ними становятся все больше и больше. В этих промежутках попадаются числа, представляющие собой сумму двух простых чисел. Вот, например, числа первого десятка: 1 (в счет не идет); 2 (простое); 3 (простое); 4 (4 = 2 + 2 — сумма двух простых); 5 (простое); 6 (3 -}- 3 — сумма двух простых); 7 (простое); 8 (3 + 5 — сумма двух простых); 9 (2 + 7 — сумма двух простых); 10 (3+7 — сумма двух простых). Мы видим, что все числа первого десятка или являются простыми, или представляют собой сумму двух простых. Но уже 27 представить в виде такой суммы не удается. Зато 27 можно записать как сумму трех простых слагаемых: 27 = 3 + 11 + 13. Спрашивается, для какого натурального числа трех простых слагаемых не будет уже достаточно? Какое наименьшее число будет суммой не меньше чем четырех, пяти и т. д. простых слагаемых?

Подобные задачи можно ставить применительно не только к простым числам. Математиков давно интересует вопрос, как заданное число записать в виде суммы некоторого числа квадратов. Если это возможно, то сколькими способами осуществляется разложение? Те же вопросы можно поставить для разложения числа на сумму кубов и т. д. Возникает своеобразная область теории чисел, в которой вместо делителей и множителей приходится иметь дело со слагае-

мыми и суммами. Ее называют аддитивной теорией чисел, производя название от латинского слова additio (аддицио), что значит «сложение». Что касается той части теории чисел, которая имеет дело с множителями и делителями (учение о делимости и т. д.), то она носит название мультипликативной теории чисел (от латинского multiplicatio — мультипликацио, — что значит «умножение»).

Вернемся к простым числам, именно к задаче о представлении любого числа в виде суммы некоторого количества простых. Этой задачей более двухсот лет тому назад занялся член Петербургской Академии наук Хр. Гольдбах. Он перепробовал очень много чисел, пытаясь разложить их на сумму простых, и пришел к убеждению, что трех слагаемых всегда достаточно. Не сумев доказать это предложение, не найдя даже путей к доказательству, он написал о нем своему другу Эйлеру, с которым уже без малого 15 лет переписывался и который был тогда в зените славы. В письме от 7 июня 1742 г. Гольдбах сообщил Эйлеру, что рискует высказать следующее предположение: «любое число, большее пяти, представляет собой сумму трех простых». Эйлер ответил, что считает безусловно верной теоремой утверждение, что каждое четное число есть сумма двух простых. Отсюда, как простое следствие, получается утверждение Гольдбаха (почему?). Впрочем, и Эйлер доказательства не дал.

Итак, поставлена следующая задача (ее называют «проблемой Гольдбаха»): требуется доказать или опровергнуть предложение: «всякое число, большее единицы, является суммой не более трех простых чисел». Ни современники Гольдбаха и Эйлера, ни даже математики прошлого — XIX — столетия почти ничего не смогли сделать для решения этой задачи. Правда, Г. Кантор, один из оригинальнейших математиков прошлого века, терпеливо перепробовал все четные числа от 2 до 1000, а Обри — от 1000 до 2000; они убедились, что в этих пределах любое четное число является суммой двух простых. В 1911 г. Е. Меле показал, что подавляющее число четных чисел от 4 до 9 000 000 являются суммами двух простых; исключений может быть не больше четырнадцати (т. е. для 4 499 986 четных чисел утверждение Гольдбаха наверняка справедливо). Наконец, на рубеже XX века появляется ряд работ, пытающихся наметить пути решения этой проблемы или связать ее с другими задачами математики. Но для строгого ее доказательства ничего сделать не

удалось, и в 1912 г. крупнейший знаток теории чисел Э. Ландау высказал на международном конгрессе математиков предположение, что эта задача средствами современной математики вообще неразрешима!..

В 1923 г. двум английским математикам — Гарди и Литтлвуду, о которых мы уже говорили, — удалось добиться некоторого сдвига в попытках найти решение гольдбаховской задачи. Им удалось связать проблему Гольдбаха с одной из труднейших и интереснейших задач специальной главы высшей математики, называемой теорией аналитических функций. Эта задача тоже до конца не решена, но установленная связь между двумя, казалось бы, разнородными ветвями науки оказалась плодотворной и привела к ряду открытий.

Решительный перелом наступил в 1930 году. Советскому математику Льву Генриховичу Шнирельману (1905—1938 гг.), талантливому ученому, удалось так видоизменить задачу, что с помощью им же придуманных путей он сумел ее решить. Именно, видя бесплодность попыток доказать утверждение Гольдбаха в его первоначальном виде, Шнирельман поставил родственную задачу, на вид более сложную, но по существу значительно более простую. Он, как говорят математики, «ослабил» требования задачи Гольдбаха. Гольдбах требует, чтобы каждое натуральное число являлось суммой не более трех простых. Можно потребовать, чтобы каждое натуральное число было суммою не более четырех, пяти, ..., ста простых. Эти требования, очевидно, слабее гольдбаховских: число, разложимое в сумму ста, может не разлагаться в сумму трех простых.

Наконец, можно, что и сделал Шнирельман, поставить вопрос так: существует ли какое-то вполне определенное, но нам неизвестное целое число (обозначим его буквою С), такое, что любое натуральное число можно представить в виде суммы не более чем С простых слагаемых?

Иными словами, каково бы ни было натуральное число n, всегда можно написать

где ри ръ рп — простые числа, а п наверное меньше (или в крайнем случае равно) С. Если удастся доказать, что С=3, то утверждение Гольдбаха будет доказано. Эту «ослабленную» георему Гольдбаха Шнирельману удалось доказать полностью. Само, пока неизвестное, число С с тех пор

Л. Г. ШНИРЕЛЬМАН

И. M. ВИНОГРАДОВ

называют «числом Шнирельмана» или «константой Шнирельмана» (слово constanta — константа — значит по-латыни «постоянная»). Значит, утверждение Гольдбаха можно сформулировать и так: «константа Шнирельмана равна трем». Но этого мало. Самый точный анализ метода Шнирельмана, сделанный разными математиками (Романов, Ландау, Хейльборн, Риччи), позволил получить оценку константы Шнирельмана; будучи очень большой, она постепенно была уменьшена до 67.

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

835 042 000 000 000 000 000 000 000

или нашего знакомца 9э9, для записи которого нужно 30 томов, тоже можно утверждать, что 67 простых слагаемых достаточно

для их представления. Даже скьюзовский гигант 10,оЮ34 можно на основании доказательства Шнирельмана представить в виде суммы не более 67 простых слагаемых (некоторые из этих слагаемых сами неизмеримо велики: гораздо больше числа 9е9). Значит, результат Шнирельмана является огромным достижением; а главное — проложены новые пути, найдены новые способы подхода к решению старой задачи. Значит, можно ждать и новых результатов. Так оно и получилось.

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

Результат, полученный И. М. Виноградовым, можно сформулировать так: для всех достаточно больших нечетных чисел проблема Гольдбаха решена полностью; или так: константа Шнирельмана для достаточно больших нечетных чисел не превосходит трех.

Почему же решение И. М. Виноградова нельзя считать полным, окончательным решением проблемы Гольдбаха; откуда взялось то злополучное «почти», о котором упоминалось выше? Дело в том, что Эйлер и Гольдбах утверждали, — и это для сравнительно небольших чисел подтвердилось на опыте, — что любое четное число является суммой двух простых. Отсюда уже, как следствие, вытекало, что любое нечетное есть сумма не более чем трех простых. Виноградов же

доказал именно последнее утверждение о нечетных числах; отсюда непосредственно следует, что для любого четного достаточно четырех простых слагаемых; но достаточно ли двух, — этот вопрос остается открытым. Кроме того, по Виноградову, утверждение Гольдбаха справедливо для всех достаточно больших нечетных чисел, иными словами, начиная с некоторого большого числа, которое некоторое время оставалось неизвестным.

В 1939 г. оно было вычислено молодым советским математиком К. Г. Бороздкиным. Это большое число может быть записано так:

где число е есть основание натуральных логарифмов: £=2,7182. Остается значительно снизить найденное К. Г. Бороздкиным число и тогда непосредственно проверить все меньшие числа, — работа, которой занимались Кантор и Обри в пределах первых двух тысяч.

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

ПРИЛОЖЕНИЕ

ТАБЛИЦА ПРОСТЫХ ЧИСЕЛ, НЕ ПРЕВОСХОДЯЩИХ 6000

ОГЛАВЛЕНИЕ

От издательства............................. 2

Из предисловия автора к первому изданию........... 3

Введение.................................. 5

Глава I. Наша система счисления................ 7

Глава II. Как считали наши предки?............... 17

Глава III. Для чего и как Архимед считал песок? ...... 28

Глава IV. Не десятками, а пятками или дюжинами...... 35

Глава V. Арифметика, в которой не нужно считать..... 42

Глава VI. Общая мера........................ 51

Глава VII. Уравнения, которыми занимается арифметика... 65

Глава VIII. Арифметика, в которой «трижды три — четыре» . 89

Глава IX. Разделится или нет?................... 106

Глава X. Еще о делимости; «большая» теорема, которую зовут «малой»........................... 116

Глава XI. Эратосфеново решето .................. 126

Глава XII. Часто или редко?..................... 139

Глава XIII. Проблема Гольдбаха................... 154

Приложение. Таблица простых чисел, не превосходящих 6000........................... 163

2 p. 45 к, С 1/1 1961 г. цена 25 к.