Светлой памяти АНДРЕЯ АНДРЕЕВИЧА МАРКОВА, создателя теории алгорифмов

ПРЕДИСЛОВИЕ, которое автор советует прочесть особенно внимательно

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

♦ ♦ ♦

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

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

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

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

Читателю можно порекомендовать следующий план изучения книжки.

При первом чтении можно ограничиться лишь основным текстом §§ 1—4 и не решать задач (за исключением задач №№ 31, 34, 36, 45, 47,49, 50). Это 4

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

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

При втором же чтении следует изучить § 5, а также решать задачи основного текста.

Наконец, при третьем чтении изучается мелкий шрифт и относящиеся к нему задачи.

Читателю, желающему углубить свои познания в области теории чисел, следует обратиться к классическому курсу акад. И. М. Виноградова «Основы теории чисел» («Наука», 1972).

Изучение абстрактной теории отношений на множестве и дальнейших связанных с этим вопросов можно рекомендовать по книге А. Г. Куроша «Лекции по общей алгебре» («Наука», 1973) или Г. Биркгофа «Теория структур» (ИЛ, 1951).

Наконец, более подробное и систематическое разъяснение понятия алгорифма содержится в брошюре Б. А. Трахтенброта «Алгоритмы и машинное решение задач» (Физматгиз, 1960), а строгое изложение теории алгорифмов можно найти в основополагающей монографии А. А. Маркова «Теория алгорифмов» (Труды матем. ин-та АН СССР им. Стеклова, т. 42, 1954).

Второе издание отличается от первого лишь отдельными редакционными улучшениями. За некоторые из них автор благодарен проф. Греллю (ГДР).

/У. Н. Воробьев

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

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

Вырица 1979 г.

Н. Н. Воробьев

• 1. ДЕЛИМОСТЬ ЧИСЕЛ

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

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

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

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

Как обычно целые неотрицательные числа: О, Ь 2, . будут называться натуральными. Говоря о всех натуральных числах, мы будем пользоваться термином множество всех натуральных чисел.

Определение. Число а делится на число b (или, что то же самое, число Ь делит число а), если существует такое число с, что а = Ьс.

Этот факт называется делимостью числа а на число b и обозначается как а • Ь.

Подчеркнем, что запись а • b означает не какое-то действие, которое надлежит произвести над числами а и Ь, а некоторое утверждение, касающееся

этих чисел. В зависимости от того, каковы числа а и Ь, утверждение а • b может быть верным или неверным. Так, например, 4-2 верно, а 4 -3 — нет.

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

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

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

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

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

Понятие признака делимости будет уточнено в следующем параграфе.

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

Пусть

а = Ьс, (1.1)

и вместе с тем

а — Ьс'.

Из этих равенств мы получаем be = bc'_t

или

