Воробьев Н. Н. Признаки делимости. — Изд. 3-е, испр. и доп. — М. : Наука, 1980. — 96 с. — (Популярные лекции по математике ; вып. 39). — Список лит.: с. 5.

Популярные лекции

ПО МАТЕМАТИКЕ

Н. Н. ВОРОБЬЕВ

ПРИЗНАКИ ДЕЛИМОСТИ

ПОПУЛЯРНЫЕ ЛЕКЦИИ ПО МАТЕМАТИКЕ

ВЫПУСК 39

H. Н. ВОРОБЬЕВ

ПРИЗНАКИ ДЕЛИМОСТИ

ИЗДАНИЕ ТРЕТЬЕ, ИСПРАВЛЕННОЕ И ДОПОЛНЕННОЕ

МОСКВА «НАУКА»

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

22.131 В 75

УДК 511

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

В 75 Признаки делимости. — 3-е изд. — М.: Наука, 1980, 96 с.— (Популярные лекции по математике.)

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

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

ББК 22.131 511

© Издательство «Наука». Главная редакция физико-математической литературы, 1980, с изменениями

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

ПРЕДИСЛОВИЕ,

которое автор советует прочесть особенно внимательно

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

* * *

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

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

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

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

* * *

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вырица 1979 г.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть

a —be, (1.1)

и вместе с тем

а = be'.

Из этих равенств мы получаем

be = be',

или

b(c-c') = 0.

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

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

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

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

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

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

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

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

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

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

Следствие. Если a] b и а Ф 0, то \a\~§i\b\<

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

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

Теорема 6. Если ai • ft, а2 : ft, ап'.Ь, то

(а{ + а2+ ... +ап)\Ь.

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

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

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

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

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

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

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

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

1. о;-а.

2. а\ 1,

3. Если 1 - а, то а = 1.

4. Каково бы ни было а Ф О, существует такое отличное от а число ft, что b • а.

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

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 неотрицательна (т. е. должно существовать такое натуральное число с, что а = 6 +с). Но ведь и явление делимости состоит в том, что некоторые пары чисел а я b подчиняются некоторому, вполне определенному условию

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

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

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

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

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

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

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

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

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

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

В самом деле, если бы такого числа не было, то мы могли бы по каждому ап находить такое a„+i, что ап ^ an+i и йп Ф an+i. Начав с произвольного ai, мы получили бы последовательность

о. û2 ^ аз ^ ... ^ ап Ш — « « •?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Будем говорить, что отношение а сильнее отношения ß, и записывать это как a zd ß, если любая пара чисел, связанная отношением ß, оказывается также связанной и отношением а, т. е. если из aßb следует aab.

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

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

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

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

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

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

Л(0), Л(1), А(п), ...

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

а) справедливо утверждение Л(0) («основание индукции»)*);

б) из справедливости утверждений А (п) следует справедливость утверждения Л(м+1) («индуктивный переход»).

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

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

Действительно, предположим, что условия а) и б) принципа индукции для утверждений А (п) выполнены, но заключение этого принципа не имеет места. Последнее означает, что должны существовать такие числа m, для которых утверждение А(т) неверно. Пусть mt — одно из таких чисел. Если для всех п < т4 утверждение А (п) верно, то mi — наименьшее из чисел, для которых А(п) не имеет места. Если же А(п) верно не для всех п < mi, то должно существовать такое т2 < mi, что A (nit) неверно.

В итоге мы приходим к некоторой последовательности различных чисел

mi ^ m2 ^ ... ^ тг ^, ..., (1.2)

для каждого из которых А(т) не имеет места. По свойству полной упорядоченности 4° в последовательности (1.2) должен быть последний член тг. Очевидно, число тг является наименьшим из всех чисел, для которых А(п) неверно.

Поскольку А (0) верно по условию, тг ф 0, так что существует число тг, непосредственно предшествующее тг (в действительности этим числом является тг — 1 ). Так как тг < тГу утверждение A (m*) должно быть верным. Но тогда по условию б) принципа математической индукции должно быть верным также и утверждение Л(тг+1), т.е. Л(тг), и мы получили противоречие. Это противоречие показывает, что нет чисел m, для которых А (т) не имело бы места (т. е. не было бы справедливо).

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

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

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

Методу математической индукции в его различных вариантах посвящены брошюры И. С. Соминского «Метод математической индукции» («Наука», 1974) и Л. И. Головиной и И. М. Яглома «Индукция в геометрии» («Наука», 1956), содержащие большое количество примеров применения этого метода. На протяжении данной книги этот метод также будет часто применяться.

Задача 10. Пусть пары объектов произвольной природы (ими могут быть числа, точки, функции, теоремы и т. д.) связываются Некоторым отношением обладающим свойствами, аналогичными свойствам Г—7°. Доказать, что тогда эти объекты (элементы) можно перенумеровать (т. е. выписать их в некотором порядке) At, Л 2, Лз, ... так, что J— Лу тогда и только тогда, когда i /.

Сказанное, по существу, означает, что отношение, обладающее свойствами 1°—7°, упорядочивает множество в линейную цепочку элементов:

8. Вернемся, однако, к отношению делимости. В случае положительных чисел теоремы 1, 2, 3 и задачи 3, 4 и 5 показывают, что в утверждениях Г—6° мы можем заменить отношение ^ отношением •. Что же касается утверждения 7°, то в применении к делимости оно гласит: «из двух чисел хотя бы одно делится на другое».

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

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

Читателю предоставляется самостоятельно переформулировать и проверить утверждения 1° — 7° для этого случая.

9. Определение. Любое отношение J—, подчиненное условиям:

1° рефлексивности {а а):

2° антисимметричности (из а £— b и b £- а следует а = Ь)\

3° транзитивности (из а £— b и b £— с следует а £— с),

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

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

10. Условия 1° — 3°, соблюдение которых делает отношение $— отношением частичного упорядочения, являются довольно свободными. Поэтому частично упорядоченными и притом упорядоченными весьма различными способами могут быть самые разнообразные объекты. В связи с этим о произвольном частично упорядочивающем отношении мало что можно сказать сверх того,

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

Дополним, однако, условия 1° — 3° следующими: 4° полная упорядоченность; 5° неограниченность;

6° каждый объект, отличный от минимального, имеет непосредственно предшествующий;

8° каждый объект имеет не более конечного числа предшествующих;

9° каковы бы ни были а и Ь^-а (Ь Ф а), существует такое с, непосредственно предшествующее fr, что с£- а.

Оказывается, что на основе частичной упорядоченности множества натуральных чисел отношением, которое удовлетворяет условиям Г — 6°, 8° и 9°, можно построить некоторое видоизменение метода индукции, состоящее в следующем.

Пусть снова А (п) — утверждение, касающееся произвольного числа п. Предположим, что

а) Справедливо утверждение А(а), где а есть минимальное число в смысле упорядочения £—;

б) Если п — некоторое число, и справедливость всех утверждений вида А(т) для всех таких m, что я £- m и п Ф m, установлена, то верно и утверждение А(п).

Новая форма принципа индукции утверждает, что при соблюдении условий а) и б) утверждение А (п) справедливо при любом п.

Задача 11. Вывести «новую форму» принципа индукции из ее «старой формы».

Так как отношение делимости условиям 1° — 6°, 8° и 9° удовлетворяет (сформулируйте и проверьте для отношения делимости условия 8 и 9°), этот принцип индукции к отношению делимости применим.

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

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

Определение. Разделить число а на число b (b > 0) с остатком — значит представить число а в виде

а = Щ + г,

где 0 г <С Ь.

Число q при этом называется неполным частным, а число г — остатком от деления а на 6. Очевидно, г = О тогда и только тогда, когда а \ 6. В этом случае q равно частному от деления а на 6.

Покажем, что деление с остатком всегда выполнимо, а неполное частное и остаток вполне определяются делимым и делителем, т. е. единственны.

Пусть сначала а 5^ 0. Будем выписывать одно за другим числа

а, а — Ь, а —- 26, ... (1.3)

до тех пор, пока не появится отрицательное число (очевидно, рано или поздно такое число должно появиться*)). Пусть последним из неотрицательных членов последовательности (1.3), т. е. самым маленьким из них, окажется число а — bq. Обозначая его через г, мы имеем

a = bq + r. (1.4)

Очевидно, г < b (иначе бы число г — 6, т. е. а—• — (q+ 1)6, было бы неотрицательным, а этого не может быть, так как г — наименьшее из неотрицательных чисел среди (1.3)). Таким образом, (1.4) и является искомым представлением числа а.

Пусть теперь а < 0. Рассуждая аналогично предыдущему, будем выписывать последовательность чисел

а, а + b, а + 26, ...

до тех пор, пока не появится первое неотрицательное число г (легко проверить, что г<6). Пусть

г = а + bq'.

Тогда, обозначая —q' через q, мы получаем а = bq + г,

а это и требовалось.

Возможность деления с остатком доказана во всех случаях.

Докажем теперь однозначность этого деления, т. е., что из

а = 6<7 + г (1.5)

*) Точнее говоря, это следует из полной упорядоченности множества натуральных чисел отношением

и

