@
БИБЛИОТЕЧКА .КВАНТ.
ВЫПУСК 3
О.ОРЕ
приrЛАШЕНИЕ
в ТЕОРИЮ
ЧИСЕЛ
I1еревод с анrлийскоrо
л. А. САВИНОй и А. п. САВИНА

МОСКВА НАУКл.
r ЛАВНАЯ РЕДАКЦИЯ
ФИЗИК О-МАТЕМАТИЧЕСКОй ЛИТЕРАТУРbI
1980

22.131
065
у ДI( 51 J
р Е Д А К I{ 11 О Н Н А Я К О Л Л Е r 11 Я:
Ан:аеМИI{ и. К. КИКОИН (председателъ), академик А. Н. Ко.л-
MOFOpOB (заместитель председателя), кандидат физ.мат. наук
и. ш. С.лооодеuкий (ученый секретарь), членкорреспондент
АН СССР А. А. Абрикосов, акадеМИf< Б. К. Вайнштейн, заслужеи-
вый учитель РСФСР Б. В. Воздвиженскии, академик В. М. rЛУПI-
КОВ, академик п. Л. Капица, профессор с. п. Капица, членкор-
респондент АН СССР ю. А. Осипьян, член-корреспондент АПН
...СССР В. r. Разумовский, акадеМИI{ Р. 3. Саrдеев, кандидат ХИМ.
наук 1\'\. л. СМОJ1ЯНСКИЙ, профессор Я. А. СМОРОДИIfСКИЙ, академик
с. Л. Соболев, член-корреспондент АН СССР д. К. Фаддеев,
леН-КGрреспондснт Ali СССР и. с. ШКЛОВСКИЙ.
Оре о.
065 Приrлашение в теорию чисел: Пер. с анrл.
J\\.: Наука. rлавная редакция физико-математи--
ческо'й литерйrуры, -198('.  128 с илл.  (Библио-
'Течка «Квант». Вып. 3): 30 К.
Кпиrа Известноrо норвежскоrо м атем ати !{а о. Оре раскрывает
красоту математики на примере одноrо НЗ ее старейших разделов.......
теории чисел. Изложение основ теории чисел в книrе во MHorOM не-
традиционно. Наряду с теорией сравнений, сведениями о' системах
счисления, в ней содеР1l<атся рассказы о маrических квадратах,
о решеНИlI арифметических ребусов и т. д. Большим достоинством
Jшиrп являет{'я то, что автор при каждом удобном случае указывает
на :возможности практическоrо применения изложенных резу,nьта-
ТОВ, а также знакомит читателя с современным состоянием еОРИJI
Чисе.'1 н эадаqами. еще не ПОЛУ'JИВIПИМIf окончательиоrо решения.
20203 ---- 08 t
О 053(02)-80 90-80.1702030000
ББК22.1Зf
517.1
20203081
О 053(02)80 9080. ]702030000
@ Ilздате,rlЬСТВО «Наука:..
rлзвная редаJ(ЦИЯ
фиэикоматематвческоА
литературы, nepeBnA
на русский язык. 1980

or л А 8Л'Е Н.И Е
От переводqИЕ<ОВ 7
r л а в а 1. ВВЕДЕНИЕ 9
 1. История 9
 2. Нумеролоrия 9
 3. Задача Пифаrора 10
 4. Фиrурные числа 12
 5. Маrические квадраты 15
r л а в а 2. ПРОСТЫЕ ЧИСЛА 23
 1. Простые и составные числа 23
 2. Простые числа Мерсенна 26
 3. Простые числа Ферма 29
 4. Решето Эратосфена 32
r JI а в а 3. ДЕЛИТЕЛИ ЧИСЕЛ 35
 1. Основная теорема о разложении на множители 35
 2. Делители 3
 3 Несколько задач о делнтелях 40
 4. Совершенные числа 42
9 5. Др ужественные числа 44
r л а в а 4. НАИБОЛЬШИй ОБЩИй ДЕЛИТЕЛЬ {1 HAI1-
МЕНЬШЕЕ ОБЩЕЕ КРАТНОЕ 41
 1. Наибольший общий делите,,'1Ь 41
 2. Взаимно простые числа 4g
 3. Алrоритм ЕвктIда 51
 4. Наименьшее общее кратное 54:
r л а в а 5. ЗАДАЧА ПИФАrОРА 57
 1. Предварительные замечания 51
 2. Решение задачи Пифаrора 58
 3. Несколько задач о !руrольниках Пифаrора 61
r л а в а 6. СИСТЕМВI СЧу!СJ}ЕНИЯ 7()
 1. Числа 70
 2. Друrие системы 71
 3. Сравнение систем счисления 75
 4. Некоторые задачи, связанные с системами сqисления 80
' 5. Компьютеры и их системы счисления 83
 6. Иrры с числами 85
Б

l' л а в а 7. СР АВНЕIИЯ 90
 1. Определение сравнения 90
 2. Некоторые свойства сравнений 91
 3. Алrебра сравнениЙ 94
 4. Возведение сравнений в степень 96
 5. Теорема Ферма 99
r л а в а 8. НЕКОТОРЫЕ ПРИМЕНЕНИЯ СРАВf1ЕrIIlй 103
 1. Проверка вычислениЙ 103
 2. Дни недели 108
 3. Расписания соревнований 114
Э 4. Простое или составное? 117
РЕШЕНИЯ :VIЗБРАННЫХ ЗАДАЧ
ЗАКЛЮЧRНИЕ
120
127

от ПЕРЕВОДЧИКОВ
IV. ""
Имя о. Оре (1899 1968) хорошо извест-
но у нас в стране. Две ero книrи по теории rрафов,
переведенные на русский язык (о. Оре. Теория rpa
фОВ.  М.: Наука. 1968 и [рафы и их пр именение. 
М.: Мир, 1965) были тепло встречены читателями в
СССР. С большим интересом был принят и перевод
ero книrи о Нильсе Абеле (о. Оре. Замечательный
математик Нильс Хенрик Абель.  М.: Физматrиз,
1 961. )
Предлаrаемая читателю книrа о. Оре «Приrла-
u
шеиие в теорию чисел» относится к чрезвычаино ред-
костному типу научнопопулярных Книr. Как правило,
о
научнопопулярные книrи по математике имеют своеи
целью научить читателя чемулибо или дать ему
представление о той или иной ветви математики.
о. Оре не ставит перед собой ни той, ни друrой за
дачи. Ero цель  заинтересовать читателя математи
кои (а читателем предполаrается школьник 13
17 лет), привить ему вкус к этой древней, но вечно
о
юнои науке.
Оре рассказывает о маrических квадратах и чис-
ловых ребусах, вычислении дней недели и составлении
расписаний соревнований  вещах либо интриrую..
щих, либо имеющих реальное практическое значение.
В результате, если читатель и не захочет стать мате..
матиком (а ими становятся единицы), то он надолrо
сохранит впечатление п красоте математики, силе и
широте диапазона применениЙ ее на практике.
1

Написанная просто и доступно, эта книrа (за ис-
ключением нескольких страниц) мо)кет быть леrко-
прочитана школьником начиная с 56 класса. По..
СI\ОЛЬКУ ЭТОТ перевод адресован в первую очередь
ШКQльникаl\ll, то переводчики СОЧ.ЛИ необходимым пол..
ностъю сменить рекомендуемую литературу на книrи,
доступные ЭТОЙ каrеrории ЧJlтатеClТ"lей.

rЛ.ВА }
.......
ВВЕДЕНИЕ
 1. История
Теория чисел  это ветвь математпи:и,
и:м-еющая дело с lеЛbl;"tu положительными ЧllслаJ1,IU
1, 2, 3, ...,
Еоторые также называют натуральными Чllслаttl.
Археолоrия и история учат нас, что человек рано
начал считать. Сначала он научился складывать чис..
ла, потом, MHoro позже, умножать и вычитать их. Де...
JJение чисел было неоБХОДИlVIЫМ для распределения на
равные части кучи яблок или улова рыбы. Эти дей..
ствия над числами называютс,Я ВЫiluсленuямu. В не...
которых случаях последовательность вычисленпй
называют «калькуляцией». Это слово происходит ОТ
,лзтинскоrо calculus, 0значающеrо «маленькиЙ ка-
мень», поскольку римляне пользовались морской
rалькой при вычислениях на своих счетных досках.
Как только люди HeMHoro научились считать, этот
процесс стал приятным времяпровождением для lVfHO
rих людей, склонных к абстрактному теоретизирова
лию. Знания о числах накапливались в течение МНО'"
rих веков, порождая интерес к новым исследованиям,
которые в свою очередь приумножали эти накопле...
ния. И сейчас, в современной математике, мы имеем
величественную конструкцию, известную как теория
чисел. Некоторые части этой теории все еще состав..
ЛЯIQТ простые иrры с числами, а друrие относятся к
}-Jаиболее трудным и сложным разделам математики.
 2. Нумеролоrия
Некоторые следы размышлений очис..
лах в давние времена мо)кно обнаружить в суеверных
предрассудках, связанных с числаl\lИ. Среди чисел
9

есть «счастливые», KOTOpbIf\1 нужно отдавать пред..
почтение и радоваться при встрече с ними, и «не..
счастливые», которых ну}кно остереrаться, как дур"
Horo rлаза. Мы обладаем обширными сведениями
о flумеРОЛО2UU в античной [реции, мыслях и предрас-
судках, связанных с символическим значением различ-
ных чисел. Например, нечетные числа, большие еди-
ницы, символизировали мужское начало, а четные 
}кенское; таким образом, число 5  сумма epBoro
мужскоrо и первоrо женскоrо чисел  символизиро-
вало супружество или союз.
)Келающие познакомиться с более развитой «тео-
рией» маrических чисел MorYT сделать это, прочтя
восьмую книrу «Республики» Платона. Такая «наука»
мало что дает в смысле математических .идей, но она
содержит умение обращаться с числами и их своЙ-
ствами. Как мы дальше увидим, некоторые замеча..
тельные проблемы в теории чисел, до сих пор зани-
мающие ум.ы математиков, берут свое начало из rpe-
ческоrо учения о маrических числах.
До сих пор у нас нет оснований считать себя выше
предрассудков, связанных с числами. Вероятно, у ка..
2кдоrо есть знакомые, которые ни за что не посадят
за стол 13 rостей, а как мало в rостиницах США эта..
жей II комнат с номером 13. По существу, мы не
знаем, откуда взялись подобные «табу» на числа.
Существует множество всевозможных объяснений, но
большинство из них совершенно беЗОСНQвательны.
Например, в «Библии» записано, что на Тайной ве..
чере было 13 rостей, разумеется, тринадцатым был
lIуда. Если же заметить, что мноrие предметы счита..,
ются дюжинами, а число 13 дает «чертову дюжину»,
Т. е. лишний предмет, то это соображение имеет боль..
ший реальный с:r..1ЫСЛ.
В «Библии», особенно в «Ветхом Завете», особую
роль иrрает число 7, в древнеrерманском фольклоре
часто встречаются числа 3 и 9, индусы же, как видно
из их мифолоrии, неравнодушны к числу 10.
 3. Задача Пифаrора
Примеро:r..1 ранней теории чисел может
С.flужить задача Пuфа20ра. Как мы знаем, в прямо..
уrольном треуrольнике длины сторон удовлетворяют
10

соотношению Пифаrора
Z2 === х 2 + у2, (1 . З. 1 )
rде z  длина rипотенузы. Это дает возмо)кность в
прямоуrольном треуrольнике вычислить длину одной
стороны, если известны две друrие. Между прочим,
то, что эту теорему назвали в честь rреческоrо фило-
софа Пифаrора, не совсем справедливо: она была
известна вавилонянам почти за 2000 лет до Пифаrора.
Иноrда все длины сторон х, У, z в (1.3.1) выра-
жаются целыми числами. Простейший случай,
х==3, у==4, z===5, (1.3.2)
был найден на вавилонских rлиняных табличкаХI
Этому случаю можно дать следующее истолкование.
Предположим, что у нас
есть веревочное кольцо с
узелками или метками,
расположенными на рав-
ных расстояниях и деля-
щими кольцо на 12 ча-
стей. Тоrда, если мы рас-
тянем кольцо на трех ко-
лышках, вбитых на поле,
так, чтобы получился тре-
уrольник со сторонами 3 и 4, то третья сторона будет
иметь длину 5, а ПРОТИВОПОЛО)I{НЫЙ ей уrол будет пр я-
M"bIM (рис. 1). Часто можно прочесть в книrах по исто-
рии математики, что именно этот метод по{:троения
прямоrо уrла использовался еrипетскими землемера-
ми или «натяrивателями веревки» при размежевании
полей по окончании разлива Нила. Однако вполне
возможно, что это один из мифов, которых так MHoro
в истории науки; у нас нет документов, подтверждаю-
щих это предположение.
u
Существует MHoro друrих целочисленных решении
уравнения Пифаrора (1.3.1), например,
х == 5, у === 12, z === 13,
х === 7, у:=;: 24, z == 25,
х===8, у=== 15, z== 17.
z
Рис. 1.
Далее мы покажем, как можно получить все такие
решения. Способ находить их был известен древним
rpeKaM, а возможно, и вавилонянам.
11

Если даны два цеЛЬ1Х числа, х н у, то всеrда мож"
НО- найти соответствующее число- z, удовлетворяющее
уравнению (1.3.1)., но вполне B03l\'lO}{{HO, что Z будет
иррациональным ЧИСJ101. Если я{е потребовать, чтобь(
все три числа были цеЛЫl\1И, то тоrда ВО3МО}l(НОСТИ
существенно оrрани.чиваются. [реческий математ.ик
Диофант (время ero }кизни точно не известно, при..
близительно 200 r. нашей эры) написал книrу Arith
metica (<<Арифметика»), в которой рассматриваю1'СЯ
подобные задачи. С этоrо времени задача нахождения
целочпrленных или рациональных решений уравнений
j-Iазывается задачей Диофанта, а диофантов анализ 
ва}кная часть современной теории чисел.
С и с т е 1\'1 а з а Д а ч 1.3.
_. Попытаитесь найтп друrое решение уравнения
Пифаrора в целых числах.
2. Попытайтесь найти решения уравнения Пифа..
.ropa, в которых rипотенуза на единицу больше, че[\.{
бо,ньший из двух I<aTeToB.
э 4. Фиrурные числа
в теории чисел мы часто встречаемся с
квадратами, т. е. такими числами, как
32 === 9, 72 === 49, 102 === 100,
и аналоrично с кубами, т. е. таКИlVIИ числами, как
23 === 8, 33 === 27, 53 =:;=: 125.
Этот rеометрический образ
. рассматриваемой операции с
числами является частью боrа
Toro наследства, оставленноrо
древнеrреческими мыслителя
l\IИ. [реки предпочитали дy
мать о числах, как о rеометри"
че.ских величинах: произведе
иие с === а. Ь рассматривалось
как ПJ10щадь с прямоуrольника со сторонами а и Ь.
Также можно брlЛО рассматривать а. Ь как число то..
чек в прямоуrольной таблице с а точками на одной
стороне и Ь точками на друrой. Например, 20 == 4. 5
есть число точек в прямоуrольной таблице на рис. 2.
<1
.
.

о
.


r.t
()
у)

\J

Q
..)
(о
ф
(J
Рис. 2
12

Любое целое число, которое является IIроизведе..
ннеА1 двух целых чисел, можно было бы назвать пря..
.моуеОЛЬНblМ числом. I(оrда две стороны прямоуrоль-
ника имеют одну и ту }I{e длину, то такое число ив...
ляется квадратным числом, или квадрато.iИ. HeKOTO
рые чисда нельзя представлять в виде прямоуrольных
чtIсел иначе, как тривиальным способом  в виде
цепочки точек, лежащих в одном ряду. Например,
<nflTb' может быть представлено
как 'прямоуrольное число лишь ·
единственным способом, взяв
u
одну сторону равнои единице,
а друrую  пяти (рис. 3). Та-
кие числа rреки называли npOCTbl.Atu числами. Точка,
взятая в одном экземпляре, не рассматривалась как
число. Число 1 явилось тем кирпичом, из KOToporo
строились все остальные числа. Таким образом, 1 не
была для них и не считается сейчас простым числом.
Можно было бы рассматривать точки, раВНОJ.лерио
заполняющие не только прямоуrольники и квадраты,
.
.
.
.
Рис. з.
.
.
.e
. .'-' ...
. . ................ ................e. ................ ...
1 3 Б 10
Рис. 4.
но н друrие rеометрические фиrуры. Последователь-
ные треусольные числа изображены на рис. 4.
В общем случае ne треуrольное число задается
формулой
1
Т n == 2 n (п + 1), n == 1, 2, 3, ... (1.4.1)
у этих чисел масса интересных свойств: например,
сумма двух последовательных треуrольных чисел ЯВ-
ляется квадратом
1+3==4, 3+6===9, 6+10==16 и Т. д.
(1.4.2)
13

Обобщением треуrольных чисел и квадратов яви
лись мноrоуrольные числа. Метод их получения про-
иллюстрируем на примере пятиуrольных чисел. Для
этоrо рассмотрим рис. 5.
..""
· 7 .""
./ "
./ 1 -"" "'-
./ /. " о
\/. ./. >;1
/ / ')/i .
. I / /
V// . . .
Рис. 5.
r лядя на Hero, леrко найти несколько первых пя:..
тиуrольных чисел,
1, 5, 12, 22, 35.
(1.4 3)
Можно показать, что n-е пятиуrольное число вы-
ражается формулой
Рn== ; (зп2п). (1.4.4)
Шестиуrольные числа, и вообще k..уrольные числа,
аналоrично определяются с помощью правильноrо
k-уrОЛЬНl1ка, и мы не будем больше тратить времени
на их обсуждение. Фиrурные числа, особенно тре...
уrольные, пользовались большой популярностью при
изучении чисел в конце эпохи Возрождения, после
Toro как rреческая теория чисел проникла в Запад-
ную Европу. И сейчас их можно иноrда встретить
в статьях по теории чисел. .
Проводя анализ TaKoro rеометрическоrо представ-
,ления чисел, можно получить несколько простых со...
отношений. Остановимся лишь на одном примере.
Уже давно было известно, что складывая последова
14

тельно нечетные числа, мы все время будем получать
квадраты, например,
1 + 3 === 4, 1 + 3 + 5 === 9, 1 + 3 + 5 + 7 === 16 и Т. д.
Чтобы доказать это соотношение, достаточно лишь
взrлянуть на рис. 6, на котором изображены после-
довательно вложенные квадраты.
с и с т е м а з а Д а ч 1.4.
1. Дока)ките по индукции общую формулу (1.4.1)
для треуrольных чисел.
2. Докажите формулу (1.4.4) для пятиуrольных
чисел.
3. Докажите, что произвольное k-уrольное число
выражается формулой
1
2" k (п 2  п)  п 2 + 2п.
9 1I
f 1
i i
1 1
i 1
..... i
..
Если вы
иrрали в «шафлборд» *),
вы можете вспомнить, что
девять квадратов, на ко-
торых вы размещаете
свои фишки, занумерова-
ны числами от 1 до 9,
расположенными так, как
на рис. 7. Здесь числа в
каждом столбце и в ка-
ждой строчке, а также в каждой из диаrоналеЙ, дают
при сложении одно и то }ке число 15.
В общем случае маzuческuм квадрато},1, является
расположение чисел от 1 до п 2 в виде квадрата так,
что числа в каждом столбце, строчке и диаrонали
v
дают одинаковую сумму s, называемую JI1tаzuческоu
суммой.
Пример маrическоrо квадрата с 42 == 16 числами
изображен на рис. 8. Маrическая сумма для Hero paB
н а 34.
1
3
5
.
 5. Маrические квадраты
са
I
..
i
i
...
.
I
.
I
i
....
...
р НС. 6.
7
.
*) Иrра с передвижением фишек по размеченной доске.
(ПРИМ. перев.)
15

Для каждоrо числа n существует только одна l\1a..
rическая сумма S. KOTOpYIO леrко найти. Так I{3K CYM
ма чисел в каждом столбце равна s, а столбцов.......... п;
то tуммз всех -чисел в маrtIЧСКОМ квадрате равиа ns.
2 9 4
7 5 J
б f 8
f 8 15 10
12 13 б 3
14 " 4 5
7 2 9 fб
Рис. 7.
Рис. 8.
Но сумма всех чисел от 1 до п 2 равна
1 + 2 + ... + п 2 === ; (п 2 + 1) п 2 ,
что следует из формулы для суммы п членов ариф..
метической п-роrрессии. Так как
1
ns == 2(п 2 + 1) п 2 ,
ТО
1
s ==="2 п (п 2 + 1).
(1.5.1)
Таким образом, если число n задано, ТО' число s оире...
делено. l\1аrические квадраты MorYT быть построены
ДЛЯ любоrо числа n, которое больше 2; читатель леr
ко мо}кет убедиться, что их не существует для n == 2.
Во времена средневековья странные свойства этих
квадратов считались волшебными и поэтому маrиче..
скпе квадраты служили талисманами, защищаю'щими
тех, кто их носил, от мноrих несчастий. Часто
воспроизводнтся маrический квадрат, присутствую
ЩИЙ на знменитой rравюре Альбрехта Дюрера «Ме..
ланхолия» (она помещена на фронтисписе нашей кии...
rи). Этот квадрат воспроизведен с большим увеличе-
нием на рис. 9; при ЭТОМ !\1Ы получили также B03MO;'"
НОСТЬ увидеть, как во времена Дюрера изображались
16

U!IQJP.bI.. Ср.еДI-f1е числа в последней CTpOIe Ifзображают
rод- 1514, в котором,. как мы знаем, была создана
э.а rравюр.а. Возмо)кно, что Дюрер, ПОЛОЖИ8 в ОСНОВУ
И..i\'iеНН(j) эти ЧИСJIа нашел остальные меТОДОl\1 проб и
ошибок. Мо}кно доказать, что при n == 3 имеется
лишь один маl'ическиЙ квадрат, а именно квадр.ат.,
Рис. 9.
изображенный на рис. 7. Докажем этот факт. Для
этоrо напишем ЧИСЛQВОЙ квадрат 3 Х 3 .в общем 8иде
Хl Yl Zl
Х2 У2 Z2
ХЗ Уз ZЗ
и выясним, какими MorYT быть ЭТИ девять чисел.
Вначале покажем, что центральное число У2 ДОЛ}f{..
НО равняться 5. Из формулы (1.5.1) следует, что при
п === 3 маrическая сумма s равна 15. ПРОСУМlVlируем
теперь числа во второй строке, втором столбце и обеих
диаrоналях. В эту сумму каждое число, кроме чис-
ла У2, ВХОДИТ ПО одному разу; число У2 ВХОДИТ четыре
u
раза, так как оно содер}кится в ка}кдои из чеТЫ,рех
17

сумм. Поэтому, так как каждая сумма равна s, то
48 == 4 Х 15 === 60 ===
=== Х2 + У2 + Z2 + Уl + У2 + Уз + Xl + У2 +
+ zз + Zl + У2 + ХЗ == 3У2 + Хl + Х2 +
+ хз + Уl + У2 + уз + Zl + Z2 + ZЗ ===
=== 3У2 + 1 + 2 + ... + 9 === 3У2 + 45.
Следовательно,
3У2 == 60  45 == 15
В таблице
и У2 == 5.
Хl Уl ZI
Х2 5 Z2
ХЗ Уз Z3
число 9 не может стоять в уrлу, так как, если, напри..
мер, Хl == 9, то Z3 == 1 (потому что s == 15), т. е. мы
получили бы таблицу
9 Уl ZI
Х2 5 Z2
ХЗ уз 1
Каждое из четырех чисел Уl, Zl, Х2, ХЗ должно быть
меньше шести, так как Уl + Zl == Х2 + ХЗ == 6. Но у нас
осталось лишь три числа, меньших шести, а именно:
2, 3 и 4. Таким образом, получилось противоречие.
Отсюда мы делаем вывод, что число 9 должно нахо.
диться в середине строки или столбца, поэтому наш
квадрат может быть записан так:
Хl 9 ZI
Х2 5 Z2
Х3 1 Z3
Число 7 не может быть в одной и той же строке с
числом 9, TaK как тоrда сумма чисел в этой строке
была бы больше пятнадцати; точно 'taK же число 7
не может быть в одной и той же строке с числом 1,
так как тоrда оставшееся в этой строке число должно
было бы быть также семеркой. Таким образом, 7 не
может находиться в уrлу, и мы можем считать, что
наш квадрат имеет следующий вид:
Х) 9 ZI
7 5. 3
Хэ 1 Z3
18

Числа, находящиеся в ОДНОЙ строке с числом 9.........
это 2 и 4, так как иначе сумма в этой .строке была бы
больше пятнадцати. Далее, число 2 'должно быть В
том же столбце, что и число 7, так как если бы там
стояло 4, то третье число в этом столбце было бы
тоже 4. Используя это наблюдение, мы можем опре-
делить место каждоrо из двух оставшихся чисел 6 и 8,
в результате получаем маrический квадрат, изобра
женный на рис. 7.
Для больших значений п можно построить вели
кое множество маrических квадратов. В XVI и XVII
веках, и даже позже, составление маrических KBaдpa
тов столь же процветало, как и составление кроссвор..
дов в наши дни. Бенджамин Франклин *) был CTpaCT
ным любителем маrических квадратов. Он позже при
знавался, что, будучи служащим 3аконодательноrо
Собрания штата Пенсильвания, он скрашивал скуч",
ные часы на службе составлением причудливых маrи..
ческих квадратов и даже маrических KpyroB, в кото....
рых числа стоят на переплетающихся окружностях,
u u
причем сумма чисел на каждои из окружностеи одна
и та же. Следующий эпизод взят нами из Собрания
сочинений Бенджамина Франклина **).
о маrических квадратах Б. Франклина стало из-
вестно, коrда один из ero старых друзей, Лоrан, по..
казал ему несколько книr о маrических квадратах.
заметив при этом, что не верит в то, что ктолибо из
анrличан Mor бы сделать что-либо замечательное в
этой области.
«Лоrан показал мне в одной из этих книr несколь....
КО необычных и довольно любопытных случаев, но ни
один из них не Mor сравниться с теми, которые, как
я помню, были сделаны мною. Он попросил меня по..
казать их. И в следующее свое посещение я принес
ему квадрат 8 Х 8, который я нашел среди своих ста..
рых бумаr и который я предлаrаю вам с описанием
ero свойств» (рис. 1 О).
Б. Франклин упоминает только некоторые свой..
ства cBoero квадрата. Мы предлаrаем читателю найти
*) Бенджамин Франклин (17061790)  выдающийся aM.
риканский общественный деятель, дипломат и ученыЙ. (П рим.
перев. )
**) The Papers of Benjamin Franclin, Yale University Рrеsз,
rr. 4. с. 392402.
19