Ь(с-с') = Ъ.

Если при этом b =/= 0, то с — с' = 0, т. е. с = с'. Если же b = 0, то, очевидно, и а = 0, а равенство (1.1) выполняется при любом с.

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

Говоря о делении, мы всегда будем предполагать делитель отличным от нуля.

Установим несколько простейших свойств делимости.

Теорема 1. а • а.

Это свойство делимости называется ее рефлексивностью (или возвратностью).

Теорема 2. Если а\Ь и Ь\ с, то с.

Это свойство делимости называется ее транзитивностью (или переходностью).

Теорема 3. Если a\b и b-а, то либо а = Ь, либо а = —b (антисимметричность делимости).

Теорема 4. Если а-b и | b | > | а |, то а = 0.

Следствие. Если а-b и а =/= 0, то |а|^±|6|«

Теорема 5. Для того чтобы а • Ь, необходимо и достаточно, чтобы |а|•|6|.

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

Теорема 6. Если а\\Ь, й2 • Ь, .» а_п: Ь, то

(ai+a₂+ Л-а_п)\Ь.

Следствие. Если сумма двух чисел и одно из слагаемых делится на некоторое число Ь, то другое слагаемое также делится на Ь.

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

Подробнее в этом разобраться нам поможет следующий пример.

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

Определение. Четное число а четно делится на четное число Ъ, если существует такое четное число с, что а = Ьс.

Очевидно, для четной делимости теорема 1 неверна, так как, например, не существует такого четного числа с, для которого а = ас.

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

Задачи. Доказать следующие утверждениям

1.  о:-а.

2.  а; 1.

3.  Если 1 • a_t то а = 1.

4.  Каково бы ни было а =/= 0, существует такое отличное от а число Ь, что b • а.

5.  Каково бы ни было число а, существует такое число Ь, что из b • с и с • а следует либо с = 6, либо с = а,

6.  Доказать теоремы, аналогичные теоремам 2, 3, 4 и 5 для четной делимости.

7.  Построить такую теорию делимости, в которой теоремы 1, 3 и 4 были бы верными, а теоремы 2 и 6 — нет.

3.  Уже при самом беглом знакомстве с конкретными фактами делимости бросается в глаза следующее обстоятельство: возможности делимости чисел практически не связаны с их величиной. С одной стороны, существуют маленькие числа, которые делятся на сравнительно большое количество чисел. Например, 12 делится на 1, 2, 3, 4, 6 и 12; число 60 имеет 12 делителей. Таким богатым делителями числам можно противопоставить весьма большие числа, которые имеют минимальное число делителей — 2 (согласно теореме 1 и задаче 2, каждое отличное от единицы число делится хотя бы на два различных числа).Хотя в действительности и известны некоторые закономерности, связывающие свойства делимости чисел с их величиной, но эти закономерности носят столь сложный и запутанный характер, что мы не будем их здесь касаться.

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

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

Ь, которое означает, что разность а — b неотрицательна (т. е. должно существовать такое натуральное число с, что а = b 4- с). Но ведь и явление делимости состоит в том, что некоторые пары чисел а и b подчиняются некоторому, вполне определенному условию и

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

В частности, подобно отношению делимости, отношение «больше или равно» между двумя натуральными числами является некоторым высказыванием об этих числах и может быть верным (например, 5^3) или неверным (например, 3^5).

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

5. Отношение обладает следующими легко проверяемыми свойствами:

1° а а (рефлексивность).

2° Если а b и b а, то а = b (антисимметричность).

3° Если а  b и Ъ с, то а с (транзитивность).

4° Во всякой последовательности натуральных чисел ^2 а₃ . а_п ., все члены которой отличны друг от друга, найдется последнее число. Это свойство отношения иногда называется свойством полной упорядоченности множества натуральных чисел.

Свойство полной упорядоченности довольно сложно по формулировке и выглядит несколько искусственно. Однако оно вскрывает чрезвычайно важные черты в строении множества натуральных чисел, упорядоченных отношением Из него выводятся многие другие свойства этого отношения. Кроме того, мы увидим, что именно на нем основаны столь употребительные в разных вопросах математики рассуждения «по индукции».

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

В самом деле, если бы такого числа не было, то мы могли бы по каждому а_я находить такое a_n+i, что а_я а_я+1 и Оп =£ Ал+1. Начав с произвольного at, мы получили бы последовательность

в| gji fl2 <Ъ £= • • • &п != flfl 4-1 • • •»

которая никогда нс кончается. Но существование такой последо- ватсльности противоречит свойству полной упорядоченности множества натуральных чисел.

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

5° Каково бы ни было число а, существует отличное от а число Ь, для которого b а.

Это свойство множества натуральных чисел называется его неограниченностью в смысле отношения

6° Каково бы ни было число а, не являющееся минимальным, существует такое Ь, что а Ь, а Ь, и для любого числа с из а с Ь следует либо с = а, либо с = Ь. Это формальное утверждение в переводе на содержательный язык означает, что каждое натуральное число, кроме 0, имеет непосредственно предшествующее натуральное число. (Иначе это можно сформулировать так: среди всех чисел, меньших данного, есть наибольшее.)

7° Либо а Ь, либо b а. Это свойство отношения называется его дихотомичностью. В математике термин дихотомия* ность обычно выражает обязательную реализацию одной из двух возможностей. Само это слово греческого происхождения и означает разделение на две части.

Подчеркнем, что 1°—7° являются свойствами самого отношения на множестве всех натуральных чисел, а не свойствами тех или иных чисел, связываемых этим отношением. Поэтому может оказаться, что для какого-нибудь другого отношения, связывающего числа в пары, но не по величине, а каким- либо иным способом, некоторые из утверждений Г—7° могут оказаться и неверными.

Задача 8. Опираясь только на свойства 1°—7° отношения и не пользуясь никакими свойствами самих чисел и действий над ними:

а)  Доказать единственность минимального числа;

б)  Доказать единственность непосредственно предшествующего числа;

в)  Сформулировать определение числа, непосредственно следующего за данным числом а (т. е. числа а+ 1), и доказать его существование и единственность.

Задача 9. Проверить, какие из утверждений 1°—7° остаются в силе для отношения «больше» (>•).

6.  Справедливость свойств отношения (как впрочем, и любого другого отношения) может быть установлена двояко. Во-первых, мы можем воспользоваться свойствами тех или иных чисел или известными особенностями строения множества всех натуральных чисел. Именно так проверялись нами свойства Г—7°. Во-вторых, мы можем, уже убедившись в справедливости свойств 1° — 7 , отвлечься от того, что отношение связывает числа в пары и выводить дальнейшие свойства этого отношения только из его свойств 1°—7°. Так были нами доказаны существование минимального числа и утверждения задачи 8.

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

ими являются утверждения 1®—7^е), которые отражают основные свойства изучаемых предметов и не подлежат доказательству, а из них чисто логическим путем, без повторного обращения к свойствам исследуемых предметов, выводятся все остальные утверждения, которые называются теоремами.

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

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

Изложенный до сих пор материал позволяет проиллюстрировать понятие отношения между отношениями примером.

Пусть а, р, . — некоторый набор отношений, связывающих натуральные числа. Это значит, что для любой пары чисел а и b и любого отношения у из нашего набора мы знаем, связывается ли пара а, b отношением у или нет. Если а и b отношением у связаны, будем писать ayb.

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

Так, например, обозначая отношение четной делимости через •, мы можем написать • => •. Далее, очевидно, что 2г >.

ч ч

Вместе с тем существуют естественные отношения на множестве натуральных чисел, относительно которых нельзя утверждать, что одно сильнее или слабее другого. Так, например, если для двух натуральных чисел а и b полагать а >■ Ь, если последняя цифра в десятичной записи числа а больше последней цифры числа 6, то ни >■ Z5 2*, ни 2г )>.

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

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