a = bq{+ru (1.6)

следует

q = q{ и г = гь

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

Сопоставляя отношения (1.5) и (1.6), мы видим,

что

bq + r = bq{ + ru

откуда

r — r{ = b(q{ — q),

т. е. г — г\ делится на Ь. Но |г — ri|<6, а по теореме 4 это возможно лишь при

г-Г! = 0,

т. е. при г = гь Но тогда

и ввиду неравенства нулю числа b

<7! —<7 = 0,

т. е. q\ = q. Однозначность деления с остатком доказана. Таким образом, нами доказана следующая теорема.

Теорема 7 (о делении с остатком). Для произвольных чисел а и b (b > 0) существуют и единственны такие числа г и q, что

a = bq + r,

причем 0 ^ г < 6.

Заметим, что в частности при 6=1 должно быть г = 0, откуда а = q. Это соответствует утверждению задачи 2. Ясно вместе с тем, что если b > 1, то а > q.

Задача 12. Сформулировать и доказать теорему о делении с остатком для четной делимости.

12. Определение. Число р, не равное единице, называется простым, если оно делится только на себя и на единицу.

Простыми числами являются, например, числа 2, 3, 5, 7, 11, 13 и т. д.

Число, отличное от единицы и не являющееся простым, называется составным.

Теорема 8. Простых чисел бесконечно много.

Всякое число, делящее одновременно числа а и Ь, называется общим делителем этих чисел. Наибольший из общих делителей чисел а и b называется их наибольшим общим делителем и обозначается обычно через (а,Ь).

Если наибольший общий делитель чисел а и b равен единице, то эти числа называются взаимно простыми.

Иначе говоря, числа а и b называются взаимно простыми, если они одновременно не делятся ни на какое число кроме единицы.

Теорема 9. Если аир — натуральные числа, причем число р простое, то либо а \ р, либо числа а и р взаимно просты.

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

Теорема 10. Если M — общее кратное а и b, а m — их наименьшее общее кратное, то M • m.

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

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

Теорема 12. Если ab ; с, причем числа b и с взаимно простые, то а • с.

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

Следствие. Если р — простое и 0 < k < р, то число

делится на р.

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

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

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

а = р«у2* ...ра/, (1.7)

где р\, р2, Рг — различные простые числа, а «ь 0с2, с&г — некоторые целые положительные числа. Произведение, стоящее в правой части формулы (1.7), называется каноническим разложением числа а.

Теорема 15. Для того чтобы числа а и b были взаимно простыми, необходимо и достаточно, чтобы ни один из простых сомножителей, входящих в каноническое разложение числа а, не входил в каноническое разложение числа Ь.

Теорема 16. Пусть (1.7) — каноническое разложение числа а. Тогда для делимости b \ а необходимо и достаточно, чтобы

ь\р\\ ь\р\\ Ыра/.

Из теорем 15 и 16 вытекает, что делимость на произведение нескольких взаимно простых чисел равносильна одновременной делимости на каждое из них.

Задача 13. Оценить сверху наименьший простой делитель составного числа а.

Задача 20. Верны ли для четной делимости аналоги теорем 11—14?

а = ра1^...ра/

— каноническое разложение числа а. Тогда для делимости а ; b необходимо и достаточно, чтобы каноническое разложение b имело вид

где

О ^ ß2 ^ а2, О ^ ßr ^ аг.

Весьма важным для целей данной книги оказывается следующий факт.

Теорема 18. Пусть m и t — натуральные числа. Тогда m можно представить в виде такого произведения m = m\m2, что (mi, t) = \ и найдется такое k, для которого tk • m2.

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

Задача 14. Указать способ построения по каноническим разложениям двух чисел канонических разложений наименьшего общего кратного этих чисел и их наибольшего общего делителя.

Задача 15. Обозначим через т(а) число различных делителей числа а (включая единицу и само число а). Показать, что для числа а с каноническим разложением Р^1Р%2 • • • Р^г

т(а) = (а1 + 1)(а2+1)...(аг + 1).

Задача 16. Найти а, если известно, что а|3, а-4 их (а) = 14. Задача 17. Каноническое разложение числа а имеет вид

pfp%* и т(а2)= 81. Чему равно т(а3)?

Задача 18. Чему равно а, если а = 2т(а)?

Задача 19. Доказать, что каково бы ни было К > 0, найдется такое натуральное число А», что для всякого числа а, имеющего k простых сомножителей, будет

§ 2. ДЕЛИМОСТЬ СУММ И ПРОИЗВЕДЕНИЙ

1. Во многих случаях при делении с остатком интересно найти именно остаток от деления числа а на число а величина неполного частного от деления не играет роли.

Пусть, например, мы хотим узнать, какой день недели будет 1 января 2000 г. (разумеется, если до того срока сохранится действующий в настоящее время календарь). Легко справиться по календарю, что 1 января 1980 г. — вторник. Двадцать лет, разделяющие эти даты, состоят из 20-365 + 4 (последнее слагаемое — число високосных лет за это время), т. е. из 7305 дней. Эти дни составляют 1043 целых недель и еще 4 дня. По прошествии 1043 целых недель снова наступит вторник, так что еще через 4 дня, 1 января 2000 г., будет суббота. Очевидно, для решения поставленной нами сейчас перед собой задачи совершенно неважно знать, сколько именно целых недель прошло за 20 лет, а интересно только число дней, прошедших сверх этих недель.

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

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

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

Продемонстрируем один из таких приемов на только что решавшейся нами задаче о дате 1 января 2000 г. Мы можем рассуждать следующим образом. Каждый простой (невисокосный) год состоит из 365 дней, что составляет 52 полные недели и еще один день. Високосный же год составляет столько же недель и два дня. Значит, весь срок от 1 января 1980 г. до 1 января 2000 г. состоит из некоторого (совершенно неважно, какого) числа полных недель плюс число дней, равное числу содержащихся в этом сроке лет, причем каждый високосный год считается за два. Это число дней равно 20 + 5 = 25. Исключив из него 3 полных недели, получаем 4 дня, которые и следует отсчитывать от нашего вторника. Оказывается, такая «замена года днем» есть проявление весьма общего приема, изучением которого мы сейчас и займемся.

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

A = antn+an^tn-{+ ... +axt + a09

где

O^ûf, </ при î = 0, 1, п (2.1)

Числа а0, вь • • • > называются t-ичными цифрами числа А*).

При /=10 мы получаем десятичную систему счисления. Запись числа в этой системе настолько привычна для нас, что говоря о числе, мы обычно только в этой форме его себе и представляем. В дей-

*) Элементарное, но вместе с тем глубокое изложение вопросов, связанных с системами счисления, содержится в брошюре С. В. Фомина «Системы счисления» («Наука», 1908).

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

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

Ясно, что из (2.1) следует

A = (antn~l + an_ltn-2+ ... +а,)/ + Оо,

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

{anf-2 + an_xtn-z + ... +a2)t + al.

Остатком оказывается предпоследняя /-ичная цифра числа А. Продолжая этот процесс повторного деления с остатком на t, мы будем последовательно получать все <-ичные цифры числа Л, считая справа налево (т. е., от низших разрядов к высшим). Очевидно (а точнее — в силу полной упорядоченности множества натуральных чисел по величине), этот процесс последовательного деления с остатком должен рано или поздно оборваться. В результате мы получим все /-ичные цифры числа Л, т. е. его запись в /-ичной системе счисления.

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

Поэтому 10 000 в шестеричной системе счисления записывается как 114 144.

3. Определение. Назовем числа а и b равноостаточными при делении на m, если остатки от деления а и b на m равны.

Установим несколько свойств равноостаточных чисел.

Теорема 19. Для того чтобы числа а и b были равноостаточными при делении на m, необходимо и достаточно, чтобы (а — b) \т.

Следствие. Если числа а и b равноостаточны при делении на m, и m \ d, то а и b равноостаточны при делении на d.

Теорема 20. Если при делении на m числа au «2, ..., ип соответственно равноостаточны числам bu b2, bn, то равноостаточными будут суммы ai + H-Û2+ ... + ап и 61 + ô2+ +bn, а также произведения а\а2 ... ап и b\b<i ... bn-

Следствие. Если при делении на m числа а и b равноостаточны, то такими же являются и степени ап и Ьп при любом натуральном п.

Теорема 20 и ее следствие дают уже довольно богатые возможности для нахождения остатков от деления.

Приведем несколько примеров.

Пример 1. Найти остаток от деления на 3 числа

Л= 1316- 225 . 515.

Очевидно, при делении на 3 число 13 равноостаточно с 1, 2 равноостаточно с —1, а 5 тоже с —1. Значит, на основании доказанного число А при делении на 3 равноостаточно с числом

I16 — (—1)25(—1)15= 1 — 1=0,

т. е. искомый остаток равен нулю, а А делится на 3.

Пример 2. Найти остаток от деления того же числа А на 37.

Представим для этого А в следующем виде:

Л = (132)8~(25)5 -(53)5.

Так как 132 = 169 при делении на 37 равноостаточно с —16, 25 = 32 равноостаточно с —5, а 53 = 125— с +14, то все число А равноостаточно с

(-16)8-(-5)5(+Н)5

или, что то же самое, с

(162)4 + 705.

Но 162, т. е. 256, равноостаточно с —3, а 70 —с —4. Значит, А равноостаточно с

(_3)4 + (_4)5

или, что то же самое, с

81 — (25)2,

а потому с

81 -(-5)2 = 81 -25 = 56.

Наконец, 56 при делении на 37 равноостаточно с 19, которое неотрицательно и меньше 37 и потому является искомым остатком.

Задача 21. Найти остаток от деления:

а) А =(116+ 1717)21 на 8;

б) А = 14256 на 17.

Задача 22. Доказать, что при любом п:

а) (п3+Пп) ; 6;

б) (4" + 15л— 1) ! 9;

в) ( 103" — 1 ) : 3"+2;

г) При любом а

(a2n+i -J- (а — 1)ге+2) : (а2 — а + 1);

д) При любом k

(Л* _!):(„_ 1);

е) При любом нечетном k

(п*+1);(и+1).

4. Равноостаточные при делении на m числа а и b называются также сравнимыми по модулю т. Это обозначается така

a =s Ь (mod m),

а сама эта формула называется сравнением.

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

Отметим несколько свойств отношения сравнимости по модулю.

1° Рефлексивность: a s= a (mod m). Действительно, а — а = 0 • т.

2° Симметричность: если а э 6 (mod m), то 6 гэ а (mod m).

В самом деле, если (а — Ъ) \ m, то (хотя бы по теореме 5) и (Ь — а) • т.

3° Транзитивность: если а = b(mod т) и b == c(modm), то а == с (mod m).

Для доказательства достаточно заметить, что из (а — Ь) \т и (Ь — с) \ m по теореме 6 следует, что (а — с) \ т.

Если некоторое отношение (обозначим его через ~) обладает свойствами рефлексивности, симметричности и транзитивности, то оно называется отношением эквивалентности (или эквивалентным отношением). Простейшим примером отношения эквивалентности на множестве чисел является отношение равенства.

Задача 23. Эквивалентное отношение ~ на множестве чисел разбивает это множество на такие классы (называемые классами эквивалентности), что любые два числа из одного класса связаны отношением эквивалентности, а никакие два числа из разных классов этим отношением не связаны. (Доказать.)

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

Так как отношение сравнимости по модулю m — отношение эквивалентности, оно также разбивает множество целых чисел на классы. Эти классы называют классами вычетов по модулю т.

4° Число классов вычетов по модулю m равно т.

В самом деле, два числа а и b принадлежат одному классу вычетов по модулю m тогда и только тогда, когда они при делении на m дают один и тот же остаток. Но остаток при делении на m может принимать ровно m значений: 0, 1, 2, ..., m— 1. Следовательно, и число классов равно т.

Отметим одно чрезвычайно интересное обстоятельство, являющееся уточнением следствия теоремы 19.

Для того чтобы каждый класс вычетов по модулю mt содержался в некотором классе вычетов по модулю т2, необходимо и достаточно, чтобы mi | т2.

Действительно, рассмотрим класс вычетов Ki по модулю mi, содержащий число 0. Очевидно, класс /Ci состоит из всех чисел, дающих при делении на mi в остатке 0, т. е. делящихся на В частности, он содержит число mt. Класс вычетов по модулю тг, содержащий Ki, также содержит 0 и потому состоит из всех чисел, делящихся на т2. Так как в него входит число mi, должно быть mi J m2. Этим доказана необходимость, достаточность же очевидна.

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

Продолжим перечисление свойств сравнимости чисел. Из теоремы 20 немедленно следуют:

5° Если а н== b(mod m) и с d(mod m), то

а + с sa b + d (mod m).

Следствие. Если a s b (mod m), то a + r =z b + r (mod m)

для любого целого г.

6° Если а = b(mod m) и с = с?(mod m), то

ас 6 а* (mod m).

Свойства 5° и 6° показывают, что сравнения подобно равенствам можно почленно складывать и перемножать.

Задача 24. Если на множестве целых чисел задано эквивалентное отношение ~, разбивающее это множество на m классов, и такое, что из а ~ b и с ~ d следует а + с ~ b + d, то отношение ~ есть сравнимость по модулю m (т.е. а ~ b тогда и только тогда, когда а = b(modm)).

Задача 25. Сформулировать и доказать правила сокращения сравнений.

Задача 26. Если число р простое и а не делится на р, то никакие два числа из а, 2а, За, (р—1)а не сравнимы друг с другом по модулю р. Поэтому при делении на р чисел а, 2а, За, (р— 1)а мы получим по одному разу все остатки, кроме нуля.

Задача 27 (теорема Вильсона). Для того чтобы число р было простым, необходимо и достаточно, чтобы (р — 1)1 + 1 = = 1 • 2 ... (р — 1 ) + 1 делилось на р.

Задача 28. Сформулировать и доказать для равноостаточности теорему, аналогичную теореме 16.

§ 3. ПРИЗНАКИ РАВНООСТАТОЧНОСТИ И ПРИЗНАКИ ДЕЛИМОСТИ

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

а = Л0, Аи Аъ (3.1)

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

Одним из простейших примеров последовательности (3.1) может служить последовательность (1.3) из п. 11 § 1:

а, а — m, а — 2т, .. •

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

Всякий способ построения последовательности (3.1), обладающей последним членом, назовем признаком равноостаточности при делении на т.

Из только что приведенного примера следует, что одним из признаков равноостаточности при делении на m является процесс последовательного вычитания числа m до получения первого числа, меньшего т.

2. Очевидно, для уверенности в безотказности работы признака равноостаточности при делении на m необходимо, чтобы он удовлетворял следующим трем требованиям:

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

2) Признак равноостаточности должен быть точно определенным, т. е. число а должно вполне определять все члены последовательности (3.1), не оставляя места какой-либо произвольности.

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

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

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

воляет находить остатки от деления варьируемого числа а на некоторое фиксированное т.

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

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

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

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

Свойство определенности признака равноостаточности означает, что уже выписанные числа Л0, Ль ...

Ап последовательности (3.1) должны быть настолько «опознаваемыми», чтобы на их основании можно было написать следующее число последовательности, Л/1+1.

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

чаемое на каждом шаге нашего процесса число Ak с делителем т.

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

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

220 — 3 - 52 • 11 • 31 • 41 и З10 —2 - 3 - 13 - 757, (3.2)

и если различны, то какое из них больше, требует для своего решения известных усилий, хотя в действительности первое из этих чисел есть всего-навсего 1, а второе 3.

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

Например, ими являются записи чисел в тех или иных (позиционных) системах счисления (см. § 2 п. 2). Алгорифм сравнения двух чисел, записанных в одной и той же системе счисления, состоит в следующем:

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

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

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

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

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

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

В случае выполнения действий навыки в обращении с десятичной системой счисления приносят суще-

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

требует известных умственных усилий.

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

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

7. В качестве иллюстративного примера рассмотрим следующее построение. Для каждого натурального числа п составим последовательность а}^, ... чисел (цифр), являющихся

цифрами бесконечного десятичного разложения числа л/п (если число п не является точным квадратом, то эта последовательность, очевидно, оказывается непериодической), и пусть г!п\ *2П\ • • • — номера всех тех цифр, которые равны нулю cr(ft)eO(i s=s 1, 2, ...). Если теперь число равных нулю цифр конечно (пусть последнее из них имеет номер так что > О при / > г^), то положим

а если их число бесконечно, то положим, скажем, f(n)= 0. Каждое из чисел f(n) является натуральным. Однако едва ли можно говорить об алгорифме, который перерабатывал бы число п в запись числа /(«) в десятичной системе счисления.

Разумеется, вся неалгорифмичность этой конструкции состоит в требовании распознавать, будет ли в десятичном разложении «Jn конечное или бесконечное число нулей. Между прочим, в известном смысле (в каком именно — мы не станем здесь выяснять) естественно верить, что f(n)= О для любого натурального п.

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

Пусть а и b — два натуральных числа, причем b > 0. Разделим а на b с остатком: а = bq0 + гь где 0 g Т\ < Ь. Если ri Ф 0, то мы имеем возможность разделить с остатком b на т%\ b = rtfi + г2, причем 0 ^ г2 < гь Продолжая эти последовательные деления с остатком на остаток от предыдущего деления, мы получим дальнейшие равенства: Г\ = г2сз + гз, г2 = г3?4 + г 4 и т. д.

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

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

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

Ь, гь г2, ... (3.3)

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

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

Задача 29. а) Последний отличный от нуля остаток гп в применении алгорифма Евклида к числам а и b есть (а, Ь).

б) Каковы бы ни были натуральные а и Ь, существуют такие целые А и В, что аА + ЬВ = (а, Ь).

Задача 30. Вывести из результата б) задачи 29 теоремы 9, 12, 13 и 14. (Подчеркнем, что наши рассуждения, связанные с алгорифмом Евклида, были основаны только на возможности деления с остатком. Мы не пользовались в них ни теоремами 9—

*) На самом деле число этих делений не может превосходить числа 5 log b. Это следует из рассмотрения чисел Фибоначчи (см., например, книжку автора «Числа Фибоначчи», «Наука», 1978, стр. 82-83),

14, ни какими-либо иными соображениями, опирающимися на основную теорему арифметики.)