И' Д1Jуrие ero свойства. Например, очеВIIДНО, что s рап-
няt:ТСЯ 260, а сумма чисел в каждой половине любой
строки и в кал{дой половине любоrо столбца равняет-
ся 130, чТо составляет половину от 260. Четыре чис.,чз,
стоящие в уrлах, в сумме с четырьмя числами, стоЯ
ШПМИ В центре квадрата, дают 260; CYl\11Ma чисел по
Н3КЛ()}П10МУ ряду, идущему от числ? 16 вправо 
вперх до числа 10, а далее по наклонному ряду, иду..
щему. от числа 23 вправо  вннз до числа 17 равна
260. То же самое верно
для ка){{доrо ряда из
восьми чисел, параллель-
Horo описанному выше.
«Потом Лоrан показал
мне старую книrу по
ари(рметике, изданную в
формате кварта *) и на-
писанную, я думаю, He
ким Штифелем (Михаил
Штифель, «Arithmetica
integra», Нюренберr,
1544). в этой книrе был
помещен квадрат 16 Х 16,
в который, по ero мнению,
был вло)кен колоссаль-
ный труд. I--Io если я не ошибаюсь, он имел лишь
обычное свойство, т. е. обладал постоянной суммой,
РаВНОЙ 2056 в каждом ряду: rоризонтальном, верти-
кальном и диаrональном.
Не желая уступить Штнфелю даже в размерах
квадрата, я, вернувшись домой, в тот же вечер co
ставил квадрат 16 Х 16, который помимо всех свойств
Moero квадрата 8 Х 8, т. е. наличия постоянной суммы
2056 во всех аналоrичных рядах и диаrоналях, имел
ellLe одно дополнительное свойство. Если вырезать из
листа бумаrи квадрат 4 Х 4 и уложить этот лист на
большоЙ квадрат так, чтобы 16 квадратиков большеrо
квадрата попали в эту прорезь, то сумма 16 чисел,
п(jявившихся в этой прорези, куда бы мы ее ни по-
ЛОЖИЛИ, на большом квадрате будет одна и та же, и
равна тому же самому числу 2056».
52 61 ч 13 20 29 36 45
1lt 3 62 51 46 35 30 t9
53 60 5 f 2 21 28 3 7 4
J f 6 59 5lt 43 38 27 22
55 58 7 10 23 26 39 42
9 8 57 56 41 4 О 25 24
50 БЗ 2 15 1 В 31 3 4 41
16 1 6ч ч9 48 333217
Рис. 10.
*) Формат кварто  формат в 1/4 ДОЛЮ листа, Т. е 1 450 мм Х
Х 300 мм. (ПрUМ. перев.)
20

Маrач-еский квадрат Б. Фрзнклина переJt вами
(рис. 1 rl) и ВЫ MO)KTC сами проверить er-o замеqа
тельные свойства.
Б. Франклин по праву rордплся своим творением,
что видно из продол}кения ero ПИСЬ!\1а: «На сдедую
щее утро я послал этот квадрат нашему друrу, KOTO
рыЙ: через несколько дней вернул ero в ответном
I 110 57 '72 89 10" 121 IJб /53 /68 185
200 217 232 2491 8 25
v' ,
/ 186 167
58 39 26 7 250 231 218 199 154 135 122 103 90 71
/ "- \
219 23О / /38/ 59/ "70 "91 ['../02 /23 IJч 155 !56 187
198 251 б 7
/ " '" "-
1 / r-- 188 )65 )56 133
БD 37 28 5 152 f29 220 )97 124 10/ 92 69
/ , "- ., .,
201 216 2ЗЗ !f ч8 9/ 21/ 4// 58/ '73 r"88 105 12Q 137 152 159 /84
/ / j / ., " "- "-
/ 10/ / / / /1 \. "- " "- "-
55 42 /23 J47 234 ,}/5 ?О2 183, /70 15/, 138, 119, /06 87 74
1/ / " ,
/ / 246 11/ / /41 / '75 86 , к " 150 )71
203 2/4 }З5 /22 /54 107 118, 139 182
/ 1/ / " , " , , "
21/ / / / / 20 181 " "- 1'10 "п Z "'108 )5 1"76
/53 /14 12 ,f45 !3б 2/3 172, 149,
l/ 1/ / / " ., , -, ,
I 2/2 / I /3/ / / 52/ '77 84 '\ " "141 48 173 IВО
205 237 J44 /20 /15 /O flб,
/ / 1/ 1/ / , " " '\ , ,
/ '" 19/ 11./ / / "/ 179 171.; '-I7 , f' 1"/10 )з '78
/51 /-16 243 }З8 ;/1 206 14 //5
v 1/ 1/ , -" , ., ., ,
/ / / / / 18/ 47 )/1 '\ /"з i4б "' ,
}07 2/0 239 2'-12 /5 50 79 82 /1'1" 175, 178,
/ 1/ 17 1/ i/ " , .,
/ / / / 241 , '" 112 1)" 80.
/'-19 /48 1/17 )6 240 209 208 177 176 /45 144, 113,
1/ ...... " ,
/ 221 228 / 1"- 157 1/54 )89
196 253 4 29 35 51 б8 93 100 125 132
/ 1/ ;- .... , " '\
/ 35 30 , "'9" i'в7
/62 3 25'1 227 222 195 190 163 158 131 128 99,
/ 1/ '\ "
/ / 226 34 53 56 95 !52 1/9/
/9'1 223 255 2 Зl 98 127 130 159
'" . '\ "
/5* 33 12 t 255 225 224 193 192 fбl fБО 129 12В 97 96 '65
",
..
Рис. 11.
письме со следующими словами: "Я возвращаю тебе
твой удивительный, а может быть, самый изумите.ЛЬ'"
ный маrический квадрат, в котором...", но этот ком...
плимент слишком экстраваrантен, и поэтому раци
Hero, а также ради caMoro себя, мне не следует er'()
повторять. К тому же это и необязательно, так как
я не сомневаюсь, что вы охотно cor ласитесь, что ЭТОТ
квадрат 16 Х 16 является самым маrическимаrиче"
СКИJ.\rI из всех маrических квадратов, составленнь[х
2!

коrдалибо каким-либо MaroM». Более подробные све-
дения о построении маrических квадратов мо}кно Hai"'I-
ти в книrах: Е. я. r у р е в и ч. Тайна древнеrо талис
мана.  М.: Наука, 1969 и И. М. П о с т н и к о в. Ма-
rические квадраты.  М.: Наука, 1964.
С и с т ем а 3 а Д а ч 1.5.
1. Mor ли Дюрер использовать вместо cBoero
квадрата, изображенноrо на рис. 9, какие-либо дру-
Рис. 12. Репродукция маrическоrо Kpyra Франклина. Ориrинал,
выполненный в цвете, был продан частному коллекционеру на
аукционе в НЬЮЙорке.
rие квадраты, в которых тот же rод фиrурировал та..
ким же образом?
2. Дюрер прожил до 1528 r. CMor ли бы он датп
роnать какую-нибудь из своих более поздних картин
таким же способом?
3. Изучите некоторые свойства маrическоrо Kpyra
Б. Франклина (рис. 12}.

r ЛАВА 2
ПРОСlЫЕ ЧliСЛА
 1. Простые и составные числа
'Дол)кно быть, одним из первых свойств
чисел, открытых человеком, было то, что некоторые
из них MOrYT быть разложены'на два или более мно-
жителя, например,
6==2.3
,
9===3.3
,
30 == 2 · 15 == 3 · 1 О
,
в то время как друrие, например,
3, 7, 13, 37,
не MorYT быть разложены на мно}кители подобным
образом. Давайте вспомним, что вообще, коrда число
с==а.Ь
(2.1.1)
является произведением двух чисел а и Ь, то мы на..
зываем а и Ь множителями или делителями числа с.
Каждое число имеет тривиальное разложение на мно"
жители
с==l.с==с.l.
(2.1.2)
Соответственно мы называем числа 1 и с тривиаль-
ными делителями числа с.
Любое число с > 1, У KOToporo существует нетри-
виальное разло}кение на множители, называется со..
ставнbtiИ. Если число с имеет только тривиальное
разложение на множители (2.1.2), то оно называется
простым. Среди первых 100 чисел простыми являются
следующие 25 чисел:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,41,
43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.
Все остальные числа, кроме 1, являются составными.
Мы можем сформулировать следующее утвер}кдение:
23

Т е о р е м а 2.1.1. Любое l{еЛQе ЧltСАО с > 1 являет
ся... .либо простым, либо U,A,teeT простоЙ множитель.
Д о к а 3 а т е л ь с т в о. Если с не является ПрОСТЫ1
ЧИСJIОМ, то У Hero есть наим:еньший нетривиальный
множитель р. Тоrда р  простое число, TaI{ как если
БЬ1 р  было составным, то число с имело бы еще
меньший множитель.
Теперь мы подошли к нашеЙ первой важной З3-
даче в теории чисел: как определить, является ли
произвольное число простыl'Л пли нет, и в случае,
если оно составное, то как найти какойлибо ero не-
тривиальный делитель?
Первое, что может прийти в rолову,  это попы-
таться разделить данное число с на все числа, мень-
шие ero. Но надо 'признать, что этот способ 1ало
удовлетворителен. Соrласно TeopeIvle 2.1.1 достаточно
делить на все простые числа, меньшие с. Но мы 1\10-
жем значительно упростить задачу, заметив, что при
разложении на МНО)i{ители (2.1.1) оба множителя а
и Ь не MorYT быть больше, чем c, так как в про-
тивном случае мы получили бы
а · Ь > 4ё ·  === С,
ЧТQ невозможно. Таким образом, чтобы узнать, имеет
ли число с делитель, достаточно проверить, делится
ли число с на простые числа, не превосходящие 4ё.
При м е р 1. Если с === 91, то -ё === 9, . . .; ПрОБе-
рив простые числа 2, 3, 5, 7, находим, что 91 == 7 -13.
При м е р 2. Если с == 1973, то находим, что
'
'\/ с === 44, ... Так как ни одно из простых чисел до 43
не делит с, то это число является простым.
Очевидно, что для б6льших чисел этот метод мо"
жет быть очень трудоемким. Однако здесь, как и при
мноrих друrих вычислениях в теории чисел, мо}кно ис-
пользовать современные методы. Довольно просто З3..
проrраммировать на ЭВМ деление данноrо числа с
на все целые числа до -ё и печатание тех из них,
{{оторые не имеют остатка, т. е. тех, которые делят с.
Друrим очень простым методом является примене-
ние таблиц простых чисел, т. е. использование про-
стых чисел уже найденных друrими. За последние
200 лет было составлено и издано MHoro таблиц про-
стых чисеu1}. Наиболее обширной из них является таб
24

ЛПЦ1} д. х. Лемера, солержащэя все простые числа
до ] О 000 000. Наша таБJJица 1 содержит все просты
чиса До 1000.
Таблиц-а 1
Простые числа сред и первой тысячи чисел
2, 3, 5. 7, 11, 13, 17, 19, 23, 29, 31, 37,
41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 8З; 89, ,
97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, :
157, 163, 167, 173, ] 79, 181, 191, 193, 197, 199, 2] 1, 223,
227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 28] ,
283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359,
367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 43], 433,
439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503,
509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593,
599 601, 607, 613, 617, 619, 631, 64] , 643, 647, 653, 659,
,
661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743,
751, 757 761, 769, 773, 787, 797, 809, 811, 821, 823, 827...
, ,
829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911$
9]9, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997,
Некоторые энтузиаСТЫВЫЧИСЛlIтели уже подrотови
ли таблицы простых чисел, превосходящих 1 О 000 000.
f-Io, по-видимому, не имеет большоrо смысла идти на
значительные затраты и усилия, чтобы опубликовать
эти таблицы. Лишь в очень редких случаях rvlaTeMa
тику, даже специалисту в теории чисел, приходится
решать вопрос. о том, является ли какое-то большое
число простым. Кроме Toro, большие числа, о которых
математик хочет узнать, являются они составными
или простыми, не берутся им произвольно. Числа, I{o-
торые он хочет исследовать, обычно ПОЯВЛ51ЮТСЯ в
специальных математических задачах, и, таким обра
зом, эти числа имеют очень специфическую форrvfУ.
Си с т е м а 3 а Д а ч 2.1.
1. Какие из следующих чисел являются простымп:
tJ) тод вашеrо рождения; б) текущий rод; в) номер
Dвшеrо дома.
2. Найдите простое число, слеДУlощее за простым
числом 1973.
25

3. Заметим, что числа от 90 до 96 включительно
являются семью последовательными составными чис..
лами; найдите девять последовательных составнЫх
чисел.
 2. Простые числа Мерсенна
в течение нескольких столетий шла по
rоня за простыми числами. Мноrие математики боро""
лись за честь стать открывателем caMoro большоrо из
известных простых чисел. Разумеется, можно было 'бtьt
выбрать несколько очень больших чисел, не имеющих
таких очевидных делителей, как 2, 3, 5, 7, и прове..
рить, являются ли они простыми числами. Этот спо
соб, как мы вскоре убедимся, не очень эффективен.
Теперь эта поrоня утихла,'она идет только в одном
направлении, оказавшемся удачным.
Простые числа Мерсенна являются простыми чис..
лами специальноrо вида
Мр == 2 Р  1, (2.2.1)
rде р  друrое простое число. Эти числа вошли в ма..
тематику давно, они появляются еще в евклидовых
размышлениях о совершенных числах, которые мы
рассмотрим позже. Свое название они получили в
честь французскоrо монаха Мерена Мерсенна (1588
1648), который MHoro занимался проблемой COBepQO
тенных чисел.
Если начать вычислять числа (2.2.1) для различ
ных простых чисел р, ТО видно, что не все они ока",
зываются простымн. Например,
М 2 === 22  1 == 3 == простое,
М3 == 23  1 == 7 == простое,
М5 == 25 ......... 1 == 31 == простое,
М7 == 27  1 == 127 == простое,
M ll == 211  1 == 2047 == 23 · 89.
Общий способ нахождения больших простых чи..
сел lViepceHHa состоит в проверке всех чисел М р для
различных простых чисел р.
Эти числа очень быстро увеличиваются и столь }ке
быстро увеличиваются затраты труда на их нахожде-
ние. То, что с этой работой всетаки можно спра 1
26

виться уже для ДОВОЛЬНО больших. чисел, объясняется
существованием эффективных способов выяснения
простоты для чисел TaKoro вида.
В исследовании чисел Мерсенна можно выделить
u
раннюю стадию, достиrшую своеи кульминации в
] 750 rоду, коrда Леонард ЭЙлер *) установил, что чис-
. т.o 1'.1"31 является простым. К этому времени было най-
дено восемь простых чисел Мерсенна, соответствую
щих значениям
р === 2,
р == 13,
р === 3,
р === 17,
р === 5,
р == 19,
р == 7,
Р == 31.
ЭЙлерово число М 31 оставалось CaMbIl\1 большим из из..
вестных ПрОGТЫХ чисел более ста лет. В 1876 rоду
французский математик Лукас установил, что OrpOM8t
ное число
м 127 === 170141183460469231731687303715884105727
является простым числом. Ну и число! С 39 цифрами.
Простые числа Мерсенна, меньшие этоrо числа, за'"!
даются значениями р, указанными выше, а также зна-
чениями
р===61,
р === 89,
р === 107.
Эти 12 простых чисел Мерсенна были вычислены с
помощью только карандаша и бумаrи, а для вычис-
ления следующих уже ИСПОЛЬЗ0вались механические
настольные счетные машины. Появление вычислитель-
HIX машин с электрическим приводом позволило про-
должить поиски, доведя их до р == 257. Однако ре-
зультаты были неутешительными, среди них не ока-
залось новых простых чисел Мерсенна.
Затем задача была переложена на плечи ЭВМ.
Создание все более высокопроизводительных ЭВМ
дало возможность продолжить поиск новых простых
чисел Мерсенна. д. х. Лемер установил, что значения
р === 521, р == 607, р == 1279,
Р === 2203, р == 2281
*) Леонард Эйлер (17071783)  выдающийся математик,
родившийся в Швейцарии, БОльшую часть жизни провел в Рос-
сии, являясь членом Петербурrской Академии наук. (П рим.
перев.)
27

дают ПрОС'fые чи"Сла Мерсенна.. ДаJIЬiIе-ЙI1Iие п<j:НскМ
также увенчались успехол. РнзеJllэ (1958) показал
что
р === 3217,
дает простое число Мерсенна, а rурвиц (1962) f1 ашел
еще два таких значения:
р === 4253, р == 4423.
OrpoMHoro успеха добился rllллельс (1964), которыЙ
нашел простые числа .l\'\ерсеииа, соответствующие 3Ha
ченйям
р == 9689,
р === 9941 ,
р=== 11213.
Итак, общий уро}кай составил 23 простых Lfисда
Мерсенна, и, так как мощности ЭВМ продол:rкают
уве.личиваться, l\1bI надеемся на дальнейший успех.
Простое число Лукаса М 127 , как мы уже упоминали,
имеет 39 цифр. Да)ке ВЫЧИС,,1ение caMoro большоrо из
известных простых чисел, числа М 11213, является до..
вольно сложной задачей и, повидимоrvIУ, нет смысла
воспроизводить здесь это число. Если же мы захотим
узнать, сколько цифр содержит это число, то мы мо'"
жем сделать это, не вычисляя caMoro числа.
Вместо наХО)l{дения количества цифр числа М р ==
=== 2 р ----- 1 рассмотрим эту задачу для числа
М р + 1 == 2 Р .
ЭТИ два числа имеют одинаковое количество цифр,
aK как если бы число М р + 1 имело на одну цифру
больше, то оно дол}кно было бы оканчиваться на о.
Но это невозможно ни для какой степени числа 2, что
ви.пно ИЗ ряда
2, 4, 8, 16, 32, 64, 128, 256, ...,
в котором последняя цифра в каждом числе може'r
быть только одним из чисел
2, 4, 8, 6.
Чтобы найти количество цифр числа 2 Р , вспомним,
что 192 P == Р 19 2. Из таблиц находим, что 192 при.
ближенно равняется 0,30103, откуда
19 2 Р === Р 19 2 == Р · 0,30103.
28

ДЛЯ fJ === 11213 IЮлчае.м,
19 211213  3375,449 . . .,
и Т..ЗI{ как характеристика этоrо числа равна 3375, то
МЬ] приходим К выводу, что число 2 р имеет 3376 цифр.
Итак, 'мы MOll{eM сказать следующ-ее.
Самое большое известное в настоящее время про..
стое число имеет 3376 цифр. (Здесь слова «в настоя..
щее время», имеют существенное значение.) Это ЧIlСЛО
GQIJJQ найдено на ЭВМ Иллинойскоrо университет i з
(США). Математический факультет этоrо универС}I"
тета был так rорд своим достижение:\1, что изобразил
это число на своем ПОЧТОВОfvl ште:мпе.ле, таким обра..
зом воспроизводя ero на каждом ОТСЬJлаемом письме,
для всеобщеrо восхищения.
 3. Простые числа Ферма