9. Применение алгорифмов (их, так сказать, «работа») может оказаться достаточно громоздким. В качестве примера рассмотрим процесс получения по числу п его канонического разложения (иными словами, алгорифм, перерабатывающий натуральное число в его каноническое разложение). Для оттенения алгорифмической сущности этого процесса включим его, как этап, в процесс последовательного нахождения канонических разложений одного за другим всех натуральных чисел. Это дает нам основание вести рассуждения «по индукции» (см. п. 7 § 1). Предположим, что для всех чисел, меньших я, канонические разложения уже выписаны. Из этого списка можно (вполне алгорифмично) усмотреть, какие из чисел, меньших п, являются простыми. Перечислив их все по возрастанию, будем делить п на каждое из них. Если п разделится на некоторое р, то будет п = п\р и п\ < п, а каноническое разложение п\ в нашем перечне по предположенному уже имеется (ввиду результата задачи 13 нам достаточно произвести деления лишь на те р, которые меньше чем л/п ) и каноническое разложение получится из канонического разложения п\ путем увеличения в нем показателя р на единицу.

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

Попробуем найти функцию f(x), подчиненную следующим условиям:

а) Значение f(x) при х ^ m есть натуральное число;

б) Значение f(x) при х<Ст не определено (т. е. не имеет смысла);

(Нет ничего удивительного в том, что та или иная функция теряет смысл при некоторых значениях аргумента. Например, не имеет смысла значение функции -~ ^!__ при jt = 0 или при *=1.)

в) Если X ^ m то f{x) < х\

г) Если х^т, то числа х и f(x) равноостаточны при делении на т.

Такие функции существуют. Примером является функция fo{x):

X — m, если х ^ m,

не определена, если х < т.

Именно эта функция и осуществляет построение последовательности (1.3) в § 1.

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

В самом деле, возьмем произвольное натуральное число а и будем строить последовательность чисел

Аь Аь А2, (3.4)

где

А0 = а и Ak+i = f(Ak) при 6 = 0,1,... (3.5)

Если Akz^m, то значение функции f(Ak) определено, и потому за Ak следует хотя бы один член. Если же Ak < m, то f(Ak) не определена, и Ak является последним членом последовательности (3.4).

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

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

Условие массовости здесь соблюдается потому, что любое число дает начало некоторой последовательности (3.4), обладающей свойством (3.5).

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

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

вают. Поэтому в ней найдется наименьший неотрицательный член. (Номер этого члена, как нетрудно про* верить, не превосходит числа а.) Если бы этот член (обозначим его через а) был больше или хотя бы равен m, то существовало бы значение f(a), по-прежнему неотрицательное, но меньшее а. Значит, член а не был бы последним среди неотрицательных членов последовательности (3.4). Следовательно, последний неотрицательный член (3.4) должен быть меньше, чем т. Но тогда значение /(а) не имеет смысла, и ос оказывается вообще последним членом нашей последовательности. Процесс построения последовательности, таким образом, заканчивается, и последний ее член является остатком от деления а на т.

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

12. Пользуясь изложенным в п. 9 приемом построения признаков равноостаточности, найдем несколько таких признаков. В соответствии со сказанным выше будем считать, что числа, остатки от деления которых требуется найти, записаны в позиционной системе счисления с некоторым основанием t. Признак равноостаточности при делении на некоторое m перерабатывает в остаток от деления на m фактически не само число, а его запись в соответствующей системе счисления. Поэтому признак равноостаточности при делении на данное фиксированное число m будет, вообще говоря, зависеть от основания системы счисления. Вместе с тем буквальная формулировка признака равноостаточности при делении на данное m в /-ичной системе счисления вполне может подходить для признака равноостаточности при делении на другое т' в системе счисления с другим основанием f. Соответствующие примеры будут получаться из содержания теорем 19, 20 и 21.

Во избежание возможных недоразумений условимся в дальнейшем как делитель m, так и основание системы счисления t записывать («называть») в десятичной системе счисления. Так, говоря о признаке равноостаточности при делении на 12 в семеричной системе счисления, мы будем под 12 понимать именно число 3-4, а не число 3-3 (как это было бы, если бы

число 12 рассматривалось как запись в семеричной системе счисления).

В качестве первого примера найдем признак равноостаточности при делении на 5 в десятичной системе счисления.

Пусть А — натуральное число. Представим А в виде 10а + 6 (Ь— последняя цифра числа А) и положим

Ь, если А ^ 10,

b — 5, если 5 ^ А < 10,

не определено, если А < 5.

Читатель сам может проверить, что так определенная функция удовлетворяет условиям а)—г) п. 10.

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

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

Задача 31. Указать и проанализировать аналогичные признаки равноостаточности при делении на 2, 4, 8, 10, 16, 20 и 25 в десятичной системе счисления.

Задача 32. Указать и проанализировать аналогичные признаки равноостаточности при делении:

а) на 9 и 27 в троичной системе счисления;

б) на 8, 9, 16, 18, 24, 36, 48 и 72 в двенадцатеричной системе счисления.

Задача 33. Представим натуральное число А в виде

I0ka + b (0^b< 10*)

и положим

Ь9 если Лй'10\

остатку от деления А на m, если m^S A<\0k9 не определена, если А<т.

Для каких чисел m такой алгорифм при некотором k является признаком равноостаточности?

Теорема 21. Представим произвольное натуральное число А в виде atk + b, где 0 ^ b < tk, и положим