Существует также еще один тип простых
чисел с большой и интересной историей. Они БЬJЛИ
впервые введены французским юристом Пьером Фер
мз (16011665), который прославился своими вы..
дающимися математичеСI{ИМИ работами. ПеРВЬJМИ
пятью простыми числами Ферма являются
ро == 2 2и + 1 == 3, Р 1 === 221 + 1 === 5,
Р 2 == 222 + 1 == 17, F з ==2 2З + 1 ==-257,
Р4 == 224 + 1 == 65 537.
В соответствии с этой последовательностью общая
формула для простых чисел Фер1-..1а должна иметь B
F n === 2 2n + 1. (2.3.1)
Ферма был аБСОЛIОТНО уверен, что все числа этоrо
вида являются простыми, ХОТЯ он не проводил вычис
лений друrих чисел, кроме указанных пяти. Однако
это предположение было сдано в архив неоправдав
ШIIХСЯ математических rипотез после Toro, как Лео
нард Эйлер сделал еще один шаr и показал, что сле
дующее ЧИСJIО Ферма
F 5 == 4 294 967 297 === 641 · 6 700 417
не является простым, что и показывает приведеннзя
запись. Возможно, что этим история чисел Ферма
29

была бы закончена, если бы ЧИСJIа Ферма не появи'"'
лись в совсем друrой задаче, задаче построения пра-
вильных мноrоуrольников при помощи циркуля и
линейки.
П равuльныJvt МНО20У20ЛЬНUКоt называется MHoro-
u
уrольник, вершины KOToporo лежат на некоторои
ОКРУ}l(НОСТИ на одинаковых расстояниях друr от друrа
(рис. 13). Если у правильноrо мноrоуrольника п вер-
шин, то мы называем ero правuльным п-У20ЛЬНUКО1(t.
Если мы проведем n радиусов, соединяющих центр
окружности с вершинами,
то получим п центральных
уrлов величиной
..!.. . 3600
n
ка:iКДЫЙ. Если можно по-
строить уrол, имеющий эту
величину, то можно по..

строить и этот п-уrольник.
LLревние rреки очень хо..
тели найти методы построе-
ния правильных мноrоуrоль...
Рис 13. ников с помощью циркуля и
линейки. Разумеется, они
u U
умели строить простеишие из них........... равностороннии
треуrольник и квадрат. С помощью повторноrо деле..
иия пополам центральноrо уrла они моrли также по..
строить правильные мноrоуrольники с
4, 8, 16, 32, ...,
3, 6, 12, 24, ...
вершинами. Kporvle Toro, они умели строить правиль
ный пятиуrольник, и следовательно, также правиль-,
ные мноrоуrольники с
5, 1 О, 20, 40, ...
вершинами. Был также получен еще один тип пра..
вильноrо мноrоуrольника. Центральный уrол в пра"\
вильном 15-уrольнике равен
J... . 3600 == 240
15 '
и он может быть получен с помощью уrла в 720, со.
ответствующеrо правильному пятиуrольнику, и уrла в
30

120°, соответствующеrо правильному треУI'ОЛЬНИI{У,
если УДВОИТЬ первый уrол и вычесть из Hero второЙ"
Следовательно, мы мо)кем построить правильные мно-
rоуrольники с 15, 30, 60, 120, ... сторонами.
В таком состоянии проблема оставалась до
1801 rода, коrда вышла работа по теории чисел мо'"
лодоrо немецкоrо математика К. Ф. [аусса (1777-------
]1855) «Арифметические исследования». Она открыла
новую эпоху в математике. [аусс превзошел rрече...
ских reoMeTpoB не только в том, что указал метод
построения циркулем и линейкой правильноrо
17уrольника, но и пошел rораздо дальше. Для всех
чисел n он определил, какие nуrольники MorYT быть
построены таким образом, а какие нет. Сейчас мы
опишем результаты, полученные [ауссом.
Выше мы отмечали, что из правильноrо nуrоль-
ника мо}кно получить правильный 2nуrольник, деля
каждый центральный уrол пополам. С друrой сторо-
ны, из 2nуrольника можно получить nуrольник, ис-
пользуя лишь каждую вторую вершину. Это показы-
вает, что достаточно провести поиск правильных
мноrоуrол:ьников, которые MorYT быть построены с
помощью циркуля и линейки, только среди MHoro
уrольников с нечетным числом вершин. raycc доказал,
eI
что правильнbtи n-Уёольник с нечетным числом вер-
шин может быть построен с помощью циркуля и ли-
нейки ТОёда, и только ТОёда, если число n является
простым числом Ферма или произведением несколь-
ких различных простых чисел Ферма.
Что это нам дает для небольших значений п?
Очевидно, что 3уrольник и 5уrольник MorYT быть
построены, в то время как 7уrольник не может, так
как 7 не является простым ЧИСЛО!\1 Ферма. Не может
быть построен и 9уrольник, так как 9 == 3. 3 являет
ся произведением двух равных простых чисел Ферма.
Для п == 11 и n == 13 мноrоуrольники не MorYT быть
построены, но M02l{HO построить для n == 15 == 3. 5 и
n ==:.1 7.
Открытие raycca, естественно, возродило интерес
к числам Ферма (2.3.1). За последнее столетие были
предприняты поистине rероические поиски, вручную,
без помощи машин, новых простых чисел Ферма.
В настоящее время эти вычисления продол)каются
со все возрастающей скоростью с помощью ЭВМ.
31

ОднакО' ДО сих пор результаты были ot-риц-атеЛ-hJIЫМ({.
Ни одноrо HOBoro npOCToro числа Ферм.а не 6ыIоo flай
депо и сейчас мноrие математики склонны' считать,
что их больше нет.
с и с т е м а з а Д а ч 2.3.
t. Найдите все нечетные числа п < 100, дЛЯ КОТО"
рых l\10ЖНО построить правильный п-уrольник.
2. Как построить правильный 51уrольник, имея
правильный 17уrольник?
3. Если не существует простых чисел Ферма, кро",
ме выше указанных пяти, то сколько существует пра..
вильных nуrольников (п нечетно), которые Moryr
быть построены циркулеlVI и линейкой? Каково то
наибольшее нечетное п, для KOToporo может быть
построен правильный пуrольник?
 4. Решето Эратосфена
Как мы уже rоворили, существуют таб..
лицы простых чисел, простирающиеся до очень боль...
тих чисел. Как можно было бы подступиться К со..
ставлению такой таблицы? Эта задача была, в
известном смысле, решена (около 200 r. до н. э.)
Эратосфеном, матеI\1атиком из Александрии. Ero схема
СОСТОIIТ в следующем: напишем последовательность
всех 'целых чисел от 1 до числа, которым мы XOTIM
закончить таблицу:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2
2
---  ..........
2 3 2
2

:l .3
I-Iачнем с простоrо числа 2. Будем выбрасывать Ka
я{дое второе ЧIIСЛО, начиная с 2 (кроме caMoro чнс
ла 2), т. е. четные числа 4, 6, 8, ] О и т. д., подчерки
вая каждое из них. После этой операции первым
неподчеркнутым числом будет число 3. Оно простое,
так как H делится на 2. Оставив число 3 неподчерк
нутым, будем подчеркивать каждое третье число пос
ле Hero, т. е. числа 6, 9, 12, 15, ... ; некоторые из
них уже были подчеркнуты, поскольку они являются
четными. На следующеl\1 шаrе первым неподчеркну",
тым числом ока}кется число 5; оно простое, Tal\ как
не делится ни на 2, ни на 3. Оставим число 5 непод'"'
черКНУТЫl\I, но подчеркнем каждое пятое число после
32

Hero, т. е. числа 10, 15, 20, 25, ... ; как и раньше,
часть из них уже оказалась подчеркнутой. Теперь
наименьшим неподчеркнутым числом окажется чис..
по 7. Оно простое, так как не делится ни на одно из
меньших ero простых чисел 2, 3, 5. Повторяя этот
процесс, мы в конце концов получим последователь--
ность неподчеркнутых чисел; все они (кроме числа 1)
являются простыми.
Этот метод отсеивания чисел известен как «ре..
шето Эратосфена». Любая таблица простых чисел
создается по этому принципу решета. В действитель..
ности, можно продвинуться rораздо дальше по ряду
простых чисел, если использовать для их хранения
память ЭВМ. Подобным образом, в Научно-исследо-
вательской лаборатории Лос-Аламоса были получены
все простые числа до 100 000 000.
Небольшое изменение метода решета позволит
нам получить большую информацию. Предположим,
что всякий раз, впервые подчеркивая числа, мы 6у..
дем подписывать под НИl\1 простое число, с помощью
KOTopora оно отсеивается. Тоrда 15 и 35 были бы за..
писаны как
15, 35
3 5
и т. д., как это показано на последовательности, вы..
писанной выше. Таким образом, мы не только ука..
зали простые числа, но и для каждоrо составно['о
числа привели наименьшее простое число, являющее..
си ero делителем. Такой СltИСОК чисел называется
т а б л и ц е й Д е л и т е л е й. Таблица делителей я в..
ляется более сложной, чем таблица простых чисел.
Чтобы HeMHoro упростить ее, обычно из нее исклю
чают те составные числа, у которых простые делители
малы, например, 2, 3, 5, 7. Самая большая такая таб..
лица была вычислена на ЭВМ д. х. Лемером и
содержит все числа, вплоть до 1 О 000 000.
I(aK мы видели, решето Эратосфена может быть
использовано для построения таблиц простых чисел
и таблиц делите,,1ей. Однако оно может быть исполь
завано и для теоретических исследований. Мноrие
важные результаты в современной теории чисел были
получены методом р-ешета. Приведем результат, из..
вестный еще Евклиду:
2 о. Ore
33

Суи{ествует бесконечное число простых чисел.
Д о к а 3 а т е л ь с т в о. Предположим, что суще'"
ствует только k простых чисел:
2, 3, 5, ..., Pk'
Тоrда в решете не оказалось бы неподчеркнутых чи-
сел, б6льших, чем Pk. Но это невозможно, так как
произведение этих простых чисел
р == 2 · 3 · 5 .... Pk
будет отсеиваться k раз, по разу для каждоrо про
cToro числа, поэтому следующее число р + 1 не МО"
жет быть подчеркнуто ни для одноrо из них.
С и с т е м а з а Д а ч 2.4.
1. Составьте таблицы простых чисел для каждой
из сотен: 1100, lOl200, . . . , 901lOOO.
2. Попытайтесь определить количество простых
чисел в диапазоне lOOOI10100.

r ЛАВА :3
.....
ДЕЛИТЕЛИ ЧИСЕЛ
 t. Основная теорема
о разложении на множители
Любое составное число с может быть за
писано в виде произведения с === а.Ь, причем ни один
из делителем не равен 1 и каждый из них меньше,
чем с; например,
72 == 8 · 9,
150 == 10 · 15.
При разложении числа с на множители ОДИН из НИХ,
и даже оба (а и Ь) MorYT оказаться составными.
Если а  составное, то разложение на множите.тIИ
можно продолжи-ть:
а === аl · а2,
с == аl · а2 · Ь.
Примерами этоrо MorYT служить рассмотренные Rыше
числа
72 == 2 · 4 · 9,
150 == 2 · 5 · 15.
Этот процесс разложения на множители можно про
должить до тех пор, пока он не закончится; это долж
НО ПрОИЗ0ЙТИ, так как делители становятся все MeHb
ше.Н меньше, но не MorYT стать единицей. Коrда ни
один из делителей нельзя у}ке будет разложить на
множители, то все делители будут простыми числами.
Таким образом мы показали, что
Каждое целое число, большее 1, является nро-
CT:blJvl. числом или проuзведенuем ПроСТЫХ Ч,uсел.
Последовательное разложение числа на множи
тели может быть выполнено мноrими способами. При
этом можно использовать таблицу делителей. Сна.
чала найдем наименьшее простое число PI делящее
число с, так что с === Рl · Сl. Если С1  составное число,
2*
35

ТО по таблице делителей найдем наименьшее простое
число Р2, делящее Сl, так что
Сl === Р2 · С2,
с === Рl · Р2 · С2.
Затем найдем наименьший простой делитель числа С2
и Т. д.
Но rлавное здесь то, что независимо от способа
разложения числа на простые множители результат
всеrда будет одним и тем же, различаясь лишь по...
рядком их записи, т. е. любые два разложения числа
113 простые множители содержат одни и' те же про-
стые числа; при этом каждое простое число содер..
жится одинаковое число раз в обоих разложениях.
Этот результат :мы можем кратко выразить следую..
щим образом:
разложение числа на простые множители един-
СТ венно.
Возможно, что вы так часто слышали об это н
TaI{ называемой «основной теореме арифметики» и
nользовались ею, что она представляется вам оче..
ВИДНОЙ, но это совсем не так. Эта теорема моЖет
быть доказана несколькими различными способами,
однако ни один из них не тривиален. Здесь мы при
B дем доказательство, используя способ «от против
1ioro», который часто называют ero латинским на..
званием reductio ad absurduт (приведением к
збурду). Этот способ заключается в следующем:
предположив ложность теоремы, I{ОТОРУЮ нужно до-
казать, показывают, что это предположение приводит
к противоречию.
Доказательство. Предположим, что наша
теорема о единственности разло)кения на множители
неверна. Тоrда должны существовать числа, имею-
щие по крайней мере два различных разложеНИ1Я на
простые множители. Выбере:rvf из них наименьшее и
()бозначим ero через со. Для небольших чисел, ска....
жем, меньших 10, истинность теоремы мо)кно уста-
новить прямой проверкой. Число СО имеет наимень
u u
шин простои множитель Ро, и мы можем записать:
СО === ро · d o .
Тзк KaI{ d o < Со, то число d o единственным образом
раскладывается на простые множители. Отсюда слеОО\
36

дует, что разложение числа СО на простые множите..
IIИ, содеРJкащее число Ро, единственно.
А так как, по предположению, имеется по край..
u
неи мере два разложения числа СО на простые мно"
жители, то должно быть разложение, не содеРJкащее
число РО. Наименьшее простое число в этом разло..
жении мы обозначим через Pl 'I запишем
СО === Р 1 · d 1. (3. 1. 1 )
Так как Рl > Ро, то d 1 < d o и, следовательно,
POd 1 < со. Рассl\tlОТРИМ число
C == СО ----- P O d 1 == (Р 1  РО) d 1 . (3.1.2)
Так как оно меньше, чем число со, то оно должно
раскладываться на простые множители единственным
способом; при этом простые множители числа СО с о...
стоят из простых мно}кителей чисел Pl  Ро и d 1 . Так
как число со делится на Ро, то из выражения (3.1.2)
следует, что число с9 также делится на РО. Следова...
тельно, РО должно быть делителем либо числа dt,
либо Pl  РО. Но любой простой делитель числа [[1
больше, чем Ро, так как Рl  наименьшее простое
число в разложении (3.1.1). Таким образом, остается
единственная возможность: РО должно быть делите...
лем числа Pl  Ро и, следовательно, оно делит PL.
Итак, мы пришли к противоречию, потому что Рl ЯВ
ляется простым числом и не может делиться на дpy
roe простое число РО.
Выше мы отмечали, что единственность разложе..
ния числа на простые множители совсем не очевид"
на. В действительности, существуют «арифметики»,
В которых аналоrичная теорема не выполняется. Про...
стейшим примером такой арифметики может служить
арифметика четных чисел
2, 4, 6, 8, 1 О, 12, ...
Некоторые из них MorYT быть разложены на два
четных множителя, а друrие  нет; ПQследние мы
назывв.ем чеТftоnростыми числами.. Это числа, ко...
торые делятся на 2, но не делятся на 4:
2, 6, 10, 14, 18, ...,
Очевидно, что каждое четное число либо является чет..
нопростым, либо записывается в виде произведения
31

четнопростых чисел. Но такое разложение на четно.
простые числа не всеrда будет единственнь]м. Напри
мер, число 420 может быть разложено на четнопро
стые числа различными способами:
420 := 6 · 70 === 1 О · 42 === 14 · 30.
с и с т е м а з а Д а ч 3.1.
1. Найдите разложение на простые множители
ка}I{доrо из чисел 120, 365, 1970.
2. Проделайте то же самое для чисел, указанных
Б задаче 1 системы задач 2.1 (стр. 25).
3. Запишите все разложения числа 360 на четно-
простые числа.
4. В каких случаях четные числа обладают един-
ственным разложением на четнопростые множители?
 2. Делители
Разложим на множители какоенибудь
число, скажем, 3600. Это разложение
3600 == 2 · 2 · 2 · 2 · 3 · 3 · 5 · 5
может быть записано как
3600 == 24 . 32 . 52.
Вообще при разложении числа n на множители ана-
лоrично можно собирать одинаковые просты-е м но..
u
)l{ители в виде степенеи и записывать
а а а
п  Р l . Р 2 . . Р r
 1 2 ... r'
(3.2.1)
r де Рl, Р2,..., pr........... различные простые множители
числа п, причем число Pl входит аl раз, Р2 входит а2
раз и т. д.
Если мы знаем вид (3.2.1) для числа, то мы CMO
жем тотчас же ответить на некоторые вопросы об
этом числе.
Например, если мы захотим, то можем узнать,
какие числа делят число n. Возьмем для примера
рассмотренное выше число 3600. Предположим, что
число d является одним из ero делителей, т. е.
3600 == d · d 1 .
Приведенное разложение на простые множители по
казывает, что единственными числами среди множи
38

телей числа d будут лишь 2, 3, 5. Кроме Toro, чис-
ло 2 может содержаться не более 4 раз, а числа 3 и 5
не более, чем по 2 раза каждое. Итак, мы видим, что
возможными делителями числа 3600 будут числа вида
d === 261 . 32 . 5 бз ,
при этом показатели степени MorYT принимать зна
чения:
61==0,1,2,3,4;
62 == о, 1, 2;
6з == о, 1, 2.
Так как эти значения MorYT сочетаться всеми воз-
можными спос-обами, то qисло делителей равно
(4+ 1)(2+ 1)(2+ 1)==5. 3. 3===45.
Для любоrо числа n, разложение KOToporo на
простые множители дается формулой (3.2.1), поло...
жение точно такое 2ке. Если число d является дели
телем числа n, т. е.
n == d · d 1 ,
то единственными простыми числами, на которые
может делиться число d, будут только те, которые
делят число n, а именно: PI, ..., р,. Таким образом,
мы можем записать разложение числа d на простые
множители в виде
б 6 б
d . Р 1 · Р 2 · . Р r (3 2 2)
 1 2 ... ,. · ·
Простое число Рl может содержаться не более СХl раз,
как и в самом числе п; аНалоrичНо........... ДЛЯ Р2 И дpy
rих простых чисел. Это значение для числа 61 мы
можем выбрать СХl + 1 споеобом:
61==0, 1, ..., аl;
аналоrично и для друrих простых qисел. Так как
ка}кдое из СХl + 1 значений, которые может ПрИНИ
мать число 61, может сочетаться с любым из СХ2 + 1
возможных значений числа 62 и т. д., то :мы видим,
что общее число делителей числа n задается фор-
мулой
т (п) == (аl + 1) (<12 + 1) . . . (а , + 1).
(3.2.3)
3')

с и с т е м а 3 а Д а ч 3.2.
1. Сколы{о делителей имеет простое число? Сколь.,
Ко делителей имеет степень npOCToro числа ра?
2. Найдите количество делителей у следуJOЩИХ чи
сел: 60,1366, 1970, вашеrо почтовоrо индекса.
3. Какое натуральное число (или числа), не nре-
восходящее 100, имеет наибольшее количество дели...
телей?
 3. Несколько задач о делителях
Существует единственное число 11 == 1,
которое имеет только оин делитель. Числами с ровно
двумя делителями являются простые числа n == р:
они делятся на 1 и на р. Наименьшим числом, имею'"'
щим два делителя, явля&тся, таким образом, р == 2.
Исследуем числа, имеющие ровно 3 делителя.
В соотвеТС!fВИИ с (з.а) имеем
3 === (<<1 + 1) (а2 + 1) .. . (а, + 1).
Так как 3  простое число, то справа может суще-
ствовать лишь один множитель, не равный 1. Отсюда
r === 1, а (.(1 === 2. Таким образом,
n === pi.
Наименьшим числом с 3 делителями является n ==
== 22 == 4. Это соображение, примененное к общему
случаю, коrда число делителей q является простым
числем, позволяет получить, что
q === а 1 + 1, Т. е. а 1 === q ....... 1 и п == pf];
на.именьшим из таких чисел является
2 q1
n=== .
Рассмотрим следующий случай, коrда существует
pOI3HO 4 делителя. Тоrда соотношение
4 == (а] + 1) (а2 + 1)
воз'можно только тоrда, коrда
а1 == 3, а2 == О или аl === а2 === 1.
40

Это при водит К двум возможностям:
n ......... Р 3 n  Р · Р . ·
 l'  1 2'
наименьшее число с 4 делителями......... это n =- 6.
В ТОМ случае, коrда имеется 6 делителей, должно
выполняться соотношение
6 == (а} + 1) (а2 + 1),
ЧТО возможно лишь тоrда, коrда
аl ::::: 5, а2 == О или аl == 2,
Это дает две ВО3МО)I{НОСТИ:
n== р 5 n== р 2. р .
l' 1 2'
а2 == 1.
при этом наименьшее значение имеет место в по..
следнем случае, коrда
р] === 2, Р2 == 3, n == 12.
Этот метод МО2Кно использовать для вычисления наи.
меньших натуральных чисел, имеющих любое задан--
ное количество делителей.
Существуют таблицы, указывающие количество
делителей для различных чисел. Они начинаются
следующим образом:
n 1 2 3 4 5 6 7 8 I 9 I 10 11 12
t (n) I 1 2 I 2 3 2 4 2 4 3 I 4 2 6
Вы леrко можете ее самостоятельно продолжить.
Будем rоворить, что натуральное число n являет...
ся сверхсостаВflЫМ, если количество делителей у ка--
ждото числа, меньшеrо n, меньше, чем количество
делителей у числа n. [лядя на нашу небольшую таб..
лицу, мы видим, что
1, 2, 4, 6, 12
являются первыl'v1И пятыо сверхсоставными числами.
О свойствах этих чисел известно еще очень м ало.
С и с т е м а з а Д а ч 3.3.
1. Взвод из 12 солдат может маршировать 6ю
различными способами: 12 Х 1, 6 Х 2, 4 Х 3, 3 Х 4,
41

2 Х 6, 1 Х 12. Какую наименьшую численность ДОЛЖ 4
ны иметь rруппы людей, которые MorYT маршировать
8, 10, 12 и 72 способами?
2. Найдите наименьшие натуральные числа f имею
Щilе: а) 14 делителей, б) 18 делителей и в) 1 00 дe
лителей.
3. Найдите два первых сверхсоставных числа,
следующих за числом 12.
4. Охарактеризуйте Бсе натуральные числа, коли
чество делителей которых является произведением
двух простых чисел.
 4. Совершенные числа
Нумеролоrия (или rематрия, как ее ино",
rда еще называют) была распространенным увлече..
нием у древних rpeKoB. Естественным объяснением
этому является то, что числа в Древней rреции изо
бражались буквами rреческоrо алфавита, и поэтому
каждому написанному слову, каждому имени СООТ",
ветствовало некоторое число. Люди моrли сравнивать
своЙства чисел, соответствующих их именам.
Делители или аликвотные части *) чисел иrрали
важную роль в нумеролоrии. В этом смысле идеаль-
ными, или, как их называют, совершенными числами
являлись такие числа, которые составлялись из своих
аликвотных частей, т. е. равнялись сумме своих де-
лителей. Здесь следует отметить, что древние rреки
не включали само число в состав ero делителей.
Наименьшим совершенным числом И8JIяетеи 6:
6 === 1 + 2 + 3.
За ним следует число 28:
28 === 1 + 2 + 4 + 7 + 14
далее число 496:
496 == 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248.
*) АлиК80Тflblе дроби  дроби вида J..; в дреlJНОСТИ было
n
принято всякую дробь представлять в 8Рlде суммы аЛl1К90ТНЫХ
дробей. Например, 152 == 112 +  . {Прим. перед.)
42

Часто математик, увлеченный решением какои-
либо проблемы и имеющий одно IfЛИ несколько част..
u u u
ных решении этоп задачи, пытается наити закономер...
ности, которые смоrли бы дать ключ к нахождению
общеrо решения. Указанные нами совершенные числа
MorYT быть записаны в виде
6 == 2 · 3 == 2 (2 2  1),
28 == 22 · 7 == 22 (23  1) 
496 == 24. 31 == 24 (25  1).
Это наталкивает нас на rипотезу:
Число является совершенным, если оно представ-
ляется в виде
р == 2PI (2 Р  1) == 2Plq,.
(3.4.1)
еде
q == 2 Р  1
является простым числом Мерсенна.
Этот результат, известный еще rpeKaM, неСЛО}l{J!rg
доказать. Делителями числа Р, включая само число
Р, очевидно, являются слдующие члсла:
1 2 2 2 2 P 1
" , ..., ,
2 2 2 P1
q, 2q, q,. . ., q.
Запишем сумму этих делителей
1+2+ ... +2P1+q(1+2+ ... +2-1),
которая равна
(1+2+ ... +2P1)(q+l)==(1+2+ ... +2P1)2P
Если вы не помните формулы для суммы членов
rеометрической проrрессии,
S === 1 + 2 + ... + 2P1,
то умножьте эту сумму на 2:
28==2+22+ :.. +2 Р .... 1 +2 Р ,
а эатем, вычтя S, П0лучите
8 == 2 Р  1 === q.
Таким образом, сумма всех делителей числа Р
есть
2 Р q == 2 . 2Plq,
43

а сумма всек делителей, кроме CaMGro числа Р ===i
== 2fJlq, равна
2 . 2Plq  2Plq === 2Plq === Р.
Итак, наше число является совершенным.
Из этоrо результата следует, что каждое простое
число Мерсенна порождает совершенное число. В Э 2
второй rлавы rоворилось, что известно Bcero 23 прci..
стых чtfсла Мерсенна, следовательно, мы знаем так..
же и 23 совершенных числа. Существуют ли друrие
виды совершенных чисел? Все совершенные числа
вида (3.4.1) являются чет н ЬПVfи, можно доказать, что
любое четное совершенное число имеет вид (3.4.1).
Остается вопрос: существуют ли нечетные совершен..
ные ЧJlсла? В настоящее время мы не знаем ни одноrо
TaKoro числа, и вопрос о существовании нечетных
совершенных чисел является одной из самых знаме'!'l
нитых проблем теории чисел. Если бы удалось об
наружить такое число, то это было бы крупным до..
стижениеJ.\.1. ВЫ можете поддаться соблазну найти та..
кое число, перебирая различные нечетные числа. Но
мы не советуем Toro делать, так как по последним
сообщениям Брайена Такхермана из IBM *) (1968),
нечетное совершенное число дол}кно иметь по край
ней мере 36 знаков.
С и с т е м а з а Д а ч 3.4.
1. Используя список простых чисел Мерсенна,
наЙдите четвертое и пятое совершенные числа.
. 5.. Дружественные числа
Дружественные числа также входят в
наследство, доставшееся нам от rреческой нуМероло....
rии. Если у двух людей имена были таковы, что их
числовые значения удовлетворяли следующему усло..
вию: сумма частей (делителей) одноrо из них равнн...
лась второму числу, и наоборот, то считалось, что ЭТО
свидетельствует об их духовной близости. В действИ....
*) Американская фирма; выпускающая выqислительное обо..
РУДQвание. (П pttAt. перев.)
44
l'

тельности rреки знали Bcero лишь одну пару таких
чисел, а именно:
220 == 22 11 5 · 11, 284 == 22 · 71.
Суммами их делителей являются соответственно
1 + 2 + 4 + 5 + 1 о + 20 +
+ 11 + 22 + 44 + 55 + 11 о === 284,
1 + 2 + 4 + 71 + 142 == 220.
Эта пара дружественных чивел оставалась един-
стве-нной извеотной до тех пор, пока Пьеру Ферh
u
не удалось наити следующую пару:
1 7 296 == 24 · 23 · 47, 18 416 === 24 · 1151.
Поиски пар дружественных чисел чрезвычайно
-;удобно вести с помощью ЭВМ. ДЛЯ К8ждоrо числа п
при помощи машины определяютея все делители это..
ro числа (=Fn) и их сумма т. После этоrо произво"
дится такая же операция с числом m. Если при этом
вновь получается первоначальное число n, то пара
чисел (п, т) оказывается дружественной. Недавно
этим способом в йельском университете на ЭВМ
IBM 7094 были проверены все числа до одноrо мил..
лиона. В результате была получена коллекция из
42 пар дружественных чисел; некоторые из них ока..
ззлись ранее неизвестными. Все пары дружественных
ТабJ]ица 2
Дружественные ЧИС,,1а до 100 000
220==22 · 5. 11
1184==25 · 37
2620==22 · 5. 131
5020==23 · 2 · 251
6232==23 · 19 · 41
10744==23 · 17 · 79
12285==33 . 5 · 7 · 13
17296==24 · 23 · 47
63020==22 · 5 · 23. 137
66928==24 · 47 . 89
67095==33 · 5 . 7 · 71
69615==32 · 5. 7. 13. 17
79750==2 · 53 · 11 · 29
284==22 · 71
]210==2. 5. 112
2924==22 · 17 · 43
5564==22 · 13. 107
6368==25 · 199
10856==23 · 23 · 59
14595==3 · 5 · 7 · 139
18416==24 · 1151
76084==22 · 23 .827
66992==24 · 53 · 79
71145==39 · 5. 17 · 31
876ЗЗ==з2 · 7 · 13 · 107
88730==2 · 5 · 19. 467
45

чисел до 100000 приведены в табл. 2. При помощи
этоrо метода, как нетрудно видеть, одновременно
«вылавливаются» И совершенные числа. Если возни..
кает желание продолжать поиски дальше, то, конеч..
но, это можно сделать, но придется затратить боль..
тое количество машинноrо времени.
В действительности мы очень мало знаем о свой
ствах пар дружественных чисел, однако, можно на
основе наших таблиц высказать несколько предполо
жений. Например, отношение одноrо из них к др у...
rOMY, по-видимому, должно все больше и больше
приближаться к 1 по мере Toro, как они увеличи...
ваются. Из таблицы видно, что эти числа бывают
либо оба четными, либо оба нечетными, но не было
найдено случая, коrда одно число четно, а дрyrое не...
четно, хотя поиски дружественных чисел TaKoro вида
были проведены среди всех чисел n  3 000 000000.

r ЛАВА 4

НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ
И НАИМЕНЬШЕЕ ОБЩЕЕ КРАТНОЕ
 1. Наибольший общий делитель
Откровенно rоворя, мы надеемся, что
MHoroe в этой rлаве окажется для вас знакомым.
В ней рассматриваются понятия, с которыми вы по..
знакомились в школе, как только научились обра--
щаться с обыкновенными дробями. Единственным
оправданием включения этоrо материала является
желание освежить ero в вашей памяти. Мы также
надеемся, что приведенное изложение материала
явится более систематическим, чем то, к которому вы
привыкли.
Возьмем некоторую дробь ajb, отношение двух
целых положительных чисел а и Ь. Обычно мы ста..
u
раемся привести ее к простеишему виду, т. е. мы
стараемся сократить множители, общие для а и Ь.
Эта операция не изменяет значения дроби, например,
24 8 2
36 === 12 ==="3'
Общим делителем двух натуральных чисел а u Ь
называется натуральное число d, которое является
множителем как числа а, так и числа Ь, т. е.
а == d · al, Ь === d · Ь 1 .
Если число d  общий делитель чисел а и Ь, ТО
он также делит числа а + Ь и а  Ь, так как
а + Ь === a1d + b1d == (al + Ьд d,
а ........ Ь === а 1 d ........ Ь 1 d == (а 1 ....... Ь д d.
Коrда известны разложения чисел а и Ь на про..
стые множители, нетрудно найти все их общие дели..
тели. Выпишем эти два разложения на простые МНО--
жители:
а 1 а,
а == Рl · ... · Р, ,
Ь  Р (31
........... 1 · ...
13
· Р, '.
(4.1.1)
41

Здесь мы доrовариваемся заПИСЬ1вать разложения чи..
см а и Ь так, как если бы они имели одинаКОВhIе
простые множители
Рl, Р2) ..., Pr,
но с условием, что мы допускаем возможность не",
пользования показателя степени, paBHoro о. Напри
мер, если Рl делит число а, но не делит число Ь, МЬ[
полаrаем, что в формуле (4.1.1) l == о. Таким об...
разом, если
а == 140,
Ь== 110,
(4.1.2)
ТО
а == 22 · 51 . 71 . 11 о,
ь == 21. 51 · 70. 111. (4.1.3)
Из формулы (4.1.1) следует, что любой делитель d
числа а может иметь простыми множителями только
числа р., которые встречаются в числе а и каждое из
пих содержится в степени бi, не превосходящей со...
ответствующей степени (X,i в числе а. Аналоrичные
условия имеют место и для любоrо делителя d чис'"
.ба а. Поэтому общий делитель d чисел а и Ь может
иметь в качестве простых множителей только чис...
8а Рё, которые встречаются одновременно в ЧИСJIах
а и Ь, а степень бi ЧИСJIа Рё в d не может пр@вооко--
дить меньшей не двух степеней: fZi и {3ё.
Из этоrо обсуждения мы можем сделать вывод:
любые два натурадьных ЧИСJIа а и Ь имеют паи..
больший общий делитель d o . Простыми множителя...
ми PI Ч11сла d o являются fe, которые одновременно
ветречs'ются в числах а и Ь, а степень числа Pi в
числе d o еоть меньшее из двух чисел (Хё и ё.
При М е р. 80зьмам два числа, указанных в
(4.1.2), имеющие разложения на простые множители
(4.1.3); очевидно, что
d o  21 · 51 == 1 О.
Так как степень простоrо числа Рё в наибольшем
общем делителе по крайней мере не меньше, чем
у любоrо друrоrо общеrо делителя, то мы получаем
характеристическое свойство:
Любой обlций делитель d делит наибольший об...
щuй делитель d o .
48

НаИ0ЛЬШИЙ общий делитель ДВУК- чисел настоль..
ко важен, что для И8rо существует специальн()е обо..
значение:
d o == D (а, Ь).
(4.1.4)
Система задач 4.1.
1. Найдите наибольшиЙ общий делитель пар чи..
сел: а) 360 и 1970, б) 30 и 365, в) номера вашеrо
телефона и вашеrо почтовоrо индекса.
2. Как бы вы стали доказывать, что  есть
иррациональное число, используя в доказательстве
теорему о единственности разложения?
 2. Взаимно простые ЧИСf1Iа
Число 1 является общим делителем для
любоЙ пары чисел а и Ь. Может случиться, что еди..
ница будет единственным их общим делителем, Т. е.
d o == D (а, Ь) == 1.
( 42.1)
в этом случае мы rоворим, что числа а и Ь 8заUJIlflО
простые.
При м е р. (39, 22) === 1.
Если числа имеют общий делитель, больший еди-
ницы, то они также имеют общий простой делитель.
Итак, два числа MorYT быть взаимно простыми только
тоrда, коrда они не имеют общих простых множите
лей, поэтому условие (4.2.1) означает, что числа а
и Ь не имеют общих простых множителей, т. е. все
их простые множители разичны.
Вернемся к началу этой rлавы, rде мы приводили
дробь а/Ь к простейшему виду. Если d o есть наиболь--
ший общий делитель чисел а и Ь, то мы можем напи
сать
а === aod o ,
ь === bod o .
(4.2.2)
Тоrда
а aod o  ай
Ь === bod o  Ь О ·
(4.2.3)
в формуле (4.2.2) числа ао и Ь О не MorYT иметь про..
стык общих множителей, в противно]\{ случае числа
а и Ь имели бы общий множитель, больший. чем d o .
€ледовательно,
D (ао, ь о ) == 1.
(4.2.4)
49

Это означает, что для второй дроби в формуле
(4.2.3) дальнейшее сокращение невозможно.
Одним из часто применяемых свойств взаимно
простых чисел является следующее.
Если произведенuе аЬ делится на число с, КОТО"
рое взаимно просто с числом Ь, то число а делится
на с.
Д о к а з а т е л ь с т в о. Так как число с делит про..
изведение аЬ, то простые множители числа с содер"
жатся среди простых множителей чисел а и Ь. Но
так как D (Ь, с) === 1, то их не может быть среди MHO
жителей числа Ь. Таким образом, все простые MHO
жители числа с делят число а, но не делят число Ь,
и они появляются в числе а в степенях, не меньших,
чем в числе с, так как число с делит аЬ.
Позже мы используем друrой факт.
Если произведение двух взаимно простых чисел
является квадратом,
аЬ == с 2 ,
D (а, Ь) == 1,
(4.2.5)
то числа а и Ь являются квадрата.м.и:
а == ai,
b  b 2
 1.
(4.2.6)
д о к а з а т е л ь с т в о. Для Toro чтобы некоторое
число было квадратом, необходимо и достаточно,
чтобы все степени в разложении ero на простые мно"
жители были четными. Так как числа а и Ь  взаим.
но простые (4.2.5), то любой простой множитель из с 2
содержится либо в а, либо в Ь, но не в обоих; от..
сюда простые множители чисел а и Ь должны иметь
четные степени.
с и с т е м а з а Д а ч 4.2.
1. Какие числа взаимно простые с числом 2?
2. Почему D (п, n + 1) == I?
. 3. Исследуйте пары дружественных чисел в табл. 2
(стр. 45) И найдите те из них, которые взаимно
ПРОСТЫ.
4. Может ли правило, выраженное в формулах
(4.2.5) и (4.2.6), быть справедливым не только для
квадратов, но и для произвольных степеней?
5(0

 3. Алrоритм Евклида
Вновь вернемся к нашим дробям ajb. ,
Еели а > Ь, то дробь является числом, большим 1, и
мы часто разделяем ее на целую часть и правильную
дробь, меньшую единицы.
При м еры. Мы пишем
32 2 2 63 О
5==6 +5:::;:65' 7===9 +7==9.
в общем случае мы используем деление с остатком
чисел а и Ь (а  Ь), а именно:
a==qb+r, rде Orbl. (4.3.1)
Очевидно, что это всеrда возможно. ДеЙствительнu,
рассмотрим числа О, 1, 2, ... на числовой прямой
I I I
012
ь
I
2Ь
r
п!} а
'  ..........

r
Рис. 14.
(рис. 14). r де-то на ЭТОЙ прямой расположено чис-
ло а. Начиная ОТ точки О станем отмечать точки Ь,
2Ь, 36 и Т. д. ДО точки qb такой, что qb не больше,
чем а, в то время как (q + 1) Ь уже больше а. Рас--
стояние от точки qb до точки а и есть '. Мы назы-
ваем число r остатком при делении (4.3.1), а q 
частным. Это частное q встречается столь часто, что
имеется специальный символ для ero обозначения:
q==[ : ].
Этот символ обозначает наибольшее целое чиСАО, не
nре80сходящее числа ajb. Для примеров, приведен..
ных выше, получим
[ 3; ] == 6, [ 6;] == 9.
в предыдущем разделе мы исследовали наибольший
оБIЦИЙ делитель двух натуральных чисел а и Ь:
C4J === D (а, Ь).
(4.3.2)
51

Чтобы найти число d o , мы полаrали, что мы знаем
разложения чисел а и Ь на простые множители. Од-
нако нахождение таких разложений моя{ет оказаться
очень трудным З8нятием для больших чисел. Суще-
ствует совсем друrой метод для нахождения наи-
большеrо общеrо делителя, который не использует
подобных разло)кений. Он основан на следующем:
Если а == qb + (, 2де О  r  Ь ........ 1, то
D(a, b)==d===D(r, Ь). (4.3.3)
Д о к а з а т е л ь с т в о. Запишем
do===D(a, Ь), d 1 ===D(r, Ь).
Таl{И\1 образом, доказательство соотношения (4.3.3)
означает доказательство Toro, что d o === d 1 . Любой об-
ЩИЙ делитель чисел а и Ь также делит число
, === а  qb.
Следовательно, число r делится на d o .
Так как число d o является делителе1\,f как числа (,
так и числа Ь, то оно должно делить и число d 1 ==
== D (Ь, '); отсюда d 1  d o . С друrой стороны, в со-
ответствии с соотношением (4.3.1) любой общий де..
литель чисел r и Ь делит число а, откуда число dl
делит число а. Так как число d, делит также и чис-
ло Ь, то оно должно делить и число do:::s D (а, Ь),
следовательно, d o  d 1 . Из сказанноrо следует, что
d o === d 1 .
При м е р. 1066 == 5. 200 + 66; следовательно, I
(1066,200)===(66,20Q).
Этот результат, сформулированный в утверждении
(4.3.3), дает нам простой метод вычисления наиболь-
шеrо общеrо делителя двух чисел. Вместо поисков
наибольшеrо общеrо делителя чисел а и Ь достаточно
найти наибольший общий 'делитель чисел r и Ь. Эта
задача более проста, так как число r меньше, чем
каждое из чисел а и Ь. Чтобы найти наибольший об-
щий делитель чисел r и Ь, мы вновь воспользуемся
тем же методом и разделим ЧIIСЛО Ь на (:
Ь == ql r + '1,
rде ,} меньше каждоrо из чисел Ь и '. В соответ-
ствии с правилам (4.3.3) мы получаем
do==D(a, b)==D(b, r)==D(r, 'д.
62

Далее, таким же способом Qбращаемся с чисами
r: и rl И Т. д. В результате получаем последователь...
ность пар чисел, каждая из которых имеет один и
тот же наибольший общий делитель:
d o === D (а, Ь) === D (Ь, ') ==
=== D (r, ,д == D (rl' (2) ==
. . .
(4.3.4)
Так как остатки постоянно уменьшаются, то эта
ПОGПедо_атальность ДОЛ1Кна закончиться после полу...
..ния овТ8тка rk+l == о. Это происходит при деле.нии
'kl == qk+lrk + о,
Т. е. число 'k делит число rkl. Тоrда
D ('kl, 'k) == 'k,
И ИЗ (4.3.4) видим, что
d o === D (а, Ь) == 'k.
Друrими словаl\1И, число d o равно первому из остат"
ков, который делит предшествующий ему остаток.
При м е р. Найдем наибольший общий делитель
чисел 1970 и 1066. Коrда мы разделим одно число
Н,а друrое и продолжим этот процесс дальше, как
было выше рассказано, то найдем
1970 == 1 · 1066 + 904,
1066 == 1 · 904 + 162,
904 == 5 · 162 + 94,
162=== 1 · 94 + 68,
94 == 1 · 68 + 26,
68 == 2 · 26 + 16,
26 == 1 · 16 + 1 О,
16 == 1 · 10 + 6,
1 О === 1 · 6 + 4,
6 == 1 · 4 + 2,
4 === 2 · 2 + о.
Следовательно, (1970, 1066) === 2.
Этот метод нахождения наибольшеrо общеrо дели'"'
теля двух чисел называется алеорuтмом Евклида, так
53

как первое ero описание содержится в «Началах» Ев-
клида. Этот метод очень удобен для пр:именения в ВЫ'!
числительных машинах.
с и с т е м а з а Д а ч 4.3.
1. Решите задачу 1  1 (с. 49), используя алrоритм
Евклида.
2. Найдите наибольший общий делитель для ка-
ждой из пяти первых пар дружественных чисел.
Сравните результаты с результатами, полученными
с помощью разложения на простые множители.
3. Каким количеством нулей заканчивается число
п! === 1 · 2 · 3. ... · п?
Сверьте свой результат с таблицей факториалов.
 4. Наименьшее общее кратное
Вновь вернемся к дробям. Чтобы ело..
жить (или вычесть) две дроби
с d
 ........
а' Ь'
МЫ ПрИВDДИМ их к общему знаменателю, а затем
складываем (или вычитаем) числители.
При м е р.
2 5 6 25 31
15+9=== 45 + 45==45.
Вообще, чтобы получить сумму
с d
й+Ь'
мы должны найти общее кратное для чисел а и Ь,
Т. е. число т, на которое делятся как число а, так
и Ь. Одно из таких чисел очевидно, а именно, их
произведение m == аЬ; в результате получаем в Ka
честве суммы дробей
!.... + !!.. ===!.!!.. + d а === с Ь + d а
а Ь аЬ аЬ аЬ'
Но существует бесконечно MHoro друrих общих KpaT
ных для чисел а и Ь. Предположим, что мы знаем
разложение этих двух чисел на простые множителн:
а 1 ( а Ь {31 t3 (4 4 1 )
а == Рl · ... · Р,', === Рl · ... · Р,'. · ·
54

Число т, которое делится одновременно на числа а
и Ь, должно делиться на каждыIй простой делитель Pl
чисел а и Ь и содержать ero в степени J1i не меньшей,
чем б6льшая из двух степеней fXi и i. Таким обра...
зам, среди общих кратных существует наименьшее
 1 r
то  р 1 · ... · Р r '
(4.4.2)
в котором каждый показатель степени J1i равен б6ль..
шему из чисел r/..,i и Bi. Очевидно, что число то яв..
ляется наименьшим общим кратным и любое друrое
общее кратное чисел а и Ь делится на то. Для наи..
меньшеrо общеrо KpaTHoro существует специальное
обозначение
то == К (а, Ь). (4.4.3)
При м е р. а == 140, Ь == 110. Разложение на про..
стые множители этих чисел таково:
а == 22. 51 .71 · 11 о, Ь == 21 .51 .70. 111,
следовательно,
К (а, Ь) == 22 · 51 · 71 · 11 1 == 1540.
Существует следующее простое соотношение ме..
жду наибольшим общим делителем и наименьшим
общим кратным:
аЬ == D (а, Ь) К (а, Ь).
Д о к а з а т е л ь с т в о. Перемножив два числа из
(4.4.1), получим
аЬ == Р а l 1 +61 . . ar+r
· · · р, .
(4.4.4)
(4.4.5)
Как мы отмечали, степень числа Pi в D (а, Ь) являет..
ся меньшей из двух чисел r/..,i и i, а в числе К (а, Ь)
она б6льшая из них. Предположим, что cx'i  i. То-
rда степень числа Pi в числе D (а, Ь) равна cx'i, а в
К(а, Ь) равна i; следовательно, в их праизведении
D (а, Ь). К (а, Ь)
она равна r/..,i + i, что в точности равняется степени
в произведении (4.4.5). Это показывает справедли-
вость соотношения (4.4.4).
При мер. а==140, Ь==110, D(a,b)==lO,
К (а, Ь) == 1540.
аЬ == 140 · 110 == 10 · 1540 == D (а, Ь) К (а, Ь).
55

Иа правила (4.4.4) вытекает, что если а п Ь вваимно
простые, то их произведение равно их наИООJJьшему'
общему KpaTHoMyt действительно в ЭТОМ случае
D(a,b)==l и поэтому abK(a,b). '
с и с т е м а з а Д а ч 4.4.
1. Найдите наибольшее общее кратное пар чисел
в системе задач 4.1 (с. 49).
2. Найдите наибольшее общее кратное для ка-
ждой из четырех первых пар дружественных чисел.

r ЛАВА 5
ЗАДАЧА ПИФАrОРА
 1. Предварительные замечания
Во введении ( 3, rл. 1) мы упоминали
об одной из древнейших теореТИКОЧИСЛОВhlХ задач:
"
наити все прямоуrОЛЬНЫ6 треуrольники с цеJ10числен-
"
выми сторонами, т. 6. наити все целочисленные pet!
шения уравнения
х 2 + у2 === z2. ( 5. 1 .1 )
Эта задача может быть решена с использованием
ЛИШЬ простейших свойств чисел. Прежде чем присту-
пить К ее решению, проведем некоторые предвари-
тельные исследования. ТрОЙI<а целых чисел
(х, у, z),
(5.1.2)
удовлетворяющая уравнению (5.1.1), называется пи..
фаZОРО80U тройкой. Отбросим тривиальный случай,
коrда одна из сторон треуrольника равна нулю.
Ясно, что если мно)кество (5.1.2) является лифа-
rоровой тройкой, то любая тройка чисел
(ах, ky, kz),
(5.1.3)
получающаяся умножением каждоrо из этих чиеел на
некоторое целое число k, также будет пифаrоровой,
и наоборот. Таким образом, при поиске решений до-
и
статочно оrраничиться нахождением простеUШllХ тре..
У20льн,UКО8, длины сторон которых не имеют общеrо
множителя k > 1. Например, тройки
(6, 8, 1 О),
( 15, 20, 25)
являются пифаrоровыми тройками, получающимися
из простейшеrо решения (3, 4, 5).
в простейшей тройке (х, у, z) не существует об-
щеrо множителя для всех трех чисел. В действитель-
57

насти справедливо более сильное утверждение: ни..
какие два числа из простейшей тройки не имеют об..
Jцеrо множителя, т. е.
D (х, у) == 1,
D(x, z)== 1,
D (у, z) == 1.
(5.1.4)
Чтобы доказать это, предположим, что, например, х
и у имеют общий делитель. Тоrда они имеют общий
простой делитель р. В соответствии с (5.1.1) число р
должно также делить и z. Итак, (х, у, z) не может
быть простейшей тройкой. Такие же рассуждения
применимы для доказательства остальных двух
утверждений.
Рассмотрим еще ряд свойств простейших троек.
Мы только что получили, что числа х и у не MorYT
быть оба четными, но мы можем также показать, что
они не MorYT быть и оба нечетными. Действительно.
предположим, что
х == 2а + 1, у == 2Ь + 1.
После возведения в квадрат этих чисел и сложения
их, получим число
х 2 + у2 == (2а + 1)2 + (2Ь + 1)2 ==
== 2 + 4а + 4а 2 + 4Ь + 4Ь 2 == 2 + 4 (а + а 2 + ь + Ь 2 ),
делящееся на 2, но не делящееся на 4. В соответ.
ствии с (5.1.1) это означает, что Z2 делится на 2, но
не делится на 4, но это невозможно, так как если Z2
делится на 2, то и z делится на 2, но тоrда Z2 делится
на 4.
Так как одно из чисел х и у........ четное, а друrое.........
нечетное, то z  также нечетное. Для определенно-
сти будем считать, что в наших обозначениях число
]с ......... четное, а у ......... нечетное.
 2. Решение задачи Пифаrора
Чтобы найти простейшие решения уран..
нения Пифаrора (5.1.1), перепишем ero в виде
х 2 === Z2  у2 == (z + у) (z  у). (5.2.1)
Вспоминая, что х  четное, а у и Z........ оба нечетные
получаем, что все три числа
х, z + у, z  у
58

четные. Тоrда мы можем разделцть обе части урав-
нения (5.2.1) на 4 и получить
( 1 ) 2 1 1
2 х == 2 (z + у) · 2 (z ........ у).
(5.2.2)
Обозначим
1 1
тl == 2" (z + у), пl == "2 (z  у);
тоrда уравнение (5.2.2) перепишется как
( ; х у == тjпj.
(5.2.3)
(5.2.4)
Числа тl и nl взаимно простые. Чтобы это уви
деть, предположим, что
d == D (ml, nl)
есть наибольший общий делитель чисел тl и пl. To
rда, как это следует из Э 1 rл. 4, число d должно
делить оба числа
тl + пl == Z, тl  пl == у.
Но единственным общим делителем чисел z и у в
простейшей тройке может быть только 1, поэтому
d === D (тl, пд == 1. (5.2.5)
Так как произведение (5.2.4) этих двух взаимно
простых чисел является квадратом, то можно исполь-
зовать результат, изложенный в конце  2 rл. 4
(стр. 50), соrласно которому числа тl и пl являются
квадратами
тl == т 2 , пl === п 2 , D (т, п) == 1. (5.2.6)
Здесь мы можем без нарушения общности считаТЬ t
что т > О, n > о. Теперь подставим т 2 и п 2 вместо
тl и пl соответственно в уравнения (5.2.3) и (5.2.4);
получим
1 1 1 1 1
т 2 == 2 z + 2 у, п 2 === 2" z  "2 у, т 2 п 2 == 4" х 2 ,
т. е.
х == 2тп, у === т 2 ........ п 2 , z == т 2 + п 2 . (5.2.7)
Проверка показывает, что эти три числа всеrда удов"
летворяют соотношению Пифаrора х 2 + у2 == Z2.
59

ОСl'8.лось определить, какие целые ,положительные
числа т и п в действительности соответствуют про..
стейшим треуrольникам. Докажем, что следующие
три условия на числа т и n являются необходимыми
и достаточными:
(1) (т, п) === 1,
(2) т > n,  (5.2.8)
(3) одно из чисел т и п четное, а друrое............ нечетное.
Д о к а з а т е л ь с т в о. Сначала покажем, что ес..ТIИ
числа х, у, z образуют простейшую тройку, ТО усло...
вия (5.2.8) выполняются. Мы уже показали, что
условие (1) является следствием Toro, что числа
х, у, z взаимно простые. Условие (2) следует из Toro,
что числа х, у, z  положительны. Чтобы увидеть,
что ус.повие (3) неоБХОДИ1\10, заметим, что если т и п
оба нечетные, то в соответстrrии с (5.2.7) У и z были
бы оба четные, в противоречие с результатами, полу'"
ченны.1И в конце предыдущеrо параrрафа.
Наоборот, если условия (5.2.8) выполнены, то со..
отношения (5.2.7) определяют простейшую тройку'
условие (2) обеспечивает по-ложит@льность чисел Х,
у и z.
Moryr ли какиенибудь два из этих трех чисел
иметь общий простой множитель р? Такое простое
число р, делящее два из них, должно также делить
и третье в силу соотношения х 2 + у2 == Z2. Если чис...
ло р делит Х, ТО оно в соответствии с (5.2.7) должно
делить 2mn. Число р не может равняться 2, потому
что у и Z нечетные в соответствии с условием (3) и
(5.2* 7). Предположим, что р =t= 2  нечетное простое
число, делящее т. Тоrда условие (1) и выражение
(.2.7) показывают, что р не может делить у и z. Та...
кие же рассуждения применимы и для случая, если р
делит число n.
Найдя необходимые и достаточные условия (5.2.8)
для TOI'O, чтобы т и п давали простейший треуrоль"
ник, можно вычислить все такие треуrольники с по...
мощью соотношения (5.2.7). Например, пусть
т === 11, n == 8.
Наши условия выполнены, и мы находим, что
х === 176, У == 57, Z === 185.
60

в табл. 3 приведены все простейшие треуrолъники
х, у, z для нескольких первых зна'чений чисел т и n.
Таблица 3
 2 3 4 5 6 7
I
1 4,3,5 8,15, 17 12,35,37
2 1215,13 20,21,29 28145,53
3 24,7,25
4 40,9,41 56,33,65
5 60, 11 ,61
6 I 84,13,85
с и с т е м а з а Д а ч 5.2.
1. Продлите таблицу для всех значений т  10.
2. MorYT ли два разных набора значений чисел т
и п, удовлетворяющих условию (5.2.8), дать один и
тот же треуrолъник
3. Найдите все пифаrоровы треуrольники, у кото-
рых длина rипотенузы не превосходит 100.
 3. Несколько задач
о треуrольниках Пифаrора
Мы решили задачу наХО}I{дения всех
треуrолъников Пифаrора. Здесь, как почти всеrда в
математике, решение одной задачи приводит к по-
становке ряда друrих задач. Часто новые вопросы
оказываются значительно более трудными, чем пер-
воначальный.
Одним из естественных вопросов о простейших
треуrольниках является следующиЙ. Пусть задана
одна из сторон простейшеrо треуrольника Пифаl'ора,
как найти остальные? Первым рассмотрим случай,
коrда известна сторона у. В соответствии с (5.2.7)
У === т 2  п 2 === (т + п) (т  п), (5.3.1)
rде т и п числа, удовлетворяющие условиям (5.2.8).
В уравнении (5.3.1) множители (т+п) и (т'п)
взаимно простые. Чтобы в этом убедиться, заметим,
что эти множители
а==т +п,
b===m11,
(5.3.2)
61

оба нечетные, так как одно из чисел т и п HeQeTHOe s
а друrое четное. Если числа а и Ь имеют обший не-
четный простой множитель р, то число р должно
было бы делить каждое из чисел
а + ь == т + п + (т  п) == 2т
и
а  ь == т + п  (т  п) == 2п,
т. е. р должно было бы делить числа т и п. Но это
невозможно, так как D (т, п) == 1.
Предположим теперь, что есть разложение дан-
Horo нечетноrо числа у на два множителя
у==а. Ь,
Из (5.3.2) получаеlv1
1 1
т === 2" (а + Ь), п == "2 (а  Ь).
а> Ь,
D(a, Ь) === 1.
(5.3.3 )
(5.3.4)
Эти два числа также взаимно простые, поскольку лю...
бой их общий множитель должен был бы делить чис..
ла а == т + n и Ь == т  n. Кроме Toro, числа т и n
не MorYT быть оба нечетными, ибо тоrда каждое из
чисел а и Ь делилось бы на 2. Отсюда заключаем, что
числа т и n удовлетворяют условиям (5.2.8) и, таким
образом, определяют простейший треуrольник, одна
из сторон KOToporo у == т 2  п 2 .
При м е р. Пусть у == 15. Для Hero существуют
два разложения на множители, удовлеТВОРЯЮI.цие
условиям (5.3.3), а именно:
у == 15 · 1 == 5 · 3.
Первое из них дает
m==8, n===7, х== 112, у== 15, z=== 113,
а второе
m==4, п== 1, х==8, у== 15, z== 17.
Пусть, далее, задана сторона х. Так как какое"то
из чисел т или n делится на 2, то очевидно, что
х == 2mn должно делиться на 4. Если разложить чис..
по х/2 на два взаимно простых множителя, то боль..
u 
шин из них можно взять в качестве числа т, а мень..
ший ...... n.
62

При м е р. Возьмем х === 24; тоrда
1
2" х == 12 · 1 == 4 · 3.
Первое разложение дает
m== 12, n== 1, х==24, у=== 143, z=== 145,
а второе
т==4, n==3, х==24, у==7, z==25.
Третий и последний случай ПрИБQДИТ нас к не-
обходимости коснуться одной важной задачи теории
чисел. Если z  rипотенуза простейшеrо треуrольни-
ка Пифаrора, то в соответствии с (5.2.7) имеем
z ' т 2 + п 2 , (5.3.5)
Т. е. число z есть сумма квадратов чисел т и n, удов-
летворяющих условиям (5.2.8).
Это приводит нас к постановке вопроса, уже ре-
шенноrо п. Ферма: к,оеда целое число можно пред--
ставить в виде CYM/J1tbt квадратов двух целых чисел:
z == а 2 + Ь 2 ? (5.3.6)
На время забудем все оrраничения на числа а и Ь.
Пусть они MorYT иметь общие множители, а также
каждое из них, или даже сразу оба MorYT обращаться
в нуль. Перечислим все целые числа, меньшие десяти,
представляемые в виде суммы двух квадратов:
О == 02 + 02, 1 == 12 + 02, 2 == 12 + 12,
4 == 22 + 02, 5 == 22 + 12, 8 === 22 + 22,
9==32+02, 102==32+12.
Оставшиеся числа 3, 6 и 7 не представляются в виде
суммы двух квадратов.
Опишем, как можно выяснить, является ли число
суммой двух квадратов. К сожалению, мы не можем
привести здесь доказательства ввиду ero сложности.
Рассмотрим вначале простые числа. Каждое про-
стое число вида р == 4п + 1 всеrда является суммой
двух квадратов; например,
5==22+ 12, 13==32+22, 17==42+ 12,
29 == 52 + 22.
БЗ

Существенно, что такое представление может осу..
ществляться единственным способом.
Остальные нечетные простые числа имеют вид
q == 4п + 3, т. е.
q===3,7, 11, 19,23,31, ...
Ни одно такое простое число не представляется в
виде CYl\1MbI двух квадратов; более Toro, вообще ни
одно число вида 4п + 3 не может быть представлено
в виде суммы ДВУХ квадратов. Чтобы убедиться в
этом, заметим, что если целые числа а и Ь оба чет..
ные, то а 2 и Ь 2 оба делятся на 4, отсюда и а 2 + Ь 2
делится на 4. Если они оба нечетные, например, а ==
=== 2k + 1, Ь == 2l + 1, то а 2 + Ь 2 === 4k 2 + 4k + 1 +
+ 4[2 + 41 + 1 === 4 (k 2 + [2 + k + l) + 2, поэтому а 2 + Ь 2
имеет при делении на 4 остаток 2. 11 наконец, если
одно из целых чисел а и Ь четное, а друrое  нечет..
ное, С ка 2кеl\f, а === 2ft, + 1, Ь === 21, то
а 2 + Ь 2 == 4k 2 + 4k + 1 + 4[2
и имеет при делении на 4 остаток 1. Итак, мы пере-
брали все возможности и можем заключить, что сум-
ма двух квадратов никоrда не представима в виде
411 + 3.
Чтобы закончить наше исследование для простых
чисел, заметим, что 2 === 12 + 12.
Для Toro чтобы проверить, является ли составное
число z суммой ДВУХ квадратов, разложим ero на
простые множители
а а (J,t.
Z === p l. p 2. . p 
1 2 ... k.
.
(5.3.7)
Число z оказыIаетсяя суммой двух квадратов тоrда и
только тоrда, коrда ка)кдое простое число Pi вида
4п + 3 входит в разложение в четной степени.
При м еры. Число z === 198 === 2. 32 · 11 не является
суммой ДВУХ квадратов, так как 11 имеет вид 4п + 3 и
входит в разложение в первой степени.
Число z === 194 == 2.97 является суммой двух KBaд
ратов, так как ни один из ero простых множителей не
является числом вида 4п + 3. Действительно,
z === 132 + 52.
Вернемся к нашей первоначальной задаче Haxo
ждения всех чисел z, которые MorYT быть rипотену",
64

вами протейших треуrоJlЬНИКОВ' ПифаrQра. Такое
число z ДОЛЖНО быть предстаВИl\10 в виде z == т 2 + п 2 ,
rде числа т и п удовлетворяют условиям (5.2.8). Не-
обходимым и достаточным условием для этоrо яв
u 
ляется следующее: каждым из простых множителеR
числа z ДОcJ1Jжен иметь вид 4п + 1. Доказательство
этоrо утверждения мы -вновь опускаем.
При м еры. z == 41. Это число леrко представить
в виде суммы двух квадратов искомоrо вида, z ==
=== 52 + 42, так что т === 5, п == 4 и х === 40, у === 9,
z === 41 выра}кают длины сторон соответствующеrо
треуrольника.
z === 1105 == 5.13.17. Существуют четыре представ
.ления этоrо числа в виде суммы двух квадратов:
1105 === 332 + 42 == 322 + 92 === 312 + 122 == 242 + 232..
Стороны соответствующих треуrольников вычислите
самостоятельно.
. .
Целый ряд задач о треуrольниках Пифаrора мо-
жет быть решен при помощи наших формул (5.2.7)
х==2тп, y==т2n2, Z==т 2 +n 2 .
Наприм-ер, можно искать треуrо.пьники Пифаrора с
заданной площадью А. Если такой треуrольник яв"
лstется простейшим, то ero площадь равна
1
А == 2 ху == тn (т  п) (т + п). (5.3.8)
Здесь три из четырех мно}кителей нечетны. Нет руд но
видеть, что они попарно взаимно простые. ПОЭТОl\fУ,
чтобы найти все возможные значения чисел т и n,
можно выделить из числа А два взаимно простых не..
четных множителя k и 1 (k > [), поло}кив
т + п === k, т  п ;:::: [,
что дает
1
т ==2" (k + 1),
1
п === "2 (k  [).
После этоrо мы проверяем, удовлетворяют ли эти
числа условиям (5.3.8).
Рассуждения несколько упрощаются, если заме-
тить, что два множителя в выражении (5.3.8) MorYT
равняться 1 только в единственном случае:
т == 2,. n == 1, А == 6.
3 о" Оре
65

Действительно, два множителя в (5.3.8) MorYT быть
равны 1, только если
п==тп==l,
что и дает указанное выше значение.
При м е р. Найдеl\1 все треуrольники Пифаrора с
площадью А == 360. Разложение числа А на простые
множители таково: А === 23. 32. 5. Число А может быть
единственным образом записано в виде произведе..
пия четырех взаимно простых множителей: А::;::::
=== 8. 1 · 5. 9. Если мы ищем простейший треyrольник,
то т + п === 9. Однако если т === 8, то fl === 1 и т 
.......... n === 7, но А не делится на 7, а вторая возможность
(п === 8, т === 1) исключается условием т > n. Поэто"
му TaKoro треуrольника не существует.
Этот результат не исключает возможности суще..
ствования треуrольников с площадью А === 360, не яв"!!
ляющихся простейшими. Следующее соображение мо'"
жет быть использовано в общем случае для нахо-
ждения треуrольников заданной площади, не являю..
щихся простейшими. Если длины всех сторон тре..
уrольника имеют общий делитель d, Т. е. MorYT быть
записаны как
dx,
то ero площадь равна
1
А == 2 dx dy == d 2 mn (т ........ п) (т + п).
dy,
dz,
Таким образом, число d 2 является множителем чис
ла А и, если число d есть наибольший общий делитель
длин сторон, то число
А
Ао === d 2 == тп (т  п) (т + п)
должно быть площадью простейшеrо треуrольника.
Применим полученный результат к только что
рассмотренному случаю А == 360. У этоrо числа СУ8
ществуют три множителя, являющиеся квадратами;
d}===4,
d 2 == 9,
d з === 36.
Соответственно находим
А
 == 90 == 2 · 32 · 5
d 1 '
66
А
 === 40 == 23 · 5,
d 2
А
=== 10=== 2. 5.
d з

Не существует способов написать, число 40 или 1 О
в виде про изведения четырех взаимно простых мно-
жителей, а число 90 может быть представлено в та..
ком виде, причем единственным образом, а именно:
90 == 1 · 2 · 32 · 5.
(В числе сомножителей 1 может встречаться не бо..
JIlсе f ОДНОfО раза, за исключением случая т == 2, п == 1,
A,6.) Так как наибольшим множителем является 9,
то М:ы должны взять т + п === 9. Однако, перебирая
все возможные значения т === 1, 2, 5, получим соот"
ветственно п == 8, 7, 4. Условие т > п исключает все
СJIучаи, кроме ln == 5, п == 4, для KOToporo, однако,
тп(т+п)(тп)*90. Итак, мы получили, что не
существует ни простейшеrо, ни иноrо треуrольника
Пифаrора с площадью А == 360.
Можно было бы затронуть еще MHoro друrих во..
просов, но упомянем лишь об одном из них. Пери..
метр треуrольника равен
с == х + у + z;
(5.3.9)
для простейшеrо треуrольника Пифаrора получаем
с == 2тп + (т 2  п 2 ) + (т 2 + п 2 ) == 2т (т + п).
Мы предоставляем читателю самому отыскать метод
нахождения всех треуrольников Пифаrора с задан..
ным периметром. Не пренебреrайте рассмотрением
числовых примеров.
Мы решили задачу построения всех треуrольни",
КОВ Пифаrора. Это ведет нас к исследованию более
общих связанных с ней задач. Естественным обобще..
ннем задачи Пифаrора является задача repOHa, на..
званная по имени древнеrреческоrо математика re-
рона, жившеrо в Александрии: найти все треУ20ЛЬflU
КU с целочислеННblАtи сторонами, площади которых
также выражаются целыми числами. Эта задача OT
личается от задачи Пифаrора тем, что условие на",
личия прямоrо уrла заменено требованием целочис..
ленности площади. Очевидно, что всякий треуrоль..
ник Пифаrора удовлетворяет условиям задачи [е..
рана.
Для про верки Toro, является ли данный треуrоль"
ник треуrольником [€pOHa, проще Bcero применить
З* 67

формулу [еро на ДЛЯ площади треуrольника
A===V  c(  cx)(  cy)(  cz),
rде с  это периметр треуrольника, определенный в
(5..9). Хотя известно значительное число треуrоль..
ников [ерона, не существует общей формулы, описы-
вающей все эти треуrольники. Приведем несколько
из них (не прямоуrольных):
х=== 7
9
13
39
у === 15
10
14
41
z === 20
17
15
50
Мы не м Qже1\1 зан:ончить рассказ о треуrольника)(
Пифаrора, не упомянув об ОДНОЙ из самых знамени-
тых проблем математики, rипотезе п. Ферма:
для n > 2 не существует натуральных чисел х,
у, z таких, что
х n + уn === zn.
Эта идея пришла к Ферма в то время, коrда он изу"
чал перевод с rреческоrо «Арифметики» Диофанта.
В этой книrе в основном рассматриваются задачи, в
решении которых применяются формулы для нахо..
ждения треуrольников Пифаrора. Читая эту книrу,
Ферма делал пометки на полях.
Ферма был взволнован своим «открытием», он
верил, что у Hero есть удивительное доказательство, и
сожалел, что не l\ложет ero записать, так как поля
слишком узки. С тех пор эта задача занимает MTe..
матиков. Для нахождения доказательства изобрета..
лись самые искусные l\fетоды; этот поиск привел к
открытцю новых фундаментальных теорий в f\tlaTeMa-
тике. Используя теоретические разработки и вычис
ления на ЭВМ, было показано, что теорема Ферl\1а
справедлива для Iноrих значениЙ степени n. В на"'
стоящее время мы знаем, что этот результат выпол"
няется для всех значений n, удовлетворяющих нера..
венству 3  n  4002.
Попытки самых выдающихся матеIаТИI{ОВ в тече-
ние столетий найти общее доказательство оказались
тщеТН!1IМИ. Поэтому распространилось мнение, что
68

Ферма, несмотря на Сll()Й беССП6рНЫЙ талант, стал
жертвоЙ самооБJ\fана. Как бы ни широки были поля
КНlfrи, маловероятно, что ero доказательство было бы
верным.
I<ончно, вы имеете право попробовать своп силы
в до[{зsательстве этоЙ теоремы. но предупре}l{даем,
что ещ ни одна теорем:а в математике не имела
столько неправильных доказательств, как теореМа
Ферма. ЛЙшь HeKOfopbIe lIЗ них прннадле)кат xopo
шим матемаТIIкам, остальные  дилетантам. Доказа.. .
" тельства «последнеЙ теоремы Ферма» продолжают
появляться в почте известных математиков, занимаю..
щихся теорией чисел. Большинство из этих доказа"
тельств сопрово}кдается письмами с требованием о
немедленном всемирном признании и выплате денеж..
ной! премии, установленной одним немецким матема-
тиком (эта премия давно уже обесценилась в резуль...
тате инфляций). \
с и с т е 1\1 а з а Д а ч 5.3.
1. Найдите все такие треуrольники Пифаrора, у
которых длина одной из сторон равна: а) 50, б) 22.
2. Используя условие представимости числа в виде
суммы двух квадратов, определите, какие из чисел
100, 101, ..., 110 MorYT быть представлены в таком
виде. Если возможно, найдите все представления. Ка..
кое из этих чисел может быть rипотенузой простей
шеrо треуrольника Пифаrора?
3. MorYT ли быть треуrольниками Пифаrора тре-.
уrОJ1ЬНИКИ с площадями А == 78, А == 120, А == 1000?
" 4. Найдите все треуrольники Пифаrора с пери..
метрами с === 88, с == 110.

r JIABA 6
..
СИСТЕМЫ СЧИСЛЕНИЯ
 1. Числа
«Все есть число»  учили древние пифа-
rорейцы *). Однако количество чисел, которыми они
пользовались, ничтожно по сравнению с фантастиче
екоЙ пляской цифр, окружающих нас сеrодня в ПО ool
вседневной жизни. OrpoMHbIe числа появляются, КО-
rда считаем мы, и тоrда, коrда считают нас. В нашу
жизнь прочно вошли: номера домов, квартир, теле-
фонов, счетов, почтовые индексы. Каждый день на-
полнен потоком счетов, чеков и друrих бухrалтерских
документов. rосударственный БЮД2кет исчисляется в
миллиардах, а ropbI статистических данных являются
принятым доводом В спорах. Эти цифры «крутятся»
В компьютерах, которые анализируют состояние про
изводства, следят за траекториями спутников и ис-
следуют атомные ядра со скоростью до одноrо МИЛО(
лиарда операций в секунду.
Ко всему этому вела длинная дороrа, начавшаяся
с первых попыток человека систематизировать OKPY
)кающие ero числа, коrда они стали столь большими,
что их нельзя уже было посчитать на пальцах. Были
перепробованы различные способы rруппировки чи
сел; большинство из них осталось на обочине этоrо
пути, не выдержав конкуренции с друrими система
ми., К настоящему времени, по счастью, наша деся-
теричная, или десятичная, система счисления, ОСНО4!
ванная на rруппировании десяткаи, принята почти
всюду; в некотором отношении эта система, повиди"
мому, случайно, оказалась той золотой серединой, KO
торая одинаково хорошо удовлетворяет' разнообраз-
ным требованиям при работе с числами.
*) Последователи философской школы Пифаrора. (П рим,
перев. )
10

Нет необходимости подробно описывать эту си-
стему. Первые два rода обучения в школе дают нам
на всю жизнь почти подсознательное знание Toro, что
означает последовательность цифр, например,
75 == 7 · 10 + 5,
1066 == 1 · 103 + о · 102 + 6 · 1 О + 6,
1970== 1.103+9 .102+7 .10+0.
И вообще, в системе, основанной на числе 10,
ananl ... a2 a l a O
(6.1.1 )
о.значает число
N==an.l0n+an1.10n1+ ...
. .. + а2 · 102 + аl · 1 О + ао, (6.1.2)
rде коэффициенты, или цифры, ai MorYT принимать
следующие значения:
ai === {О, 1, ..., 9}.
(6. 1.3)
Число Ь === 1 О называется основан'ием этой системы.
Индоарабская числовая система пришла в Европу с
Востока около 1200 r. нашей эры, и с тех пор не
оспаривалась. Она известна как позициОн'н'ая систе-
ма, так как место каждой цифры определяет ее зна-
чение; использование символа О дает возможность
просто и безболезненно обозначать пустующее место.
Более Toro, оказалось, что эта система очень удобна
при арифметических операциях с числами: сложении,
вычитании, умножении и делении.
9 2. Друrие системы
Известны различные друrие системы, ко..
торыми пользовались народы мира, чтобы навести
порядок среди чисел. Но почему и как возникли эти
системы? Ответы на эти вопросы большей частью
затерялись в туманном прошлом человечества.
Никто не сомневается, что широко используемая
rруппировка' десятками объясняется тем, что люди
считали на пальцах. Довольно странно, что сохрани-
лось мало свидетельств Toro, что человек считал на
одной руке; пятеричная система встречается исклю"
71

чительно редко,. Нр в то же время очень часто ветре...
чаются примеры двадцатеричной системы. Не нужно
И}.lеть семи пядей во лбу, чтобы понять, что в этой
системе в nроцессе счета участвуют пальцы как рук,
так и Hor. Из этих двадцатеричных систем счисления,
возможно, самая известная  система племени l\fаЙя,
но и в Европе такие системы были широко распро
странены несколько столетий назад. ДвадцатеРИЧ1l3Я
система прослеживается во французском языке в ЧIIIС
лах от 80 до 100, что мо)кно увидеть из слеД.УЮЩIИХ
примеров:
80 == quatrevingts ==
== четыре раза по двадцать,
90 === quatrevingtsdix -===
== четыре раза по двадцать и десять
91 === quatrevingtsonze ===
=== четыре раза по двадцать и одиннадцать
и так далее.
Менее известно, что в датском языке счет парами
десятков процветает вплоть до наших дней. Эта дpeB
няя система, которая ранее была широко распростра
'вена среди rерманских племен, столь ориrинальна,
что мы не можем не привести хотя бы несколько ее
деталей.
При счете до 20 естественно использовать такие
термины, KaI<:
tredsindstyve == три раза по двадцать,
firsindstyve === четыре раза по двадцать,
femsindstyve == пять раз по двадцать.
Но система становится более сло)кноЙ, если усло
вн\ться, что всякий раз, коrда мы просчитаем несколь
ко полных двадцаток, а затем еще десяток, объяв
лять, что находимся на половине следующей ДBaдцaT
ки; например,
90 == halvfemsindstyve === половина пятой двздцатки.
Чтобы закончить наше описание, следует сказзть,
что в датском языке количество единиц ставится пе-
72

l'ед количеством десятков, что ПРИВОДМt к 'числовым
конструкциям типа
93 === treoghalvfemsindstyve === три и половина пятой
двадцатки.
Ясно, что в любой ЦИВИЛlIзации, насыщенной чис-
лами, подобно нашей, такие системы обречены. Спо-
:аоб записи чисел, при котором единицы ставятся пе-
ред десятками, особенно неприятен. Такая система
бlJ1>Iла также распространена в Анrлии дО XVIII века:
Bl\lIeCTO twenty-tllree (двадцать три) обычно rоворили
1hree and twenty (три и двадцать). В Норвеrии лишь
несколько лет назад парламент специальным зако-
ном отменил использован:ие таI{ОЙ системы в школах
и всех официальных сообщениях. Однако подобная
система продол)кает процвета.ть в rермании, что при-
водит к мноrочисленным числовым ошибкам, напри..
мер, при набирании номера телефона.
С давних времен до наших днеЙ астрономы поль-
зуются древней вавилонской шестидесятеричной си-
стемой (с основанием 60). Правда, сейчас ее достоин-
ства уменьшились, но мы все же придерживаемся
этой системы при отсчете времени и уrлов в минутах
и секундах. Мы не знаем, почему вавилоняне ввели
столь большое основание в свою систему, можно лишь
предположить, что эта система возникла как комби..
нация двух систем с различными основаниями, ска-
. жем, 10 и 12, у которых наименьшее общее кратное
равно 60.
Теперь скажем несколько слов о математических
вопросах, связанных с использованием систем с раз-
личными основаниями. При основании Ь мЫ записы-
ваем целое число
N === спь n + Cп1bn 1 + ... + С2 ь2 + Сl Ь + СО (6.,2.1)
та'к же, как и в (6.1.2), с той разницей, что здесь
коэффициенты Ci MorYT принимать значения
с i === О, 1, ..., Ь........ 1, (6.2,2)
BMCTO значений, приведенных в (6.1.3). Для крат-
ности можно записать число N из (6.2.1) в сокра-
.щенной форме
(сп, С n ':"1, '. · ., 'С2' 'Сl, СО)Ь,
(6.2.3)
73

с-оответствующей записи (6.1.1), при этом в записи
(6.2.3) необходимо приписать используемый базис.......
число Ь, чтобы избе)кать путаницы.
При м еры. В шестидесятеричной системе
(3, 11,. 43)60 == 3 · 602 + 11 · 60 + 43 == 11 503.
в системе с основанием Ь == 4
(3, 2, о, 1)4 === 3 · 43 + 2 · 4? + о · 4 + 1 == 225.
Вообще, коrда число задано в системе с OCHOBl
нием Ь, мы находим это число в обычной десятичной
системе, вычисляя значения степеней числа Ь, YMHO
жая каждое из них на соответствующую цифру и
складывая, как уже делалось в вышеприведенных
примерах.
Теперь рассмотрим обратную задачу. Задается
число N и мы хотим представить ero при основа'"'
нии Ь. Мы можем сделать это повторным делением
на Ь. Взrляните на формулу (6.2.1). Можно записать
ее в виде
N == (Cпbnl + ... + С2Ь + Cl) ь + Со.
Так J{aK Со меньше, чем Ь, то Со является остатком
при делении числа N на Ь. Мы можем записать это
деление
N == qlb + Со, ql == Cnbnl + ... + С2 Ь + Сl,
для TOrO чтобы показать, что Cl получается делением
числа ql на Ь тем же способом, и т. д. Таким образом:
мы находим коэффициенты Ci в результате серии де..
лений на число Ь:
N == q1b + Со,
ql == q2 b + Ct,
. . . . . .
qnl == Qn b + Cn...t,
qn === О · Ь + Сп,
при этом мы продолжаем деление до тех пор, пока
не окажутся выполненными соотношения qn < Ь,
qп+l == о. Мы приводим два примера, которые помоrут
вам понять этот процесс.
14

Пример 1. Выразим число 101 при основании 3.
Мы выполняем деление на 3, как указывалось выше,
и находим
Отсюда
1 О 1 === 33 · 3 + 2,
33 === 1 1 · 3 + О,
11 === 3 · 3 + 2,
3 === 1 · 3 + О,
1==0.3+1.
]01 == (1, О, 2, О, 2)з.
При м ер 2. Выразим число 1970 при основании
12. Здесь деление на 12 таково:
1970 == 164. 12 + 2,
164==13.12+8,
13== 1.12+ 1,
1 ==0.12+ 1.
Следовательно, 
1970 ==- (1, 1, 8, 2)12.
с и с т е м а з а Д а ч 6.2.
1. :Выразите числа (1, 2, 3, 4) 5, (1, 1, 1, 1, 1, 1) 3 В
десятичной систе:ме.
2. Представьте числа 362, 1969, 1 О 000 при основа..
ниях Ь == 2; 6; 17.
 3. Сравнение систем счисления
Американское общество сторонников две...
надцатеричной системы предложило изменить нашу
десятеричную систему на более эффективную иудоб..
ную, как они думают, систему с основанием 12. Те,
кто предлаrает эту систему, указывают, что было бы
выrоднее иметь систему с основанием, делящиl\tIСЯ на
числа 2, 3, 4 и 6, так как процесс деления на эти ча
сто встречающиеся делители упрощается. Доводы та..
Koro типа привели бы нас к шестидесятеричной си.,j
стеме, основание которой, число 60, делится на числа
2, 3, 4, 5, 6, 1 О, 12, 15, 20, 30.
75

В ряде стран н{)rие вещи все еще считают ДЮЖИ"
нами и; rроссами (т. е. дюжинами ДЮЖИН) и есте..
ственно, что для них двенадцатеричная система яв...
ляется вполне возможной. Для перехода в двенадца..
rеРИЧНУIО систему нужно было бы ввести двенадцать
новых символов, что потребует для их разработки
столь же MHoro усилий, сколько потребовалось для
создания десятеричноЙ системы. Некоторые энтуз И а,"
сты считают, что необходимо ввести новые СИМВОЛрI
ЛИШЬ для 10 и 11, но такой способ не учитывает .не;
удо6ств, возникающих в период перехода: никто не
б.удет понимать, например, означает ли запись 325
3 · 102 + 2 · 1 О + 5 == 325
или
3 · 122 + 2 · 1 2 + 5 == 461 .
Для Toro чтобы ПОiIУЧИТЬ представление о том,
как меняется количество знаков в числе в зависимо
сти от системы счисления, возьмем число
n
 
1 О'  1 == 99 ... 9 == N
(6.3.1 )
в десятеричноiI системе. Это самое большое число с п
3,наками. Чтобы найти т  количество знаков при
записи этоrо числа при основании Ь  МЫ дол}кны
()цределить т как целое число, для KOToporo выпол"
няются неравенства
ь т > lOn  1  bтl. (6.3.2)
Это условие мо}кет быть также записано в виде
ь т  1 ОП > bт,l.
Возьмем лоrарифмы этих трех чисел. Вспомнив,
что Ig 10 == 1, получим, что
тlgb п > (т  l)lgb.
В свою очередь эти неравенства MorYT быть пе..
рписаны в виде
n
ттgь>тl;
(6..з.3)
таким образом, т является первым целым числом
не меньшим, чем
п
19 Ь ·
(6.3.4)
'16

Отсюда дел а e1\J1 вывод, что, rрубо rоворя, т.......... но-
вое 'количество знаков, может быть получено деле-
Hi1eM числа п на 19 Ь.
При м еры. Пусть вновь n будет количеством
Rh-аков числа в десятичной системе. Для Ь == 2 мы
имеем: Ig2 == 0,30103, таким обраЗО1\l, количество
цифр в двоичной системе приблизительно равно 3,32п.
Kor.1J.a Ь === 60, мы И1\1еем: 1960 === 1,778, отсюда КОJ1И
"fecTBo знаков прпблизительно равно 0,56 'п, т. е. Н'е-
MHoro больше, чем половина количества знаков в
десятичной системе.
Ясно, что КОрОТКИl\1И числами удобнее опериро-
вать. Но, с друrой стороны, числа при б6льших осно-
ваниях имеют ряд недостатков. Вопервых, нужно
иметь названия и обозначения для Ь различных цифр,
37 ==    w == ]./0+7
Рис. 15.
чеrо обычно нет для больших значений Ь. Например,
в вавилонской шестидесятеричной системе считали
единицы до 60, rруппируя их по десять, как показано
на рис. 15.
Это означает в действительности, что эта система
расщеплялась на подсистемы с десятеричной записью.
Аналоrичная ситуация существует в двадцатеричной
систе1'ле народа майя. Здесь цифры до 20 считались
пятерками, как показано на рис. 16.
Вторым и rораздо ббльшим недостатком является
u
трудность, возникающая при попытках вычислении с
помощью обычных методов. Коrда мы выполняем
действие умножения, то пользуемся знанием наиусть
таБлицыI умножения, т. е. знанием произведеl-IИЙ всех
десяти цифр. Эта таблица Пифаrора, как ее назы'!l
l3ают во мноrих странах, вдалбливалась нам в тече
вне первых школьных лет, и знаем мы ее почти авто..
матически. Это знание не столь тривиально,! как мы
СI\ЛОННЫ думать. Из средневековых. рифме'r.ических
11НУСКРИПТОВ ясно видно, что умножение было на
rрани высшей математики, а деление больших чисел
77

было в действительности редким искусством. Но
"
можно привести и rораздо оолее поздние примеры.
Самюэль Пепис, известный блаrодаря своему
дневнику, был в возрасте около тридцати лет и слу.
жил клерком канцелярии лорда-хранителя печати, ко-
rда летом 1662 rода он решил, что он должен знать
u u
кое-что из математики, по краинеи мере основы
арифметики, чтобы самостоятельно проверять счета.
'Заметим, что он тоrда уже получил степени бака..
.лавра и маrистра в Кембридже. В то время было
довольно обычным, что хорошо образованный анrлий..
ский джентльмен совершенно не владеет повседнев"
ными расчетами; эти расчеты моrли перепоручаться
младшим счетовод()м.
I ....... .
5 
б . ==1+5
.......
17 . . == 2+3.5
........
.
137 == .. == 6-20 +17 = ( f +5 )-20 + (2+3. 5)
Рис. 16.
4 июля 1662 rода Пепис записывает в своем
дневнике: «Вскоре придет мистер Купер, помощник
капитана на "Ройял Чарльз", у KOToporo я собираюсь
IУЧИТЬСЯ математике, и сеrодня мы начнем; он очень
способный человек, я полаrаю, что не найдется дела,
которое способно полностью ero удовлетворить. Пас.
ле часа занятий арифметикой (я пытался выучить
таблицу умножения) мы расстались с ним до завтра».
Каждый день и рано утром и поздно вечером Пе..
ине учил проклятую таблицу умножения, с трудом
,продвиrаясь вперед при поддержке cBoero моряка-
Iучителя. Например, 9 июля он записывает: «Встал В
четыре часа утра и снова упорно учу таблицу умно.
u
жения, которая для меня является rлавнои труд..
ностыо арифметики». Так продолжалось несколько
дней, пока 11 июля он cMor записать: «Встал В четы..
78

ре часа утра и УПОрНо работал над таблицей умно-
жения, которой я теперь почти 'овладел». Пепис ха.
рото использовал полученные с таким трудом зна.
ния на Bcex все более важных постах, на которые он
наэначался. Однако может показаться слишком быст-
рым ero продвижение, коrда вы узнаете, что он был
избран членом знаменитой Британской академии
наук  Королевскоrо общества  спусrя два с поло-
виной rода после Toro, как выучил таблицу умно..
жения.
Мы привели эту историю, которая никоим образом
не является уникальной, чтобы подчеркнуть: запоми"
нание таблицы умножения в те дни не было обычным
этапом математическоrо знания. Таким образом, мы
видим, что использование в нашей арифметике чисел
с небольшим основанием дает"ряд преимуществ, как
механических, так и интеллектуальных. Например,
коrда основанием является число Ь === 3, то в таблице
умножения
о
О, О
1 О
2 О
1 2
О О
1 2
2 (1,1)з
существует только единственное не!ривиальное YMHO
жение, а именно:
2 · 2 === 4 === (1, 1)з.
Для Ь === 2 мы имеем совершенно тривиальную таб
лицу
о 1
О О О
1 О 1
с и с т е м а 3 а Д а ч 6.3.
1. Доказать, что количество нетривиальных YMHO
}кений цифр (получающееся отбрасыванием умноже...
ний на О и 1) в системе с основанием Ь равно
1
2" (Ь ----- 1) (Ь  2).
2. Чему равна сумма всех элементов в таблице
умножения? Проверьте для Ь == 10.
19

 4. Некоторые задачи,
связанные с системами счисления
Обсудим несколько задач, связанкых с
системами счисления, которые имеют отношение к
выбору оснований систем счисления, удобных для ма...
шинноrо счета. ПреДПОЛО)I\И1\1, что мы имеем дело с
обычным настольным арифмометром, который рабо..
тает при помощи сцепленных числовых колес, ка..
}кдое из которых имеет 10 цифр: 0,1, ..., 9. Если
имеется n колес, то мы можем представить все числа
вплоть до
n

N == 99 ... 9,
(6.4.1)
ка'к' и в (6.3.1).
ПреДПОЛОЖИl\1 теперь, что в качестве основания
мы взяли число Ь, отличное от 10, но продолжае
рассматривать числа до N. Тоrда мы должны иметь
т колес, rде т  целое число, удовлетворяющее
условиям (6.3.2) и (6.3.3). Как и в (6.3.4), число т
является целым числом, равным числу
n
19 Ь
или следующим за ним. Так как каждое колесо не..
сет Ь цифр, то количество цифр, записанных на коле
сак, !приближенно равно
Ь
D === n. 19 Ь · (6.4.2)
Можно теперь спросить: какое нужно выбрать
число Ь, чтобы получить наИ1\1еньшее количество чи-
сел, записанных на колесах? Чтобы найти наимень-
шее значение числа D, в формуле (6.4.2) необходимо
лишь исследовать функцию
f'(b)  1: ь (6.4".3)
для различных оснований Ь == 2, 3, 4, ... с помощью
таблицы лоrарифмов получаем значения
ь I 2 3 4 I 5 6
f (Ь) I 6,64 I 6,29 I 6,64 1,15 I 1,71
80

Пос..ледующие З8ачения дЛЯ '(Ь) еще больше; на..
пример, f (1 О) == 1 О, как у?Ке отмеча.л-GСЬ. М-ы эа-клю
чаем, что для таких арифмометров имеет место аllе"
дующее утвер/кдение.
Наименьшее общее число цифр на арифмометре
достuеается при Ь == 3.
Видно, что для Ь === 2 и Ь === 4 общее число циф-р-
не 'на MHoro больше; в этом смысле маленькие ОсНО....
ваfНИЯ имеют преимущество.
Рассмотрим небольшое изменение этой задачи..
Обычные счеты Toro типа, который иноrда исполъ..
зуется для обучения детей счету, имеют несколько
металлических спиц с девятью *) подвижными косточ..
ками на каждой из них, чтобы ОТl\1ечать цифры чи....
сел. С таким же успехом можно провести параллель
ные прямые на листе бумаrи и отмечать цифры со..
ответствующим количеством спичек, или же подобно
древним начертить эти прямые на песке и отмечать.
цифр.ы камешками.
Но вернемся к счетам. Если имеется 11, спиц и на
каждой по 9 косточек, то можно представить ВНОВ(.-
Все целые числа с п знаками вплоть до числа N, запи..
caHHoro в (6.4.1). Теперь зададим следующий вопрос:
можно ли, взяв друrое основание Ь, сделать счеты
более компактными, Т. е. обойтись меньшим коли..
честном косточек?
При основании Ь количество косточек на каждой
спице будет Ь  1. Как и прежде, для Toro чтобы
счеты имели ту }ке вместимость N, количество зна..
ков или спиц должно определяться соотношеfIием
1.(6.3.4). Это дает значение
n
Е == .............. (Ь ...... 1)
19 Ь
(6;4.4)
в качестве приближения для общеrо количества ко...
сточек. Чтобы найти, коrда это число принимает наи...
меньшее возможное значение, мы должны исследо..
вать функцию
( Ь ) === Ь...... 1
g 19 Ь
(6.4.5)
*) На CQeTaX, принятых в СССР, на каждой спице расп<ма-
rается 10 косточек. (Прu.м.. перев.)
81

для различных значений числа Ь == 2, 3, ... Значение
функции g(b) для небольших значений числа Ь даны
в таблице
Ь 2 3 4 5 6
g (Ь) I 3,32 I 4,19 4,98 I 5,72 6,43
Для больших значений числа Ь ФУНКЦИЯ продолжает
возрастать, поэтому мы заключаем, что
необходимое количество косточек на счетах будет
минимально при Ь === 2.
01КHO интерпретировать этот результат с друrой
точки зрения. Предположим, что мы отметили цифры
нашеrо числа, используя спички или камешки, рас"'!
положенные на прямых линиях. В десятичной систе-
ме будет от О до 9 отметок на каждой прямоЙ. Это
дает в среднем по 4,5 спички на каждой прямой для
науrад взятых чисел; следовательно, числа с п зна-
ками потребуют в среднем 4,5 п спичек, Kor да они
укладываются произвольно.
Посмотрим, какое время потребуется, чтобы уло-
жить эти спички на места. I-Iмея в виду какое-нибудь
расположение, преДПОЛО)l{ИМ, что потребуется одна
секунда, чтобы уложить одну спичку. Тоrда общее
время, требуемое для Toro, чтобы уложить все спич..
ки, будет в среднем составлять приблизительно
4,5 n секунд.
Предположим, что мы изменили наше основание
на число Ь и допустим ту же самую вместимость для
представления чисел. В таком случае на каждой пря-
мой будет от О до Ь  1 спичек, следовательно, в
среднем
1
"2 (Ь  1)
из Bcero количества спичек. Как мы упоминали не..
сколько раз, мы будем иметь приблизительно
п
19 Ь
прямых. Отсюда делаем вывод, что среднее время,
требуемое ДЛЯ представления числа с п знаками, со-
82

стаВJIяет примерно
n 1 ) l В
 · ...... ( Ь ....... 1 == 
tg Ь 2 2
секунд, здесь Е есть выражение из (6.4.4). Так как
это время было минимальным для Ь == 2, мы также
можем сделать вывод:
среднее вреtя, необходиJltlое для установления чис-
ла с /1,ОМОlЦЬЮ спичек на прямых, минимально для
Ь == 2.
с и с т е м а 3 а Д а ч 6.4.
1. Постройте rрафики функций у == '(Ь) из (6.4.3)
и у == g(b) из (6.4.5) для Ь > 1. Если вы уже зна-
комы с дифференциальным исчислением, используйте
ero для определения формы кривых.
 5. Компьютеры
и их системы счисления
До появления электронных вычислитель..
ных машин всюду при вычислениях безраздельно roc-
подствовала десятичная система. Интерес к друrим
системам носил либо исторический, либо познаватель-
ный характер. Существовало лишь несколько отдель-
ных задач, которые наиболее удачно формулирова-
u u
лись с использованием двоичнои или троичнои систем
счисления. Одним из излюбленных примеров в кии-
rax по теории чисел является иrра «Ним» *). к тому
времени, коrда появилось MHoro различных типов
компьютеров, возникла задача сделать устройство
ЭВМ как можно более компактным и эффектив
ным. Это привело к тщательному изучению систем
счисления с целью нахождения более подходящей
системы. По ряду причин, некоторые из которых мы
обсудили в предыдущем параrрафе, двоичная систе-
ма была признана предпочтительной. Единственным
ее недостатком явилось то, что для большинства из
нас требуются немалые усилиядля Toro, чтобы чув-
*) При иrре в «Ним» раскладывается некоторое количество
камешков в несколько кучек. Двое иrрающих по очереди берут
камешки из кучек, при ходе можно брать произвольное количе-
ство камней, но только из одной кучки. Выиrрывает иrРОК 1 взяв..
ший последний камень. (ПрUМ. перев.)
&з

СТБовать себя в НЙ, «как дома», так как' мы БНI'31И
в-еспитаны в друrих традициях. Следовательно,. по..
скольку числа, которые должны вводиться в KOM
nbioTepbI, обычно записаны в десятичной системе, то
требуется начальное устройство, переводящее .их в
ДБОИЧНУЮ систему, а ответы в конце K{)HЦOB ДОЛ)l{НЫ
быть выражены в десятичной системе, как уступка
менее матеlVlатически подrотовленным членам обще-
ства.
Разумеется, двоичная система, используемая в
ЭВМ, является той же самой системой, КОТОРУЮ мы
обсуждали в предыдущем параrрафе, однако исполь-
зуемая терминолоrия носит более технический от'"'
тенок. Двоичные цифры О, 1 называются битами,
что является сокращением анrлийскоrо выражения
BInary digiTs (двоичные цифры). Так как существут
лишь две возможности: О и 1 в каждой позиции, то
часто rоворят об элементе с двумя состояниями.
Если следовать общему правилу, изложенному в
 2 этоЙ rлавы, то представление данноrо числа в
двоичной системе довольно просто. Например, воэь
мем N:::=: 1971. Повторное деление на Ь == 2 дает
1971 === 985 · 2 + 1,
985 === 492 · 2 + 1.
492 === 246 · 2 + О,
246 === 123 · 2 + О,
123 === 61. 2 + 1,
61 == 30. 2 + 1,
30 === 15. 2 + О,
15== 7.2+1,
7== 3.2+1,
3== 1.2+1,
1== 0.2+ 1,
Следовательно,
197110===(1, 1, 1 1, 0,1,1, О, 0,1,1)2_
Ранее мы отмечали, что в двоичной системе ЧИСJlа
имеют более длинные выражения, следовательно, ста..
новится труднее с первоrо взrляда оценить величин
84

Чlfсла. По этой причине.в языке ЭВМ ч,аСТQ ИСп.Qль-
зуется восьмеричная система счисления (с основа..
нием 8). Это является лишь незначительным измене..
нием двоилной системы, которое получается разбие--
ннем бr1Т в числе на rруппы по три. ЭТО M01KHO пред"
ставить се.бе как систему с основанием
Ь==8==2 3 .
I(оэффициентами при этом являются восемь чисел
6 == 000,
1 === 00 1 ,
2==010
,
3===011
,
4 == 100,
.5 === 1 01,
6 === 11 О,
7=== 111.
в качестве иллюстрации возьмем число 1971 из pac
cMoTpeHHoro выше примера; в восьмеричной системе
оно представляется как
1971 === 011, 110, 110,011 === (3,6,6, 3)8.
Таким образом, этот способ записи незначительно
ОТЛIIqается от предыдущеrо. В действительности, та..
кое деление на rруппы нам хорошо знакомо по обыч
ным десятичным числам: при записи и произнесении
большоrо числа мы обычно делим ero цифры на Рруп'4
пы по три, например,
N === 89747 321 924.
Таким образом, мо}кно сказать, что это является
представлением нашеrо числа при основании
Ь == 1000 == 103.
в компьютерах иноrда исhОЛЬЗУIОТСЯ и друrие
представления чпсел. Предположим, что мы хотим
записать десятичное число, cKa}J{eM, N == 2947, в ЭВМ,
работающей в двоичной спстеме. Тоrда, вместо Toro
чтобы полностью менять N на двоичное число, можно
было бы изменить лишь цифры этоrо чиса
2 == 0010,
9 === 1 00 1 ,
4 === 0100,
. ' I
7==0111
85

н, таким образом,
N == 0010, 1001, 0100, 0111.
Такие числа известны как кодированные десятичные
числа. Этот метод иноrда называется «системой 8421»,
так как эти десятичные цифры представляются в
виде сумм двоичных единиц
0==0000,1==0001,2==0010,
22 == 4 == 0100, 23 == 8 == 1000.
Такие кодированные десятичные числа неудобны
для всех видов вычислений, но не всеrда целыо ЭВМ
являются вычисления. Тем же образом, любая буква
алфавита или любой друrой символ MorYT быть при..
писаны какомунибудь ДВОИЧНОl\1У ЧИСЛУ. Это озиа",
чает, что любое слово или предложение можно ззло-
минатькак двоичное число. Таким образом, если бы
мы были соответствующиь,1 образом натренирова11Ы
и имели бы дело со столь же подrотовленнои ауди-
торией, то моrли бы общаться лишь с помощью
бит.
с и с т е l\,f а 3 а д а ч 6.5.
1. Найдите двоичное представление чисел Ферма
( 3, rл. 2)
t
F t === 22 + 1.
2. Найдите двоичные представления четных со-
вершенных чисел (4, rл. 3)
р === 2P 1 (2 Р ........ 1).
 6. Иrры с числами
Существует множество видов иrр с чис-
лами, некоторые из которых были известны еще в
средние века. Большинство из них не представляет
интереса для теории чисел, скорее Bcero, они подобно
маrическим квадратам принадлежат к классу кросс-
вордов с числами. Некоторые из них проиллюстри",
руем примерами.
86

Перед вами телеrраММ8, поланная школьником
домой, с настоятельной просьбой:
S Е N D
М О R Е
М О N Е У *)
Будем рассматривать эту схему, как сложение
двух четырехзначных чисел SEND и MORE, в сумме
дающих число MONEY. Каждая буква означает опре..
деленную цифру. Задача состоит в том, чтобы опре-
делить, какие это цифры. Так как Bcero 10 цифр, ТО
в' каждой такой задаче может фиrурировать не ба..
лее 1 О букв, в этом примере 8. В идеальном случае
задача дол}кна иметь единственное решение.
В нашем примере очевидно, что
М===l,
так как М  первая цифра либо суммы S + м, либо.
S + м + 1, rде S и М  числа, не превосходящие
числа 9. Тоrда для числа S имеются две возможности:
S == 9 или S === 8,
так KaI{ либо S + 1, либо S + 1 + 1 есть двузначное
число. Установим сначала, что S не может быть циф..
рой 8, ибо, если бы S было 8, то должен был бы быть
перенос из колонки сотен, что дает
S + м + 1 ==8 + 1 + 1 == 10
при сложении в колонке сотен. Следовательно, О
должно было бы быть нулем и наше послание чита-
пось бы так:
8 Е N D
1 О R Е
1 О N Е У
Но, исследуя колонку сотен, находим, что обязатель-
110 должен быть перенос из колонки десятков (иначе
'Е + О == Е, а не N), и так как Е ::::;;; 9, то
E+O+l==lO.
Это вынудило бы нас положить N == О, но мы уже
знаем, что О === О, поэтому такой случай невозможен,
..
$) Вышлите побольше денеr.
81

и мы ззключ-аем, что .8 === 9, и послание теп€рь чи
тается так:
9 Е N D
1 О R Е
1 О lV Е У
Так как Е =1= N, то сложение в колонке сотен приво
,lI.ИТ к условию
Е + 1 ;::== N
и
9
1
Е
О
Е+ 1 D
R Е
1 О Е+l
Е
у
Слокение в КОЛОНI{е десятков дает либо
Е + 1 + R === 10 + Е, либо Е + 1 + R + 1 == 10 + Е.
Первый случай невозможен, так как он дает R == 9,
что противоречит тому, что S == 9. Во втором случае
R === 8,
и послание читаеtся так:
9 Е Е+l D
1 О 8 Е
1 О Е+l Е У
и наконец, сумма в колонке единиц такова:
D + Е== 10 + У.
ДЛЯ трех букв D, Е, У осrаются только значения 2,
3, 4, 5, 6, 7. Наибольшая сумма двух различных чисел
из них равна 13. Отсюда существует Bcero две воз..
можности дЛЯ У: либо У === 2, либо У == 3. Последний
случай неВОЗМО)l{ен, так как при этом D + Е == 13,
но мы .не можем иметь Е == 7, так как тоrда N ==
=== Е + 1 == 8 == R; TaK}Ke не может быть D == 7, 'так
как тоrда Е == 6 и
N === Е + 1 === 7 === D.
Та'ким образом, У == 2 и D + Е == 12. Из имеющихся
цифр 2, 3, 4, 5, 6, 7 единственной парой, в сумме
88

дающей 12, ЯВЛЯЮТСЯ 5 и 7. TK как. Е =1= 7, то это
означает, что D == 7, Е == 5 и, таким -обр.аэом, еДин.
..,
ственное решение нашеи задачи следующее:
9 5 6 7
1 085
10 6 5 2
Этот процесс довольно сложен, во l\/lноrих случаях
можно получить решение rораздо более простым
путем.
с и с т е м а з а Д а ч 6.6.
1. Попытайтесь проанализировать следующие при-
меры только что показанным методом:
1.
s
м
G
Е N D
О R Е
О L D
2. Н
Р
Р R
о с и s
о с и s
Е S Т о
м
о lv Е
3. F
у
о R
т
т
т у
Е N
Е N
S I
4. А D А М
А N D
Е V Е
А
R А F Т
х т
5.
у
s Е Е
S Е Е
S Е Е
у Е S
Е А S У
Переводы этих ребусов таковы:
1. «Шлите больше золотых монет», 2. «Фокус........
Покус  Престо», 3. «Сорок + десять + десять ==
== шестьдесят», 4. «Адам и Ева на плоту», 5. «CMOT
ри, смотри, смотри. Да! Леrко».
Если хотите, попробуйте Придумать свои ребусы.
Есл» вы знакомы с ЭВМ, то попытайтесь заПрОliр.ам
мировать решение таких задач.

r "ТIABA 7
СРАВНЕНИЯ
 1. Определение сравнения
Теория чисел имеет свою алrебру, из..
вестную, как теория сравнений. Обычная алrебра
первоначально развивалась как стеноrрафия для опе..
раций арифметики. Аналоrично, сравнения представ..
лают собой символический язык для делимости,
OQHoBHoro понятия теории чисел. Понятие сравнения
впервые ввел [аусс.
Прежде чем мы обратимся к понятию сравнения,
сделаем одно замечание о числах, которые будем
изучать в этой rлаве. Мы начали эту книrу, заявив,
ЧТО будем рассматривать целые положительные чис..
ла 1, 2, 3, ..., и в предыдущих rлавах мы оrраничи"
вались только этими числами и дополнительным чис..
ЛQМ о. Но теперь мы достиrли стадии, на которой
целесообразно расширить наши rраницы, рассматри
вая все целые числа:
О, + 1, + 2, + 3, . . .
Это никоим образом не повлияет на наши предыду..
щие понятия; далее, коrда мы будем rоворить о про..
стых числах, делителях, наибольших общих делите..
лях и тому подобном, мы будем считать их целыми
положительными числами.
Теперь вернемся к языку сравнений. Если а и
Ь  два целых числа и их разность а  Ь делится на
число т, мы выражаем это записью
а == Ь (mod т), (7.1.1)
которая читается так:
а сравнимо с Ь по модулю т.
Делитель m мы предполаrаем положительным; он на-
зывается модулем сравнения. Наше высказывание
90

(7.1.1) означает, что
а  Ь == wk,
При м еры.
1) 23 == 8 (mod 5),
2) 47 == 11 (mod9),
3) 11 == 5 (mod 8),
4) 81 === О (mod 27),
rде k  целое число.
(7.1.2)
так как 23  8 === 15 === 5 · 3;
так как 47  11 == 36 == 9. 4;
так как  11  5 ==  16 ===
===8. (2);
так как 81  О == 81 == 27 · 3.
Последний пример показывает, что вообще, вме-
сто Toro, чтобы rоворить: число а делится на число т,
мы можем записать
а == О (mod т),
так как это означает, что
а  О::=: а === mk,
rде k  некоторое целое число. Например, вместо
Toro, чтобы сказать, что а  четное число, мы можем
записать
а == о (mod 2).
Таким же образом видно, что нечетное число является
числом, удовлетворяющим сравнению
а == 1 (mod 2).
Эта несколько странная терминолоrия является до-
вольно обычной для математических работ.
 2. Некоторые свойства сравнений