Ь, если А ^ /*,

b — m, если m^S- A <tk,

не определено, если А < т.

Чтобы для данной функции f алгорифм построения последовательности (3.4) по правилу (3.5) был признаком равноостаточности при делении на m, необходимо и достаточно, чтобы было tk \ т.

13. В качестве второго примера рассмотрим признак равноостаточности при делении на 3 в десятичной системе счисления.

Запись натурального числа А в десятичной системе счисления имеет вид

ап\0п + an-ilOn-1 + ... +0,-10 + 00,

где

О ^ at < 10 для i = 0, 1, ..., п.

Положим

во + ci\ + ... + + ап, если А ^ 10, остатку отделения А на 3, если 3 ^ А < 10, не определена, если А < 3.

Задача 34. Проверить, что функция /г(*) удовлетворяет условиям а)—г) и определяет тем самым некоторый признак равноостаточности при делении на 3.

Задача 35. Применить построенный признак равноостаточности при делении на 3:

а) к числам 858 773 и 789 988;

б) к числу, десятичная запись которого состоит из 4444 четверок.

Задача 36. Указать и проанализировать аналогичные признаки равноостаточности при делении на 7, 9, И, 13 и 37 в десятичной системе счисления.

Задача 37. Указать и проанализировать признаки равноостаточности при делении:

а) на 2, 4 и 8 в троичной системе счисления;

б) на 2, 4 и 8 в семеричной системе счисления.

Теорема 22. Представим произвольное натуральное число А в виде

где

и положим

^ + а{+ ... +ап_1 + аПУ если A^tk, A— m, если m ^ А < /*,

не определено, если А < т.

Тогда для того чтобы порождаемый функцией f алгорифм построения последовательности (3.4) по правилу (3.5) был признаком равноостаточности при делении на m, необходимо и достаточно, чтобы было (tk—l)': m.

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

Теорема 23. Пусть А — натуральное число, представленное в виде

где

Положим

а0 — а{ + а2 — ... ± ап, если А ^ tk, остатку от деления А на m, если m ^ А, < tk> не определено, если А<ш.

Тогда для того чтобы порождаемый функцией f алгорифм построения последовательности (3.4) по правилу (3.5) был признаком равноостаточности при делении на m, необходимо и достаточно, чтобы было {Р+ 1) \т.

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

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

Назовем числа а и b равноделимыми при делении на /тг, если либо и а и & делятся на m, либо на m ни а, ни b не делятся.

Задача 40. Каково бы ни было m, любые равноостаточные при делении на m числа являются равноделимыми на т. Показать на примере, что обратное неверно.

Задача 41. Для каких m из равноделимости двух чисел при делении на m следует их равноостаточность при этом делении?

Задача 42. Доказать, что отношение равноделимости при делении на данное число m является эквивалентным отношением и разбивает множество целых чисел на два класса.

Задача 43. Будет ли справедлива для равноделимых чисел теорема 20? Ее следствие?

15. Пусть нужно выяснить делимость на m числа А. Будем строить последовательность убывающих натуральных чисел

А = Ло, Ль Л2, ..., (3.6)

равноделимых с А при делении на m с остатком. Способ построения последовательности (3.6) выберем такой, чтобы за всяким членом этой последовательности, большим или равным m по абсолютной величине, следовал еще хотя бы один член. Если при этом последний член (3.6) будет равен нулю, то А делится на m, а если не равен нулю, то не делится.

Всякий способ построения последовательности (3.6) назовем признаком делимости на т.

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

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

Нетрудно проверить (это предоставляется читателю), что при помощи всякой функции f(x), удовлетворяющей условиям а)—в) из п. 10 и условию г*) если f(x) имеет смысл, то числа х и f(x) равноделимы на m,

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

Найдем несколько признаков делимости.

Согласно теореме 16 достаточно уметь определять делимость чисел на числа вида ра (степени простого числа).

16. Признак делимости на 7 в десятичной системе счисления. Пусть Л — натуральное число. Представим А в виде 10а + 6, где 0 ^ 6 < 10, как это уже делалось раньше. Положим

I ä — 26 I, если А ^ 19,

остатку от деления А на 7, если 7 ^ А < 19, не определена, если А < 7.

Задача 45. Проверить выполнение для функции /з(Л) условий а)—в) и г*).

Функция fz(A) дает нам известный признак делимости на 7: число 10а + b (0 5g b < 10) делится на 7 тогда и только тогда, когда на 7 делится число а — 26; полученное число снова проверяется этим же способом на делимость на 7 и т. д.

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

17. Признак делимости на 13. Представим натуральное число А в виде 10а + 6 и положим

а + 46, если А ^ 40,

остатку от деления Л на 13, если 13^Л<40, не определена, если Л<13.

Задача 47. Проверить выполнение условий а)—в) и г*) для функции /4(*) и сформулировать полученный признак делимости на 13.

Задача 48. К каким последствиям приведет замена в определении функции f4 числа 40 на меньшее?

Задача 49. По аналогии с построенными признаками делимости на 7 и 13 построить аналогичные признаки делимости на 17, 19, 23, 29 и 31.

Задача 50. Построить два признака делимости на 49.

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

Признак делимости на 11 в шестеричной системе счисления. Представим натуральное число А в виде 6а + 6, где 0 =g 6 < 6 (в соответствии со сказанным выше все рассуждения ведутся с употреблением обозначений и названий чисел в десятичной системе счисления), и положим

а + 2Ь, если А ^ 11,

0, если А = 11,

не определено, если А < 11.

Задача 51. Проверить соблюдение условий а)—в) и г*) для функции f и сформулировать полученный признак делимости.

Задача 52. По аналогии с только что построенным признаком делимости построить признаки делимости:

а) на 5 в семеричной системе счисления;

б) на 7 в одиннадцатеричной системе счисления;

в) на 17 в двенадцатеричной системе счисления.

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

Некоторые признаки равноостаточности, такие, как при делении на 2, 3, 5, 10 в десятичной системе счисления (и вообще — на делитель степени основания системы счисления) действительно оказались весьма практичными и удобными. Применение других

признаков связано с более или менее громоздкими вычислениями.

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

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

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

Так, например, очень легко убедиться в том, что остаток от деления числа 31 025 на 8 есть 1. Для этого достаточно найти остаток от деления на 8 числа 25. Но для нахождения остатка от деления 30 525 на 8 следует разделить на 8 с остатком число 525, а это уже требует большего числа выкладок (безразлично;, проводимых в уме или на бумаге).

В качестве другого примера рассмотрим признак равноостаточности при делении на 37 (см. задачу 36). Остаток от деления на 37 числа 10014 023 находится сложением 10+14 + 23 и делением полученной суммы на 37. Остаток, как легко видеть, равен 10. Однако немногие смогут в уме применить этот признак равноостаточности к числу 782 639 485.

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

§ 4. ОБЩИЕ ПРИЗНАКИ РАВНООСТАТОЧНОСТИ И ДЕЛИМОСТИ

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

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

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

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

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

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

В этом смысле описанный в п. 6 § 3 способ задания признака равноостаточности, а также описанный в п. 9 § 3 способ нахождения признаков делимости не являются общими признаками. Действительно, указание функций, удовлетворяющих нужным условиям, является процессом, не удовлетворяющим пока ни одному из требований определенности, массовости и результативности.

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

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

Один такой общий признак равноостаточности фактически нами уже был построен в п. 11 § 1 при

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

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

На житейском языке

На языке алгорифмов

1. Я должен найти остаток от деления данного а на данное m;

2. Для этого я буду делить на m;

3. Вот я начинаю делить а на m...

4. ... делю и получаю остаток.

Общий признак равноостаточности начинает переработку числа m;

Общий признак «выдает» результат переработки числа т: конкретный признак равноостаточности при делении на m, заключающийся в непосредственном делении на m с остатком;

Полученный конкретный признак начинает переработку числа а: деление на m с остатком;

Конкретный признак приводит к цели: к остатку от деления а на т.

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

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

Пусть m — натуральное число. Составим последовательность чисел

г и гъ г3, ..., (4.1)

полагая

Г\ равным остатку от деления 10 на m, г2 » » » Юн » m,

r3 » » » Юг о » m

и т. д.

Представим теперь произвольное натуральное число Л в виде

104+10n-1a„-i+ H-Ktei + Oo

и определим функцию

ûo + ^i^i + ^2+ ••• Л"ГпаПУ если Юп ^ m, остатку от деления А на m, если 10rt < m ^£ Л, не определена, если Л < т.

Задача 53. Проверить, что функция Fm при любом m удовлетворяет условиям а)—г) из п. 10 § 3.

Итак, нами построен признак равноостаточности при делении на произвольное m, т. е. некоторый общий признак равноостаточности.

Задача 54. Сформулировать получаемые из общего признака равноостаточности Паскаля признаки равноостаточности при делении:

а) на 2, 5 и 10;

б) на 4, 20 и 25

в) на 3 и 9;

г) на 11;

д) на 7.

Задача 55. Пусть в последовательности (12) г\ есть остаток от деления 100 на m, г2 » » » 100/*! на т,

г3 » » » 100г2 на m

и т. д.

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

Задача 56. Вывести общий признак равноостаточности в /-ичной системе счисления, аналогичный признаку Паскаля.

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

Так, например, общий признак Паскаля наряду с вполне приемлемыми признаками равноостаточности при делении на 3 и 11 дает весьма громоздкий и неудобный к применению признак равноостаточности при делении на 7 (см. задачу 54, д)).

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

§ 5. ДЕЛИМОСТЬ СТЕПЕНЕЙ

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

Пусть k — некоторое натуральное число и г есть остаток от деления tk на т:

tk = mq + r (0 ^ г < m).

По следствию теоремы 20 (см. п. 3 § 2) при любом п числа гп и tkn при делении на m также должны быть равноостаточными.

Составим теперь для произвольного числа А его разбиение на £-значные «грани» справа налево, т. е. представим его в виде

A = antkn + an_xtkin-l)+ ... +а/ + оо,

где

0^üi<tk при / = 0, 1, fly и положим /04) = апгп + ап_хгп-1 + ... +а1г + а0, если А ^ tk, остатку от деления А на m, если m^A<tk, не определено, если А < т.

Ясно, что, как и ранее в аналогичных случаях, процесс построения чисел

Aq = A, A{ = f (Ао), А2 = f (Ai), ...

является признаком равноостаточности.

Задача 57. Убедиться все-таки в том, что это действительно так.

Задача 58. Полагая t = 10 и k = 2, найти остаток от деления числа 1.048 576 на 7.

Задача 59. Убедиться в том, что только что описанный признак равноостаточности является лишь более явной формой того обобщения признака Паскаля, которое было упомянуто в задаче 56.

2. Говоря формально, при составлении в п. 1 общего признака равноостаточности мы пользовались свойствами степеней, относящимися к их делимости. Однако вопрос о делимости степеней по существу является вопросом о делимости некоторых произведений. Поэтому и решить этот вопрос в принципе удалось на основе результатов § 2. Вместе с тем практическая реализация полученного признака равноостаточности для тех или иных комбинаций значений чисел t и m может приводить к крупным значениям k и г, так что вычисление значений функции / может потребовать выполнения значительных вычислений, возможно даже превосходящих по объему выкладки по непосредственному делению на т.

Ясно, что вычисление значений функции / оказывается тем проще, чем меньшими будут значения чисел k и г. Разумеется, наиболее удобным оказывается в этом отношении тот случай, когда г=1. Тогда значение / получается в результате выполнения наименее трудоемкого действия: сложения.

Согласно теореме 22 этот случай (г=1) имеет место тогда и только тогда, когда (tk—1) \т или, иными словами, когда tk при делении на m дает в остатке 1. Встает вопрос: найдется ли при данных / и m такое k> что (tk — 1 ) ; m?

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

3. Расширим несколько наши познания в области теории чисел.

Теорема 24 (теорема Ферма). Если число р простое, то разность ар — а делится на р.

Не следует путать эту так называемую «малую теорему Ферма» с «великой теоремой Ферма». Последняя утверждает, что при целом п > 2 не существует таких целых a, b и с, что ап + Ьп = сп. Несмотря на многочисленные попытки, великая теорема Ферма до сих пор не доказана и не опровергнута.

Следствие. Если р— простое и а не делится на р, то ар-{ — 1 делится на р.

Задача 60. Привести пример, показывающий, что как теорема 24, так и ее следствие для составного р, вообще говоря, неверны.

Задача 61. Доказать теорему Ферма, опираясь на результат задачи 26.

Пусть натуральное число m имеет каноническое разложение:

m = (5.1)

положим

Ф(m) = (Pi - 1 ) Pi2"' (Р2 - 0 • • • (Рн ~ О'

(5.2)

Формулы (5.1) и (5.2) ставят в соответствие каждому натуральному числу m некоторое вполне определенное число ф(т). Это значит, что мы можем говорить о функции ф от натурального аргумента.

Определение. Определенная выше функция ф называется функцией Эйлера.

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

Теорема 25. При взаимно простых тп\ и т% имеет место равенство

Ф {m\m2) = Ф (mi) ф (т2).

Задача 62. Вычислить ф(12), ф(120), ф(1000). Задача 63. Определить все числа m, для которых:

а) ф(т)= 10;

б) ф(т)=8.

Задача 64. Доказать, что не существует такого m, для которого ф(т)= 14.

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

Теорема 26 (теорема Эйлера). Если числа а и m взаимно просты, то а^т) — 1 делится на т.

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

Задача 66. Пусть (mi,m2)= 1, a ai и а2 — числа, равноостаточные с А при делении соответственно на т\ и т2. Тогда равноостаточным с А при делении на ш\гп2 будет число

(а{т2 + а2т1) {тх + m2f

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

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

Итак, пусть нам даны числа mut. Представим m в виде такого произведения m = т\т2, что (m\}t) = = 1, и для некоторого показателя k имеет место делимость tk\m2. Согласно теореме 18 такое представление возможно. В силу задачи 66 вопрос о равноостаточности при делении на т\ш2 может быть сведен к аналогичным вопросам для деления на т\ и т2. Но признак равноостаточности на т2 содержится в теореме 21, а признак равноостаточности на т\— в теореме 22. После применения этих признаков равноостаточности следует воспользоваться результатом задачи 66.

Например, в случае нахождения признака равноостаточности при делении на 12 в десятичной системе счисления, очевидно, т\ = 3, т2 = 4 и k = 2.

Описанный процесс является общим признаком равноостаточности в том смысле, что по любому m он выдает некоторый конкретный признак равноостаточности. Это вытекает из алгорифмичности представления числа m в форме, указываемой в теореме 18, а сама эта алгорифмичность следует из алгорифмичности построения канонического разложения чисел (см. п. 9 § 3).

Нам остается сформулировать в явном виде указанный признак равноостаточности при делении на ти пользуясь возможностью определить показатель k на основании теоремы Эйлера.

5. Применяя доказанные теоремы, построим несколько общих признаков делимости и равноостаточности.

Фиксируем натуральное m и представим число А в виде

Л = а0 + а110ф(т) + а2102ф(т)+ .... +akWk*{m\

где

0^а0, аи а2, ak^ 10ф(т),

т. е. все ai (i = О, 1, ..., k) являются (р(т)-значными числами. Функция

F(A) =

яо + ах + ... +ак9 если А ^ 10ф (т),

остатку от деления А на ш, если т^Л<10ф(т), не определена, если А < т,

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

Задача 67. Проверить это обстоятельство.

Теорема 27. Если числа а и m взаимно просты, а числа k\ и £2 равноостаточны при делении на ср(т), то числа akx и акг равноостаточны при делении на т.

Задача 68. Сформулировать получаемые на основе этого общего признака равноостаточности конкретные признаки равноостаточности при делении на 7, 11 и 13.

Задача 69. Сформулировать аналогичный общий признак равноостаточности для произвольной f-ичной системы счисления. Убедиться в том, что получаемый так общий признак равноостаточности по своей формулировке не зависит от основания системы счисления t.

Задача 70. Доказать, что (я13 — п) ] 2730.

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

Поэтому, с одной стороны, при пользовании этим признаком приходится складывать большие числа, а с другой стороны, ф(т)-значные числа при этом приходится делить на m непосредственно (или же пользоваться каким-нибудь другим признаком делимости и равноостаточности). Желательно поэтому попытаться взять вместо ф(га) другой, меньший показатель. В ряде случаев это удается сделать. Например, при m = 37 вместо ф(т)=36 можно взять показатель 3, ибо 1000 при делении на 37 дает в остатке единицу; при га= 11 вместо ф(т)= 10 можно взять показатель 2 и т. д.

Определение. Наименьшее число о, для которого а6 при делении на m с остатком дает в остатке 1, называется показателем, которому принадлежит число а при делении на m с остатком.

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

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

Задача 71. Модифицировать построенный общий признак делимости, используя вместо ф(т) показатель, которому принадлежит 10 при делении на m с остатком.

Задача 72. То же для /-ичной системы счисления.

7. Показатель, которому принадлежит число а при делении на т, может, вообще говоря, быть и равным <p(m). Например, последовательностью остатков от деления степеней числа 2 на 11 будет

2, 4, 8, 5, 10, 9, 7, 3, 6, 1,

так что при делении на 11 число 2 принадлежит показателю 10. Значит, для применения признака равноостаточности из п. 5 в этом случае приходится брать k = 10 = ф(11).

Однако во многих случаях удается обходиться показателем

■i- ф (m).

Пусть, например, m есть степень простого числа: m = р<* и р ф 2. Тогда ф (m) = ра~{ (р — 1), и теорема Эйлера приобретает вид: для (а, р) = 1 должно быть (ара 1 (р-1) — l) \ ра. Так как число ра~1 (р — 1) четное, последнее делимое есть разность квадратов, и мы имеем

Так как р Ф 2, оба сомножителя одновременно на р делиться не могут. Значит, на р делится либо а +1, либо а — 1.

В первом случае мы оказываемся в условиях теоремы 23 с k = ~ ф (m), а во втором — в условиях теоремы 22 с тем же k = — Ф (m).

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

Теорема 28. Если числа а и b взаимно просты, то уравнение

ах + Ьу = с (5.3)

всегда разрешимо в целых числах, и целыми его решениями будут все пары чисел (xt,yt)9 где

(t — любое целое число).

Задача 73. Доказать теорему, аналогичную теореме 28, не предполагая взаимной простоты чисел а и Ь.

Задача 74. Найти способ решения уравнений вида (5.3) в целых числах на основе результата задачи 29,6).

Задача 75. Решить в целых числах уравнения:

а) 5л: + 7у = 9;

б) 25л: + 13t/= 8.

9. Теорема 29. Пусть m взаимно просто с 10 и k равноостаточно с Ю^т)-1 при делении на т. Тогда числа

10а + ô и a + kb

равноделимы на т.

Опираясь на эту теорему, можно построить следующий общий признак делимости. Обозначим через k остаток от деления 10<P(m)-i на m с остатком, представим произвольное число А в виде

10а + b (О^Ь < 10)

и положим F(A) =

а + kb, если А > а + kb,

остатку от деления А на m, если m^A<a+kb, не определена, если А< т.

Если k велико (близко к m), то вместо него в формулировке соответствующего признака целесообразно брать k — т.

Задача 76. Проверить для функции F выполнение условий а)—в) из п. 10 § 3 и г*) из п. 15 § 3.

Задача 77. На основании только что построенного общего признака делимости вывести признак делимости на числа 17, 19, 27, 29, 31 и 49.

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

100а + Ь (О^й < 100),

и вывести из него признаки делимости на 17, 43, 49, 67, 101, 199.

Задача 79. Построить аналогичный общий признак делимости в /-ичной системе счисления.

Задача 80. На основании построенного общего признака делимости вывести конкретные признаки делимости:

а) на число 21 в восьмеричной системе счисления;

б) на число 31 в двенадцатеричной системе счисления.

ДОКАЗАТЕЛЬСТВА ТЕОРЕМ

1. Достаточно заметить, что а = а-1.

2. По условию, найдутся такие d\ и d2, что а = bd\ и b = cd2. Но тогда а = cdid2, т. е. а • с

3. Мы имеем а = Ьс\ и 6 = ас2, откуда следует, что а = acic2, т. е. CiC2 = 1. Так как числа С\ и с$ по условию целые, то либо Ci = c2=l, либо с\ = = с2 =—1. В первом из этих случаев а = b, а во втором а = —Ь.

4. Пусть а = be. Если |с|^1, то поскольку |&|>|а|, должно быть и |6с|>|а|, что, однако, противоречит предположенному. Значит, |с|<1, а так как по условию число с целое, должно быть с=0, а потому и а = 0.

5. Очевидно, из а = be следует |a| = |ô||c|, а из I а I = I & 11 с J следует а = be или а = 6 (—с), причем числа с, —с и |с| целые или нет одновременно.

6. В самом деле, пусть

а{ = Ьси а2 = bc2t

ап = Ьсп,

где все числа с\, с2, сп — целые. Сложив все эти равенства почленно, мы получим

ai+ 02+ ... +an = b(ci + c2+ ... +сп).

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

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

PU Р2> . « •> Рп* (Д-1)

Произведение всех этих чисел обозначим через Р и рассмотрим разность Р—1, Эта разность больше каждого из простых чисел, перечисленных в списке (Д.1), и потому не может быть простым числом. Следовательно, она делится хотя бы на одно простое число р*. Но Р также делится на р*. Следовательно, на основании следствия теоремы 6, должно быть и 1 ; Pky откуда следует, что pk= I, а это противоречит простоте числа pk (см. стр. 21).

Приведенное доказательство бесконечности множества простых чисел было найдено Евклидом (IV век до н. э.).

9. Если числа аир взаимно просты, то теорема доказана. Если же эти числа не взаимно просты, то оба они делятся на одно и то же число, отличное от единицы. Ввиду простоты р таким числом может быть только само р. Значит, в этом случае а\р, а это и требовалось.

10. Разделив M на m с остатком, получим

M = mq + г,

где 0 ^ г < т. Так как M и m делятся на а и Ь> по следствию теоремы 6, число г также должно делиться и на а, и на & и тем самым быть общим кратным этих чисел. Но г < га, a m есть наименьшее положительное общее кратное а и Ь. Значит, г не может являться положительным числом, так что г = 0. Поэтому M ] га.

11. Пусть числа а и b взаимно просты, и га— их наименьшее общее кратное. Так как ab] а и ab\b по предыдущей теореме ab \ га. Пусть ab = mk. Положим га = ас. Тогда ab = ack, т. е. b = ck, так что b\k. Точно так же убеждаемся в том, что и а\k Так как числа а и & по условию взаимно простые, должно быть k= 1, а это и означает, что m=ab.

12. Обозначим через m наименьшее общее кратное чисел b и с. По предыдущей теореме m = be. Далее, по условию ab | с> кроме того, очевидно, ab • b. Значит, по теореме 10, ab]bct т. е. ab = bek или, после сокращения на b, а = ck, а это и требовалось.

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

а\й2 ... ana«+\ - p. Обозначим a\a2 ... an через A. Тогда Aan+\:P. Если an+\ • p, то теорема доказана, a если нет, то по теореме 9 числа ап+\ и р взаимно просты. Но тогда по предыдущему А ] р. Так как А есть произведение п сомножителей, по индуктивному предположению один из них должен делиться на р. Теорема доказана.

Следствие. Вся дробь представляет собой целое число, т. е. ее числитель делится на знаменатель. Будем считать, что числитель является произведением двух сомножителей: р и 1-2 ... (р—1) = (р—1)!

Ни один из сомножителей знаменателя дроби не делится на р. Следовательно, по предыдущей теореме, на р не делится и весь знаменатель. Но тогда на основании теоремы 9 он взаимно прост с р. Поэтому на знаменатель должен делиться второй сомножитель числителя. Обозначая частное от этого деления через q, мы имеем Cp = pq, и требуемое доказано.

14. Сначала докажем возможность разложения любого числа, отличного от единицы, на простые множители. Предположим, что все числа, меньшие N, могут быть так разложены. Если число N простое, то оно автоматически разлагается в произведение простых (именно, в произведение, состоящее только из одного сомножителя — самого числа N), и теорема доказана. Пусть теперь N составное, N\ — некоторый делитель N, отличный как от N, так и от единицы, и N2— частное от деления N на N\. Тогда N = N\N2y причем, как легко проверить, 1 < N2 < N. Так как N\ и N2 меньше N> то, по предположению, они разлагаются в произведения простых множителей. Пусть N\ = Р1Р2 ... Pk и N2 = q\q2 ... qi — эти разложения. Тогда Р1Р2 ... Pkq\q2 ... qi является искомым разложением числа N. Возможность разложения, таким образом, доказана.

Переходим к доказательству единственности разложения. Пусть нам даны два разложения числа N на простые множители: pip2 ... Pk и q\q2 ... qi- Очевидно,

Р1Р2 ... Pk = Q\Q2 ... qi. (Д.2)

Так как q\q2 ... qi делится на pi, то по предыдущей теореме хотя бы одно из чисел qu ?2, qi делится

на рь Пусть q\ \р\ (то, что мы считаем именно первый сомножитель в (Д.2) справа делящимся на ри никакого дополнительного предположения не означает, так как мы вправе переставлять сомножители местами и обозначить через qx именно тот из них, который делится на pi). Так как число q\ простое, это возможно лишь при pi = <7ь Сокращая равенство (Д.2) на pu получаем

р2рз ... Pk = <72<7з (Д.З)

Аналогично предыдущему убеждаемся в том, что некоторое из чисел q2y <7з, ..., qi (например, q2) делится на р2, и потому р2 = q2. Сокращая равенство (Д.З) на р2, мы уменьшаем число сомножителей в его частях еще на единицу. Такой процесс сокращения, очевидно, можно продолжать до тех пор, пока мы не сократим одно из произведений полностью. Пусть первым сократится произведение, состоящее в (Д.2) слева. Произведение, стоящее в (Д.2) справа, тоже должно при этом сократиться нацело, так как в противном случае мы получили бы равенство вида

1 =Як+\ •••?/>

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

Pi = <7b р2 = ?2> ...» Pk = 4k-Теорема полностью доказана.

16. Пусть р^р"2 ... р\к и q\lql2 ,.. q** — соответственно канонические разложения чисел а и &, a d — некоторый общий делитель этих чисел. Если аф\> то d делится на некоторое простое число р. Тогда по теореме 3 а\р и Ь\р, так что р находится как среди чисел pi, р2, pk, так и среди чисел qu ?2, qu Поэтому среди простых чисел, входящих в каноническое разложение а, существует хотя бы одно, входящее в каноническое разложение 6.

Наоборот, если а и b взаимно просты и р входит в каноническое разложение а, то b не делится на р, так что р не может входить в каноническое разложение 6,

16. Необходимость. Так как а\р** (/=1, 2, k)y мы из Ь\а получаем требуемое простой ссылкой на теорему 2.

Достаточность доказывается по индукции. Делимость Ь]р*1 мы имеем в числе условий. Предположим, что нами уже установлено, что

Кроме того, в нашем распоряжении имеется делимость b\p*$l. Так как числа ра{1 ... р\1 и p"j+l по

предыдущей теореме взаимно просты, мы можем применить следствие теоремы 11, которое дает нам

Этим индуктивный переход обоснован.

17. Необходимость. Пусть а\Ь. Из теоремы 13 следует, что каждый простой делитель b является простым делителем а. Таким образом, b имеет вид

где 0 ^ ßi, 0 ^ ß2, *.., 0 ^ ßjfe. Предположим, что ßi > ai. Так как

— целое число, числитель последней дроби должен делиться на знаменатель и тем более на число pßi-ale Но Т0Гда по теореме 13 на pi должно делиться хотя бы одно из чисел р2, pk, чего не может быть. Значит, ßi ^ ai. Так как нумерация простых делителей а для нас безразлична, мы тем самым доказали, что и ß2 ^ а2, ..., ß* ^ а*. Необходимость доказана.

Для доказательства достаточности заметим, что если b имеет указанный вид, то

18. Напишем канонические разложения чисел m

и t:

Отберем среди простых pu ..., Рп те, которые делят т. е. содержатся среди qu ..., qu Пусть для определенности это будут pu рг> равные соответственно числам qu ..., qr- Положим тогда

Согласно теореме 15 будет (тиt)=l. Кроме того, возьмем натуральное число к, которое было бы не меньше каждого из отношений

Это значит, что kßt ^ at для i = 1, г, откуда согласно теореме 17 tk\m2.

19. Необходимость. Пусть

a = mq{ + rx (0^r{< m), (Д.4)

b = mq2 + r2 (0 ^ r2 < m), (Д.5)

Ввиду равноостаточности a и b должно быть r\ = г2. Значит,

a — b = m(qi — q2),

т. е. (а — b) \ т.

Достаточность. Пусть (а — Ь)\т. Разделив а и b на m с остатком, мы получим (Д.4) и (Д.5). При этом

a —b = m{q[ — q2) + г{ — г2,

т. е.

(а — Ь) — m(qi — ?2) = гх — г2.

По теореме 6 (г\— г2)\т. Но \г\ — r2|<m. Значит, по теореме 4 ri — г2 = О или г\ = r2, а это и требовалось.

20. Из условия на основании теоремы 16 мы имеем

(Д.6)

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

что по теореме 19 и означает равноостаточность сумм.

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

(k + bm) (p + qm) = kp + (pq + Ip + Iqm) m.

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

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

а{а2 ... ап = Ьф2 ... bn + mt,

где / — некоторое целое число. Равноостаточность произведений, таким образом, доказана.

21. Необходимость. Если описанный алгорифм является признаком равноостаточности при делении на m, то числа Л и b при делении на m должны быть равноостаточными. В частности, это будет так, если А = tk + b. Но это значит, что А — b = tk ] m.

Достаточность. В наших обозначениях A — b = atk9 т. е. числа А и b равноостаточны при делении на /п. Если tk - m, то по следствию теоремы 17 они равноостаточны и при делении на т. Поэтому конструируемая алгорифмом в этом случае последовательность Ло, Ль ... состоит из равноостаточных при делении на m чисел. Следовательно, процесс построения этой последовательности является признаком равноостаточности при делении на т.

22. Необходимость. Если описанный алгорифм действительно является признаком равноостаточности при делении на m, то он, в частности, должен быть применим и к числу А = tk + а0. Здесь /(Л)=ао+1, и равноостаточность чисел Л и f(A) при делении на m означает (tk—\) \ т.

Достаточность. Пусть А ^> tk. Тогда из определения функции / следует, что

Здесь каждое слагаемое (см., например, задачу 22, п. д)) делится на tk— 1. Значит, если (tk— 1) ] m, то и (А — f(A))]m. Равноостаточность остальных членов последовательности (3.4), а также ее членов, если она начинается с числа А < tk, вытекает из ее построения.

23. Необходимость. В случае A = tk-\-cto равноостаточность чисел А и f(A)= а0—1 при делении на m дает нам (tk + 1) | т.

Достаточность. Мы имеем в нашем случае при A^tk

(Д.7)

(знак «плюс» стоит здесь в члене, соответствующем нечетному коэффициенту при k в показателе, а знак «минус» — в члене, соответствующем четному коэффициенту). Согласно пп. д) и е) задачи 22 при нечетном г выражение tkr + 1 делится на /*+ 1, а при четном г выражение tkr—1 делится на th+\. Значит, если (/*+1);/л, то на m делится каждый член в (Д.7) справа, а потому и вся разность А — f(A)4 Тем самым числа А и f(A) оказываются равноостаточными при делении на /п. Равноостаточность остальных членов последовательности (3.4), а также членов этой последовательности, если она начинается с числа А < tkt вытекает непосредственно из ее построения.

24. Доказательство ведется индукцией по а. При а = 1 имеем

ар-а=1-1=0

и о;р.

Предположим, что ар — а делится на р, и докажем, что (а+1)р—(а+1) также делится на р.

Действительно, разлагая (а + 1)р по формуле бинома Ньютона, имеем

оР—а делится на р по предположению. По следствию теоремы 13 С* (при l^ft^p—1) также делится на р. Следовательно, на р делится каждое слагаемое правой части соотношения (Д.8), а потому (теорема 6) и вся сумма.

Индуктивный переход обоснован, и вся теорема доказана.

Следствие. По теореме Ферма

Если при этом а не делится на р, то по теореме 13 на р должно делиться аР~х— 1. 25. Пусть

По теореме 15 каждое из чисел рь р* отлично от каждого из чисел qu qi- Значит, каноническим разложением т\гп2 будет р"1 ... pakkq\l ... q\l. Поэтому

26. Докажем сначала индукцией по а, что apa~l(p-i)— 1 делится на ра. При а= 1 доказываемое утверждение является, очевидно, следствием теоремы Ферма, справедливость которого уже была установлена. Таким образом, основание индукции доказано.

Предположим теперь, что

и рассмотрим выражение apQ,{p~l)— 1. Мы должны доказать, что оно делится на ра+1. Но

Так как ара мр-О— 1, по предположению, делится на ра, число ара~1(р_1) имеет вид Npa+l. Значит,

т. е. по формуле бинома

В последней сумме первое слагаемое делится на ра+1, так как оно делится на рар и ар^а + 1. В каждое из следующих р—1 слагаемых этой суммы входит р с показателем, не меньшим а, и, кроме того, биномиальный коэффициент, в силу следствия теоремы 13 делящийся на р. Значит, каждое из этих слагаемых также делится на ра+1. Наконец, разность 1 — 1=0 может быть отброшена. Поэтому по теореме 6

Случай, когда число m имеет только один простой делитель, таким образом, разобран.

Предположим теперь, что теорема Эйлера доказана для показателей гп\ и т2, причем числа т\ и т2 взаимно простые. Докажем теорему Эйлера для показателя m = т\гп2. Если потом положить

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

Пусть числа а и m взаимно просты. Тогда а также взаимно просто с т\. Значит, и аТ{тг) взаимно просто с гп\. Поэтому, по предположению,

(дф (m2)yP <mi> — i — аФ (т,) Ф (т2)_\ — аФ (т{т2) — j _аф (т) — \

делится на т\. Точно так же убеждаемся в том, что дФ(т)—j делится и на m2. А так как числа т\ и т2 взаимно простые, а^т) — 1 делится и на их произведение, т. е. на т. Теорема Эйлера доказана. 27. Пусть

Тогда

На основании теоремы Эйлера и теоремы 20 число аФ(т)^,аг равноостаточно при делении на m с числом аг. Аналогично устанавливается равноостаточность при этом делении чисел акг и аг. Значит, и числа ак{ и акг при делении на m равноостаточны.

28. Найдем сначала хотя бы одно решение (х\у') этого уравнения. Очевидно, что для этого достаточно найти такое число х\ что (ах' — с) \ Ь. По теореме Эйлера (a^W—l)';b. Значит, (ca^b) — с) • b, и в качестве х' можно взять число са^Ь)~1.

Пусть теперь (х"> у") — какое-то другое решение уравнения ах + by = с. Покажем, что числа х' и х" равноостаточны при делении на Ь. В самом деле, пусть

Вычитая почленно второе равенство из первого, получаем

откуда a(xf — х") \ Ь. Так как а и b по условию взаимно просты, по теореме 12 (х' — х")\Ь, и нам остается сослаться на теорему 19.

Таким образом, все искомые значения х находятся среди чисел

Но (axt — с) ;6, так что, полагая

мы получаем, что все пары чисел xt и yt являются решениями нашего уравнения.

29. Ввиду взаимной простоты m и 10, числа 10а + Ь и (10а + Ь) 10Ф<тЫ по теореме 15 равноделимы на т. Но

(10а + Ь) 10ф(тЬ1 = 10ф (т)а + 10ф(тЬ1й,

так что по теореме Эйлера и теореме 20 число Юа+6 равноделимо на m с числом a + kb<

РЕШЕНИЯ ЗАДАЧ

1. О = а-0 при любом а.

2. а = 1 • а, значит, а ] 1.

3. Пусть 1 \а. Это значит, что 1 = ас при некотором целом с. Отсюда следует, что А так как а Ф О, должно быть а = 1.

4. Достаточно взять любое Ol и положить & = ас.

5. В качестве такого b можно взять, например, 2а. Пусть при этом для некоторого с и 2а\с и с \а. Это значит, что найдутся такие d\ и d2, что 2а = die и с = d2a. Отсюда следует, что 2а = d\d2a или, после сокращения на а,

Но при целых d\ и d2 такое равенство возможно лишь в случае, когда одно из этих чисел равно 1, а другое 2. Если d\ = 1, то с = 2а = &; если же rf2 = 1, то с = а.

5. Доказательства ничем не отличаются от доказательств в случае обычной делимости.

7. Пусть п — некоторое фиксированное число, большее единицы. Положим а : 6, если найдется такое целое с, что а = be и с ^ п. Справедливость теорем, аналогичных теоремам 1, 3 и 4, проверяется без труда. Однако если мы возьмем а = nb и 6 « ne, то а : b и b \ с. В этом случае а = я2с, a так как п2 > п, делимость а : с не имеет места. Точно также не имеет места делимость (а + а) \ Ь.

8. а) Пусть имеются два минимальных числа ai и а2. В силу дихотомичности либо ai ^ аг, либо аг ^ ai. Если а4 ^ аг, то из минимальности ai следует, что ai = аг. Если же аг ^ ai, то ai = аг следует из минимальности а2.

б) Пусть a — некоторое число, а ^ и Ьг — два непосредственно предшествующих ему числа. По дихотомичности должно

быть либо bi ^ b2, либо Ьч ^ bi. Пусть, для определенности, Ь\ ^ Ьг. Мы имеем а ^ Ьх ^ Ь2, а так как число Ь2 непосредственно предшествует числу а, должно быть либо bi = а, либо fti = &2. Но по условию Ь\ ф а; значит, bt = Ьг, и требуемая единственность доказана.

в) Непосредственно следующим за а числом называется такое Ьу что Ь ^ a, b ф а, и из б^с^а следует либо с = Ь, либо с = а.

Предположим, что некоторое а не имеет непосредственно следующего за ним числа. Это значит, что для любого ап ^ а и отличного от а найдется такое ап+и отличное как от ап, так и от а, что ап ^ an+i ^ а. Возьмем теперь произвольное ûi^a й отличное от а (в силу 2° это сделать можно) и, исходя из него, построим бесконечную последовательность различных чисел

ai ^ а2 ^ ... ^ ап ^ ап+\ ^ ... ^ а.

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

9. Остается в силе транзитивность (3°), неограниченность множества чисел (5°), свойство 4° и существование непосредственно предшествующего числа (6°). Дихотомичность заменяется трихотомичностью (либо а > Ь, либо b > а, либо а = Ь).

Становится неверным свойство рефлексивности (1°), ибо а > а всегда неверно.

Что же касается, наконец, утверждения 2°, то формально оно остается в силе (хотя, быть может, и выглядит несколько парадоксально).

В самом деле, говоря строго, это утверждение в нашем случае формулируется так: для любых натуральных чисел а и b из а > b и b > а следует а — Ь.

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

10. Пусть множество упорядочено отношением £—, обладающим свойствами Г —7°. Как уже было установлено, оно обладает минимальным элементом. Обозначим этот элемент через a<j. Из результатов задачи 8 следует, что каждый элемент обладает непосредственно следующим. Обозначим непосредственно следующий за Go элемент через аи непосредственно следующий за ai — через Û2 и т. д. В итоге мы получаем последовательность

а<ь au (*2, (Р.1)

в которой яп+1 S~~ ап при любом п. По рефлексивности и транзитивности отношения отсюда следует, что а^-а^ тогда и только тогда, когда i 7^ /. Нам остается показать, что последовательность (РЛ) охватывает все рассматриваемые нами объекты. Это достигается довольно тонким рассуждением по индукции.

Предположим, что fto не принадлежит последовательности (Р.1). Получение этого bo будем считать первым шагом нашего индуктивного рассуждения. Пусть п его шагов уже проведены, в результате чего нами получен некоторый элемент ftrt-t.

Если bn-i — а0, то наш процесс будем считать законченным; если же Ьп-\ Ф ао, то элемент Ьп-\ имеет непосредственно предшествующий, который мы и возьмем в качестве Ьп. В результате мы получаем последовательность различных элементов

На основании 4° эта последовательность должна иметь последний член. Но по самому принципу построения этой последовательности ее последним членом может быть только ао. Пусть для определенности Ьп = ао.

Нетрудно проверить, что если некоторое а непосредственно предшествует о, то b непосредственно следует за а. Значит, bn-i = л|, Ьп-2 = 02, ..., bo = CLn-

Последнее означает, что bo принадлежит последовательности (Р.1), но это противоречит предположенному. Следовательно, последовательность (Р.1) содержит все рассматриваемые нами объекты.

//. Пусть а — некоторое число. Всякую последовательность различных чисел ао = а, ai, аг, ..., ап, для которых

а0 S- ai а2 £- • • • Ь~ (*п, (Р.2)

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

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

В самом деле, пусть a — некоторое число, а bu 02, ..., bk — непосредственно предшествующие ему числа.

Если ai не предшествует а0 непосредственно, мы можем на основании 9° вставить в цепь (Р.2) некоторое непосредственно предшествующее a число. Поэтому если имеются сколь угодно длинные цепи предшественников а, должны найтись и такие его сколь угодно длинные цепи предшественников, которые начинаются с чисел, непосредственно предшествующих а. Будем далее рассматривать только такие цепи.

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

Значит, при нашем предположении хотя бы одно из чисел, непосредственно предшествующих а0, имеет сколь угодно длинные цепи предшественников. Обозначим это число через а\ и повторим в применении к нему все только что проведенные рассуждения. Это даст нам некоторое число а2, непосредственно предшествующее ai и имеющее сколь угодно длинные цепи предшественников. Повторяя этот процесс, мы приходим к последовательности

a0£-ai $-а2$-

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

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

Следовательно, для каждого числа а среди его цепей предшественников можно выбрать самую длинную. Обозначим бе длину через п(а). Если 6 непосредственно предшествует а, то очевидно, п(Ь) = п(а)—1, a для всех минимальных а п(а)=0.

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

12. Каковы бы ни были четные числа а и 6, существуют такие четные числа (/иг, что

a = bq + r (0 ^ г < 2Ь).

Такие числа q и г единственны.

Доказательство. Разделим а на 26 с остатком обычным образом:

а = 2bq + г (0 ^ г < 26). (Р.З)

При этом числа q и г определяются однозначно. Из четности а и 2bq следует четность их разности, т. е. числа г. Нам остается, положив 2q = q', переписать (Р.З) в виде

a = ?'6 + г (0^г<26)

и заметить, что оба числа q' и г четные и определяются единственным образом.

13. Пусть р— наименьший простой делитель числа а. Отсюда следует, что а = pb. Всякий простой делитель q числа b является вместе с тем и делителем а. Поэтому <7 ^ р, значит, и b ^ р, так что а ^ р2 и, наконец, р ^ Va •

14. Пусть pu Р2у Pk — полный список всех простых чисел, входящих хотя бы в одно из канонических разложений а и Ь. Положим

(Если а не делится на ри то а.- = 0; если b не делится на pi, то ßi = 0.) Пусть yi — наибольшее из чисел ai и ß; для i= 1, 2, k, а 6,-— наименьшее из них.

Тогда, на основании теоремы 17, наибольший общий делитель а и b есть р\1р*£ ... pôkk, а их наименьшее общее кратное—p^pj2 ... pykk.

15. Как следует из теоремы 17, каждый делитель числа а с каноническим разложением Р\?2 •••Pk должен иметь вид р^1, ...,p^Ä, где ßi принимает ai + 1 значений: 0, 1, 2, ai ß2 принимает a2 + 1 значений и т. д. Так как любые комбинации этих значений возможны и дают нам все делители а, причем; каждый по одному разу (если бы какой-нибудь делитель повторился несколько раз, то это означало бы наличие у него нескольких канонических разложений), число делителей а равно

(a, + l)(a2+l)...(oft+l). (Р.4)

16. Пусть каноническое разложение а есть р^Рг2 • • • ptk' Очевидно, можно положить р\ = 2, ai ^ 2 и р2 = 3, а2 ^ 1. Далее, согласно (Р.4), мы имеем

(a, + l)(a2+l)...(aft+l)-14.

Отсюда k = 2, ai + 1 = 7 и a2 + 1 = 2. Таким образом, a =• = 26-3 = 192.

17. Мы имеем

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

В первом из этих случаев ai = 0, что противоречит предположенной положительности числа ai. Оставшиеся случаи дают нам

ai»1, a2—13; ai — 4, a2 = 4.

Значит, либо

либо

18. Пусть рх lp2* ... PfJ* — каноническое разложение числа а. Условие задачи дает нам

или

(Р.5)

Заметим, что

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

причем их произведение есть 2. Но это может быть лишь в двух случаях: когда в (Р.5) слева стоит только одна дробь или когда там стоят две дроби ^ _^ | и ^ ^ . Этим двум случаям соответствуют два ответа задачи: 8 и 12. /Р. Напишем каноническое разложение числа а:

Тогда

и согласно (Р.4) (задача 15)

Легко видеть, что каждая дробь (2а/ + 1)/(а/ + 1) с ростом щ возрастает (приближаясь к 2), так что наименьшее значение этой дроби будет достигаться при а/ = 1 и будет равно 3/2. Это значит, что

Ясно, что при достаточно большом k будет (3/2)* > К. Для этого достаточно взять

Например, при К = 100 достаточно взять k > 2/0,18 = 11,1; так как число k должно быть целым, можно взять k = 12.

20. Аналоги теорем 11—14 для четной делимости неверны. В самом деле, числа 30 и 42 четно простые. Их наименьшее четное кратное есть 420, а произведение — 1260.

Далее, 60 = 6 10 четно делится на четно простое число 30; 6 и 30 четно взаимно просты, а 10 четно на 30 не делится.

Наконец, 60 = 6-10 = 30-2 — два различных разложения числа 60 на четно простые множители.

21. а) 116 при делении на 8 равноостаточно с 4, а 17 — с 1. Значит, А равноостаточно с 521 = (52)10-5. Но 52 = 25 при делении на 8 равноостаточно с единицей. Следовательно, А при делении на 8 дает в остатке 5.

б) 14 при делении на 17 равноостаточно с —3. Поэтому А равноостаточно с (—З)256 = З256 = (33)85-3. Но З3 мы можем заменить на 10: 1085- 3 = (102)42-30. Далее, 102 при делении на 17 равноостаточно с числом —2, а 24 с —1. Значит, А равноостаточно с (_2)42.зо = 242.30 = (24)10.4-30 = (—1)10-4-30 = = 120. Последнее же число при делении на 17 дает в остатке 1.

22. а) Пусть п\ — остаток от деления п на 6. Тогда П\ может принимать значения 0, 1, 2, 3, 4 и 5, а п\ + llttj при делении на 6 равноостаточно с п3 + + 11л. Значит, нам следует испытывать делимость на 6 чисел 0, 12, 30, 60, 108 и 180. Но все эти числа на 6 делятся.

Для получения того же результата можно воспользоваться и более частными соображениями. Число п3 + 11 /г равноостаточно при делении на 6 с числом п3+11я—12я = /г3— п = (п—1)/г(/г+1), Но из трех последовательных целых чисел п—1, п и п+ 1 хотя бы одно — четное (т. е. делится на 2) и ровно одно делится на 3. Значит (согласно следствию теоремы 11), произведение этих трех чисел делится на 6. Кстати, можно заметить, что

б) При п ^ 2 мы имеем (пользуясь формулой бинома)

и оба слагаемых, очевидно, делятся на 9-

При п = 1 наше выражение равно 41 + 15-1 — — 1=18.

в) Доказательство ведется по индукции. При п = О

1030 — 1 = 101 — 1 = 9 и 3°+2 = 9. Пусть теперь делимость

(103Л-1):зЛ+2

имеет место. Тогда

Юзп+1- 1 = (l03rt)3- 13 = (юЗЛ— i)(io2-8" + 103"+1).

Первый сомножитель справа делится на Зл+2 по индуктивному предположению. Во втором же сомножителе мы можем заменить десятки на равноостаточные им при делении на 3 единицы; полученное число 3 показывает, что второй сомножитель делится на 3. Следовательно, все произведение делится на 3«+з — 3^+0+2^ что и требовалось.

г) При делении на а2— а+ 1, очевидно, а2 равноостаточно с а—1. Значит, а2я+1 + (а — 1)я+2 равноостаточно с

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

д) (л* —l)==(/i —1)(я*-1 + п*-* + ... + л + 1).

е) (я2'*1 + 1) — (п + 1) (п21 — п21-1 +... — /1+1).

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

Рассмотрим теперь произвольное число 6, не принадлежащее К. Если бы было b ~ с, где с — некоторое число из К, то было бы и b ~ а, чего, однако, не может быть по выбору Ь. Значит, ни одно из чисел, лежащих вне /С, не эквивалентно ни одному из чисел К. Следовательно, К есть класс эквивалентности, содержащий а.

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

24. Очевидно, среди чисел О, 1, m найдутся два, принадлежащие одному классу. Пусть этими числами будут k и /: k ~ I. Таких пар чисел из одного класса может оказаться, вообще, говоря, и несколько. Выберем ту из них, для которой

величина |£ —1\ будет наибольшей. Поскольку — I ~ — 7, мы, по условию, получаем

Далее, мы находим, что и при любом целом л

л(£-/)~0.

Наконец, при любом г

n(k — /) + r~r,

т. е. из а = о (mod Л — /) следует а ~ Ъ. Таким образом, классы отношения ~ содержат целиком классы вычетов по модулю т.

Для того чтобы классов ~-эквивалентности было m, необходимо, чтобы каждый класс ~-эквивалентности содержал не более одного класса вычетов и чтобы k — I = т.

25. а) Обе части сравнения и модуль можно разделить на одно и то же число (разумеется, отличное от нуля).

В самом деле,

ad=bd (mod md)

означает, что

ad-bd = (a-b)d\md,

т.е. (a — b) : m, откуда a ss ö(modm).

б) Обе части сравнения можно разделить на число, взаимно простое с модулем.

Действительно, если d и m взаимно просты, то из

ad^bd (mod m),

т.е. из (а — b)d\mf следует на основании теоремы 12, что (а — Ь) \ m, что и требовалось.

26. Предположим, что

1^£</^эр — !, kaz=xla (mod р).

Это значит, что (/ — k)a\ р. Поскольку а не делится на р, должно быть (/ — k) * р. Но и этого не может быть, так как О < / — k < р.

27. Необходимость. Пусть число р простое. Возьмем О < q < р. Среди чисел я, 2q, (р—\)q найдется ровно одно, дающее при делении на р в остатке единицу. Пусть этим числом будет qq:

$<7==1 (modp). (Р.б)

С другой стороны, среди чисел q, 2q, (р— 1)^ также может быть лишь одно, дающее при делении на р в остатке единицу. Это, как уже установлено, число qq.

Выясним, в каких случаях q = q. Во всех таких случаях сравнение (Р.б) переписывается так:

<?2==1 (mod р),

или, что то же самое,

q2 — 1=0 (mod р).

Это значит, что

Ввиду того, что число р простое, по теореме 13 должно быть либо (<7+1):Р, либо (q—1) : р. Так как число q заключено между нулем и р, первый из этих случаев возможен лишь при <7 = р—1, а второй —при q = 1. Таким образом, при р = 2 и р = 3 всегда q = q, при р ^ 5 — лишь в случаях q = 1 и я = р— 1-

Следовательно, при р ^ 5 все оставшиеся числа 2, ...» р—2 можно объединить в такие (р —3)/2 пары, что произведение чисел, составляющих каждую из пар, при делении на р дает в остатке 1. Выпишем сравнения вида (Р.6) для всех таких пар, добавив в этот список сравнение

р — \=р — 1 (mod р),

и перемножим все (р—1)/2 полученных сравнений почленно.

В результате такого умножения мы получим слева произведение всех чисел от 2 до р— 1, а справа р— 1:

2-3 ... (р— 1)=р— 1 (modр)9

или

1.2-3 ... (р- 1) + 1=0 (mod р). Последнее сравнение означает, что

(1-2...(р-1) + 1):Р.

а это и требовалось.

Остается проверить случаи р = 2 и р = 3. Но для них, очевидно, (1 + 1) : 2 и (2+ 1) : 3.

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

р = Plp2.

Если pi ф р2, то и pi и р2 входят сомножителями в произведение 1-2...(р—1), которые тем самым делятся на р.рг, т.е. ца р. Пусть теперь р4 = рг — q. Тогда р = q2 (т. е. р есть квадрат простого числа). Если q > 2, то р > 2q, и в произведение Ь2...(р—1) входят множителями q и 2q, так что в этом случае оно делится на q2, т. е. на р. В обоих случаях 1*2...(р — 1)+ 1 на р делиться не может. Наконец, если р = 4, то 1 -2-3 — 1 = 5, и на 4 не делится.

28. Теорема. Пусть m = р^1р^2 • • • Pkk — каноническое разложение т. Тогда для того чтобы числа А и В были равноостаточными при делении на m, необходимо и достаточно, чтобы они были равноостаточными при делении на р/, на р22, на

Доказательство. Необходимость. Равноостаточность А и В при делении на m означает (А — В) \ пг. Тем более

(Л — B)\ptl (i = 1, ..., k), и числа А и В оказываются равноостаточными при делении на все р^ *.

Достаточность. Пусть числа А и В при делении на каждое pi равноостаточны. Обозначим через п остаток от деления А и В на р"' (/ = 1, 2, k). Это значит, что

A=rt (mod p*1). (Р.7)

Положим, далее,

m -it

-—^т^ t=\t k,

Pi1

и умножим в сравнении (Р.7) обе части и модуль на m/: Ami = miri (mod m).

Сложив все такие сравнения почленно, мы получим Л (mj + m2 + .,. + mk) = + m2r2 + ... + ткгк (mod m).

(P.8)

Ввиду равноостаточности A и В при делении на p"1, p"*» • • • ...,pftR мы получаем также £ (mj + m2 + ... + mk) = mirl + m2r2 + ... + ткгк (mod m).

(P.9)

Вычтя почленно сравнение (Р.9) из (Р.8), мы имеем (Л — В) (т{ + т2 + ... + wÄ)=0 (mod m),

т. е. (Л — В) (mi + m2 + ... +mk) \ т.

Но сумма mi + т2 + ... +т* взаимно проста с т. В самом деле, если бы она имела с m некоторый общий простой делитель р, то он входил бы в каноническое разложение m, т. е. имел бы вид pi. Но тогда на него делилась бы как вся сумма, так и каждое слагаемое, кроме одного, m/, а этого быть не может.

Теперь мы можем применить теорему 12, которая даст, что (Л — В) I т, т. е. числа Л и В при делении на m равноостаточны.

29. а) Выпишем систематически все равенства, описывающие деления с остатком, которые составляют применение алгорифма Евклида к числам а и Ь:

(Р.10)

Мы имеем rn-t \ гп. Вместе с гп-г = rn-iqn-i + гя, это дает нам Гп-2 : гп. Продвигаясь аналогичным образом вверх по систем^ равенств (Р.10), мы получаем, наконец, что а\гп и b \ гп. Зна* чит, гя есть общий делитель а и Ь,

Пусть d — любой общий делитель а и Ь. Вместе с а =* t= bq0 + ri это дает нам п • d. Продвигаясь по системе равенств (Р. 10) вниз, мы будем последовательно получать, что г г \ d, Гг\ d, ..., rn \ d. Значит, гп делится на любой общий делитель а и Ь, являясь тем самым наибольшим общим делителем этих чисел.

б) Доказательство ведется по индукции. Полагая Ао = 0, Во = 1, Ai == 1, Bi = —<7о, мы имеем г0 = b = аА0 + ЬВ0 и fi = aAi + 62?i.

Пусть теперь

Но тогда

и нам остается положить

Числа Ап и Вп окажутся искомыми А к В.

30. Если b и с взаимно просты, то по предыдущему можно найти такие целые В и С, что ЬВ + сС=\, или, после умножения на а, ab В + асС = а; ab • с по условию; а£ • с очевидным образом; значит, и а \ с.

31. Ограничимся рассмотрением признака равноостаточности при делении на 8.

Пусть произвольное натуральное А представлено в виде 1000а + ft, где 0 ^ b < 1000 (т. е. о —трехзначное число, которым оканчивается Л), и о, если А ^ 1000, остатку от деления А на 8, если 8 ^ А < 1000, не определено, если А < 8.

32. Ограничимся рассмотрением признака равноостаточности при делении на 18 в двенадцатеричной системе счисления.

Пусть А представлено в виде 144а + 6, где 0 <i b < 144 (т. е. & — двузначное в двенадцатеричной системе счисления число, которым оканчивается записанное в этой системе число Л), и Ь, если А ^ 144,

остатку отделения Л на 18, если 18 ^ А < 144, не определено, если А < 18.

Проверка того, что процесс построения последовательности Л, /(Л), /(/(Л)), ... действительно является признаком равноостаточности, осуществляется стандартно.

35. Для тех m, у которых каноническое разложение имеет вид 2а-5&.

34. Условия а) и б) выполняются автоматически. Поскольку при делении на 3 числа 10 и 1 равноостаточны, равноостаточными же должны быть и числа Л и /(Л). Наконец, то, что /(Л)<Л при А ^ 3, устанавливается простым подсчетом.

35. а) /(858773) = 38; f(38)= 11; /(11)= 2.

б) /(Л) = 4444-4 = 17776; /(17776)= 28; /(28) = = 10; /(10)= 1.

36. Признак равноостаточности при делении на 9 аналогичен рассмотренному признаку равноостаточности при делении на 3.

Для получения признака равноостаточности при делении на 11 представим число А в виде

где 0 ai < 100. Очевидно, такое представление соответствует разбиению числа на двузначные «грани» (справа налево). Пусть

остатку от деления Л на 11, если 11 ^Л < 100, не определена, если А< 11.

Нам остается указать, что числа Л и /(Л) действительно равноостаточны при делении на 11 и, кроме того, /(Л)< Л.

Другой признак равноостаточности при делении на 11 получается на основе представления числа Л в виде

Л — 10"^ + 10п-1ап_г + . •. + 10а! + а0

и использования того, что 10 при делении на 11 равноостаточно с —1, а 100 — с 1. Поэтому Л равноостаточно с числом а0—ai+ 02 — a3+... ± ал, и формулировка соответствующего признака равноостаточности не составляет труда.

Наконец, можно, разбивая число А на трехзначные «грани», представить его в виде

103Х + 103*-Зая_, + ... + \03а{ + а0

(О at < 1000). Тогда А при делении на 37 равноостаточно с суммой а0 + ai + ... + ап, а при делении на 7, 11 и 13 — со знакопеременной суммой а0 — — а\ + а2 — ...±аЛ.

37. Для примера рассмотрим признак равноостаточности на 8 в троичной системе счисления. Представим для этого произвольное А в виде

ап32п + ап_{32(п-1)+ ... + а{Ъ2 + а0, где 0^а,<9.

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

Яо + яi + • • • + ял, если А ^ 9, 0, если А = 8,

не определено, если А < 8,

и провести стандартные рассуждения.

38. В шестеричной системе счисления: 5 (k = 1), 7 (£ = 2), 43 (£ = 3);

В семеричной системе счисления: 2, 3, 6 (£ = 1),

4, 6, 12, 16, 24 (£ = 2), 171 (£ = 3);

В девятеричной системе счисления: 2, 4, 8 (k = 1),

5, 10, 20, 40 (k = 2), 7, 13, 14, 26 и т. д. (ft = 3);

В тринадцатеричной системе счисления: 2, 3, 4, 6 (ft= 1), 7, 14, 21 и т. д. (ft = 2).

39. В троичной системе счисления: 2, 4 (ft=l), 8, 12, 24 (ft = 2), 13, 26 (ft = 3), 41 (ft = 4);

В пятеричной системе счисления: 2, 3, 6 (ft = 1), 8, 12, 24 (ft = 2), 31 (ft = 3);

В восьмеричной системе счисления 3, 9 (ft=l), 5, 13 (ft = 2);

В десятичной системе счисления: 11 (ft=l), 101 (ft = 2), 7, И, 13 (ft = 3).

40. Если числа а и b равноостаточны, то (а — Ь) - т. Поэтому в силу теоремы 6 числа а я b делятся или не делятся на m одновременно.

Числа 4 и 5 равноделимы, но не равноостаточны при делении на 3,

41. Пусть из равноделимости на m следует равноостаточность при делении на т. Это значит, что все не делящиеся на m числа имеют при делении на m один и тот же остаток. Значит, этот остаток должен быть равен единице, так что га = 2.

42. Отношение равноделимости на m, очевидно, является рефлексивным (всякое число равноделимо на m с самим собой), симметричным (если а равноделимо с b, то и b равноделимо с а) и транзитивным (если а равноделимо с by a b равноделимо с с, то и а равноделимо с с).

Следовательно, это и есть отношение эквивалентности. При этом в один класс попадают все числа, делящиеся на m, а в другой — все не делящиеся на т.

43. Нетрудно проверить, что при m > 2 равноделимость сумм не следует из равноделимости слагаемых.

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

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

Наоборот, если число р составное, то произведения равноделимых сомножителей могут уже равноделимыми не быть. Достаточно положить р = р\р2 (pi Ф 1, р2 Ф 1). Тогда числа 1 и pu а также числа 1 и р2 равноделимы на р, а произведения Ы и ргрг» очевидно, нет.

44. Непосредственное следствие задачи 36.

45. Выполнение условий а) и б) очевидно.

Если, далее, а — 26=^0, то, очевидно, f(A)<mA. Если же а — 2Ь < 0, то это неравенство может и нарушиться. При этом наибольшее значение модуля \а — 2bI достигается при а=0 и 6 = 9 и равно 18. Следовательно, при А ^ 19 должно быть /(Л)<Л. Справедливость этого неравенства при меньших значениях обеспечивается определением функции /,

Наконец, 10а + 6 равноделимо на 7 с 50а + 56 (ибо числа 5 и 7 взаимно простые) и тем самым с 50а + 56 — 7(7а + 6) = а — 2Ь.

46. Число 15 при делении на 7 дает в остатке 1, а 1 — 2 • 5 = —9 дает в остатке 5.

47. Условие в) f(A)<A означает а + 46< <10а + 6, т. е. ЪЬ < 9а. Поэтому при а ^ 4 нужное условие выполняется.

Условие г) очевидно, 10а + 6 при делении на 13 равноделимо с 40а + 46, a последнее число равноостаточно с а + 46.

48. Признак делимости утратит результативность, так как/(39)= 39.

49. Пусть нам нужно построить признак делимости на некоторое т. Постараемся подобрать такое 5, взаимно простое с m и по возможности небольшое, что (105+ 1) : m (так было в случае т = 7; s оказалось равным 3) или же (105—1):т (например, при m =13, 5 = 4).

В первом из этих случаев А = 10а + 6 равноделимо на m с

10а5 + б5 = (105+ 1)а —а + 65, т. е. с а — Ô5, a во втором — с

т. е. с а + bs.

В связи со сказанным число 10а+ 6

при делении на 17 равноделимо с а —56,

» 19 » а+ 26,

» 23 » а+ 76,

» 29 » а —36,

» 31 » а+ 36.

Завершение точных формулировок этих признаков делимости предоставляется читателю.

50. а) Так как 100 при делении на 49 равноостаточно с 2, всякое число вида

Ю2Пап + 102Л-2аЛ_! + ... + 102а! + Оо (0 ^ а, < 100) при делении на 49 равноостаточно с

б) 10а+ 6 при делении на 49 равноделимо с а+ 56.

51. Очевидно, при А ^6 должно быть f(A)<.A.

52. а) В семеричной системе счисления представление А в виде 7а + 6 дает, что при делении на 5 число А равноделимо с а + 36;

б) В одиннадцатиричной системе счисления представление А в виде Па+ 6 дает, что при делении на 7 число А равноделимо с а + 26;

в) В двенадцатиричной системе счисления, представляя А в виде 12а + 6, получаем, что при делении на 17 число равноделимо с а — 76.

53. Условия а) и б) выполняются автоматически. Условия в) и г) соблюдаются потому, что переход от А к F (А) сводится к замене некоторых чисел на их остатки при делении на А (которые меньше самих чисел и равноостаточны с ними).

55. Предоставляется читателю.

56. Возьмем произвольное m и положим

т\ равным остатку от деления t на m, г2 » » » tri на m

и т. д. Тогда число

при делении на m равноостаточно с числом

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

57. Предоставляется читателю.

58. 102 = 7-14 + 2, так что г = 2, и мы имеем

59. Если / равноостаточно с г—г\ при делении на т9

то

и т. д.

60. Ни 24 —2, ни 23— 1 не делятся на 4.

61. Если а-р, то а*-/?, и теорема доказана. Если же а не делится на р, то а взаимно просто с р, и мы можем приведенное в условии теоремы сравнение сократить:

ар-1ш*1(тоер).

Для доказательства последнего сравнения разделим каждое из чисел вида ta (/=1, 2, р — 1) на р с остатком:

ta = qtp + rt. Это можно переписать так:

(РЛ1)

Из результата задачи 26 следует, что среди чисел ft ровно по одному разу встретится каждое из чисел 1, 2, р — 1. Перемножая все сравнения, мы получаем

1 • 2 .. . (р - 1) ар~1 шш 1 . 2 ... (р - 1 ) (mod р). Нам остается это сравнение сократить на 1-2

63. Будем искать m в виде р"1р°2 • • • Рьк* Тогда

Юр?'-1 (Pl -1)1 (а- О • • • рТ1 (р*-1) = ю.

Стоящее слева произведение должно делиться на 5. Значит, либо одно из чисел ри Р2, ...» Pk есть 5 (пусть для определенности р\ — 5), либо на 5 делится

одна из разностей р\ — 1, р2— 1, .Pk—1 (пусть в этом случае (pi— 1) :5). В первом из этих случаев pi — 1=4, чего не может быть, так как 10 на 4 не делится. Второй случай, поскольку р\ должно быть простым числом и 10 -(pi — 1), возможен лишь при pi = 11. Но тогда ai = 1, и из теоремы 25 следует, что

т. е. либо -тг = 1> либо

В итоге мы имеем

Если m нечетное, то ai = a2 = ... = а* = 1 (ибо правая часть написанного равенства есть степень двойки):

(Р1-1)(Л-1)...(рА-1)-8.

Это возможно лишь при k = 2, pi = 3, р2 = 5, т. е, при m = 15.

Пусть теперь число m — четное. Положим для определенности pi = 2. Очевидно, по-прежнему а2 = ... = а* = 1, и мы имеем

2a-1(P2~l)...(pÄ-l) = 8.

Очевидно, а ^ 4. Если а = 1, то случай подобен рассмотренному: написанное неравенство возможно также лишь при k = 3, р2 = 3, рз = 5, т. е. при m = 30,

Если a = 2, то k = 2, р3 = 5 и m = 20.

Если a = 3, то k = 2, р2 = 3 и m = 24.

Если, наконец, a = 4, то k = 1 и m = 16.

Итак, решения нашей задачи: гп\ = 15, т2 = 30, гпз = 20, т4 = 24, т5 = 16.

£4. Предположим, что

(Pi - О РГ ' (Р2 - 1) - - • РГ1 (Р* - 1) = И.

Каждое из чисел вида р.- — 1 есть либо единица, либо четное число, и потому не может быть семеркой. Будучи на единицу меньше простого числа, оно не может равняться 14. Значит, семеркой является одно из чисел р*г\ Но тогда р.— 1 = 6, а 14 на 6 не делится.

65. Пусть m — p*lpl2... pi*. Рассмотрим сначала случай, когда m есть степень простого числа: m = = ра. Для того чтобы некоторое число было взаимно простым с m, необходимо и достаточно, чтобы оно не делилось на р. Но среди чисел 0, 1, 2, m—1 имеется всего — делящихся на р чисел. Следовательно, взаимно простых с р чисел в этом списке имеется столько:

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

По только что установленному число остатков от деления на р"', взаимно простых с р"', равно ф(р?*). Но, как было выяснено в процессе решения задачи 28, из равноостаточности чисел при делении на все р*1 следует их равноостаточность при делении на m, и наоборот. Кроме того, для взаимной простоты некоторого числа с m необходимо и достаточно, чтобы оно было взаимно просто с каждым из чисел р*1.

Следовательно, каждой комбинации остатков от деления на р"1, р\2, pakk, взаимно простых с соответствующими делителями, соответствует ровно один остаток от деления на m, взаимно простой с т. Нам остается заметить, что число таких комбинаций остатков равно

66. Мы имеем

Поэтому

Здесь по теореме Эйлера первое слагаемое при делении на mim2 равноостаточно с Л, а второе делится

на т\тъ Значит, вся сумма при делении на т\т2 равноостаточна с Л.

67* Предоставляется читателю.

68. Предоставляется читателю.

69. Предоставляется читателю.

70. п1* — п = п{п12—\). Но

п 12 _ пф (13) _ п2ф (7) _ п3ф (5) _ п6ф (3) _ п12ф (2)в

Поэтому либо п ; р, либо (/I12 — 1) ; р для р = 2, 3, 5, 7, 13. Остается сослаться на теорему 16. 7L Предоставляется читателю.

72. Предоставляется читателю.

73. Пусть наибольший общий делитель чисел а и b есть d. Если с не делится на d, то уравнение

ах + Ьу = с

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

74. Пусть А и В таковы, что

аА + ЬВ=1.

Положим

Тогда

и (xt,yt) действительно является решением нашего уравнения.

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

В самом деле, мы можем написать:

или, полагая мы получаем

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

б) Воспользуемся тем, что 25 по модулю 13 принадлежит показателю 2. Мы можем написать:

или, после упрощений,

76. Условие в) обеспечивается автоматически, а условие г) следует из теоремы 25.

78. Предоставляется читателю.

79. Предоставляется читателю.

80. а) в**21*-1 = 8П = 645-8. При делении на 21 это число равноостаточно с 8. Значит, числа 8а + Ь и а + 86 равноделимы на 21.

б) 12<р<31>-1 = 1229 = (122)14-12 = 14414-12 при делении на 31 равноостаточно с 1114» 12 = 1217« 12 = = (—З)7-12 = —(33)2-3.12 = —(31 — 4)2(31 + 5), что равноостаточно с —16-5 = —80. Последнее число очевидно равноостаточно с 13. Значит, числа 12а+ 6 и а+ 136 равноделимы на 31«

СОДЕРЖАНИЕ

Предисловие .............. 3

§ 1. Делимость чисел . . . . ....... 7

§ 2. Делимость сумм и произведений ..... 24

§ 3. Признаки равноостаточности и признаки делимости............. 31

§ 4. Общие признаки равноостаточности и делимости ............... 48

§ 5. Делимость степеней.......... 53

Доказательства теорем.......... 61

Решения задач............. 72

Николай Николаевич Воробьев

ПРИЗНАКИ ДЕЛИМОСТИ

(Серия: «Популярные лекции по математике»)

М., 1980 г., 96 стр. с илл.

Редакторы Ф. И. Кизнер и Т. Л. Панькова Техн. редактор Л. В. Лихачева Корректор Н. В. Румянцева

ИБ № 11602

Сдано в набор 18.03.80. Подписано к печати 01.09.80 < Бумага 84X108%, тип. № 3. Литературная гарнитура. Высокая печать. Условн. печ. л. 5*04. Уч.-изд. д. 5* Тираж 200 000 экз. Заказ № 581. Цена книги 15 коп.

Издательство «Наука» Главная редакция физико-математической литературы 117071, Москва, В-71, Ленинский проспект, 15

Ленинградская типография № 2 головное предприятие ордена Трудового Красного Знамени Ленинградского объединения «Техническая книга» им. Евгении Соколовой Союзполиграфпрома при Государственном комитете СССР по делам издательств, полиграфии и книжной торговли. 198052, г.Ленинград, Л-52, Измайловский проспект, 29

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

117071, Москва, В-71, Ленинский проспект, 15

ГОТОВЯТСЯ К ПЕЧАТИ в 1981 г. в серии «Популярные лекции по математике»:

Беран Л. Упорядоченные множества: Пер. с чешск. Под ред. Л. А. Скорнякова.

Книга содержит популярное изложение важнейшего для современной математики понятия частично упорядоченного множества. Рассмотрены понятия точной верхней и точной нижней грани, введены структуры (решетки), рассмотрены алгебраические свойства операций взятия точных граней, введены дистрибутивные структуры. Изложение оживлено многочисленными примерами «из жизни». Для закрепления изученного материала предлагаются интересные упражнения.

Для учащихся старших классов средней школы и студентов младших курсов вузов.

Успенский В. А. Теорема Гёделя о неполноте

Брошюра посвящена одному из наиболее замечательных достижений математической логики — теореме Гёделя о неполноте фомальной арифметики.

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

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

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

ПОПУЛЯРНЫЕ ЛЕКЦИИ ПО МАТЕМАТИКЕ

Вып. 1. А. И. Маркушевич. Возвратные последовательности.

Вып. 2. И. П. Натансон. Простейшие задачи на максимум и минимум.

Вып. 3. И. С. Соминский. Метод математической индукции.

Вып. 4. А. И. Маркушевич. Замечательные кривые.

Вып. 5. П. П. Коровкин. Неравенства.

Вып. 6. Н. Н. Воробьев. Числа Фибоначчи.

Вып. 7. А. Г. Курош. Алгебраические уравнения произвольных степеней.

Вып. 8. А. О. Гельфонд. Решение уравнений в целых числах.

Вып. 9. А. И. Маркушевич. Площади и логарифмы.

Вып. 10. А. С. Смогоржевский. Метод координат.

Вып. 11. Я. С. Дубнов. Ошибки в геометрических доказательствах.

Вып. 12. И. П. Натансон. Суммирование бесконечно малых величин.

Вып. 13. А. И. Маркушевич. Комплексные числа и конформные отображения.

Вып. 14. А. И. Фетисов. О доказательствах в геометрии.

Вып. 15. И. Р. Шафаревич. О решении уравнений высших степеней.

Вып. 16. В. Г. Шерватов. Гиперболические функции.

Вып. 17. В. Г. Болтянский. Что такое дифференцирование?

Вып. 18. Г. М. Миракьян. Прямой круговой цилиндр.

Вып. 19. Л. А. Люстерник. Кратчайшие линии.

Вып. 20. А. М. Лопшиц. Вычисление площадей ориентированных фигур.

Вып. 21. Л. И. Головина и И. М. Яглом. Индукция в геометрии.

Вып. 22. В. Г. Болтянский. Равновеликие и равносоставленные фигуры.

Вып. 23. А. С. Смогоржевский. О геометрии Лобачевского.

Вып. 24. Б. И. Аргунов и Л. А. Скорняков. Конфигурационные теоремы.

Вып. 25. А. С. Смогоржевский. Линейка в геометрических построениях.

Вып. 26. Б. А. Трахтенброт. Алгоритмы и машинное решение задач.

Вып. 27. В. А. Успенский. Некоторые приложения механики к математике.

Вып. 28. Н. А. Архангельский и Б. И. Зайцев. Автоматические цифровые машины.

Вып. 29. А. Н. Костовский. Геометрические построения одним циркулем.

Вып. 30. Г. Е. Шилов. Как строить графики.

Вып. 31. А. Г. Дорфман. Оптика конических сечений.

Вып. 32. Е. С. Вентцель. Элементы теории игр.

Вып. 33. А. С. Барсов. Что такое линейное программирование.

Вып. 34. Б. Е. Маргулис. Системы линейных уравнений.

Выи. 35. Н. Я. Виленкин. Метод последовательных приближений.

Вып. 36. В. Г. Болтянский. Огибающая.

Вып. 37. Г. Е. Шилов. Простая гамма (устройство музыкальной шкалы).

Вып. 38. Ю. А. Шрейдер. Что такое расстояние?

Вып. 39. Н. Н. Воробьев. Признаки делимости.

Выл. 40. С. В. Фомин. Системы счисления.

Вып. 41. Б. Ю. Коган. Приложение механики к геометрии.

Выи. 42. Ю. И. Любич и Л. А. Шор. Кинематический метод в геометрических задачах.

Вып. 43. В. А. Успенский. Треугольник Паскаля.

Вып. 44. И. Я. Бакельман. Инверсия.

Вып. 45. И. М. Яглом. Необыкновенная алгебра.

Вып. 46. И. М. Соболь. Метод Монте-Карло.

Вып. 47. Л. А. Калужнин. Основная теорема арифметики.

Вып.. 48. А. С. Солодовников. Системы линейных неравенств.

Вып. 49. Г. Е. Шилов. Математический анализ в области рациональных функций.

Вып. 50. В. Г. Болтянский, И. Ц. Гохберг. Разбиение фигур на меньшие части.

Вып. 51. Н. М. Бескин. Изображения пространственных фигур.

Вып. 52. Н. М. Бескин. Деление отрезка в данном отношении.

Вып. 53. Б. А. Розенфельд и Н. д. Сергеева. Стереографическая проекция.

Вып. 54. В. А. Успенский. Машина Поста.