Способ, которым мы записываем срав-
нения, напоминает нам уравнения, и в действительно..
сти, сравнения и алrебраические уравнения имеют
MHoro .общих свойств. Простейшими из них являются
три следующих свойства:
а == а (mod т); (7.2.1)
это является следствием Toro, что
а  а == т · О,
а == Ь (mod т) означает, что и Ь == а (mod т). (7.2.2)
Это следует из Toro, что Ь  а ===  (а ......... Ь} == т (  k) .
91

Из
a===b(modпz) и b == c(modт) (7.2.3)
следует, что а == c(nl0d т), потому что первые два
утверждения 0значtlIОТ, что
а  ь == nlk,
ь  с === ml,
поэтому
а  с == (а  Ь) + (Ь  с) === т (k + [).
При м е р. Из Toro, что
13==:35(modll) и 35==9(modll)
следует, что
13==9(mod 11).
Мы rоворили, что сравнения похожи по своему
свойству на равенства. В действительности, мы м о...
жем рассматривать равенства как тип сравнения,
а именно, сравнения по модулю о. По определению,
а == Ь (mod О)
означает, что
ab===O.k===O
или
а === Ь.
Вы почти никоrда не встретите такую форму
u 
сравнения для записи уравнении в математичеСКоff
литературе. Но существует друrое сравнение, оче..
видно, довольно тривиальное, которое иноrда исполь...
зуется. Коrда модуль есть число т == 1, мы имеем,
что
a:=b(mod 1)
(7.2.4)
J(ЛЯ любой пары целых чисел а и Ь, так как это оз'На'"
чает, что
а ........ ь === 1 · k === k
(7.2.5)
есть целое число. Но предположим теперь на MrHO"
вение, что а и Ь....... произвольные веIцественные числа.
необязательно целые. Тоrда тот Ф"акт, что они сравни
мы по модулю 1, означает, что их разность есть целое
число, т. е. эти :два числа имеют одинаковую дробную
часть.
92

1 1
При мер. 8з-==l з (mоdl), или
8,333 ... == 1,333 ... (Пl0d 1).
Вернемся к свойствам оычных сравнений целых
чисел; с этоrо момента мы будем всеrда считать, ЧТО
модуль является целым числом т  2.
Мы можем разделить числовую ось, начиная ОТ
начала координат в обоих направлениях на отрезки
дли,ной т, как на рис. 17. Тоrда каждое целое чис-
ло а, положительное или отрицательнее, попадает на
m 2т km а
..., I t I I i
D 1 2 
r
Рис. 17.
один из этих отрезков или на одну из точек деления;
таким образом, мь] можем записать
a==km+r, (7.2.6)
rде k  некоторое целое число, а r  одно из чисел
О, 1, 2, ..., m  1. (7.2.7)
Это является незначительным обобщением деления
положительных чисел, описанноrо в  3 rлавы 4. Здесь
мы таК2ке называем число r в формуле (7.2.6) остат..
ком при делении числа а на число т или octaTKoM по
модулю т.
При м еры.
1) а===11, т ===7, 11===7.1+4,
2) a==II, т===7, ]]===7(2)+3.
Деление (7.2.6) может быть также записано как
сравненпе
а == r (mod т).
(7.2.8)
Таким образом, каждое число сравнимо со своим
остатком по модулю т. В приведенных выше приме..
рах мы имеем
11 == 4 (mod 7),  11 == 3 (mod 7).
Никакие два остатка в (7.2.7) не сравнимы по
(m,od т), так как разность между любыми двумя, иа
них меньше, чем т. Поэтому два числа, которые не
93

сравнимы по (mod т), должны иметь разные остатки.
Итак, мы делаем вывод:
сравнение а == Ь (mod т) выполняется ТОсда u
то Itько ТОёда, КОсда числа а и Ь имеют оди/{,аk,овЬtе,
остатки при делении на число ,n.
Существует друrой способ представления эrоrо
сравнения. Предположим на мrновение, что а и Ь..........
целые положительные числа. Мы видели при обсх'i
ждении системы чисел в  2 rлавы 6, что коrда чис.. 1
ло а записано при основании т,
а == (а п , .. ., аl, аО)т,
"
то последняя цифра ао является остатком числа а
при делении ero на число т. Если мы используем
этот факт, чтобы иначе выразить нашу интерпрета..
цию сравнения, то можно сказать:
сравнение а == Ь (mod т) выполняется для целых
(положительных) чисел а u Ь ТОёда u только ТОсда,
коеда часла а и Ь и.iиеют одинаковые последние циф..
ры в записи при основании т.
Например,
37 == 87 (mod 1 О),
так как эти два числа имеют одну и ту же последнюю
цифру в десятичной системе чисел.
с и с т е м а 3 а Д а ч 7.2.
1. Найдите остатки 37(mod 7), ........111 (mod 11),
365 (rnod 30).
 3. Алrебра сравнений
Из алrебры мы помним, что уравнения
можно складывать, вычитать, умножать. Точно та..
кие же правила справедливы для сравнений. Пред...
поло}кпм, что мы имеем сравнения
а == Ь (mod т), с == d (mod т). (7.3.1)
По определению, это означает, что
а == Ь + п],k, с === d + тl, (7.3.2)
rде k и 1  целые числа. Сложим уравнения (7.3.2}1I
В результате получаем
а + с == Ь + d + т (/l + [),
94

что можем записать как
а + с == Ь + d (mod т);
(7.з.з)
друrими словами, два сравнения можно складывать.
Таким же образом мол{но показать, что ОДНО cpaB
нение можно вычитать из друrоrо, т. е. что
а  с == Ь  d (mod т).
(7.3.4)
П' р и м е р.
1 } ==  5 (mod 8)
и
7 == ....... 9 (mod 8).
(7.3.5)
Складывая их, получаем
18 ==  14 (mog8),
а вычитая,
4 == 4 (mod 8).
Оба эти сравнения справедливы.
Можно также перемножить два сравнения. Из
(7.3.1) и (7.3.2) следует, что
ас === bd + т (kd + bl + mkl),
таким образом,
ас == bd (mod т).
(7 .3.6) 
При м ер. Коrда два сравнения из (7.3.5) перемно'"
жены, получается
77 == 45 (mod 8).
Сравнение а == Ь (mod т) может быть умножено
на любое целое число с, при этом получаем
ас == Ьс (mod т).
(7.3.7)
Это можно рассматривать как частный случай YMHO
Жен'ия сравнений (7.3.6) при с === d. Ero можно также
рассматривать как прямое следствие-из определея
сравнения.
При м ер. Коrда первое сравнение из (7.3;5)
умножается на 3, получаем, что
33 == ........ 15 (mod 8).
Возникает естественный вопрос: в каком случае
можно в сравнении (7.3.7) сократить общий множи-
тель с и получить при этом верное сравнение
a  Ь (mod т)?
95

Именно здесь сравнения отличаются оТ уравнений.
Например, верно, что
22 ==  2 (mod 8),
НО сокращение на мно}китель 2 дало бы сравнение
11 ==  1 (mod 8),
которое неверно.
В одном важном случае сокращение допустим.!
если ас == bc(mod т), то а == b(mod т) при yCJl:(J<4
вии, что числа т и с взаимно просты.
Д о к а 3 а т е л ь с т в о. Первое сравнение 0знаЧ1ет.
что
ас  Ьс == (а  Ь) с === mk.
Если D(m, с)=== 1, то отсюда следует, что а.... Ь
делится на т в соответствии с результатом, дока[1ан"
ным в  2 rлавы 4.
При м е р. В сравнении
4 == 48 (mod 11)
мы можем сократить на множитель 4, так как
D(II, 4) == 1. Это дает
1 == 12 (mod 11).
с и с т е м а 3 а Д а ч 7.3.
1. Придумайте еще несколько примеров на исполь..
u со'
З0вание изложенных правил деиствии со сравнениями.
* 4. Возведение сравнений в степень
Предположим вновь, что имеется срав"
нение
а == ь (mod т).
Как мы только что видели, можно умножить это
сравнение на себя, получив
а 2 == Ь 2 (mod т).
Вообще можно, умножив это сравнение на себя нуж
ное количество раз, получить
а n == Ь N (mod т)
для любоrо целоrо положительноrо числа n!
96

При м е р. Из сравнения
8 == ........ 3 (mod 11)
после возведения в квадрат следует сравнение
64 == 9 (mod 11),
а после возведения в куб получаем сравнение
512 == ........ 27 (mod 11).
Мноrие результаты теории сравнений связаны с
остатками высоких степеней чисел, поэтому покажем,
как можно продолжить процесс возведения в степень.
Предположим, например, что мы хотим найти оста..
ток сравнения
389 (mod 7).
Одним из путей для выполнения этоrо является по
вторное возведение в квадрат. Мы находим;
9 === 32 == 2 (mod 7),
34 == 4,
38 == 16 == 2,
3 Н ) == 4,
332 == 16 == 2,
364 == 4 (mod 7).
Так как
89 == 64 + 16 + 8 + 1 === 26 + 24 + 23 + 1,
то отсюда следует, что
389 == 364 · 316 · 38 · 3 == 4 · 4 · 2 · 3 == 5 (mod 7).
Таким образом, остаток (по модулю 7) есть 5, или,
rоворя друrими словами, в соответствии с изложен"
HhIM в  2, последняя цифра числа 389, записанноrо в
системе счисления при основании 7, равна 5.
В действительности, для Tor9 чтобы найти этот
остаток, мы записали показатель степени
89 == 26 + 24 + 23 + 1 == (1, О, 1, 1, О, О, 1)2
В двоичной системе счисления. Повторным возведе"
нием в квадрат мы нашли остатки (по модулю 7)
4 О!, Оре 97

тех степеней числа 89, которые сами являются CTe!l
пенями числа 2:
1, 2, 4, 8, 16, 32, 64.
Соответствующий метод можно использовать дЛЯ ЛЮ'JI
бых друrих оснований. Однако в частном случае бы..
Бает ВQЗМОЖНОСТЬ упростить вычисление, если заме"
тить особенности этоrо случая. Например, в случае,
разобранном выше, мы можем отметить, что
33 ==  1 (mod 7),
36 == 1 (mod 7),
откуда заключаем, что
384 == (36)14 == 1 (mod 7).
Поэтому
В89 == 384.33.32 == 1 (1). 2 == 2 == 5 (mod 7),
как и раньше.
В качестве друrой иллюстрации сказанноrо мож",
но рассмотреть числа Ферма, с КО'fорыми мы позна 8J
комились в  3 rл. 2:
F t === 2 2t + 1.
Первые пять чисел Ферма таковы:
Ро===3, Р 1 ===5, Р2===17, F з ==257, Р 4 ==65537.
Отсюда можно высказать предположение:
десятиЧн'ая запись всех чисел Ферма, за uсключе..
нием РО и Р 1 , окан'чивается цифрой 7.
Докажем с помощью сравнений, что это действи-
тельно так. Очевидно, что оно равносильно утвержде-
нию, что числа
2 2t , t == 2, 3, ...
оканчиваются цифрой 6. Это можно доказать по ин-
дукции.3аметим,что
2
22 === 16 == 6(mod 10),
з
22 === 256 == 6 (mod 10),
4
22 == 65536 == 6 (mod 10).
98

Более Toro, если мы возводим в квадрат число 2 2k ,
то результатом будет число
( 2k ) 2 2.2 k 2k+l
2 ===2 ===2 .
Предположим, что для HeKoToporo значения t
2 t
2 == 6 (mod 10);
возводя в квадрат это сравнение, мы находим, что
2 t + 1
2 == 36 == 6 (mod 10),
что и требовалось.
* 5. Теорема Ферма
Из алrебры мы знаем правила возведе..
ния бинома в степень:
(х + у)l == Х + у,
(х + у)2 === х 2 + 2ху + у2,
(х + у)3 === х3 + 3х 2 у + 3 ху 2 + уЗ,
(х + у)4 === х 4 + 4х 3 у + 6х 2 у2 + 4 ху 3 + у4
и вообще
(х + у)Р == х Р + CxP...ly + CxP"'2y2 + . . . + у". (7.5.2)
Здесь первый и последний коэффициенты равны еди...
нице. Средними биномиальными коэффициентами ЯВ-
ляются
C 1 Р С 2 .......... Р (р  1) С 3 .......... Р (р  1) (р ...... 2)
р==т' p 1.2 ' p 1.2.3 ' ...
(7.5.3)
(7.5.1)
и вообще
c r ....... р (р ...... 1) (р ...... 2) ... (р  r + 1)
р....... 1.2...r '
(7.5.4)
rде
r === 1, 2, .. ., р....... 1.
Так как эти коэффициенты получаются в результате
ооследовательноrо умножения на бином (х + у), то
ясно, что они являются целыми числами. .
С этоrо момента будем считать, что р ---- простое
число. Чтобы записать эти коэффициенты в целочис
4*
99

ленном виде, необходимо сократить все общие мно...
жители знаменателя
1.2.3. ....,
и числителя
р (р  1) ... (р  r + 1).
Однако знаменатель не содержит простоrо множите-
ЛЯ р, поэтому после сокращения число р останется
множителем в числителе. Мы делаем вывод.
Все биномиальные коэффициенты (KpOte nереосо
u последнеzо) в выражении (7.5.2) делятся на р,
если р  простое число.
Пусть теперь х и у в выражении (7.5.2) будут
целыми числами. Если мы рассмотрим формулу
(7.5.2) как сравнение по модулю р, TQ можно сделать
вывод, что для любых целых чисел х и у и простоrо р
(х -+- у)Р == х Р + уР (mod р). (7.5.5)
В качестве примера возьмем р == 5:
(х + у)5 == х 5 :+- 5х 4 у + 10х 3 у2 + 10х 2 у3 + 5 ху 4 + у5.
Так как все средние коэффициенты делятся на 5, то
(х + у)5 == х 5 + у5 (mod 5)
в соответствии с (7.5.5).
Из сравнения (7.5.5) можно сделать важные BЫ
воды. Применим ero для случая х === у == 1. Получаем
2 Р ==(1 + I)Р == l Р + l P ===2(modp).
Возьмем затем х == 2, у === 1 и найдем, что
З Р ==(2+ I)Р == 2 Р + l Р ;
теперь, используя предыдущий результат, 2 Р ==
== 2(mod р), получаем
2 Р + l Р == 2 + 1 == 3 (mod р).
Итак, 3 Р == 3 (mod р). Далее для х === 3, у === 1 по-
Jlучаем
4 Р == 4 (mod р).
Используя этот процесс, можно доказать по индук-
ции, что аР == а (mod р) для всех значений числа
а == О, 1 J ... J Р  1. (7.5.6)
100

Случаи а == О и а == 1 очевиднь{. Так как каждое
число сравнимо (mod р) с одним из остатков, запи..
санных в (7.5.6), мы делаем вывод:
для люБО20 цеЛО20 числа а и любоzо пpOCTOO
числа р
аР == а (mod р). (7.5.7)
Это утверждение обычно называют теоремой Ферма,
хотя некоторые авторы называют ее малой теоремой
Ферма, чтобы отличить от последней теоремы Ферма,
или rипотезы Ферма, о которой мы упоминали в  3
rлавы ,5.
При м е р. Для р == 13 и а == 2 мы находим: 13 ==
== 8+ 4 + 1, т. е. 213 == 28+4+1 == 28.24.21. Так как
24 == 16 == 3 (mod 13), 28 == 9 (mod 13),
то
213 == 28 . 24 · 2 == 9 · 3 · 2 == 2 (mod 13),
как и утверждает теорема Ферма.
В соответствии с правилом сокращения для срав"
f1:ений, сформулированном в конце  3, мы можем
сократить общий множитель а в обеих частях записи
теоремы Ферма (7.5.7) при условии, что число а
взаимно просто с числом р, являющимся модулем
сравнения. Это дает следующий результат:
если а является целым числом,. не делящимся на
простое число р, то
a P -- 1 == 1 (mod р). (7.5.8)
Этот результат также называют теоремой Ферма.
При м ер. Коrда а == 7, р == 19, мы находим, что
72 === 49 == 11 (mod 19)
74== 121 ==s7(mod 19),
78 == 49 == 11 (rnod 19),
716 == 121 == 7 (mod 19),
и это дает
а Р "' 1 == 718 === 716 . 72 == 7 · 11 == 1 (mod 19),
что соответствует утверждению (7.5.8).
В качестве приложения теоремы Ферма вновь рас-
смотрим треуrольники Пифаrора, обсужденные в rл. 5
и докажем следующее утверждение;
101

проuзведенuе длин сторон треУ20льника Пифа20ра
делится на 60.
Д о к а з а т е л ь с т в о. Очевидно, достаточно до..
казать это для простейших треуrольников. В соот-
ветствии с формулой (5.2.7), это произведение есть
р === 2тп (т 2 ........ п 2 ) (т 2 + п 2 ) === 2тп (т 4 ........ п 4 ).
Число р делится на 60 тоrда и только тоrда, коrда
оно делится на 4, на 3 и на 5. Так как одно из чи...
сел т и п четно, то 2тn, а следовательно, и число Р"
делится на 4. Оно делится на 3, если хотя бы одно
из чисел m или n делится на 3, но если ни одно из них
не делится на 3, то Р все же будет делиться на 3, так
как из условий (7.5.8), а также D (т, 3) === 1 и
D (п, 3) === 1 следует, что т 2 == 1 (mod 3) и п 2 ==
== 1 (mod 3), так что
т 2 ........ п 2 .1 ........ 1 == О (mod 3).
Аналоrично, число Р делится на 5. Это очевидно,
если т или n делится на 5. Если ни одно из них не
делится на 5, то вновь по теореме Ферма (7.5.8} по..
JIучаем
т 4  п 4 == 1 ...... 1 == О (mod 5).

r ЛАВА 8
.
НЕКОТОРЫЕ ПРИМЕНЕНИЯ
СРАВНЕНИЙ
 1. Проверка вычислений
Как мы уже упоминали, создателем тео.
рии сравнений был немецкий математик Карл Фрид'!!!
рих [аусс. Ero знаменитая работа по теории чисел
«Арифметические исследования» появилась в 1801 ro-
ду, коrда ему было 24 rода. В первых rлавах этой
книrи рассказывается о теории сравнений. Однако
здесь следует упомянуть, что следы теории сравнений
можно обнаружить за несколько столетий до [аусса.
Некоторые из них присутствуют В древних правилах
проверки арифметических вычислений. Они состав-
ляют существенную часть инструкции по арифметиче-
ским операциям эпохи Ренессанса. Некоторые из них
используются до сих пор, а из Bcero Toro, что нам
известно об их происхождении, можно сказать, что
их корни лежат в античности.
Мы не знаем, каким образом эти правила были
впервые введены, однако попытаемся указать один
из возможных путей, на котором они моrли быть от..
крыты. Вернемся к временам счетных досок. На та-
ком абаке каждая цифра в числах, которые участво"
вали в вычислениях, обычно выкладывалась с по..
мощью фишек, камней, палочек или орехов, причем
каждая rруппа отмечала количество единиц, десят;.
ков, сотен и т. д. В соответствии с местом их нахо...
ждения. В нашей десятичной системе число
N == anlO n + an110n1 + ... + a2 102 + a1lO + ао ==
== (а п , an1, ..., а2, аl, аО)10 (8.1.1)
потребовало бы для своей записи
SN==an+anl+ ... +а2+ а l+ а о (8.1.2)
фишек. Это число мы называем суммой цифр числа N"
103

Теперь предположим, что мы хотим выполнить на
доске простое действие, а именно: сложить два чис-
ла N и М. Тоrда мы должны отметить на доске также
второе число
М === (Ь m , bm], ..., Ь 2 , Ь 1 , bO)IO,
у K6Toporo на тех же линиях лежит
SM===bm+bml+ ... +b 2 +b l +b o
складываемых фишек. На некоторых линиях может
теперь лежать больше, чем по 9 фишек. Операция,
необходимая для нахождения числа N + М, состоит
в замене десяти фишек на одной линии одной фиш-
кой на следующей линии. И так нужно продолжать
до тех пор, пока такой процесс возможен. На каждом
шаrе заменяют десять фишек однойединственной и
таким образом происходит потеря девяти фишек на
доске. Итак, мы видим, что если сложение выполнено
правильно, то число фишек, остающихся на доске,
должно удовлетворять условию
SN+M == SN + SЛ1 (mod 9),
(8.1.3)
т. е. количество фишек, находящихся на доске; долж-
но отличаться от первоначальноrо' общеrо числа фи
тек на число, кратное 9. Эта проверка (8.1.3) до сих
пор сохранила СБое старое название «выбрасывание
девяток».
После Toro как это правило было открыто, не
составило труда заметить, что оно также применимо
при сложении нескольких чисел, при вычитании и при
умножении; в последнем случае, в соответствии с
(8.1.3) ,
SM · SN == SMN (mod 9).
(8.1.4)
Теоретическое доказательство этих правил являет-
ся леrкой задачей при использовании сравнений. Оче-
видн{), что
1 == 1, 1 О == 1, 1 02 == 1, 1 03 == 1, ... (m о d 9); (8. 1 .5)
таким образом, из (8.1.1) и (8.1.2) мы делаем вывод,
что
N == SN (mod 9).
(8.1.6)
104

Поэтом-у на правил сравнений, KqTopbIe мы устано-
вили в  3 rлавы 7, ясно, что
SN + SM == N + м == SN:I: М,
SN · SM ==- N · А1 == SN.M (mod 9).
Правило «выбрасывания девяток» чаще Bcero при-
меняется к умножению. Возьмем в качестве примера
числа
м === 3119, N === 3724
и их проиаведение
М · N == 11 614 156.
(8.1.7)
Это вычисление не может быть верным, так как если
бы оно было верным, то мы имели бы, что
М == S м == 3 + 1 + 1 + 9 == 5 (mod 9),
N == S N == 3 + 7 + 2 + 4 == 7 (mod 9)
н
MN == SMN ==- 1 + 1 + 6 + 1 + 4 + 1 + 5 + 6 ==- 7 (mod 9).
Но
5 · 7 === 35 ==- 8 =1= 7 (mod 9).
В действительности же это произведение равно
MN === 11 615 156.
В средневековых школах ученики имели строrий
наказ обязательно проводить проверку своих упрж-
нений. Поэтому в рукописях, сохра-
нившихся с тех времен, мы видим
множество знаков, похожих на эм-
блему из скрещенных костей. Такой
знак для нашеrо примера выrлядит
так, как на рис. 18.
Здесь числа 5 и 7, лежащие сле-
ва и справа, означают остатки чи-
сел М и N (по модулю 9), а верх-
нее число 8 является остатком вы- Рис. 18.
численноrо произведения М .N. Оно
должно проверяться с помощью произведения остат-
Ков начальных чисел, записываемоrо в нижней части.
Здесь
5 · 7 == 35 == 8 (mod 9).
105

Рис. 19.

 Такая проверка «скрещенных к'остей» была совер"!!
теино обычной в ранних изданиях учебников ариф
метики (рис. 19), например, в анrлийских учебниках
семнадцатоrо и восемнадцатоrо веков. Конечно, су-
ществует возможность, что вычисления содержат
ошибку, необнаруживаемую методом «выбрасывания
девяток», но тоrда мы знаем, что ошибка является
«ошибкой по модулю 9».
Ясно, что и при друrом основании системы счис-
ления можно использовать простейшую проверку.
Для числа
М === тпЬ n + mnlbnl + ... + т2ь2 + тlЬ + то,
записанноrо при основании Ь, как и в (8.1.5), мы имеем
1 == 1, Ь== 1, Ь 2 ==. 1, ... (mod(b  1»);
поэтому, как и раньше,
М == SM === т п + тпl + · · · +т2 + тl+ т о (mod (b 1),
и проверочное правило остается прежним.
Это, повидимому, совершенно тривиальное заме
чание применимо даже в нашей обычной десятичной
системе. Мы упоминали в  5 rлавы 7, что если мы
разобьем цифры десятичноrо Ч1fсла
на rруппы по три, то тоrда эта rруп
пировка может рассматриваться как
представление числа при основании
Ь == 103 == 1000.
Аналоrично, если rруппировать циф-
ры в пары, то это соответствует
представлению числа при основании
Ь == 102 == 100.
Взяв числа 3119 и 3724 вновь в качестве
записав
м == 3119, N === 3724,
MN === 11 61 51 56,
мы находим
Рис. 20.
примера и
м == 31 + 19 == 50 (mod 99), N == 37 + 24 == 61 (mod 99),
MN == 11 + 61 + 51 + 56 == 179 == 80 (mod 99).
107

.Здесь наша проверка «скрещенных костей» бу.дет та...
кой, как на рис. 20, потому что, как леrко видеть,
50 · 61 == 80 (mod 99).
Эта проверка более эффективна, чем «выIидыыаниеe
девяток», потому что модули в этом случае rораздо
больше и вероятность, что ответ будет правильным,
соответственно rораздо больше. Друrими словами,
«ошибка по модулю 99» менее вероятна, чем «ошибка
.по модулю 9». ,,1
 2. Дни недели
Мноrие задачи астрономии и хронолоrии,
связанные с периодичностью, MorYT быть сформули"
рованы в терминах теоретикочисловых ПОНЯТИЙ4
Возьмем простой пример: определение дня недели,
который падает на заданный день. Дни недели по..
вторяются с периодом 7, поэтому вместо обычных
названий мы можем aTЬ каждому дню номер:
воскресенье == О,
понедельник == 1 
вторник  2,
среда == 3,
четверr == 4,
пятница === 5,
суббота == 6.
Если мы это сделаем, то каждому целому числу co
ответствует день недели, а именно: день, определяе 04
МЫЙ ero остатком по модулю 7. .
Если бы мы имели блаrоприятнейшую ситуацию,
при которрй количество дней в rоду делилось на 7,
то все даты падали бы на одни и те же дни ежеrодно,
и составление расписаний было бы rораздо проще, а
издатели календарей имели БыI меньше работы. Од..
о
нако количество днен в rоду равно
365 == 1 (mod 7),
за исключением високосных лет, в которых количе..
u
СТВО днен
366 == 2 (mod 7).
.108

Это показывает, что для обычноrо rода номер W
ДНЯ Н.едели заданной даты в следующем rоду увели-
чится на 1, например, если в этом rоду 1 января 
воскресенье, то в следующем rоду он будет падать
на понедельник. Это не слишком сложно, однако, эта
простая схема нарушается високосными rодами. Это
происходит каждый че!вертый rод, тоrда номер ДНЯ
недели увеличивается на 2. Более Toro, возникает дo
полнительная трудность изза Toro, что добавочный
день високосноrо rода прибавляется не в начале ии
конце rода, а 29 февраля. Поэтому, для удобства, в
общей формуле для вычисления W, которую мы дa
дим ниже, доrоворимся считать март  первым меся
цем, апрель  вторым и т. Д., при этом январь будет
одиннадцатым месяцем, а февраль  двенадцатым Me
сяцем предшествующеrо rода.
Но на этом наши трудности не кончаются. В юли..
анском календаре, введенном по указу Юлия Цe
1
заря, было принято, что rод точноравен 365 4" дня,
в соответствии справилом високосноrо rода. Однако
это не совсем правильно, так как астрономический rод
в действительности равен 365,2422 дня.
Эта маленькая ошибка вызвала постепенный сдвиr
сезонов по отношению к календарю, например, в
шестнадцатом B,eKe день BeceHHero равноденствия
(первыIй день весны) пал на 11 марта вместо 21 мар...
та, как это должно было быть.
Чтобы исправть положение, в 1582 rоду папа
[риrорий XIII после долrих колебаний произвел ре...
форму календаря в странах с католическим вероие...
поведанием. В том rоду было опущено 1 О дней,  а
именно, пятницу 5 октября стали считать пятницей
15 октября. Более Toro, для корректирования кален...
даря были введены следующие rриrорианские прави
-ла для високосных лет.
[оды столетий
1700, 1800, 1900, 2100, 2200, 2300,
. . .,
в которых количество столетий не делится на 4, не
считаются високосными rодами. Оставшиеся rоды
столетий
1600, 2000, 2400, ...
109

продолжают считаться високосными rодами. Полу..
чается очень хорошее приближение к правильной дли-
не rода, однако капельку длиннее. Было предложено
,не считать rоды 4000, 8000, ... високосными вопреки
rриrорианскому правилу; но так как этот вопрос еще
открыт и не имеет отношения к ближайшему буду...
щему, то мы не будем это принимать в нашей фор..
муле.
Предположим теперь, что нам задана дата: dй
день в тM месяце (rде т определяется так, как было
казано выше), в rоду, равном
N === с · 100 + У,
(8.2.1 )
rде C, количество столетий, а У  номер rода в
столетии. Тоrда можно доказать, что наш номер ДНЯ
недели определяется при помощи сравнения
w == d + [  (13т  1)] +
+ у + [ У] + [ с]  2с (mod 7). (8.2.2)
Квадратные скобки, фиrурирующие в этой формуле,
были введены в  3 rлавы 4 для обозначения наи
большеrо целоrо числа, не превосходящеrо числа,
стоящеrо внутри этих скобок.
При м е р. День ПирлХарбора *), 7 декабря
1941 r. Здесь
d===7, m===IO, с==19, У===41,
так что
w === 7 + 25 + 41 + 10 + 4  38 == О (mod 7),
'1'. е. это было в воскресенье.
При м е р. Каким днем недели будет 1 января
2000 rода? Здесь
d == 1, m === 11, с === 19, У === 99
и
w == 1 + 28 + 1 + 3 + 4 ....... 38 == 6 (mod 7);
*) День нападения японскоrо флота на американскую воен.
ную базу Пирл-ХарБОРr начало войны США и lIпонии. (Прим.
перев.)
110

таким образом, первый день следующеrо столетия *)
будет субботой.
При пользовании этой формулой следует помнить,
что ее нельзя применять для Toro периода, коrда еще
не был введен rриrорианский календарь. В Анrлии и
aHf лийских колониях он был введен в 1752 rоду, при
этом из календаря было опущено одиннадцать дней:
3 сентября стали считать 14 сентября по новому
стилю **). ,
Оставmаяся часть этоrо параrрафа предназначена
для тех, кто хотел бы познакомиться с выводом фор-
мулы (8.2.2). Вывод формулы проведем в два этапа.
Вопервых, определим номер дня недели ДЛЯ
1 марта произвольноrо Nro rода в формуле (8.2.1).
Начнем отсчет от HeKoToporo rода, скажем, от
1600ro, и обозначим номер дня недели для 1 марта
этоrо rода через d I600 . Можно было бы узнать номер
этоrо дня из архивных документов, но можно обой-
тись и без этоrо, а получить ero, как результат рас-
суждений.
Если бы не было високосных лет, то мы моrли бы
найти d N  номер дня недели 1 марта Nro rодз, про-
сто добавляя по одному дню к d 1600 для каждоrо из
прошедших лет. Это дает число
d 1600 + (100с + у ....... 1600) (mod 7).
(8.2.З}
Принимая во внимание високосные rоды и предпо-
u u
лаrая, что они следуют реrулярно каждыи четвертыи
rод, мы должны прибавить к первому выражению еще
следующее:
[ (100с + у  1600) 1 == 25с  400 + [  у]. (8.2.4)
Однако это чуть больше, чем нужно, потому что rод
окончания каждоrо столетия обычно не бывает ВИСО IIJ
косным, и ввиду этоrо мы должны вычесть число
с ........, 16.
(8.2.5)
*) Это распространенная ошибка. Первым днем следующе..
ro столетия будет 1 января 2001 rода, который будет flопедель-
НИКОМ. (Пpu-м. перев.)
**} у' нас переход на rриrорианский календарь произошел
в 1918 rоду; вместо I февраля ста poro стилй Стали считать
14 февраля HOBoro стиля. (ПРUAJ. перев.)
111

Но мы должны еще учесть следующее исключение
если с......... номер столетия, делится на четыре, то rод
100 с считается високосным. Таким образом, нужно
добавить последнюю поправку
[ (c 16)]== [ c]4. (8.2.6)
Теперь мы сложим выражение (8.2.3) и (8.2.4).
вычтем (8.2.5) и прибавим (8.2.6). Это даст нам но...
мер дня недели 1 марта Nro rода в виде выражения
d N == d l600 + 124с + у  1988 + [  с] + [  У] (mod 7).
Чтобы упростить ero, мы приводим числа по модулю 7
и таким образом получаем
dN==dI6002c+Y+[  c]+[  У] (mod 7). (8.2.7)
Применим эту формулу к 1968 rоду, в котором
1 марта падает на пятницу, следовательно, d 1968 == 5.
Здесь
с== 19, [i,c]:=s4, У==68, . [ У]== 17.
и мы находим
d 1965 == 5 == d + 2 (mod 7).
Э,!,о даст нам, что d 1600 == 3, следовательно, 1 .MapT.
1600 rода рыло средой. Коrда мы вставим получеи"
ное значение в (8.2.7), мы придем к формуле
d N == 3  2с + у + [ с] + [ У] (mod 7) (8.2.8)
для номера дня недели 1 марта Nro rода.
Вторым этапом будет определение колиqства
дней по модулю 7 от 1 марта до произвольно взитоrо
ДНЯ этоrо tода. Так как количество дней в месяце
меняется, то для этоrо требуется некоторая хитрость..
Начнем с нахождения количества дней, которые нуж
но прибавить к номеру дня 1 марта, чтобы полу
чить номер дня 1 числа любоrо друrоrо месяца по
модулю 7.
Так как в марте 31 день, то для получения номера
1 апреля нужно добавить 3, для получения но..
мера 1 мая мы должны добавить 3 + 2 дней, так как
112

в апреле 30 дней. Продолжая рассмотрение ДЛЯ по-
следующих месяцев, мы получаем добавочные ела-
raeMbIe в виде следующей таблицы:
1 Март О VII Сентябрь 16
II Апрель 3 УI 1 1 Октябрь 18
lLI Май 5 IX Ноябрь 21
IV Июнь 8 Х Декабрь 23
V Июль 10 XI Январь 26
УI ABrycT 13 XII Февраль 29
Стоит отметить, что начав наш отсчет rQ.да с 1 марта,
мы в действительности вернулись к древнему рим.
скому календарю, введенному Юлием Цезарем, rде
сентябрь, октябрь, ноябрь, декабрь были седьмым,
восьмым, девятым и десятым месяцами, что видно,
если заметить, что по латыни septem  семь, okto..........
восемь, попо  девять, deca  десять.
Вернемся к таблице добавочных слаrаемых. Чис...
ла в таблице, хотя и не образуют реrулярной после-
довательности, но возрастают в среднем на
29
11 == 2, 6 ... в месяц.
Так как первое число есть о, то мы должны приба
вить около 2,6 и взять следующее целое число, чтобы
поJiучить число, стоящее на строчку ниже. Очевидно,
что это не совсем правильно, однако, манипулируя
вычитаемым числом, мы мож-ем получить выIа.жние
[,6т  ,2] == [ (l3m  11>], т == 1, 2, ..., 12.
(8.2.9)1
С изумлением мы можем сказать: «Теперь все в по..
рядке!» Если вы проверите значения этоrо выражения
для т == 1, 2, ..., 12 в формуле (8.2.9), то получите
в ТQЧНОСТИ те же значения, что и в нашей таблице.
'Поэтому выражение (8.2.9) нужно прибавить к
номеру дня недели 1 марта (8.2.8), чтобы получить
день недели первоrо дня тro месяца. И наконец,
так как мы хотим получить номер дня недели dro дня
этоrо месяца, мы должны прибавить еще d  1. Ко-
rда это будет сделано и будет произведена неболь-
113

mая перестановка членов, мы придем в точности к
нашеЙ формуле (8.2.2).
с и с т е м а 3 а Д а ч 8.2.
1. Найдите день недели вашеrо дня рождения.
2. Как можно упростить формулу (8.2.2), если
рассматривать лишь rоды с 1900 по 1999?
3. Как распределены дни недели дней рождения
учеников вашеrо класса?
 3. Расписа'ния соревнований
в качестве друrоrо простоrо применения
теории сравнений можно рассмотреть составление
расписаний соревнований, проходящих по круrовой
системе, подобных тем, которые составляются во всех
видах соревнований от шахмат до футбола.
Обозначим количество участников (или команд)
через N. Если число N  нечетное, то в каждом туре
соревнований невозможно разбить все команды на
пары  каждый раз одна из команд будет свободна
от иrры. Мы можем обойти эту трудность, добавив
фиктивную команду Т () и составляя расписание для
(N + l)й команды, включая команду То. В каждом
u u
туре команда, которои выпадает иrрать с командам
Т(}, будет свободна от иrры.
Из сказанноrо следует, что можно считать коли-
чество команд N четным числом. Каждой команде мы
сопоставим число
х == 1, 2, ..., N  1, N.
Общее количество туров, которое должна сыrрзтъ
чаждая команда, равно N ......... 1.
Предположим теперь, что х принадлежит множе-
ству
{1, 2, ..., N  1}.
(8.3.1)
в качестве противника команды х в 'M ту ре мы
назначим команду с номером у, из множества (8.3.1),
rде число у, удовлетворяет сравнению
х + у, == r (mod (N  1».
(8.3.2)
114

Чтобы увидеть, что при этом раЗНQIе команды х имеют
разных противников, заметим, что сравнение
х + У, ==, == х' + У, (mod (N  1»)
означает, что
х == х' (mod (N  1»
или х === х', так как эти числа принадлежат м ноже...
ству (8.3.1).
Единственная сложность возникает в том случае,
коrда Х === Yr, И таким образом в формуле (8.3.2) по-
лучаем
2х == r.(mod (N  1».
(8.3.3)
Существует лишь одно значение х во множестве
(8.3.1), для KOToporo выполняется это соотношение,.
действительно, если
2х == r == 2х' (mod (N  1»),
то отсюда следует, что
2 (х  х') == о (mod (N  1»,
ИЛИ
х == х' (mod (N  1),
так как N  1  нечетное число. Решение сравнения
(8.3.3) на множестве (8.3.1) всеrда существует, а
именно:
f r
I 2'
х=={
I r+Nl
t 2
если ,четное,
если r  нечетное.
С помощью соотношения (8.3.2) мы приписали
в ,-м туре для каждой команды х ее противника, за
исключением номера Хо, который удовлетворяет усло..
вию (8.3.3). Команда хо в этом туре будет встре-
чаться с командой, имеющей номер N.
Осталось показать, что в результате TaKoro под.
бора любая команда в каждом туре, == 1, 2, ..., N
иrрает с различным прот,ивником. Сначала мы удо-
стоверимся в этом для команды с номером N, имею-
щей в некотором смысле особое положение. В '!8М
U U
туре она иrрает с командои Хо, определяемои из со-
отношения (8.3.3}. Предположим, что s =1= (; TorAa в
115

SM туре Nя команда иrрает с командой, имеющей
номер X, удовлетворяющий соотношению
2хо == s (mod (N  1».
При этом не может случиться, что ХО == х', так как
это привело бы к тому, что
2хо == 2хо == r == 5 (mod (N ....... 1»
и, следовательно, , == s.
Теперь рассмотрим различных противников коман:,
ды х, принадлежащей множеству (8.3.1). с командой,
имеющей номер N, эта команда иrрает только одии
раз, а именно в туре 'о, rAe '0 определяется из cpaB
нения
2х == 'о (mod (N ....... 1 »).
Предположим теперь, что r =1= 'о и s =1= '0. Тоrда про
тивники команды х в 'M И 5M турах будут опреде
JJЯТЬСЯ из соотношения (8.3.2):
Х + У, == , (mod (N ....... 1)) и х + Ys == 5 (mod (N ....... 1).
Вновь цз равенства у, == Ys будет следовать , === 5,
откуда мы делаем вывод, что у, =1= Ys.
Построим таблицу соревнований, проходящих по
круrовой системе, для N === 6 команд с помощью из-
ложенноrо метода. Проведя несколько простых вы-
числений, получим приведенную ниже таблицу. На
пересечении ,й строки и xro столбца стоит номер
Toro противника команды с номером х, с которым она
иrрает в 'M туре.
>,,1 1
2
3
4
5
6
1 5 4 6 2 1 3
.
2 6 5 4 3 2 1
3 2 1 5 6 3 4
4 3 6 1 5 4 2
5 4 3 2 1 6 5
с и с т е м а э а Д а ч 8.3.
1. Постройте таблицу для N == 8 иrроков.
2. Покажите, что коrда , == 2, команды 1, 2, ...
'i . ., N встречаются с командами N, N  1, ..., 2, 1
соответсtвеино.
116

3. Почему команда с номером N  1 в ,-М туре
иrрает всеrда с ,й командой, за исключением r ==
== N ..-.--. 1? С какой командой она иrрает в этом ис..
ключительном случае?
4. Убедитесь, что если в соответствии с формулой
команда х в 'M туре иrрает с командой у, то команда
у в этом туре иrрает с командой х.
 4. Простое или составное?
В заключение обсудим применение срав"
нений в качестве метода определения Toro, является
ли некоторое большое число простым или составным.
Этот очень эффективный метод особенно хорош, ко..
rда речь идет о некотором числе, выбранном науrад.
Он основан на малой теореме Ферма (7.5.8).
Пусть N  исследуемое ЧИСJJО. Выберем небольшое
число а взаимно простое с N. Удобно в качестве чис..
ла а брать некоторое небольшое простое число, не
являющееся делителем числа N, например, 2, 3 или 5.
Если бы N было простым числом, то для Hero было
бы справедливо сравнение
aNl == 1 (mod N), (8.4.1)
в соответствии с малой теоремой Ферма. Следователь..
но, если MhI проверим это сравнение (8.4.1) и убе..
димся, что оно не выполняется, то можно утверждать,
что число N является составным.
При м ер. Возьмем N === 91 и выберем а === 2. To
rда
aNl === 290 === 264 . 216 . 28 . 22.
Более Toro,
28 === 256 ==  17 (mod 91),
216 == (28)2 == ( 17)2 === 289 == 16 (mod 91),
232 === (216)2 == (16)2 == 256 ==  17 (mod 91),
264 == (232)2 == ( 17)2 == 289 == 16 (mod 91),
так что
290 === 264 . 216 · 28 · 22==16 · 16 · (17) · 4==64 Ф 1 (mod 91).
Отсюда делаем вывод, что число N составное. Идей..
ствительно, 91 === 7 · 13.
117

Наш пример слишком прост, чтобы на нем уви-
деть действитеЛЬНУIО силу метода. Составив соответ"!I
ствующую проrрамму дЛЯ ЭВМ, можно таким спосо-
бом установить, что некоторые очень большие числа
являются составными. К сожалению, этот метод не
указывает на то, какие именно множители Иl\1еет дан..
ное число, следовательно, во мноrих случаях мы
знаем, что число состаВ"ное, однако не имеем пред..
ставления о ero делителях.
В особенности это относится к числам Фер:ма
F n === 2 2n + 1,
которые мы обсуждали в  3 rлавы 2. Как мы уже
отмечали, они являются простыми для п === О, 1, 2, 3, 4.
Чтобы проверить число
F s === 225 + 1 == 232 + 1 === 4294967297
с помощью теоремы Ферма, можно взять а == 3. Если
бы Рб было простым числом, мы бы имели, что
3232 == 1 (топ Р 5 ). (8.4.2)
Чтобы вычислить остаток степени в левой части срав"
нения, мы должны возвести число 3 в квадрат 32 раза
и всякий раз привести полученный результат по мо-
дулю Рб. Мы избавим читателя от подробностей.
Можно найти, что сравнение (8.4.2) не выполняется,
следовательно, число Рб является составным. Извест-
ный множитель 641 был найден путем проб. Тот же
самый метод был использован для Toro, чтобы пока..
зать, что несколько больших чисел Ферма не яв..
ляются простыми. Для некоторых из них нам извет",
ны множители, а для друrих нет.
Если сравнение (8.4.1) выполняется для некото-
poro числа а, взаимно простоrо с числом N, то чис..
ло N может как быть простым, так и не быть им.
При этом случаи, коrда сравнение выполняеТGЯ для
cocTaBHoro числа N, являются исключительными, по..
этому при выполнении сравнения мы можем быть
почти уверены в том, что число N  просто. Однако
для мноrих целей хотелось бы знать наверняка, яв"
ляется ли данное число простым. Это удается сделать
с помощью усовершенствованноrо метода, основан..
Horo на следующем замечании: N является простым
118

числом в том случае, если сравf!ение (8.4.1) выпол..
н,яется для степени N  1, но не выполняется ни для
какой степени, являющейся делителем числа N  1.
Имеется друrой ПОДХОД, эффективный для не
слишком больших чисел N. Возьмем а == 2. Амери-
канские математики Пуль и Лемер нашли с помощью
ЭВМ все значения чисел N  1,00000, исключитель-
ные в том смысле, что выполняется сравнение
2N1 === 1 (mod N), (8.4.3)
но число N является составным. Такие числа N ино-
rда называют псевдопростыми. Для каждо-rо из этих
исел N были указаны также наибольшие простые
множители.
С помощью таблиц Пуля и Лемера можно {)пре.
делить ПРОСТОТУ любоrо числа N  100 000 000. Сна-
чала проверяется выполнимость сравнения (8.4.3).
Если это сравнение не выполняется, то число N........
составное. Если же это сравнение выполняется и чис-
ло N есть в таблицах, то оно также составное, и мы
можем прочесть в таблицах ero простой множитель.
И наконец, если сравнение (8.4.3) выполняется и чис-
ла N нет в таблицах, то оно простое.
Наименьшим составным числом, удовлетворяю-
щим сравнению (8.4.3), является
N === 341 === 11 · 31.
В пределах 1000 существуют еще два таких числа,
а именно:
N === 561 === 3 · 11 · 17,
N == 645 === 3 · 5 · 43.
Число 561 является замечательным, т-ак как соответ-
ствующее сравнение (8.4.1) выполняется для к,аждО20
целоrо числа а, взаимно простоrо с числом N. Мы
н а'зываем такие особые числа числами, имеющими
сВойство Ферма. По таким числам в последнее время
было проведено orpoMHoe количество исследований.

РЕШЕНИЯ ИЗБРАННЫХ ЗАДАЧ
С и с т е м а з а Д а ч 1.3.
Ответы для обеих задач можно найти в табл. 3
на стр. 61.
Система задач 1.4.
11) Предположим, что верно соотношение
1
т n 1 == 2" (n ........ 1) n.
Можно проверить ero для n === 2, 3, 4. Из рис. 4 вид-
но, что Т n получается из Т пl прибавлением числа n,
поэтому
1
Tп==Tnl +n==2"n(n+ 1).
2. Из рис. 5 видно, что для Toro, чтобы получить
Р п , нужно прибавить к Pпl числ-о
1 + 3 (п  1) === 3n  2.
Если мы уже знаем, что
1
Pn1===2 (3(n 1)2(п l)
(это справедливо для n == 2, 3, 4, в соответствии с
последовательностью (1.4.3», то отсюда следует, что
1
Рn == Pпl + 3п  2 ==2 (3п 2  п).
3. Мы можем получить пe kуrольное число из
(n ....... 1) ro, прибавив к нему
(k ........ 2) (n  {) + 1
и выводя формулу таким же СПOfобом, как и в за-
даче 2. Задачи 2 и 3 MorYT быть решены иначе: де-
лением точек на треуrольники, как указано на рие. 5,
120

и использованием формулы для Т п . Пр{)ведите это до-
казательство во всех деталях.
с и с т е м а з а Д а ч 1.5.
1. Например, квадрат
16 3
9 6
5 10
4 I 15
2 13
7 12
11 8
141 1
полученный перестановкой второй и третьей строк
квадрата Дюрера, также является маrическим. Ме-
нее тривиальным является квадрат
16 4
9 5
6 10
3 I 15
1 13
8 12
11 7
141 2
2. Так как числа в квадрате 4 Х 4 не превышают
16, возожны лишь два rода, 1515 и 1516. ПервыЙ,
очевидно, исключается, во втором случае построить
квадрат оказывается невозможным.
с и с т е м а з а Д а ч 2.1.
2. 1979.
3. Числа от 114 до 126 все составные.
с и с т е м а з а Д а ч 2.3.
1. n == 3, 5, 15, 17, 51, 85.
2. Имеем
3600 3600 3600
51 == 6 17 ....... 3.
3. Количество различных произведений чисел
Ферма (от одноrо до пяти чисел в одном произведе..
нии) равно
5+10+10+5+1==31.
Таково количество чисел, для которых MorYT быть
построены мноrоуrольники. Наибольшим значением
является
n === 3 · 5 · 17 · 257 · 65537 ==- 4 294967 295.
121

с и с т е м а з а Д а ч 2.4.
1. В каждой из первых десяти сотен имеется соот"
BeTC'lBeHHO 24, 20, 16, 16, 17, 14, 16, 14, 15, 14 простых
чисел.
2. Существует 11 таких простых чисел.
С и с т е м а з а Д а ч 3.1.
1. 120 == 23. 3. 5; 365  5. 73; 1970 == 2. 5. 197.
3. 360 == 2. 2 · 90 === 2 · 6 · 30 == 2 · 1 О · 18 == 6 · 6. 1 о.
С и с т е м а з а Д а ч 3.2.
1. Простое число имеет два делителя; ра  сте..
пень простоrо числа, имеет сх. + 1 делитель.
2. ,;(60)== 12, 17(366)==8, 17(1970)==8.
3. Наибольшим количеством делителей у числа, не
превосходящеrо 100, является 12. Такое количество
делителей имеют числа 72, 84, 90, 96.
С и с т е м а з а Д а ч 3.3.
1. 24; 48; 60; 10080.
2. 192; 180; 45360.
3. 24 и 36.
4. Пусть число делителей равно ,. s, r де r и s.........
простые числа. Тоrда
п == p'Sl или п == р'.....l . qSl,
rде р и q  простые числа.
с и с т е м а з а Д а ч 3.4.
1. 8 128 и 33550336.
Система задач 4.1.
1. а) D(360, 1970) == 10; б) D(30, 365) == 5.
2. Предположим, что   рациональное число,
... / а
Т. е. 'V 2 == ь. Можем считать, что все сокращения
произведены и числа а и Ь не имеют общих множи-
телей. Возводя в квадрат это соотношение, получаем
2Ь 2 == а 2 .
По теореме о единственности разложения число а
делится на 2, следовательно, а 2 делится на 4. И вновь
по теореме о единственности разложения, применен-
122

НОЙ К числу Ь 2 , получаем, что Ь делится на 2, что
противоречит предположению о TOf\I, что числа а и Ь
не имеют общих множителей. Полученное противоре-
чие показывает, что ,у2  число иррациональное.
с и с т е м а з а Д а ч 4.2.
1. Нечетные числа.
2. Если простое число р является  делителем чи..
сел n и n + 1, то оно будет делителем числа
(п+l)n===1.
3. Никакие из них не являются взаимно простыми.
4. Да.
с и с т е м а з а Д а ч 4.3.
2. D (220,284) === 4, D(1184, 1210)===2, D(2620, 2924)==
== 4, D (5020, 5564) === 4.
3. Чтобы определить наибольшую степень числа
1 о, на которую делится число n == 1 · 2. 3 ... n, мы
должны сначала найти наибольшую степень числа 5,
на которую оно делится. Каждое пятое число 5, 1 о,
15, 20, 25, 30 делится на 5, Bcero таких чисел, не пре..
ВОСХОДЯЩИХ числа п, [  ]. Однако некоторые из них
делятся на вторую степень числа 5, а именно, 25, 50,
75, 100 ... ; таких чисел существует [  ]. Некото-
рые из них делятся на третью степень числа 5, т. е.
на 125: 125, 250, 375; их существует [ ] и т. д. Это
показывает, что выражение для точной степени чис
ла 5, делящей число n! таково:
[ ]+ [] + [;з ]+' ..
(*)
в этой сумме достаточно выписать лишь те члены, в
которых у выражения в квадратных скобках числи-
тель не меньше знаменателя.
Точно такие же рассуждения можнg провести для
нахождения соответствующей степени любоrо друrо-
ro простоrо числа р. В частности, коrда р == 2, полу
чается выражение
[ ; ]+[ ;2 ]+ [; ]+' ..
123

Ясно, что это выражение не меньше, чем выражение
(*), т. е. в числе п! каждому множителю 5 можно
подобрать множитель 2. Таким образом, выражение
(-к.) также дает и величину степени числа 10, деля...
щей п!, которая равна числу нулей, стоящих в ко...
нечпой части записи числа.
При м еры. n === 10, [ O ] == 2, [? ] == О, поэтому 101
оканчивается двумя нулями;
п==31,
[3; ] ==6,
[ : ] === 1,
[ .!!. ] == О
53 ,
поэтому 31! оканчивается 7 нулями.
с и с т е м а з а Д а ч 4.4.
1. К (360, 1970) == 70 920, К (30, 365) == 2190.
2. l( (220, 284) == 15620, l( (1184, 1210) === 716 320.
l( (2620, 2924) == 1 915 220, l( (5020, 5564) ==
== 6 982820.
с и с т е м а 3 а Д а ч 5.2.
1. т === 8, п === 1: (16, 63, 65), п == 3: (24, 55, 73),
п == 5: (80, 39, 89), п == 7: (112, 15, 113),
т == 9, п === 2: (36, 77, 85), п == 4: (64, 65, 97)
,
n == 8: (144, 17, 145),
т === 1 О, n === 1: (20, 99, 1 О 1), п == 3: (60, 91, 109)
n === 7: (140, 51, 149), n.== 9: (180, 19, 181)'
,.
2. Нет. Если
2тп == 2mlпl, т 2 ......... n 2 === m ......... п, т 2 + п 2 === m + пТ,
то отсюда следовало бы, что
2 2 2 2
т == ml, п === nl или т == ml, n == nl.
3. Если число с является величиной rипотенузы
пифаrорова треуrольника, то произведение k.c, rде
k  любое целое число, обладает теми же свойства-
ми. Таким образом, достаточно рассмотреть лишь
значения с  100, которые не имеют делителей и мо-
rYT быть величиной rипотенузы. Соответствующие
124

значения таковы:
с == 5, 13, 17, 29, 37, 41, 53: 61, 73, 89, 97.
с и с т е м а 3 а Д а ч 5.3.
1. (120, 50, 130), (624, 50, 626), (48, 14, 50),
(40, 30, 50), (120, 22, 122).
2. 100 == 102 + 02, 101 == 102 + 12, 104 == 102 + 22,
106 == 92 + 52, 109 == 102 + 32.
Числа 101, 106, 109 являются длинами rипотенуз
простейших пифаrоровых треуrольников.
3. Нет пифаrоровых треуrольников площади 78
или 1000. Существует единственный треуrольник (24,
10,26) площади 120.
4. Эти числа не MorYT быть периметрами пифаrо..
ровых треуrольников.
с и с т е м а 3 а Д а ч 6.2.
1. 194 и 364.
2. 362 == (1, О, 1, 1, О, 1, О, 1, 0)2 == (1, 4, О, 2)6===
== (1,4,5)17' 1969 == (1, 1, 1, 1, О, 1, 1, О, О, О, 1)2===
== (2, 2, О, О, 2, 2, 1 )3 == (6, 13, 14) 17
3. 10000 == (1, О, О, 1, 1, 1, О, О, О, 1, О, О, 0,0)2==
== ( 1, 1 , 1, 2, О, 1, 1, О, 1)з == (2, О, 1 О, 4) 17 .
С и с т е м а 3 а Д а ч 6.5.
1. 2 n + 1 === ( 1, О, О, ..., 0,1) 2 С (п  1)  м ну л ем.
2. 2 р  1 == (1,1, ..., 1)2 С Р единицами, поэтому
2p1 (2 Р  1 ) == (1, ..., 1, О, О, ..., О) 2 С Р единицами
и (р  1)M нулем.
Система 3 а Д а ч 6.6.
2. 92836 3. 29786 5. 411
12836 850 411
105672 850 411
31486 714
1947
Задачи 1 и 4 решаются подобным же образом.
12о

с и с т е м а з а Д а ч 8.2.
2. Для с == 19 последние два члена в формуле
(8.2.2) можно заменить числом 1, поскольку тоrда
[  с]  2с == 1 (mod 7).
с и с т е м а з а Д а ч 8.3.
1. 1 : 2 : 3 : 4 : 5 : 6 : 7 : 8
7:6:5:8:3:2: 1:1
8:7:6:5:4:3:2:1 I
2: 1 :7:6:8:4:3:5
3:8: 1 :7:6:5:4:2
4:3:2: 1 :7:8:5:6
5:4:8:2: 1 :7:8:3
6:5:4:3:2: 1 :8:7
2. Коrда r == 2, исключительный случай попадает
на х == 1, следовательно, 1 иrрает с 8, а 8 иrрает с 1.
Для друrих значений х == 2, 3, ..., 7
У == 2  х == 9  х (mod 7),
Т. е. соответственно у === 7, 6, ..., 2.
3. Команда N  1 иrрает с
у == r  (N  1) == r (mod (N ....... 1»)
в 'M туре. Команда N  1 может быть исключитель...
u u
нои командои, если
2 (N  1) == r (mod (N ....... 1»,
следовательно, r == N ....... 1 и тоrда команда N...... I
иrрает с командой N.
4.: Условие (8.3.2) симметрично относительно х и
У" коrда х  обычная команда. Если х удовлетворяет
условию (8.3.3), то эта команда иrрает с командой N
и, по определению, команда N иrрает с командой х.

ЗАКЛЮЧЕНИЕ
Таково наше приrлашение, в теорию чисел. Если
она заинтересовала вас и вы хотите познакомиться с ней по-
ближе, то для этоrо следует прочесть какой-нибудь системати-
ческий курс теории чисел, например,
и. М.' В и н о r р а Д о в. Основы теории чисел.  М.: Наука,
1972.
Существует также ряд популярных книr, освещающих ОТ-
дельные вопросы теории чисел. Из них мы рекомендуем вам сле-
дующие:
 Н. Н. В о р о б ь е в. Признаки делимости....... М.: Наука, 1980.
л. А. К а л у ж н и н. Основная теорема арифметики........ М. 
Наука, 1969.
В. С е р п и н с к и й. о решении уравнений в целых числах.......
М.: Физматrиз. 1963.
В. С е р п и н с к и й. Что мы знаем и чеrо не знаем о простых
числах.  М.  л.: Физматrиз, 1961.
В. С е р п и н с к и й. 250 задач по элементарной теории чи-
сел. ....... М. z П росвещение, 1968.
А. я. Х и н чин. Три жемчужины теории чисел........ М.! Наука.
1979.
М. М. П о с т н и к о в. Теорема Ферма........ M.f Наука} 1978.

о. Оре
приrЛАШЕНИЕ в ТЕОРИЮ ЧИСЕЛ
М., 1980 r., 128 стр. с ПJlJl.
(Серия: «Библиотечка «вант..)
РеАактор А. А. Моеu.л.евск.uй
Технический редактор Н. В. Вершинина
l\oppeKTop Т. С. Вайсберв
ИВ Н!! i 1629
Сдано в набор 29.01.80. Подписано к печати 10.06.80. BYMara a4xtG8 1 "I'
Тип. М!! 2. Литературнаи rариитура. 8ысокаR печать. УСЛОВИ. uеч. 4. 6,7.
Уч...изд. л. 6,32. Тираж 150 000 кз. Заказ Не 520. ЦeHa кииrи 30 коп.
Издательство «Наука.
rлавнаи редакции физикоматематической яитературы
111071, Москва, 8-71, Ленинский проспект, 15
Ленинrрадскаи типоrрафИR Н! 2 rоловное преДПРИRтие ордена Tp}"AOBorca
KpacHoro Знамени Ленинrрадскоrо объедииении сТехническая: книrа.
ИМ. Евrении Соколовой Союзполиrрафпрома при rосударственком кОМИтете
СССР по делам издательств, полиrрафии и киижной торrОВJlИ.
198052, r. Ленинrра.ц, Л-52, Измайловский проспект, 29.