А. А. БЕЛЬСКИЙ, Л. А. КАЛУЖНИН
ДЕЛЕНИЕ
С ОСТАТКОМ
БИБЛИОТЕЧКА ФИЗИКО-МАТЕМАТИЧЕСКОЙ ШКОЛЫ
МАТЕМАТИКА
А. А. БЕЛЬСКИЙ, Л. А. КАЛУЖНИН
ДЕЛЕНИЕ
С ОСТАТКОМ
Издательское объединение «Вища школа»
Головное издательство
Киев —1977
517.1
Б44
УДК 511
Деление с остатком. Бельский А. А., Калу та-
нин Л. А. Издательское объединение «Вита школа»,
1977, 72 с.
В книге освещены некоторые важные вопросы теория
чисел. Приведено доказательство теоремы о единствен-
ности разложения на простые множители, рассмотрены
алгоритм Евклида, диафантовые уравнения, арифметики
целых комплексных чисел и классов вычетов, представ-
ление чисел в различных позиционных системах и др.
Рассчитана на учащихся физико-математических школ.
Книгой могут пользоваться учителя математики и уча-
щиеся старших классов общеобразовательных школ.
Ил. 3. Список лит. 10
Редакционная коллегия: член-кор. АН УССР
А. В. Скороход (ответственный редактор), проф.
Л. А. К а л у ж н и н, проф. Н. И. К о в а н ц о в, доц.
В. И. Коба, доц. Н. Я. Лященко, доц. Ю. М. Ры-
жов, доц. М. И. Я д р е н к о (заместитель ответственно-
го редактора), канд. пед. наук Л. В. К о в а н ц о в а.
Редакция литературы по математике и физике
Зав. редакцией А. С. Макуха
Б
20203—124 <го
М211 (04)—77 152 /7
£) Издательское объединение «Вища школа», 1977,
Глава I
ОСНОВНАЯ ТЕОРЕМА АРИФМЕТИКИ
Эту теорему учащиеся хорошо знают и часто пользу-
ются ею при арифметических вычислениях (например, при
нахождении общего знаменателя дробей), не осознавая
порой того, что речь идет о важной теореме, требующей
строгого и подробного доказательства. Имеется в виду
следующее: каждое целое число мы умеем раскладывать
в произведение простых чисел. Например,
420 = 2.2.3.5 • 7.
(1)
При этом, если число достаточно велико, то для нахож-
дения соответствующего разложения нужно иногда потра-
тить немало времени, тем не менее, мы всегда это разло-
жение получаем. Но, может быть, нам до сих пор просто
везло? Уверены ли мы в.том, что любое целое число можно
всегда представить в виде произведения простых чисел?
Это действительно так, но этот факт требует доказательст-
ва. Первую часть основной теоремы как раз и составляет
утверждение:
Всякое целое число может быть представлено в виде
произведения простых чисел.
Доказательство этого утверждения приводится ниже.
Прежде чем сформулировать второе утверждение теоре-
мы, обратимся опять к примеру разложения числа 420
на простые сомножители. В школе этот процесс записы-
вается так:
420
210
105
35
2
2
3
5
7
1 ,
что и дает разложение (1). Но может быть существуют
и другие методы разложения? Как знать, дадут ли они
тот же результат? Естественно, например, пытаться разло-
з
жить данное число в пр оизведение двух меньших чисел
(не обязательно взаимно простых), а затем каждое из
них — в произведение меньших чисел и т. д. до тех пор,
пока мы не придем к числам, уже не разложимым далее,
т. е. к простым. Однако уже после первого шага ясно,
что такой процесс неоднозначен. Действительно, для того
же числа 420 имеем:
420 = 20 • 21, 420 = 15 . 28.
Таким образом, совершенно естественен вопрос: быть
может существуют целые числа, которые можно разложить
различными способами в произведение простых чисел? Ока-
зывается, что таких чисел нет, и соответствующее утверж-
дение— утверждение об однозначности разложения числа
в произведение простых сомножителей — составляет как
раз вторую часть основной теоремы:
Если некоторое число п разложимо двумя способами
в произведение простых сомножителей
n = ptp2... рь=ы,... qi,
то эти разложения совпадают с точностью до порядка
сомножителей: оба они имеют одно и то же число сомно-
жителей, т. е. k — l, и каждый сомножитель, встречаю-
щийся в первом разложении, встречается столько же раз
во втором1.
Доказательство этого утверждения мы приведем доволь-
но подробно. Оно сложнее, чем доказательство первого
утверждения, так как связано с рядом свойств арифмети-
ки целых чисел.
§ 1. ДЕЛЕНИЕ С ОСТАТКОМ И НАИБОЛЬШИЙ ОБЩИЙ
ДЕЛИТЕЛЬ (НОД) ДВУХ ЧИСЕЛ
Исходными для наших последующих рассуждений явля-
ется утверждение о возможности «деления с остатком»
в области целых чисел. Это утверждение формулируется
так:
1 Если рассматривать любые целые числа (как положительные,
так и отрицательные), то под единственностью разложения на простые
множители следует понимать, что два разложения п = ptp2.. . pk
ип = qrfz ... qt могут отличаться не только порядком сомножителей,
но и знаками соответствующих сомножителей.
4
Теорема 1. Пусть aub - целые числа и b =£0. Тогда
существуют такие целые числа q и г, причем 0 < г < | b |,
что
a — qb 4- г.	(1)
Числа q и г определяются по а и b однозначно, т. е. если
а = qtb + г, = qtb 4- r2.
где 0 < rt < | b |, i = 1, 2, то qt = q2 и rt = г2. Если в равен-
стве (1) г = 0, то это означает, что число а делится на число
b и соответственно записывается
Ь]а.
Примечание. Для двух целых чисел а и & выражения «число а
делится на число &», «число а — кратное числа &», «число b является
делителем числа а» или, наконец, «число b делит число а» имеют
один и тот же смысл; мы будем пользоваться каждым из них.
Докажем возможность представления (1). Пусть снача-
ла b > 0. Заметим, что для каждого рационального числа т
(как, впрочем, и для любого вещественного числа) сущест-
вует такое целое число t, что t < т < t 4-1. В частности,
предположим, что такое целое t найдено для т =
/<></4-1.
Отсюда
bt < а < Ы 4- b и 0 < а — bt <Zb,
Пусть q — t и r — a — bt, тогда a — bq+r и при этом,
как вытекает из последнего неравенства, 0 < г < Ь. Мы
получили представление (1) для случая b > 0.
Пусть теперь b < 0; вновь отметим, что существует
такое целое число t, что
Умножая это неравенство на & и учитывая, что b < 0,
получим: b (t 4-1) < а < bt, откуда 0 < а — b (t 4- 1) < — b.
Пусть ^ = /4-1 и r = a — b(t 4-1). Представление (I)
вновь получено: а = bq 4- г, где 0 < г < — Ь, т. е. 0 <
<г<|&|.
Остается доказать единственность. Пусть
а = qtb 4- гх = q2b 4- г2.

Тогда b (ft — q2) = r2 — rt. Tак как 0 < rz < | & |, то разность 1
r2 — Г1 по абсолютной величине будет меньше, чем | b |
и, следовательно, деление на b здесь возможно лишь при
условии, что г2—1\ — 0. Но если rt = г2, то qtb = q2b
и, таким образом, = q2.
Число q называют частным, а число г — остатком
от деления числа а на число Ь.
При помощи теоремы 1 можно ввести понятие наиболь-
шего общего делителя двух чисел и доказать ряд его
свойств.
Определение 1. Если а и b — два целых числа,
отличных от нуля, и если число с таково, что с | а и с | Ь,
то с называется общим делителем чисел а и Ь.
Заметим, что любые два числа всегда имеют общие
делители: ими являются числа 1 и — 1. Если других общих
делителей нет, то числа а и b называются взаимно
простыми. О взаимно простых числах речь будет идти '
ниже.	।
Определение. 2. Число d называется наибольшим
общим делителем (НОД) чисел а и Ь, если- 1) d является
общим делителем чисел а и b и 2) d делится на любой-
другой общий делитель чисел а и Ь.
Так, например, 6 есть НОД чисел 18 и 30, так как
6| 18 и 6130 и, с другой стороны, 6 делится на все общие
делители этих чисел: 1, —1, 2, —2, 3, —3, 6, —6.
Из этого определения непосредственно не вытекает,
что для произвольных двух чисел а и b НОД всегда сущест-
вует. Мы сейчас докажем, что это действительно так; при
этом мы не будем использовать разложение чисел а и b
на простые множители.
Теорема 2. Для любой пары целых чисел а =£0 и b
=# 0 существует НОД.	
Доказательство. Наряду с числами а и Ь мы ;
будем рассматривать всевозможные числа вида ха 4- yb, ’
где х и у какие-либо целые числа. Числа такого вида:
v = ха + yb	(2) •
называют линейными комбинациями чисел а и Ь. Напри-
мер, для а = 6, b — 22 линейными комбинациями будут
числа 28 = 1 • 6 + 1 • 22, 10 = (—2) - 6 Д- 1 - 22, —92 =
= 3-64- (—5) -22 ит. д. Вообще для заданных чисел
а и Ь существует бесконечно много чисел, являющихся
их линейными комбинациями. Обозначим множество таких
чисел через М. Заметим, что множество М содержит,
6
в частности, и сами числа а (при х — 1, # = 0) и b (при
х = 0, у = 1), а также число 0 (при х = 0, у = 0). Все
числа v из множества М являются, очевидно, целыми
числами. Если v принадлежит Л4, то и —v тоже принад-
лежит М (если v — ха + yb, то —v = (—%) а + (—у) Ь).
Отметим еще одно свойство чисел v из М, которое мы
будем использовать: все эти числа делятся на все общие
делители чисел а и Ь. Действительно, если с | а и с | b и
пусть а = а' • с и b ~ Ь' . с, то v = ха + yb = ха’с + yb'c =
= (ха' + yb') с, т. е. с | о. Пусть теперь d #= 0 — наимень-
шее по модулю число среди всех чисел из М, отличных
от 0.
Такое число во множестве М действительно существует. Заме-
тим, что во множестве М содержатся числа, не равные нулю (напри-
мер, а или 6), а их модули — положительные целые, т. е. натураль-
ные, числа. Но одно из основных свойств натуральных чисел, прини-
маемое обычно за аксиому (см. И. С. С о м и н с к и й, «Метод мате-
матической индукции», с. 9, замечание), состоит в том, что во всякой
непустой совокуйности натуральных чисел всегда содержится наимень-
шее число.
Покажем, что d является НОД чисел а и Ь. Свойством
2) определения НОД оно обладает, так как им обладают
все числа из Л1. Нужно только еще установить, что оно
обладает и свойством 1), т. е. что d является общим дели-
телем чисел а и Ь. Покажем, что d | а. Так как d принад-
лежит Л4, то d = sa + tb, где s и t — целые числа. Разде-
лим а на d с остатком, т. е. найдем такие числа q и г,
О < г < | d ], что
а = qd + г.
Но тогда и остаток г должен принадлежать множеству М.
Действительно,
г = a—qd = a — q (sa + tb) = (1 — qs)a + tb.
Вспомним теперь, что d —наименьшее по модулю число
среди отличных от нуля чисел множества М, а число г
меньше | d |. Следовательно, г = 0 и d | а. Аналогично дока*
зывается, что d\b. Теорема доказана.
Мы установили существование НОД двух целых чисел,
отличных от нуля. Из доказательства теоремы вытекает сле-
дующая теорема:
Теорема 3. НОД чисел а и b можно представить
в виде линейной комбинации этих чисел.
Возникает вопрос: определен ли НОД чисел а и b
однозначно? Ответ, конечно, отрицательный: если число
7
d обладает свойствами 1) и 2) определения НОД, то и—d
тоже ими обладает. Но этим неоднозначность исчерпыва-
ется. Действительно, пусть dad' —два НОД чисел а
и Ь. Так как d обладает свойством 2), a d’ —свойством 1),
то d'jd. Но аналогично, d\d'. Итак, а — и у —	—
= 1 — целые числа. Но единственные целые числа, обрат-
ные от которых также целые,—это числа 1 и —1. Итак,
а = 1 или а = —1, откуда d' — d или d' — —d. Если бы
в определении НОД было условие, что это число должно
быть положительным (это иногда бывает удобным), то мож-
но было бы сказать, что НОД двух отличных от нуля
целых чисел существует и однозначно определен.
В дальнейшем мы будем обозначать НОД чисел а и b
через (а, Ь), как это обычно принято в литературе по
теории чисел.
Перейдем к рассмотрению пар взаимно простых чисел.
Мы уже встречались с этим понятием.
Определение 3. Целые числа а Ф 0 и b 0 назы-
ваются взаимно простыми, если их НОД равен 1.
Иными словами, можно сказать, что взаимно простые
числа — это такие числа, единственными общими делите-
лями которых являются числа 1 и —1.
Из сказанного выше (теорема 3) следует, что если
(а, Ь) = 1, то 1 можно представить в виде:
1 = sa + tb,	(3)
где s и t — целые числа. Обратно, если равенство (3)
выполняется для соответственных $ и t, то а и Ь взаим-
но просты. Действительно (см. доказательство теоремы 1),
d — (а, Ь) —это наименьшее по модулю число среди отлич-
ных от нуля чисел вида ха + yb. Следовательно, если
(3) выполняется, то | d | < 1 и d 4= 0, так что d = ± 1.
Из сказанного непосредственно вытекает важнейшее
свойство взаимно простых чисел:
Теорема 4. Если а\Ьс и (a, b) = 1, то а\с (это свой-
ство читается так: если число а делит произведение двух
чисел и взаимно просто с одним из сомножителей, то оно
делит другой сомножитель).
Доказательство. Так как (a, b) = 1, то найдутся
такие числа s и t, что
1 = sa 4- tb.
(4)
8
Умножим последнее равенство на с. Имеем!
с — (sc) а + t (be).
Оба слагаемых в правой части делятся на а, следователь-
но, с делится на а.
Теорема 5. Если число а взаимно просто с числами
Ь и с, то оно взаимно просто с произведением Ьс.
Доказательство. Так как (a, b) = 1, то найдут-
ся целые числа s и t, удовлетворяющие равенству
1 — sa + tb.
Аналогично, так как (а, с) = 1, то
1	= иа + ис
для соответственных и и v. Перемножив почленно два
последних равенства, получим:
1 = (sa 4- tb) (иа 4- vc) — sue? 4- save 4- tbua 4- tbvc =
= (sua 4- sue 4- tbu) a 4- (tv) (be).
Пусть m = sua + svc 4- tbu и n — tv, тогда /пип — целые
числа и
1 — та 4- п (be),
следовательно, а и & — взаимно просты.
Утверждение только что доказанной теоремы легко
обобщается на произвольное число сомножителей:
Теорема 6. Если а взаимно просто в числами blf
b2.....bk, то а взаимно просто с произведением bt,
b2,..., bk.
Доказательство этой теоремы проводится методом мате-
матической индукции по числу k сомножителей.
§	2. ОСНОВНАЯ ТЕОРЕМА АРИФМЕТИКИ
Теорема. Любое целое число, отличное от нуля, может
быть представлено в виде произведения простых чисел,
причем такое представление единственно с точностью до
порядка сомножителей и их знаков.
Доказательство. Существование разложения
целого рационального числа в произведе-
ние простых чисел. Ограничимся сначала случаем
положительных целых чисел.
Примечание. Число 1 по многим причинам не принято считать
простым числом, несмотря на то, что оно не разложимо в произведем
ние меньших чисел. Тогда возникает вопрос: в каком же смысле
9
указанная выше теорема верна для числа 1? Или, иначе, в каком
смысле число 1 представимо в виде произведения простых чисел?
Мы будем считать, что 1 = 1 и есть разложение числа 1 в произ-
ведение простых чисел, причем число простых сомножителей в правой
части равно 0. Эта условность напоминет определение нулевой степе-
ни о0 = 1 (число сомножителей а равно 0). Подобное соглашение
мы принимаем и для числа —1.
Воспользуемся методом математической индукции:
а)	Для п — 1 равенство 1 — 1 и есть искомое представ-
ление: 1 является произведением пустого множества прос-
тых чисел.
б)	Предположим, что для всех положительных чисел
т меньших, чем п, разложимость в произведение простых
чисел уже установлена. Докажем тогда, что и для числа
п такая разложимость будет иметь место. Если п — прос-
тое число, то
п = п
и есть искомое разложение (один простой сомножитель).
Если п сложное составное число, то оно является произ-
ведением п = nL • п2 двух целых чисел nt и га2, каждое
из которых отлично от 1 и от п и, следовательно, < п
и га2 < п. Но тогда, по предположению индукции, разло-
жимость чисел гах и га2 в произведение простых чисел уже
установлена:
«1 = Pi - Pi • • • Рг,
~ Я1  41 * • * Яь<
где Pj и qt — простые числа. Имеем: п — pt • р2. .. pr X
X Я1 • q2... qs, е. мы получили искомое разложение
числа га.
Пусть га — отрицательное целое число, тогда —га — чис-
ло положительное. Как уже доказано, —га разложимо в
произведение простых чисел:
— п = pi  р2 • .. рк,
тогда га = (—1) pt . р2  .. pk,
или, например,
и = (—Pi)Pi • • • Pk
— искомое разложение числа га. Тем самым первая часть
теоремы доказана.
Примечание. Доказательств единственности разложения сущест-
вует довольно много. То, которое мы приведем, не самое короткое
и не совсем простое. Однако наше доказагельство имеет то преиму-
10
щество, что оно непосредственно обобщается на ряд других облас-
тей, например на область полиномов от одной переменной и на область
целых комплексных чисел.
Доказательство единственности разло-
жения целого рационального числа в про-
изведение простых сомножителей.
Заметим, что по определению простого числа два раз-
личных простых числа взаимно просты. Доказательство
однозначности разложения будем вести методом матема-
тической индукции по абсолютной величине числа п.
а)	Если |n| = 1, то п = ± 1 и 1 = 1, —1 — —1, т. е.
имеет место единственность разложения для чисел 1 и —1.
б)	Предположим, что доказываемое свойство уже уста-
новлено для всех чисел т, для которых |т| <|п|. Пусть
п —	• р2... pk — <7i • q2... Qi
— два разложения числа п в произведение простых чисел
pi, Pz, - - - , Р* и qlt q2,... , qt, соответственно. Мы утверж-
даем, что простое число pk встречается среди простых
чисел qlt... , qi или, быть может, противоположно како-
му-то из них. Действительно, если бы это было не так,
т. е. pk 4= qi, i = 1, 2,... , /, то pk было бы взаимно просто
со всеми числами qi, а следовательно, согласно теореме 6,
оно было бы взаимно просто с их произведением, т. е.
с числом п. Но это невозможно, так как pk | п, т. е.
(Рй, «) = Pk- Итак, pk равно какому-то из простых чисел
±<7г. Пусть pk,= qi (в противном случае этого равенства
можно было бы добиться перестановкой сомножителей qi,
а если все же pk = —qi, то мы изменили бы знаки у qi
и соответственно у какого-либо qi).
Итак, получаем:
п — Pi • р2 • • • Pk—1 • Pk ~ <7i • <?2 • • • <7<—1 • Pkt
откуда
п
т — pk~ pi • Pi • • • pk—i — q\ • qz • • • qi—i'
Ho | tn ] < | n | и, по предположению индукции, для m утвер-
ждение теоремы уже доказано, т. е. k —1 = / — 1. После-
довательности рь р2,...', pk-i и qit q2...Qi—i содер-
жат с точностью до знаков одни и те же простые числа,
и соответствующие простые числа входят в оба представ-
ления одинаковое число раз, а так как р* = qi, то это же
справедливо и для последовательностей рь р2,... , pk-i, Pk
и qit q2, •  • , <7<-i, qi- Теорема доказана.
U
§ 3. АЛГОРИТМ ЕВКЛИДА И РЕШЕНИЕ
ЛИНЕЙНЫХ ДИОФАНТОВЫХ
УРАВНЕНИЙ
С ДВУМЯ НЕИЗВЕСТНЫМИ
Согласно теореме 2 два целых числа а и b имеют НОД.
Рассмотрим сейчас один из способов нахождения НОД,
который был указан еще в «Элементах» Евклида и назы-
вается алгоритмом Евклида. При этом будем счи-
тать, что | а | > | b |.
Первый шаг. Делим а на b с остатком:
(1)	а = ft • 6 4-Г1, 0<Г1 < |&|.
Если /1 = 0, то Ь | а и (а, Ь) = Ь. Если гх =/= 0, то делаем
следующее:
Второй шаг. Делим b на
(2)	b = q-i • G + г2, 0 < r2 < rt.
Если г2 ¥= 0, то переходим к третьему шагу:
Третий шаг.
(3)	Г1 = Яз • гг + г3. 0 < г8 < г2
и т. д. На каждом шаге новый остаток меньше остатка
на предыдущем шаге:
|Ь|>г1>г2>...
и на каком-то й-м шаге (й<|6|) остаток станет равным
нулю:
k-u шаг:
(k)	fk—i^qkifk-i-
Покажем, что последний, не равный нулю, остаток гк_{
является искомым НОД чисел а и Ь. Действительно, мы
имеем цепочку равенств:
(1)	а = 9i. b + гх;
(2)	b = 92 . Г1 4- г2;
(3)	fi = 9а • г2 4* /"э!
(k — 1)г*_3 = 9ft—i • fft-2 4- rk_i;
(k)	rk-2 = qk -/-ft-i.
Из последнего равенства вытекает, что fft-i [гк_2> из пред-
последнего —гк_ 1 |rft-i и Г4-1|/-*_2 и, следовательно,
12
rk-\\rk-3 и, поднимаясь, таким образом, к первым равен-
ствам, заключаем, что rk-i |г2, г*—11 rif rk-} 16, rk-\\a.
Отсюда r*_i является общим делителем чисел а и Ъ.
Пусть теперь с| а и с | Ь. Тогда из равенств (1), (2),... ,
(k — 1) последовательно получаем: с | rt, с|г2,... , с|г*_ь
Таким образом, rk-i —действительно НОД чисел а и Ь.
Рассмотрим пример: а — 858, b = 253. Найти НОД этих
чисел.
Имеем:
(1)	858 = 3 • 253 + 99;
(2)	.253 = 2 • 99 + 55;
(3)	99 = 1 • 55 + 44;
(4)	55 = 1.44+ 11;
(5)	44 = 4-11,
откуда (858, 253) = 11. Как видим, при помощи алгорит-
ма Евклида НОД двух чисел находится без использова-
ния разложения этих чисел на простые сомножители.
В теореме 3 мы установили, что (a, b) =d можно запи-
сать в виде:
d = s • а + t • b,
но в доказательстве не было никакого указания на то,
как найти соответствующие числа s и t. Это очень прос-
то сделать, применяя алгоритм Евклида. Мы не будем
излагать это решение в общем случае, а разберем его
на вышеприведенном примере.
Итак, нужно найти такие целые числа s и t, что
11 =s-858 + t- 253.
Из равенств (4), (3), (2), (1) последовательно получаем:
П =55 + (—1) .44,
44 = 99 + (—1) - 55,
55 = 253 + (—2) - 99,
99 = 858 + (—3) - 253.
Подставляя теперь в первое равенство выражение для
44 из второго, затем для 55 — из третьего и т. д., получим:
11 = 55 + (—1) • (99 + (—1) - 55) = 2 - 55 + (—1) • 99 =
= 2 - (253 + (—2) - 99) + (—1) • 99 = 2 - 253 + (—5) • 99 =
= 2 - 253 + (—5) .(858 + (—3) - 253) = (—5) -858 + 17 -253.
Следовательно, $ = —5, t = 17.
13
Равенства, появляющиеся в алгоритме Евклида при
нахождении НОД чисел а и Ь, позволяют решить в целых
числах уравнение вида
d = ха + yb,
где d = (а, Ь).
Вообще, уравнение вида
ха + yb = с,
где а, Ь, с — заданные целые числа, для которого надо
найти целочисленное решение х, называется линейным
диофантовым уравнением с двумя неизвестными. Линей-
ным оно называется потому, что неизвестные х и у входят
в него в первой степени. Термин «диофантово» указывает
на то, что коэффициенты уравнения—целые числа и что
решения также находятся целочисленные.
Примечание. «Диофантово»—по имени древнегреческого матема-
тика Диофанта, около 250 г. до н. э., который в своей книге «Арифме-
тика» исследовал целочисленные уравнения; ниже мы остановимся
на квадратичных диофантовых уравнениях.
Заметим, что мы уже умеем решать линейные диофан-
товы уравнения вида
ха + yb = с.	(1)
Но мы должны рассмотреть вопрос о всех решениях этого
уравнения более детально. Отметим сначала, что не вся-
кое уравнение такого вида имеет решение. Действительно,
если уравнение (1) имеет решение в целых числах, напри-
мер х = х0, у — у0, т. е. с = хйа 4- уйЪ, и если d — (а, Ь),
то, так как d\a, d\b, число d делит оба слагаемых в пра-
вой части и, следовательно, также делит с. Отсюда делаем
вывод:
Для существования целочисленного решения уравнения
(1) необходимо, чтобы правая часть этого уравнения дели-
лась на НОД чисел а и Ь.
Например, уравнение
9х + 15# = 7
целочисленного решения не имеет, так как 7 не делится
на 3 = (9, 15). Если же в уравнении (1) d\c, то это
уравнение имеет целочисленное решение, и мы даже знаем,
как такое решение найти. Действительно, пусть с = с' х
X d и пусть s и t — такие целые числа, что
d = а • s + b • t.
14
с — с'  d = a (sc1) 4- b (t • с'),
т. е. xQ = sc', yQ — t • c' — решение уравнения (1).
Решим, например, диофантово уравнение
33 = 858х + 253г/.	(2)
Выше мы показали, что
11 =858-(-5)4-253.17.
Умножая это равенство почленно на 3, получаем
33 = 858 • (—15) 4- 253.51.
Итак, х——15, у = 51 — решение уравнения (2). Не сле-
дует думать, -что найденное решение единственно. Вообще,
оказывается, что если диофантово уравнение вида (1)
имеет решение, то оно имеет бесконечно много решений.
Мы сейчас исследуем этот вопрос более подробно: дока-
жем сформулированное утверждение и найдем общий вид
всевозможных решений уравнения (1).
Найдем сначала общий вид решения. Предположим,
что уравнение (1) наряду с целочисленным решением х0,
у0 имеет еще и решение х1( yt. Тогда
с = ах0 + Ьуо, с = axt 4- byL.
Вычитая второе равенство из первого, получим:
а (х0 — хх) 4- b (у0 — уг) = О,
или
а (х0 — х1) = Ь (yL — уо).	(3)
Если d = (а, Ь), то положим а' =—, Ь' — т. е.
4 1,1	а’ а
а = a'd;
b = b'd,
Где а' и Ь' — взаимно простые числа. Сокращая равенст-
во (3) на d, приходим к равенству
а' (х0 — xi) = Ъ' (ух —уо)-
Но так как а', Ь' взаимно просты, то а' | (Ух — уо) и. ана-
логично, Ь' | (хо—Xi). Пусть
Ух — Уо —a'kx\
Хо — Хх = b’k2,
15
имеем: a'b' • ki = a'b'kz, откуда k\ —ki = k. Таким обра-
зом, окончательно получаем
У\ = Уо + a'k = у0 + jk-,	(4)
Xi = хо — b'k = хо — £ k,	(5)
где k — некоторое целое число. Обратно, легко прове-
рить, что если Хо, Уо — целочисленное решение уравне-
ния (1), то все пары чисел вида (4) и (5) при любом
целочисленном k дают решение уравнения (1). Действитель-
но,
ах! 4- byi = а (х0 — у + b (у0 + kj =
= ахо + Ьуо + — ^-^4“^^j=c4-O = c.
Итак, если х0, Уо — целочисленные j решения уравнения
(1), то все числа вида х0— k, уо + ^'k, где k — лю-
бое целое число, являются также решениями этого урав-
нения (решений бесконечно много — по одному для каж-
дого k) и других решений нет.
§ 4. ПИФАГОРОВЫ ТРОЙКИ
Метод, по которому были найдены решения линей-
ного диофантова уравнения с двумя неизвестными, а
главное—форма, в которой был дан
ответ, применяются при решении
следующей классической задачи:
Найти все тройки целых чисел
а, Ь, с, для которых
а2 + Ь2 = с2.	(1)
Тройка таких чисел называется
пифагоровой, потому что при
ненулевых а, Ь, с, удовлетворяю-
щих условию (1), всегда существует,
и притом единственный, прямоуголь-
ный треугольник со сторонами а, Ь,
с. В самом деле, если отложить
отрезки а и b на сторонах прямого
угла, как это показано на рис. 1, и соединить их концы
А и В, то по теореме Пифагора АВ2 = а2 4- Ь2 — с2, т. е.
АВ = с, Единственность треугольника АВС при данных
16
a, b и g вытекает из признака равенства треугольников
по трем сторонам. Итак, рассмотрим подробно пифаго-
ровы тройки а, Ь, с, считая выполненным равенство (1).
Если с = 0, то обязательно а — b — 0. Поэтому доста-
точно взять лишь случай с #= 0. Из равенства (1) получаем:
(т)+(1)=Е	®
Положим у = х и y = у. Тогда соотношение (2) при-
нимает вид
х2 + у2 => 1.
(3)
Если мы сможем найти все рациональные (а не только
целые) решения уравнения (3), то тем самым будет полу-
чен ответ на задачу о пифагоровых тройках. Действи-
тельно, если (х, у) — решение уравнения (3), то всякая
тройка чисел (ах, ау, а) (где а такое целое число, что
ах и ау тоже целые) будет пифагоровой: равенство а2х2 +
+ а2х/2 = а2 получается из (3) умножением его на а2.
Поэтому рассмотрим все рациональные решения уравне-
ния (3).
Прежде всего, уравнение (3) эквивалентно уравнению
х2=1-у2.	(3')
Если из множества всех решений этого уравнения исклю-
чить решения х=0, у — ± 1, то все оставшиеся реше-
ния будут составлять множество решений уравнения
Пусть
х _ 1 +у
1 — у х *
(5)
Числа и и V, очевидно, тоже рациональные, причем х
и у выражаются через них так:
2и	UV— 1
X —  ГТ, У “ ГТ.	(6)
UV + 1 ’ 27 UV + 1	V '
(Читатель легко проверит справедливость равенств (6),
решив систему (5) относительно х и у). Уравнение (4)
в терминах и и v выглядит совсем просто:
и = v.	(7)
17
Таким образом, если (х = хо, у — уо)—решение уравне-
ния (4), то (ио = г- 9—, v0 —  +	— решение уравнения
\	1 —Ун	хо, /
(7) и обратно, если («о, уо)— решение уравнения (7), то
(см. формулы (6) (хо=~^р уо =	решение урав-
нения (4).
Но все решения уравнения (7) получаются так: надо
неизвестным и и v придавать одинаковые и всевозмож-
ные рациональные значения. Следовательно,, все решения
уравнения (4) задаются формулами (6) при и и v, рав-
ных одному и тому же, но произвольному рациональ-
ному числу t:
t2 — 1	v ’
.У ~ &+ г
Пусть t = — — несократимая дробь. Тогда система (8)
принимает вид
Х ~ т2 4- л2’
_ /”2 —
. У т2 -р п2'
Гаковы все рациональные числа х и у, которые удовлет-
воряют уравнению (4). Подставляя вместо /пип произ-
вольные целые значения, одновременно не равные нулю,
мы получаем решение уравнения (4). Заметим, что при
т = 0, п = 1 имеем решение: х = 0, у = — 1, а при т —
= 1, п — 0 — решение х = 0, у = 1. Оба эти решения
раньше были исключены для законного выполнения пре-
образований, но теперь, как мы видим, они не утеряны.
Итак, при любых целых т и п, одновременно не равных
нулю, тройка целых чисел
2тп, т2— п2, т2 + п2	(10)
— пифагорова. Более того, как уже было сказано, пифа-
горовой является всякая тройка целых чисел
2атп, а (т2 — п2), а (т2 + п2)	(10')
при любом допустимом рациональном числе а (в част-
ности, и при а = 0). Напомним, мы начали с равенства
18
(1) и затем последовательно перешли от него через ра-
венства (2)—(8) к равенству (9), т. е. к равенствам
а __ 2тп
~с ~ m2+n2’	( ’
b  т2 — п2
с	т2 + л2’
Положим а = 2/nnpi, b — (т2 — п2) р2, с = (т2 4- п2) р3 при
некоторых рациональных числах pi, р2, рз. Тогда из
первого равенства в (9') следует, что = 1, а из вто-
рого — “ = h т- е- а — “Ztnna., b = {т2 — п2) а, с = (т2 +
4- п2) а при некотором рациональном а.
Остается выяснить, каким может быть знаменатель
рационального числа а. Так как число 2/ипа— целое, то
делителями знаменателя а могут быть лишь делители чисел
т, п и 2. С другой стороны, так как (т2— п2) а — целое
число, то делители знаменателя числа а должны быть
делителями числа т2— п2, а потому среди них нет дели-
телей чисел тип: ведь (т, п) — 1 по условию. Итак,
число а—либо целое, либо рациональное со знаменате-
лем 2. В последнем случае числа тип одновременно
нечетны.
Таким образом, мы пришли к теореме:
Теорема. Тройка целых чисел (а, Ь, с) является пифа-
горовой тогда и только тогда, когда она имеет вид (2атп,
а (т2 — п2), а (т2 4- я2)), где т и п — целые взаимно простые
числа, а а — любое целое число; если тип.— нечетные
числа, то число а может быть не только целым, но и
числом вида где р — нечетное число.
Например, положив т = 2, п — 1, а — 1, мы получаем
пифагорову тройку 4, 3, 5, а с ней и пифагоровы тройки
при тех же т и п, но других а: (12, 9, 15); (20, 15, 25)
и т. д.
В Древнем Египте пифагоровы тройки использовались
для построения прямых углов. Если числа а, Ь, с свя-
заны соотношением (1), то треугольник со сторонами а,
b и с — прямоугольный. Построение же треугольника по
трем сторонам легко проводится циркулем и линейкой:
на концах отрезка с как из центров описываются дуги
радиусов а и b соответственно, и точка их пересечения
соединяется с концами отрезка с. На практике отрезки
19
a, b и в были кусками веревки, длины которых относи-
лись друг к другу как числа какой-нибудь пифагоровой
тройки. Например, 3:4:5.
Упражнения
1.	Найти все целые числа х такие, что выражение х3 + 2х + 7
при делении на 5 дает остаток 2.
2.	Пусть т — натуральное число т > 1, a f (х) = aQxn +
+ .. . + ап — полином с целыми коэффициентами а0, ар . . .,
Доказать, что если х целое число, то остаток при делении f (х) на т
зависит лишь от остатка числа х при делении на т.
3.	Докажите, что d — НОД (а, Ь) и — d единственные общие дели-
тели чисел а и bt которые можно представить в виде линейной ком-
бинации чисел а и Ь.
4.	Покажите, что число шагов в алгоритме Евклида может быть
сколь угодно велико.
5.	Найти НОД (а, Ь) и представить его в виде аа + ₽6 для:
а) а = 127, 6 = 211; б) а = 111 111, 6=111; в) а=191, 6 = 291.
6.	Доказать, что НОД (а, 6) = НОД (а, а + 6) = НОД (а, а — 6).
7.	Найти все целочисленные решения уравнений:
a) 2x+3z/ = 5; б) 10х + 2у = 5; в) 121^+1331^=11.
8.	Доказать, что если р —простое число, то Vp —-число ирра-
циональное.
9.	Найти все пифагоровы тройки а, Ьг с, для которых [с| < 100.
Глава II
АРИФМЕТИКА ГАУССОВЫХ ЧИСЕЛ
§ 1. ГАУССОВЫ ЧИСЛА И ЦЕЛЫЕ ГАУССОВЫ ЧИСЛА
Естественным обобщением целых рациональных чисел
являются «целые комплексные числа», или, как их обычно
называют, «целые гауссовы числа» по имени великого
немецкого математика К. Ф. Гаусса, который их впер-
вые подробно изучал.
Определение 1. Целым гауссовым числом называется
комплексное число, вещественной и мнимой частью кото-
рого являются целые рациональные числа. Иначе говоря,
это комплексные числа а вида
а = a + W,	(1)
где а и Ь — целые рациональные числа. Наряду с целыми
гауссовыми числами нам понадобятся также (просто) гаус-
совы числа, т. е. комплексные числа, у которых веще-
ственная и мнимая част и — числа рациональные.
20
Связь между областями гауссовых чисел и целых гаус-
совых чисел аналогична связи между рациональными
числами и целыми рациональными числами. Более точно,
имеются в виду следующие утверждения, которыми в
дальнейшем мы будем часто пользоваться без особой
оговорки и которые читатель легко проверит непосред-
ственно:
I.	Сумма, разность и произведение двух целых гауссо-
вых чисел также являются целыми гауссовыми числами (это
свойство выражают кратко, говоря, что целые гауссовы
числа образуют кольцо).
II.	Сумма, разность, произведение и частное (в случае,
если делитель не равен нулю) двух гауссовых чисел также
являются гауссовыми числами (это свойство выражают
кратко, говоря, что гауссовы числа образуют поле).
III.	Частное двух целых гауссовых чисел является гаус-
совым числом и, обратно, всякое гауссово число представимо
как частное двух целых гауссовых чисел.
Это утверждение требует небольшого пояснения: пусть
а = а + Ы и р = с + di — целые гауссовы числа (т. е. а,
Ь, с, d — целые рациональные числа) и пусть р #= 0. Пока-
жем, что у = а/р — гауссово число. Действительно,
_ а + bi _ (а + Ы) (с — di) ас + М + bci — adi _
"I ~ с + di ~ (с + dii (с — di)	с2 -|- d2	~~
__ас + bd .be — ad .
~ с2 + d2 + c2 + d2 l'
IT ac-i-bd be —ad ,
Числа e2 и	(вещественная и мнимая части
числа у)— числа рациональные и, следовательно, у —
гауссово число.
Отметим, наконец, что, очевидно, всякое рациональ-
ное число является гауссовым (мнимая часть равна 0)
и что всякое целое рациональное число является целым
гауссовым числом.
Рассмотрим расположение целых гауссовых чисел на
комплексной плоскости. По определению целые гауссовы
числа изображаются точками с целочисленными коорди-
натами (рис. 2). Они лежат в вершинах сетки квадратов
со стороной, равной 1, покрывающей комплексную плос-
кость.
В дальнейшем нам из теории комплексных чисел нужны
будут понятия нормы и модуля комплексного числа.
Напомним, что нормой комплексного числа а = х + iy
21
Рис. 2
называется неотрицательное вещественное число N (а) =
= х2 4- г/2; модулем комплексного числа а (обознача-
ется |а|) называется вещественное число j/x2 + Z/2- Гео-
метрически модуль комплексного числа—это расстояние
соответствующей точки на комплексной плоскости от
начала координат. Норма N (а)_числа а представима как
произведение N (а) = а . а, где а — комплексно сопряжен-
ное число х—iy числа
1 а. Известным предпола-
, гается также свойство
мультипликативности
нормы, т. е. что
2V (а . р) = W (а) . W (р).
(2)
Отметим сразу, что если
а — гауссово число, то
N (а) — неотрицатель-
ное рациональное чис-
ло, а если а — целое гауссово число, то N (а) — неотри-
цательное целое число.
Примечание. Модуль | а | гауссова числа уже не всегда будет
рациональным числом, поэтому в дальнейшем мы в основном будем
пользоваться не модулем, а нормой.
Однако не всякое положительное целое рациональ-
ное число является нормой целого гауссового числа. Дей-
ствительно, докажем следующую теорему:
Теорема 1: Положительное целое рациональное число
с является нормой некоторого целого гауссова числа тогда
и только тогда, когда число с представимо в виде суммы
двух квадратов целых чисел.
Доказательство. Если а=а + Ы — целое гауссово число,
то N (а) = а2 + Ь2 — сумма квадратов целых чисел а и Ь.
Наоборот, если с = х2 + У2, где х и у — целые рациональ-
ные числа, то с = N (х + yi), где х + iy — целое гауссово
число. Теорема доказана.
Нетрудно показать, что не всякое положительное целое
число представимо в виде суммы двух квадратов. Так,
например, если нечетное положительное целое число t
представимо в виде суммы двух квадратов целых чисел,
то оно дает при делении на 4 остаток, равный 1, т. е.
является числом вида / = 4&4-1. Действительно, пусть
22
t = x2 + у2, тогда одно из чисел, скажем х, должно быть
четным, другое — у — нечетным. Пусть х=2т и у = 2п 4-1.
Следовательно, х2 *= 4m2 и у2 = 4 (n2 4- n) + 1 и, оконча-
тельно, t = 4 (т2 4- п2 + n) + 1, что и доказывает наше
утверждение. Таким образом, числа 7, 11, 15 и др. не
представимы в виде суммы двух квадратов и не являются
поэтому нормами гауссовых чисел.
Вопрос о том, какие целые числа представимы в виде
суммы двух квадратов или, что то же самое, какие числа
являются нормами целых гауссовых чисел, мы выясним
в результате исследования арифметики целых гауссовых
чисел.
Как и в области (кольце) целых рациональных чисел,
так и в области целых гауссовых чисел основной инте-
рес представляет вопрос делимости.
Будем говорить, что целое гауссово число а делит целое
гауссово число 0 (и записывать это так: а 10), если для
некоторого целого гауссова числа у имеет место равенство
₽ = а • Т-	(3)
Так как из (3) следует: N (0) = N (а) . N (у), то необходи-
мым условием для а|0 является делимость 7V (а) | jV (£),
где N (а) и N (0)—целые рациональные числа.
В случае целых рациональных чисел имеются только
два числа, которые делят все целые числа: 4-1 и —1;
в случае целых гауссовых чисел таких чисел имеется
четыре: 4-1. —1. 4- Л —i. Действительно,
а = а . 1,
а = (— а) (—1),
а = (— ai) . f,
а = (ai) . (— i).
Других чисел с данными свойствами среди целых гаус-
совых чисел нет. В самом деле, если некоторое целое
гауссово число 5 делит все целые гауссовы числа, то оно,
в частности, должно делить число 1 (поэтому такие числа
называются делителями единицы). Из N (£) 11 следует, что
N ($) = 1. Если $ = х 4- iy, то х2 4- У2 = 1. Очевидно, что
это уравнение имеет в целых рациональных числах в точ
ности четыре решения: х — 1,-у = 0; х = —1, у—0; х
— 0, у = 1; х = 0, у — — 1, которые и соответствуют
целым гауссовым числам 4-1, —1, i, —f.
23
Для целых гауссовых чисел, аналогично тому, как
это делалось для целых рациональных чисел, определя-
ются понятия общего делителя, наибольшего общего дели-
теля, взаимно простых чисел и простых чисел. Первые
три понятия дословно определяются как и в случае целых
рациональных чисел. Однако на определении простого
целого гауссова остановимся более подробно.
Определение 2. Целое гауссово число я называется
простым, если в любом его разложении к = т . о в произ-
ведение двух целых гауссовых чисел один из сомножителей
(т или а) является делителем единицы {при этом делители
единицы простыми числами не считаются).
Иначе это свойство можно выразить так: простое
гауссово число я — это такое целое гауссово число, отлич-
ное от нуля, норма которого больше единицы и которое
не разложимо в произведение двух целых гауссовых чисел,
нормы которых меньше, чем норма числа я.
Согласно этому определению простыми гауссовыми
числами будут, например, числа = 2 -f- i, (N (it!) = 5);
it2 = 3 + 2i, (N (it2) = 13). Вообще, простыми числами
будут все числа, нормы которых являются простыми ра-
циональными числами. В дальнейшем мы увидим, что
этими примерами простые гауссовы числа не исчерпыва-
ются. В ходе наших исследований мы опишем все простые
гауссовы числа. Теперь же перейдем к формулировке и
к доказательству основной теоремы арифметики целых
гауссовых чисел:
Теорема. Любое целое гауссово число а ф 0 разложимо
в произведение простых гауссовых чисел
а = iti . я2..•. я*	(4)
(я(-— простые гауссовы числа, не обязательно все различ-
ные). Такое разложение однозначно в следующем смысле:
если
а = 01 • а2 .. . а/	(5)
—другое разложение числа а в произведение простых гаус-
совых чисел а;, то оба разложения имеют одно и то же
число сомножителей, k =1, и разложения (4) и (5) могут
отличаться друг от друга только порядком сомножителей
и множителями, являющимися делителями единицы.
Относительно части формулировки, касающейся одно-
значности разложения, сделаем еще одно замечание. Если,
скажем, а = iq . я2. я3 есть произведение простых чисел
яь тс2, *3, то, например, а = (—я3) • (iit2) • (itti) есть «дру-
24
гое» представление числа а в виде произведения простых
чисел —^3, iit2, iitt, отличных от простых чисел 14,
к2, Однако легко заметить, что любое из чисел
— «з, ^2> получается умножением какого-то из
чисел it], «2, «з на некоторый делитель единицы, при
этом изменен также первоначальный порядок чисел. Такие
различия в разложениях одного и того же числа допуска-
ются. Вторая часть формулировки теоремы как раз и
утверждает, что подобного рода различными разложе-
ниями неоднозначность представления исчерпывается. Это
обстоятельство ничем не отличается от ситуации в ариф-
метике целых рациональных чисел. Оно усложняется тем,
что в случае арифметики целых гауссовых чисел мы рас-
полагаем большим числом делителей единицы.
Примечание. Отметим, что однозначность разложения с точностью
до знаков сомножителей, о которой шла речь в случае целых рацио-
нальных чисел, и означает как раз однозначность с точностью до
множителей, являющихся делителями единицы, так как 4-1 и —1 —
единственные делители единицы в этом случае.
Утверждение об однозначности разложения можно
сформулировать короче, если ввести понятие ассоцииро-
ванности целых гауссовых чисел.
Определение 3. Два целых гауссовых числа назы-
ваются ассоциированными, если они отличаются друг от
друга на сомножитель, равный делителю единицы, т. е.
р, —р, ip, —ip—ассоциированные целые гауссовы числа,
если р — произвольное целое гауссово число,
С использованием этого определения утверждение об
однозначности в основной теореме формулируется так:
 Если а = it] . л2.. . it* и а = 01 . о2.. . oz — где к( (i = 1,
2,. .., k) и bj(j = 1, 2.Z) — простые числа, то I — k
и сомножители а/ можно так переставить, что каждое
о/ будет ассоциировано с соответствующим простым
ЧиСЛОМ Kj.
Доказательство основной теоремы арифметики целых
гауссовых чисел проводится так же, как и доказатель-
ство соответствующих утверждений для целых рацио-
нальных чисел. Поэтому мы не будем подробно излагать
его, а рекомендуем читателю сделать это самостоятельно.
Первое утверждение теоремы (о существовании разло-
жения) можно провести индукцией по норме числа:
а)	Если N (а) = 1, то а=1, —1, Z, —i, т. е. число
разложимо в произведение пустого множества простых
чисел.
25
Примечание. Относительно «разложимости» делителей единицы
в произведение простых сомножителей мы принимаем то же положе-
ние, что и для ±1 в случае целых рациональных чисел.
б)	Пусть N (а) = л, а для всех целых гауссовых чисел
с меньшей нормой утверждение уже доказано. Тогда или
а простое число и все доказано, или а = р . т, где N (р) <
< п и N (т) < п. По предположению индукции для р и т
существуют разложения: р =	. nk и т~ ai . а2 • • •
тогда а = Тс1 • ^2 • •.	• «I • о2... а/ — разложение для а.
Доказательство утверждения об однозначности можно
вести по пути установления свойств наибольшего общего
делителя и свойств взаимно простых чисел в области
целых гауссовых чисел. Ключом для всего доказательства
является утверждение о возможности деления с остатком
в области целых гауссовых чисел. Оно формулируется
здесь так:
Пусть а, р (р =# 0) —два целых гауссовых числа; тогда
существуют такие целые гауссовы числа у и р, причем
N (р) < N (р), что
а = у • р + р.
Примечание. Число 7 называют частным, а число р — о с т а т-
ком от деления а на ₽. В теореме 1 на стр. 5 эти понятия вводи-
лись для обычных целых чисел, но при этом остаток должен был быть
неотрицательным (г>0). Однако это требование несущественно.
Если от него отказаться и принять лишь неравенство | г | < Ь<
то определение час1ного и остатка для гауссовых чисел будет,
естественным обобщением определения в обычной ситуации.
Доказательство основано на очень простом геометри-
ческом факте: если Р — точка, лежащая внутри квадрата
со стороной а или на одной из его сторон, то расстоя-
ние от точки Р до ближайшей вершины меньше, чем а.
Действительно, точка, наиболее
шин,—это центр квадрата. Но
любой вершины равно ^а < а.
удаленная от всех вер’
расстояние от нее до
Любая другая точка
квадрата удалена от ближайшей вершины еще меньше.
Из этого простого утверждения непосредственно вы-
текает, что для любой точки т комплексной плоскости
найдется точка у с целыми координатами—точка, пред-
ставляющая целое гауссово число,—удаленная от т
меньше чем на 1 (рис. 3). Иначе говоря, для всякого
комплексного числа т существует такое целое гауссово
число у, что N (т—у) < 1. Найдем такое у для числа
26
т = -Т- и положим
р
число,
р = а — Тогда о — целое гауссово
лЧр) = л^).И|-т]<^(₽)
и
а =	+ р.
Рис. 3
Утверждение доказано.
Имея уже теорему о делении с остатком, все осталь-
ные свойства можно доказать так же, как мы это делали
выше в случае рациональ-
ных чисел: 1) доказыва-
ется существование НОД
двух целых гауссовых чи-
сел а, р, как числа В =/= О
с наименьшей нормой из
множества чисел, предста-
вимых в виде а; +
(£ и т] — целые гауссовы
числа); 2) вводится поня-
тие взаимно простых це-
лых гауссовых чисел и до-
казывается основная лем-
ма: если а взаимно просто
с и а взаимно просто
с р2, то а взаимно просто
с Pi • ₽2- Затем уже совсем
просто индукцией по норме доказывается однозначность
разложения на простые сомножители.
§ 2. ПРОСТЫЕ ГАУССОВЫ ЧИСЛА
И ПРЕДСТАВЛЕНИЕ ЦЕЛЫХ
РАЦИОНАЛЬНЫХ ЧИСЕЛ
В ВИДЕ СУММЫ ДВУХ КВАДРАТОВ
Перейдем теперь к описанию всех простых гауссовых
чисел. Докажем сначала несколько вспомогательных
утверждений.
Лемма 1. Всякое простое гауссово число является де-
лителем простого рационального числа.
Примечание. Заметим, что простое рациональное число является
всегда и целым гауссовым числом, но как гауссово число оно не
27
обязательно простое, а может делиться на целые гауссовы числа с
меньшей нормой. Так, например, число 2— простое, если его рассма-
тривать как целое рациональное число, но оно не простое, если его
рассматривать как целое гауссово число. Действительно, в области
целых гауссовых чисел число 2 допускает разложение 2 = (1 +1) х
X (1 — 0 и ни один из сомножителей 1 + i и 1 —i не является де-
лителем единицы. Очевидно, что и 5 не является простым в области
гауссовых чисел, так как 5 = (2 + i) • (2 — 0.
Доказательство. Действительно, так как N (а) = а • а,
то всякое целое гауссово число делит свою норму:
а|М(а). Пусть теперь тс—простое гауссово число, тогда
тс | N (тс), и пусть Af (тс) = pi • р2... рг — разложение числа
Af (тс) в произведение простых рациональных чисел. Имеем:
тс|р1 • р2...рг, следовательно, тс делит одно из простых
чисел pi. В самом деле, если бы простое целое гауссово
число тс не делило бы ни одно из чисел рь то оно
было бы взаимно просто с каждым из них, а следова-
тельно, и с их произведением N (тс). Но это невозможно,
так как тс|М(тс). Итак, число тс является делителем
одного из простых целых рациональных чисел рь Лемма
доказана.
Лемма 2. Норма Affrc) простого гауссова числа тс
является или простым рациональным числом, или квадра-
том простого рационального числа.
Доказательство. Как мы уже знаем, тс делит некото-
рое простое рациональное число р. Пусть р = тс • у. Пере-
йдем к нормам: Af (тс) • Af (у) = р2. Возможны только два ;
случая: 1) N (тс) = N (у) = р и 2) N (тс) = р2 = N (р), а
Af (у) = 1. Лемма доказана.	
Случай 2) означает, что у—делитель единицы и что'
справедливо одно из равенств: тс = р, тс = —р, тс = ip, |
тс == —ip. Следовательно, р — такое простое рациональное]
число, которое одновременно является и простым гаус-1
совым числом. В случае 1) у—простое гауссово число,
так как N (у) = р. Можно утверждать, что у = тс. Дейст-1
вительно, Af (тс) = р = тс • тс и тс — простое число. Но мы!
имеем также р = тс • у, так что тс = у.	1
Если же р такое простое рациональное число, кото-1
рое не является простым гауссовым числом, то оно!
делится на какое-либо простое гауссово число, отличное!
от р, и при этом, как мы видели, р = тс • тс, т. е. р явля-1
ется произведением двух простых гауссовых комплексно!
сопряженных чисел. В этом случае р является нормой!
целого гауссового числа и, следовательно, представимо!
28
в виде суммы двух квадратов. Такое простое число,
если оно нечетное (т, е. р =/= 2),—число вида 4га+1.
Можно показать, что все простые числа вида 4п +1
представимы в виде суммы двух квадратов, т. е. явля-
ются нормами некоторых целых гауссовых чисел, а по-
тому не являются простыми гауссовыми числами и,
следовательно, принадлежат к классу тех простых раци-
ональных чисел, которые разложимы в произведение
двух комплексно сопряженных простых гауссовых чисел.
Доказательство этого утверждения мы приведем ниже
(гл. III, §3). Все простые рациональные числа, отличные
от чисел вида 4п + 1 и от числа 2, т. е. числа вида
4п + 3, и составляют как раз множество простых раци-
ональных чисел, остающихся простыми и в области
гауссовых чисел.
Несколько особое положение занимает простое число 2.
Легко видеть, что
2 = i • (1 — i)2
N (1—i) =* 2. Таким образом, 2 делится на квадрат
простого гауссова числа (1—i).
Предполагая известным, что все простые числа вида
4п + 1 представимы в виде суммы двух квадратов, мы
можем теперь установить, каковы все целые рациональные
числа, представимые в виде суммы двух квадратов. Как
мы уже знаем, для всякого числа t с таким свойством
необходимо и достаточно, чтобы оно было нормой неко-
торого целого гауссова числа a: t = N (а).
Число а раскладывается в произведение простых гаус-
совых чисел:
а = lei • иг ... тег.	(6)
Разобьем все простые числа те/ (i = 1, 2,..., г) на два
класса: к первому классу отнесем те числа те/, нормы
которых — простые числа, а ко второму соответственно
числа, нормы которых — квадраты простых чисел (может
оказаться, что один из классов пуст, но это не повлияет
на ход наших рассуждений, надо только иметь в виду,
что все числа at или все bk в разложениях (7) и (8)
могут быть нулями). Обозначим различные числа первого
класса через а/ (/= 1, 2,...,/), а все различные числа
второго класса—через р^(^=1, 2,..., s). Имеем: У(а/) =
= pi, N (pfe) = q2k, где р/ — простое число вида 4га + 1 или
2, a qk—простое число вида 4га 4-3. Объединяя равные
29
простые числа в правой части равенства
это произведение в виде степеней простых
(6),
запишем
чисел
а/ и
а —	... а?1 • pf1 ... ps&s
и, переходя к нормам, имеем:
t = pi1 ... piLq\ 1 ...?s s.
(7)
(8)
Мы видим, что простые числа qk
числа в четных степенях.
входят в разложение
Обратно, пусть число t представимо в виде (8), i
каждое р/ — простое число вида 4/г 4-1 или число 2, qk
простые числа вида 4п4-3 и аь b\,..., bs—целые
неотрицательные числа. Поскольку каждое р, является
суммой двух квадратов, то можно подобрать о/ так,
чтобы N(aj) — pi. Положив далее	и, наконец,
a=ai* ... оГ'р^ ... ps&s, получим t — N (а), т. е. t представимо
в виде суммы двух квадратов. Окончательно имеем сле-
дующую теорему:
Теорема 2. Для того чтобы целое рациональное число
было представимо в виде суммы двух квадратов, необходимо
и достаточно, чтобы простые числа вида 4п -(- 3 входили
в разложение этого числа на простые сомножители в
четных степенях.
Примечание. Такая формулировка охватывает и случай, когда
простых чисел вида 4л + 3 нет в разложении рассматриваемого
числа,— ведь число 0 также является четным.
Как видим, эта теорема дает критерий того, чтобы
диофантово уравнение второй степени вида
х2 + у1 = t
имело решение (целочисленное). Вообще изучение дио-
фантовых уравнений вида
ах2 + ЪЬху + су2 — t
тесно связано с арифметиками в областях чисел, ана-
логичных области целых гауссовых чисел.
Существенным в таких исследованиях оказывается
следующий удивительный факт: не во всех подобных
арифметиках имеет место теорема об однозначности раз-
ложения чисел в произведение простых чисел. Приве-
дем пример такой «арифметики».
Рассмотрим комплексные числа вида
a = x +	5,	(1)
30
где х и у целые рациональные числа. Легко видеть, что сумма,
разность и произведение чисел вида (1) являются числами такого же
вида. Обозначим совокупность всех чисел вида (1) через Г. Очевид-
но, что Г содержит все целые рациональные числа (при у = 0). Так
же, как в случаях целых рациональных и целых гауссовых чисел,
можно говорить о делимости в Г: а делит р (а|3), если -— число из
Г т. е. представимо в виде (1). Как и в случае целых гауссовых
чисел, в вопросе делимости важную роль играют нормы чисел из Г:
N (а) = N (х + уУ~Ь) = (х + уУ—5) (х — у У—5) = х2 + 5//2.
Таким образом норма всякого числа из Г есть целое рациональное
число и, так как W (£ • tj) = ДО (£) • ДО (tj), то необходимым (но, вооб-
ще говоря, не достаточным) условием для а | р является условие
/V(«)l W).
Так же, как и в случае целых гауссовых чисел, естественно
вводится понятие делителей единицы и простых чисел. В отношении
делителей единицы дело обстоит здесь даже проще, чем для целых
гауссовых чисел. А именно, делителями единицы являются только
числа ±1. Действительно, для делителей единицы ^=и-\-юУ—5"
должно выполняться условие ДО ($) = и2 + 5 и2 = 1. Но это диофан-
тово уравнение, очевидно, не может иметь решений, отличных от
и = +1 и v = 0.
Тот факт, что каждое число из Г представимо в виде произве-
дения простых чисел из Г, доказывается индукцией по норме точно
так же, как и в случае целых гауссовых чисел. А вот утверждение
об однозначности такого разложения здесь уже не верно, и мы это
покажем на таком примере.	____ ________________
Покажем сначала, что числа 2 = 2~1~0»У—5, 3 = 3 -J- 0 - У—5,
1+У—5, 1—У—5 — простые числа в Г. Действительно, АГ(2) =4,
Л7(3) = 9, ДО(1+/—5) =	=6. Если бы одно из этих чи-
сел не было простым в Г, то оно могло бы делиться 'только на не-
которое число а = х + уУ—5, для которого ДО (а) = х2 + 5у2 = 2,
или ДО (а) = х2 + 5у2 = 3. Но таких чисел в Г нет, так как очевидно,
что уравнения
х2 + 5 г/2 = 2
и	1 *
х2 + Ьу2 = 3
не имеют целочисленных решений.
Итак, указанные четыре числа — простые числа в Г. Отметим
теперь легко проверяемое равенство
6 = 2.3=(1 +/^=5) • 0-/=5).
Оно показывает, что число 6 из Г имеет два различных представле-
ния в виде произведения простых чисел.
С этим фактом столкнулся немецкий математик Э. Куммер
(1810—1893) при^попытках решить так называемую великую теорему
Ферма. В дальнейшем трудности, возникающие в связи с невыпол-
нением основной теоремы арифметики в некоторых областях чисел,
были успешно преодолены как самим Куммером, так и другими ма-
тематиками — Р. Дедекиндом, Е. Золотаревым, Л. Кро-
неккером и др. Возникла большая новая область в математике —
теория алгебраических чисел.
31
Упражнения
1.	Разделить с остатком целое гауссово число а на целое гаус-
сово число Ь, если: а) а = 2 -j- 3z, 6=1 — i; б) а — 1 -j- i, b — 2 -\-i.
2.	Разложить на простые множители целые гауссовы числа:
14-i. 2-f- 5г; 5; 10.
3.	Представимы ли в виде суммы двух квадратов целых рацио-
нальных чисел числа: а) 197; б) 1472; в) 111 112?
4.	Докажите, что для комплексных чисел вида а-}-ьУ—2, где
а и b — целые рациональные числа, выполняется основная теоре-
ма арифметики.	___
5.	Докажите, что в кольце чисел вида а 4- ьУ—5, где а и b —>
целые рациональные числа, 7, 14-2)^—5 и 1—У—5 — простые.
Глава III
КОНЕЧНЫЕ АРИФМЕТИКИ
С первыми применениями деления с остатком мы по-
знакомились, доказывая основную теорему арифметики
и решая несложные диофантовы уравнения. Обратимся
теперь к важнейшей конструкции, связанной с делением
целых чисел,—классам вычетов.
Основная идея состоит в следующем: различных ос-
татков от деления на данное натуральное число п всего
лишь п: это числа 0, 1, 2  —1. Поэтому бесконечное
множество целых чисел можно разбить на конечное чис-
ло (на п) подмножеств, в каждое из которых входят
числа с одним и тем же остатком от деления на п. Та-
кие подмножества называются классами вычетов по моду-
лю п. Оказывается, что на них естественным образом пе-
реносятся обычные действия арифметики (умножение,
сложение, вычитание), и это приводит к новой интересной
«арифметике», которую называют конечной.
§ 1.	КЛАССЫ ВЫЧЕТОВ
Условимся, что если нет специальных оговорок, то
под «числами» подразумеваются «целые числа». Их мно-
жество представляет собой «кольцо», которое всюду бу-
дет обозначаться через Z.
Определение 1. Числа х и у называются сравни-
мыми по модулю п, где п — число, отличное от нуля, если
их разность х — у делится на п.
32
В этом случае пишут:
x = t/mod(n) или t/=xmod(n).
Для несравнимых по модулю п чисел пишут:
х =/= у mod (п) или у =/= х mod (п).
Например, 12= 15 mod (3), потому что 12 — 15=—3
делится на 3, и 21	10 mod (5), потому что 21 —10 = 11
не делится на 5.
Пусть п = 3. Каково множество всех чисел из Z,
сравнимых с числом 5 по модулю 3? Во-первых, в это
множество входит само число 5: 5 = 5 mod (3). Далее, ес-
ли х = 5 mod (3), то х — 5 = 3k при некотором k из Z, т. е.
х = 5 4- 3k. Наоборот, при любом k число х = 5 4- 3k бу-
дет сравнимо с 5 по модулю 3, потому что х — 5 = 3&,
а это кратно 3. Следовательно, придавая k в формуле
х = 5 4- ЗА всевозможные значения из Z. мы получим
множество всех чисел, сравнимых с 5 по модулю 3. Это
множество (обозначим его 5) — является обычной арифме-
тической прогрессией, бесконечной в обе стороны и раз-
ность которой равна 3; вот несколько ее последователь-
ных членов: при k = —3, —2, —1, 0, 1, 2, 3 имеем
—4, —1, 2, 5, 8, 11,...
Определение 2. Множество X всех тех чисел из
Z, которые сравнимы с числом х по модулю п, называет-
ся классом вычетов числа х по модулю п и обозначается
одним из трех способов: х mod (п) или х или х, если чис-
ло п фиксировано. Числа из X называются вычетами
числа х по модулю п или представителями класса X.
Таким образом, в рассмотренном выше примере был
описан класс вычетов 5 mod (3) числа 5 по модулю 3.
Очевидно, что 8 mod (3) = 5 mod (3) и, вообще, класс вы-
четов х = х mod (3) любого представителя х из 5 mod (3)
равен 5.
Теорема 1. Пусть x — qn-\-rt где 0<.г<п. Тогда
х mod (п) = г mod (п).
Доказательство. I способ. Достаточно заметить,
что х mod (п) и г mod (п) — это одна и та же бесконечная
в обе стороны арифметическая прогрессия х 4- kn или
г 4- kn с разностью п, потому что х 4- kn = г 4- (k 4- q) п.
2 6-364
33
II способ. Каждое число г, сравнимое с х по mod (л),
сравнимо и с г по модулю mod (п), потому что если
г—х = kn, то z — r — z—х — qn=kn — qn = (k— q)n.
И наоборот, если г — г = kn, то г — х — г—x + qn —
= (k + q)n.
Остаток г от деления числа х на п называется канони-
ческим представителем класса х mod (п). В рассмотренном
выше примере класса 5 mod (3) каноническим представи-
телем будет, следовательно, число 2.
Следствие. Всевозможные классы вычетов по моду-
лю п таковы:
О mod (n), 1 mod (п), 2 mod (п),..., (п — 1) mod (п),
то есть, это 0, 1, 2, п — 1.
Действительно, числа 0, 1, 2, ..., п — 1 составляют
множество всевозможных остатков от деления на п — по-
этому других классов вычетов кроме 0, 1, 2, ..., п — 1,
быть не может. Но нет ли среди этих классов совпадающих?
Если бы а — Ь, где а и b — различные остатки от деле-
ния на п, то при некотором целом k выполнялось бы
равенство а — b = kn, а это при k Ф 0 невозможно, так
как \а — b\<n, а |kn | > п. Следовательно, а = Ь, и все
классы 0, 1, 2, ..., п— 1 различны.
В дальнейшем мы будем обозначать через Zn множе-
ство классов вычетов по модулю п.
Упражнения
1.	Докажите, что если какое-либо целое число а принадлежит
двум классам вычетов X и Y по модулю п, то X = Y.
Указание. Заметить, что если х= a mod (п) пу=а mod (л), то
x = ymod(n) и, следовательно, х mod (л) — у mod (л).
2.	Доказать, что если л = ml, где т, I — натуральные числа, то
каждый класс вычетов по модулю т состоит из I классов вычетов по
модулю л.
3.	Доказать, что Zn и Z—п,	0 —< одно и то же множество.
§ 2.	АРИФМЕТИКА КЛАССОВ ВЫЧЕТОВ
Изучая делимость целых или целых гауссовых чисел,
мы пользовались тем, что они образуют кольцо, т. е. тем,
что сумма, разность и произведение двух любых чисел
рассматриваемого множества ему принадлежат, и упомя-
нутые операции подчинены привычным законам — пере-
местительному, сочетательному и распределительному.
Свойства кольца целых чисел составляют арифметику или,
34
точнее говоря, арифметику целых чисел. В предыдущей
главе мы познакомились с арифметикой целых гауссовых
чисел. Сейчас мы введем арифметические операции на
множестве Zn и познакомимся с арифметикой классов
вычетов. Для определенности условимся, что в понятии
«по модулю п» число п— натуральное.
Определение 3. Суммой двух классов вычетов по
модулю п —х и у — называется класс х + у. В этом сл у-
чае пишут:
х + у = х + у.
Но тут может возникнуть сомнение: ведь классы х
и //—множества, даже — бесконечные множества. Пред-
ставители х и у, с помощью которых мы определили
сумму х + у, внутри своих классов равноправны со всеми
другими представителями; поэтому, если определение 3
не таит в себе никаких противоречий, то, выбрав в х и у
другие представители, скажем, х' и у', мы должны в ка-
честве класса х' + у' получить тот же самый класс х + у,
т. е. необходимо выполнение равенства: х' + у' — х + у
(если бы х' + у' =# х + у, то определение таило бы в себе
следующее противоречие: х' + у' = х' 4- у' = х + у = х + у
вопреки х' + у' Ф х + у). Проверку равенства х' + у' =
=я х + у математики называют проверкой определения
на корректность.
Действительно, пусть гх и ги — остатки от деления
на п чисел х и у, соответственно. Тогда класс х-\-у
состоит из всех тех чисел, которые при делении на п
дают тот же остаток, что и гх 4- ry. С другой стороны,
класс х' 4- у' состоит из тех же самых чисел, потому
что остатки от деления на п чисел х' и у' есть гх и гу.
Корректность определения 3 доказана.
Рассмотрим несколько примеров. Пусть п — 2. Тогда
классов вычетов всего лишь два: 0 и 1. Их сложение
описать легко:
0 + 0 = 0,
1 + 0 = 0 + 1 = 1,
1 + 1=0.
2'
35
Удобней, однако, эти результаты описать таблицей:
Табл. /
Читать ее следует так: допустим, надо найти сумму 0 + 1.
В левом столбце отыскиваем первое слагаемое (т. е. 0),
а в верхней строке — второе (т. е. 1). На пересечении
той строки, где стоит первое слагаемое, и того столбца,
где стоит второе, указана их сумма: 1. Эту таблицу на-
зывают таблицей сложения для Z2.
Пусть п =5 3. Тогда классы таковы: 0. 1 и 2. Соот-
ветствующая им таблица сложения имеет вид:
Табл, 2
Читателю будет полезно проверить и следующие таб-
лицы сложения для я - 7 и для п = 10:
Табл< 3
Таблица сложения в Z1
0 1 2 3 4 5
0	0	1	2	3	4	5
1	1	2	3	4	5	6
2	2	3	4	5	6	0
3	3	4	5	6	0	1
4	4	5	6	0	1	2
5	5	6	0	1	2	3
6	6	0	1	2	3	4
6	0 12 3
6	0	0	1	2	3
0	112	3	4
1	2	2	3	4	5
2	3	3	4	5	6
3	4	4	5	6	7
4	5	5	6	7	8
5	6	6	7	8	9
7	7	8	9	0
8	8	9	0	1
9	9	0	1	2
Табл> 4
Таблица сложения в Zio
4	5	6	7	8	9
4	5	6	7	8	9
5	6	7	8	9	0
6	7	8	9	0	1
7	8	9	0	1	2
8	9	0	1	2	3
9	0	1	2	3	4
0	1	2	3	4	5
1	2	3	4	5	6
2	3	4	5	6	7
3	4	5	6	7	8
36
Итак, сложение классов вычетов в Zn определяется
через сложение представителей этих классов. Аналогично
определяются вычитание и умножение. Вот точные опре-
деления:
Определение 4. Разностью двух классов вычетов
по модулю п—хи у — называется класс х—у. В этом
случае пишут:
х — у = х—у.
Определение 5. Произведением двух классов выче-
тов по модулю п —х и у — называется класс ху. В этом
случае пишут:
xz/ = ху, или х • у = ху.
Читатель, вероятно, уже заметил, что определения 4
и 5, как и определение 3, нуждаются в проверке на кор-
ректность. Доказательство соответствующих равенств —
х'—у' = х—у и х'у'=ху— несложно. Первое из них
мы оставляем в качестве упражнения, а второе устанав-
ливается так. Имеем: х' = х 4- kxn и у' — у + kyn, где kx
и ky — целые числа. Тогда х'у' = ху + п (xky 4- ykx 4- kxkyn).
Поэтому
х'у' = ху mod (n).
Таблицы сложения (см., например, таблицы 1—4)
удобны не только для описания сложения, но и для
описания вычитания. Связано это со следующим простым
наблюдением: если а = b — с, то b = а 4- с. Действи-
тельно, прибавим к обеим частям равенства а = b — с
класс с. Получим:
а + с — (Ь — с) + с.
Очевидно, что b — с = & 4* (—с) (и то, и другое — класс
(& — с) mod (п)). Поэтому (& — с) 4- с = (& 4- (—с)) 4- с.
Но для трех любых классов х, у, г справедлив соче-
тательный закон:
(x+y)+z = х + (у +Z)
(и то, и другое —класс (х + у 4- г) mod (и)). Поэтому
(& 4" (—£)) 4- с = b 4- (—с 4- с) = b 4- 0 = Ъ, так что а 4-
4" с — д.
Следовательно, чтобы по таблице сложения найти
разность а — Ь, достаточно в левом столбце найти вы-
читаемое Ь, затем в этой же строке таблицы найти умень-
37
шаемое а, и тогда разность а — b будет указана вверху
столбца, в котором было найдено а. Так, по таблице 3
легко найти, что 4mod (7) — 6mod (7) = 5mod (7), или, ска-
жем, по таблице 4 4mod(10)—6mod (10) = 8mod(10)
и 6mod (10) — 4mod (10) = 2mod (10).
Что касается умножения в Zn, то и его удобно опи-
сывать таблицами, аналогичными таблицам сложения —
только вместо того, чтобы указывать сумму классов
вычетов, в них мы будем указывать произведение.
Табл, 5
Таблица умножения в Z2		
-	0	1
0	0	0
1	0	1
Табл. 1
Таблица умножения в Z?
0 1 2 3 4 5 6
0000Q000	0
1 0 1 2 3 4 5 6	1
20246135	2
30362514	3
40415263	4
50531642	5
60654321	6
7
8
9
Табл. 6
Таблица умножения в 2з
	0	1	2
0	0	0	0
1	0	1	2
2	, 0	2	1
Табл, 8
Таблица умножения в Zio
0123456789
0000000000
0123456789
0246802468
0369258147
0482604826
0505050505
0628406284
0741852963
0864208642
0987654321
Итак, классы вычетов в Zn можно складывать, вычи-
тать и умножать. Переместительный, сочетательный и рас-
пределительный законы, действующие при сложении
и умножении чисел, переносятся и на классы вычетов.
Доказательство соответствующих равенств мы оставляем
читателю. Множество Zn с введенными выше сложением,
38
вычитанием и умножением является кольцом, которое
принято называть кольцом классов вычетов по модулю п.
Элементы 0 и 1 из Z„ естественно называть нулем и еди*
ницей кольца Zn.
Наконец, обратимся к делению в кольце Z„. Пусть
а = a mod (п) и Ь — b mod (п); говорят, что класс b делит
класс а (и пишут b | а), если существует такой класс
r = cmod(n), что а = Ь • с. Например, при п = 10 (см.
табл. 8) класс 2 делит класс 4, а класс 4 делит класс 6.
Если & | а, то Ь называют также делителем класса а.
В кольце целых чисел Z делителями числа 0 явля-
ются все числа, потому что х • 0 — 0 для любого х, а де-
лит елями числа 1 являются лишь два числа: 1 и —1.
Конечно, и в кольце Z все классы х делят 0, а классы
1 и —1 делят 1. Но, в отличие от кольца Z, здесь при
том или ином п можно установить и несколько специ-
фических, не свойственных кольцу Z качеств.
Так, в кольце Z равенство ху = 0 возможно лишь
тогда, когда, по крайней мере, один из элементов х или у
равен 0. А вот в кольце Zlo имеем: 2-5=0, хотя 2 =# 0
и 5 =/= 0! Далее, в кольце Z делителями числа 1 явля-
ются лишь 1 и —1, а в том же кольце Z10 класс 1
делят сразу четыре элемента: 1,3, 7, 9, потому что 1 =
= 1 -1=3-7 = 7-3 = 9-9. Наконец, в кольце Z можно
смело производить сокращения (т. е. гарантировать, что
из равенства ах — ау и условия а =/= 0 следует равенство
чисел х — у), а в кольце Zn — нет; например, в Z10 из
равенства 2 • 7 = 2 - 2 и условия 2 =£ 0 не следует, что
7 = 2.
Сейчас мы докажем основную в этом плане теорему
о кольцах 1п. Введем два термина:
Класс х кольца Тп называется делителем нуля, если
х 0 и существует такой класс у =/= 0 в Тп, что ху = 0.
Класс х из Ln называется делителем единицы, если
существует такой класс у в Тп, что х - у = 1.
Делители единицы называют также обратимым и
элементами.
Теорема 2. (1) Класс х кольца Тп является делите-
лем единицы тогда и только тогда, когда числа х и п
взаимно просты.
(2) Класс х кольца Z7 явл яется делителем единицы тогда
и только тогда, когда он не является делителем нуля.
Следует отметить, что наибольший общий делитель
чисел х и п не зависит от выбора представителя в клас-
39
се х. Действительно, если x'^xmod(ra), то x' — x-l-kn
и каждый (в частности, наибольший) общий делитель х
и п является общим делителем для х' и п. Поэтому
(х, га)|(х', п) и, конечно, наоборот: (х', га) | (х, га). Таким
образом, формулировка теоремы 2 в части (1) корректна.
Доказательство. (1) Пусть х и га взаимно просты.
Согласно теореме 3, главы I, это означает, что xs 4- nt =
= 1 при некоторых s и t из Z. Но тогда, переходя
к вычетам по модулю га, мы получаем:
xs 4- nt = 1
или
(as) mod (га) + (nt) mod п = 1 mod (га),
т. е. xs = 1, поскольку nt = Ot = 0 и х — обратим в Z„.
Обратно, пусть xs — 1 в Zn при некотором классе $.
Тогда xs — 1 = 0 mod (га), т. е. xs — 1 = k • га и, следова-
тельно, х и га взаимно просты.
(2) Пусть х не является делителем нуля. Рассмотрим
наибольший общий делитель d чисел х и га. Пусть
d = xs + nt
при некоторых целых $ и I и п = d • п'. Если d = 1, то
из доказанного выше, х обратим в Zn. Если же d =# 1,
то п’ =# 0, и, кроме того, для х = х' -d
хп' = x'd-n' = х' п =0	(1)
и х—делитель нуля в противоречии с предположени-
ем. Следовательно, d = 1 и х обратим в Zn.
Обратно, пусть х обратим в Zra, т. е. ху = 1 при
некотором у из Z„. Если бы xz = 0 при z ¥= 0, то из
последнего равенства следовало бы, что yxz = уО = 0,
т. е. (ух) z = 0 или I . z — 0, но z =/= 0 по предположе-
нию. Теорема доказана.
Следствие 1. Класс х из Тп, х =/= 0 является дели-
телем нуля тогда и только тогда, когда числа х и п не
взаимно просты.
Следствие 2. В кольце 1Р, где р — простое число,
нет делителей нуля.
Действительно, каждое из чисел 1, 2, ..., р — 1 вза-
имно просто с р, если р — простое; поэтому классы 1,
2, ..., р — 1 обратимы в 1Р.
В заключение этого параграфа мы приведем еще две
теоремы, посвященные «необычным» фактам конечной
арифметики.
40
Теорема 3. Если р — простое число и а = a mod (,о)
b = b mod (р), то (а + Ь)р = ар + Ьр.
Доказательство. Напомним прежде всего, что
для любых чисел х и у бином (х + у}р раскладывается
по следующей формуле Ньютона:
(х + у}р = хр + СрХр~'у + •.. + CkpxP-kyk +
+ ...+Срр~'хур-' +ур,
где
Ck - Р(Р~1) •••(Р-^+1) a_i о п-1
Биномиальный коэффициент Ср при любом k делится
на р, потому что р, будучи простым, взаимно просто
с каждым из чисел 1, 2, ..., k при k < р. Следовательно,
разность (х-+ у)р — хр — ур представляется в виде суммы
чисел, каждое из которых делится на р; поэтому (х +
+ у)р = (хр + z/c) mod (р), откуда при х = а и у = Ь полу-
чается требуемое:
(а + Ь)р = ар + Ьр.
Не менее интересным является следующий факт, но-
сящий название «малой теоремы Ферма»:
Теорема 4. Если р — простое число и х => х mod (р),
то хр = х.
Доказательство. Если х — 0, то утверждение
очевидно. Пусть х #= 0. Это означает, что число х не
делится на р, а так как р — простое, то числа х и р
взаимно просты. Следовательно, классы х, 2х, ..
(р — \)х — попарно различны: равенство lx = kx озна-
чало бы, что I — k (по теореме 2 этой главы элемент х
обратим, и если ху — 1, то, умножив обе части равенства
lx — kx на у, мы получим, что I = к), а это невозможно,
если 0 < I, k < р и I =f=k. Таким образом, х, 2х, ...,
(р — 1) х —это в каком-то порядке переставленные классы
1, 2, ..., р — 1, а потому произведение л:.2л:-...Х
х (Р — О х равно 1 • 2 ... (р — 1), т. е. 1 . 2 ... (р — 1) X
X хр~{ = 1 .2 ... (р — 1). Следовательно, если последнее
равенство сократить на 1 • 2 ... • (р — 1), то получится
хр~'=1, .или после домножения на х имеем хр = х.
Теорема доказана.
Множество ненулевых классов вычетов 1, 2.р — 1
по простому модулю р обладает многими интересными
з 6-364
41
свойствами. Одно из них состоит в следующем: среди
этих классов всегда есть такой класс а, что любой дру-
гой класс является некоторой его степенью, т. е. для
любого другого класса х существует такое натуральное
/, что а* = х.
Упражнения
1.	По таблице 7 найти для каждого х из Z7 обратный класс
(т. е. такой у, что ху — 1).
2.	Доказать, что если класс х кольца Zn обратим, то существует
ровно один класс у, для которого ху = 1 (предположив противное,
т. е. существование равенства 1 = хуг = ху2, надо последнее из них
домножить на yj или на у г).
3.	Доказать, что на элемент а =£ 0 кольца Zn можно сокращать
(т. е. гарантировать, что из ах = ау следует х = у), тогда и только
тогда, когда а является делителем единицы.
Указание. Достаточность этого условия почти очевидна,
а необходимость следует установить от противного: если а не явля-
ется делителем единицы, то аЬ = 0 при некотором b =/= 0 из Zn\
после этого нужно представить b в виде х—у при некоторых х^у
из Zn и рассмотреть равенство а(х—у) = 0.
4.	Составить таблицы сложения и умножения для Z8 и найти
в этом кольце все делители нуля и все делители единицы.
5.	Пусть N — произвольное натуральное число и г — число, рав-
ное количеству взаимно простых с N чисел ряда 1,2, . . ., N — 1.
Доказать, что для любого целого числа а, взаимно простого с
в кольце Zn имеет место равенство: ar = 1 (теорема Эйлера).
$ 3. ДИОФАНТОВЫ УРАВНЕНИЯ И ВЫЧЕТЫ
Теперь мы уже можем приступить к исследованию
диофантовых уравнений более общего типа, чем рассмат-
ривались в главе I.
Сначала введем понятие целочисленного полинома от
п переменных. Будем говорить, что х19 х2, ..хп— неза-
висимые переменные, если каждая из них принимает
целочисленные значения независимо от всех остальных.
Мономом от переменных xlt х2, ..хп называется
всякое выражение вида
ахТ'хТ ... х”п,	(1)
где ml9 т2, .. гпп-— целые неотрицательные числа, а а —
произвольное целое число, называемое коэффициен-
42
том монома. Если вместо каждой из букв xif хг, ..
хп подставить в моном конкретные числа, например xt =
= ai, Х2 = ai, ..хп = ап, то моном обратится в опре-
деленное целое число а • аТ'аТ1 ... а™п.
Два монома от одних и тех же переменных ах™'хг*...
.. .х™п и &Х1*Х2г •••**" можно «умножать» и снова полу-
чать моном по следующему правилу:
{ах^хТ .. . х^") (&хМ‘ ... х*")
= abxt1+k,xT‘+k! ... х^+Ч	(2)
Конечно, равенство (2) остается верным, если вместо хц
.......хп подставить конкретные числовые значения.
Условимся и о том, как «складывать» мономы: под
суммой двух мономов ах^'х1!2 ... х™п и ftxf'x** ... хкп мы
будем подразумевать выражение
ахГ* • Х2г... х™п + Ьхк'хкг ... хкпп,
которое при конкретных целочисленных значениях Xi,
Х2, • • •> хп, скажем, Xi = Хг = а2......хп — ап, прини-
мает целочисленное значение adi'a™ ......" + baklakt...
... акп. После этого нетрудно определить сумму любого
конечного числа мономов от переменных х\, х2, ..., х„.
Определение 6. Целочисленным полиномом от пе-
ременных xi, хг, ..., хп называется любая сумма конечного
числа мономов от переменных х>, Хг, ..., хп. Коэффици-
енты мономов-слагаемых называются коэффициентами
полинома. Полином от п переменных мы будем обозначать
через f(xit х2, ..., х„).
Так, например, f(xi, Хг) = Xi + Хг — полином от двух
переменных; его коэффициенты равны единице; для по-
линома ^(хь хг) — xi 4- 2х]Хг + xi характерно, конечно,
то, что все его значения (т. е. числа, получающиеся при
замене xi и х2 на конкретные целые числа) являются
квадратами — ведь
g(xb х2) = (xi 4-х2)2.
Само собой разумеется, что многократное повторение
слова «целочисленный» во всей проведенной конструкции
обусловлено конкретностью наших целей: мы построили
полином от п переменных хь ............ который при
3*
43
целочисленных значениях последних принимает целочис-
ленные значения. Но можно было говорить и о веществен-
ных или о комплексных полиномах от п переменных, толь-
ко коэффициенты мономов следовало бы тогда брать ве-
щественными или, соответственно, комплексными и, ана-
логично, — значения переменных Xi, х2,..., хп. Более того,
можно построить (и это нам понадобится) полином от п
переменных хь х2, ..., хп, коэффициенты которого явля-
ются классами вычетов по фиксированному модулю т
и чьи переменные принимают значения из ZOT. Такой
полином мы будем называть (в отличие от целочисленного
полинома) полиномом над кольцом классов вычетов по
модулю т.
Рассмотрим связь между целочисленными полиномами
и полиномами над кольцом классов вычетов. Пусть f(xi,
х2, . •хп)—целочисленный полином от п переменных
и т — целое положительное число. Придадим переменным
Xi, х2, ..хп какие-нибудь числовые значения, например
xi = ai, х2 — 02, ..хп — ап, тогда полином обратится
в число f(oi, 02, .... оп). Обозначим теперь через f(xi,
х2, ..., хп) полином над кольцом классов вычетов по
модулю т, который получается из /(xj, х2, ..хп) заме-
ной коэффициентов на их классы вычетов по модулю т.
Тогда, как следует из § 2,
f(ai, а2, ..., ап) = }(сц, 02, ..ап),
где f (01, ..оп) =/(аь о2, .... an)mod(/n) и oz =
= azmod(m) (i = 1, 2, ..., п). Мы будем называть поли-
ном /(xi, х2, ..., хп) редукцией полинома f(xi,
х2, ..., хп), по модулю т.
Например, если /п = 9, п = 2 и f(xi, х2) = 15xi 4-
+ 9xi2x2 +8х]Х2 + 11x2, то
/ (Х|, х2) = 6xi 4- 0xix2 ~Т 8xix2 4“ 2х2 — 6xi 4- 8xix2 4“ 2х2.
Определение 7. Диофантовым уравнением от п
неизвестных называется уравнение вида
f(xit х2, ..., хп) = О,	(3)
где /(xi, х2, ..., хп) — целочисленный полином от п пере-
менных и xi, х2, ..., хп принимают только целые значения.
44
Отметим, что если х\ — а\, г2 = хп = ап—ре-
шение диофантова уравнения (3), т. е. f(a\,	ал) =
= 0, то
/(fli, а2, .. м ап) = б	(4)
для редукции по любому модулю т. Следовательно, если
при каком-либо т равенство (4) не выполняется для
всевозможных вычетов а\,	по модулю /и, то
уравнение (3) решений не имеет. Иными словами, спра-
ведлива теорема:
Теорема 5. Необходимым условием существования
решения уравнения (3) является выполнимость равенств (4)
при всех модулях т и каких-либо вычетах at = mod (/и),
/ = 1, 2, п.
Примеры 1. Найти все решения диофантова уравнения
х2 + 21 ху + 1 Ау2 — 3 = 0.
Редукция по модулю 7 этого уравнения выглядит так:
х2 = 3.
Но среди классов вычетов б, Т, 2, 3, 4, 5, 6 по модулю 7 квадратами
являются лишь классы 0, 1, 2, 4 — это проверяется непосредственно
О2 = б, I2 = Т, 22 = 4, З2 = 2, 42 = 2, 52 = 4 и 62 = Г; поэтому ра-
венство х2 = 3 никогда не выполняется и заданное уравнение не име-
ет решений.
2. Найти все решения диофантова уравнения:
15х2 _ 7г/2 = 9.
Пусть х = т, у = п — решение. Из рассмотрения делимости на 3
и на 9 следует, что т2 и п2 делятся на 9; при этом частным от де-
ления будут тоже квадраты, что легко получается из основной тео-
ремы арифметики. Итак, т2 = 9/л2 и п2 = 9 л2. Данное уравнение
приводится теперь к виду:
15/nf —	= 1.
а редукция по модулю 5 дает
—2л2 = Т.
Учитывая, что —22 = —4 = I, получаем
п2 =2.
Но среди вычетов по модулю 5 квадратами являются лишь 0, Г и 4.
Поэтому данное уравнение не имеет решений.
Естественно задать следующий вопрос: является ли
условие разрешимости редукций данного диофантова
45
уравнения по всевозможным модулям достаточным для
того, чтобы само диофантово уравнение имело решение?
В общем случае ответ на этот вопрос отрицательный.
Можно показать, что, например, диофантово уравнение
(х2 - 13) (х2 —17) (х2 — 221) = О,
не имеющее, очевидно, решений (ведь ни 13, ни 17, ни
221 не являются квадратами в кольце Z) при редукции
по любому модулю т приобретает решение среди соот-
ветствующих классов вычетов. Наших сведений, однако,
для этой цели сейчас недостаточно: необходимо подробное
описание подмножества квадраюв в кольце классов вы-
четов по модулю т. Вот как его получить, по крайней
мере, при простых т.
Пусть р — простое число, отличное от 2 (следовательно, — не»
четное), ——,...,—1,0,1,...,^—~все элементы из Zp.
Если каждый из них возвести в квадрат, то получится не больше
Р — 1
—2— различных ненулевых элементов: ведь все они содержатся во
множестве
1 = (-1)2.
22= (—2)2,
/р — 1V _ f_ р —
\ 2 /	\	2 ) *
/о—1\2
Кроме того, все квадраты I2, 22.....—I попарно различны:
если бы а2 = р2, то обязательно (а — Р) (а + Р) = 0, и либо (ведь
в Zp нет делителей нуля) а = р, либо а = —Р; первое невозможно,
так как по условию аир различны, второе исключено, так как а
и р различные элементы множества 1, 2, ...»	. Следовательно,
в Zp ровно —~ ненулевых квадратов.
Когда среди этих элементов находится —1? По малой теореме
Ферма = 1 для всех а =£ 0 из Zp- Если а— квадрат, т. е.
р—1	р—1	р-»1
а — Ь2 при некотором Ь, то а 2 = (b2) 2 =	Вообще, х 2
равно 1 или —1 в зависимости от того, является ли х квадратом
или нет. Действительно, если х — квадрат, то, как мы уже видели,
р—1
это так; если же х не является квадратом, то х 2 но уже
46
г8=1, или r2 —1 = 0. Последнее, в силу соотношения г2—1 =
=(г -—!)(/'+ 1) и отсутствия в Zp делителей нуля, возможно лишь
р—1
при г = 1 или / = —1. Если бы г = 1, то полином г 2 — I над Zp
р ____________________________________ 1
обращался бы в нуль более, чем при^—значениях г. Это, однако,
невозможно по следующей причине:
Пусть / (г) =	. + ап — произвольный полином над Zp
и f (с) = 0 при некотором с из Zp; тогда обязательно f (z) = (z
— с) g (z) при некотором полиноме g(z) над Zp. Действительно, про-
ведем индукцию по числу /г, называемому степенью полинома
f(x). При п— 1 полином f (z) имеет вид а0?+ ах и, так как f(c) =
= 0, т. е. аос + аг = 0, обязательно f (z) — aoz — aGc. Следовательно,
f(z) — (z— с) a0. Предположим, что утверждение доказано для всех
степеней, меньших п. Полином gi (z) — f (z) — (z — с) имеет
степень меньшую, чем п и, очевидно, обращается в нуль при z — с.
Поэтому по предположению индукции, gi (z) = (г — с) g2 (z) и, следо-
вательно, f (г) = g, (г) + аог"_1 (г — с) = (г — с) (aoz"-1 + g2 (z)). Ут-
верждение доказано. Из него вытекает, что если .,, ck — разные
элементы из Zp, для которых f (ci) = .. . — f (rfe) = 0, то f (z) =
=(z—Ci). . .(z—ck)g(z). Надо рассуждать так же, как выше, выделяя
сначала в f (z) множитель г — сг (получается f (z) = (z — cj gi (z)
и, следовательно, gi (c2) = 0), затем г — c2 в gi(z) и т.д. Так как
степени полиномов при умножении складываются, то в выражении
f (г) = (г — Ci) • .. (z — ck) g (z) справа не может быть больше множи-
телей вида (Z“CZ), чем степень полинома f (z). Вот почему полином
2Р—1 — 1, упомянутый в предыдущем абзаце, не может иметь более,
р 1	_
чем —2~" значений z, для которых его значение равно 0.
р—1
Следовательно, х 2 = —1. Отсюда принципиально важный вы-
вод: элемент х из Zp является квадратом тогда и только тогда,
р—1
когда х 2 = 1 и не является квадратом тогда и только тогда, когда
р—1	р—1
х 2 = —1. Таким образом, —1 является квадратом, когда (—1) 2 =
р—1
= 1, и не является квадратом, когда (—1) 2 =—-1. Число р == не-
четное; следовательно, либо р = 4k + 1, либо р — 4k— 1. В первом
р-1
случае обязательно (—1) 2 = (-—I)2* = 1 и (—1) — квадрат; во вто-
р—1
ром случае обязательно (—1) 2 = (—l)2fe—1 = —1 и —1 не явля-
ется квадратом. И еще одно утверждение: если х и у из Zp не яв-
ляются квадратами, то обязательно ху — квадрат (докажите это
самостоятельно).
В диофантовом уравнении (х2 — 13) (х2 — 17) (х2 — 221) = 0 заме-
чаем, что 221 = 13 • 17; следовательно, в редукции по простому
47
модулю это уравнение имеет решение (хотя один из классов 13, 17
или 13 • 17 — квадрат).
Теперь можно доказать утверждение, сформулированное еще
в гл. II: всякое простое число р вида р = 4&+ 1, где & —целое,
является нормой целого гауссового числа (и, следовательно, предста-
вимо в виде суммы двух целых квадратов): р = х2+г/2. Доказа-
тельство проведем индукцией по р. При р = 5 (это самое маленькое
р вида 4k + 1) утверждение очевидно: 5=22+ I2. Допустим, что
утверждение доказано для всех простых чисел вида 4 k + 1, меньших
простого числа р такого же вида: р = 4k + 1. В кольце Zp класс
— 1 является квадратом (это было доказано выше), т. е. х2+1 = 0
при некотором х из Zp. Это означает, что в кольце целых чисел Z
х2 ф у2 = /р, где х и у — целые числа и где класс вычетов числа
у — это класс 1. Поскольку все квадраты в Zp получаются из серии
j\2
I , можно считать, что 0 < xty < и, следо-
О2, I2, 22,
вательно, I < р. Конечно, будем считать, что х и # —взаимно прос-
тые целые числа (в противном случае мы сократили бы равенство
д'2 у2 = 1р на их общие делители).
Пусть 1 = pi • р2 ... рг — разложение числа I на простые мно-
жители в кольце Z. Так как (х, у) = 1 и х2-\-у2 делится на ру
(/ = 1,2, . . ., г), класс — Imod р. является квадратом в Zp? то Ру =
= 4/Пу + 1 при некотором целом tri] (j = 1, 2, .. г). Поскольку
Ру < р, то по предположению индукции
₽/=*/ + Vj = (•*•/ + ^/) (*/ — iyl) =	.
где №—простые множители в кольце целых гауссовых чисел/
и, как обычно, а-\-Ы = а— Ы — сопряженное число.
Следовательно,
(*+ iy) (х — iy) = pf(1) . ..	.
В правой части равенства имеем произведение простых гауссовых
чисел. Пользуясь справедливостью основной теоремы арифметики'
в кольце целых гауссовых чисел, сократим правую и левую части
последнего равенства на простые числа	. ..	в ре-
зультате получим представление простого целого числа р в виде
произведения сопряженных гауссовых чисел. Теорема доказана.
Изучение уравнений над кольцами классов вычетов
имеет важное значение в теории чисел именно потому,
что позволяет во многих случаях «предугадать» исход
решения той или иной диофантовой задачи.
Мы закончим эту главу примером изучения редукций
одного частного диофантова уравнения:
f (х, у) = ах2 + 2Ьху + су2 = 0.
Условимся символом fp (х, у) обозначать редукцию поли-
нома /(х, у) по модулю р.
48
Теорема 6. Пусть р^2 — простое число. Уравнение
fy {х, £) = О
имеет решение, отличное от х = у = б — Omod (р), тогда
и только тогда, когда Ь2 —а • с = (Ь2 — ас) mod (р) явля-
ется квадратом в кольце Zp.
Доказательство. Пусть & — ас — г2 и допустим,
что а Ф б. Поскольку среди ненулевых классов вычетов
по простому модулю возможно деление, то в результате
алгебраических преобразований можно получить следую-
щее равенство:
ах2 4- ~2Ьху + су2 = а\х —	*р)|х — р)
\ а / \ а /
(в его справедливости можно убедиться непосредственно,
на основании определения действий над мономами). Сле-
довательно, достаточно найти решение уравнения:
/ г — b \!	& + z \ п
х----=г-р х + -^-р = 0.
\ ° / \ а /
Эти решения, ввиду отсутствия делителей пуля в кольце
классов вычетов по простому модулю, описываются двумя
независимыми равенствами:
—Ь + г	—b — г
X =--у и х = —— у.
а	а
Если а = б, а с =# б, то все сказанное выше легко
переносится и на этот случай. Если же а = с = б, то
ненулевым решением данного уравнения будет, например,
х= 1, р = б.
Обратно, пусть х = х,_у =_у — решение, причем либо
х #= 0, либо р #= б. Если а = с = б, то утверждение оче-
видно: Ь2 является квадратом. Пусть а =# б. Тогда
0 — ах2 4- 2Ьху 4- су2 — а2 (х2 4- ху 4- 4- у2
\ а а
(/	—	\2	—	_ \
- , Ь Ь2— ас-Л
x + -=rd-----—у2 .
\ а / a2 J
Следовательно,
t & “V &2 — ас -»
а2
49
Так как а =£ б, то класс у отличен от б; если бы у = О,
то и х — 0, а это противоречит условию. Следовательно,
— /	_	\ 2
Z2 ~ ~ a2 I- . b ~\
Ъ* — а.с~ — x +
У2 \ а /
а
.У
- , b -
х + — у
Теорема доказана.
В условии предполагалось, что р Ф 2. Однако это
было сделано не потому, что при р — 2 теорема не верна:
в этом случае ее утверждение тривиально, потому что!
редукция /2 (х, у) равна ах2 4- су2, а оба класса вычетов
по модулю 2 являются квадратами и в то же время урав-
нение ах2 +су2 = б обязательно обладает решениями —’
это устанавливается просто перебором всевозможных?
значений полинома /2 (х, У)-
Глава IV
СИСТЕМЫ СЧИСЛЕНИЯ
При записи чисел мы обычно пользуемся десятью^
символами: 0, 1, 2, 3, 4, 5, б, 7, 8, 9. Их называю-
десятичными цифрами. В этой главе мы рассмотрим роль
числа 10 в традиционной записи чисел и опишем воз-
можные способы замены «десятки» на другие натураль-
ные числа. Особенно важной в наше время стала такая
форма записи, в которой роль десятки играет двойка:
в электронных вычислительных машинах применяют н<
десятичную, а так называемую двоичную систем;
записи.
§ 1. ДЕСЯТИЧНАЯ СИСТЕМА СЧИСЛЕНИЯ
Под десятичной системой счисления понимают bci
систему чисел, записанных в обычной форме с помошы
десятичных цифр — символов 0, 1,2, . .., 9, каждый и:
которых обозначает и некоторое целое
неотрицательное
число. Подобные системы записи чисел называются «по-
зиционными»— в них цифра означаег различные числа
в зависимости от того, какое место она занимает в записи.:
Конечно, вместо этих десяти символов можно было бы
взять и другие, но если бы этих других было снова десять?
и употреблялись они аналогично традиционным цифрам,
50
то систему чисел все равно следовало бы назвать деся-
тичной.
В чем же состоит роль числа десять? Дело в том,
что мы записываем числа с помощью всевозможных
остатков от деления на 10; именно как остатки от деле-
ния на 10 ведут себя десятичные цифры во всех ариф-
метических операциях над числами. Действительно, рас-
шифруем десятичную запись числа:
Пусть сначала N — натуральное число. Из алгоритма
деления с остатком следует, что N — 1О</о + го» где
О<го<9 и 0 < ?о < N (если, например, N = 6, то qo — 0
и го = 6). Если частное qo > 0, то точно так же qo =
= 1 Oft -f- г2, где 0 < г\ < 9 и
N = 1О<7о + г0 = 1 02<7i + 1 On + г0.
Если qi > 0, то этот процесс можно продолжить, получив
N = 103<72 + Ю2г2 + 1 On + г0.
Частное </2 будет меньше, чем qi, a q\—меньше, чем
qo, которое меньше, чем N. Поэтому после конечного
числа шагов п мы получим, что qn = 0 и
N = 10"г„ +	+ ... + Юн + го, (1)
где го. • • •, гп — неотрицательные целые числа, не пре-
восходящие 9. Запись (1), полученная вполне конкрет-
ным образом по числу N, называется десятичным пред-
ставлением (или десятичным разложением) числа N.
Следует заметить, что если бы существовало второе
выражение
= Ю"'4 +	... + 10п' + го, (1')
полученное каким-то иным способом, и в котором
Гп', ...» го — неотрицательные целые числа, не превосхо-
дящие 9, то оказалось бы, что п = п и г\ = г( для i =
= 1,2, ..., га. Действительно, остаток от деления на 10
числа N определен однозначно и, как следует из пред-
ставлений (1) и (Г), равен г0 и г'о. Поэтому го = г'о. Ра-
венство чисел г\ и Г1 получается из единственности остат-
ка от деления на 10 числа Предоставляем чита-
телю самостоятельно завершить доказательство.
Если принять, что символ anOn-i ... гао обозначает
записанные подряд десятичные цифры an, ап-\, ..., а0
51
то, конечно, число N, записанное десятичными цифрами,
имеет вид:
связано немало интересных
них:
между числом и суммой егс
имеем число N, представлен-
N = ГпГЛ-\ ... Го-
С представлением (1)
фактов. Вот некоторые из
Теорема 1. Разность
цифр делится на 9.
Доказательство. Пусть
ное в виде (1). Тогда
N — (г о + ... +/•«)= Юягл +	+ ... + 10п +
+ го — Гп — Гп-1 — ... —Г1 — г0 =
— (10я —1) гя 4-(10я-1 — 1)гл_1 + ... 4- (ГО- 1)П.
Но 10 mod (9) = Imod (9), так что и 10я mod (9) = Imod (9).
благодаря чему N mod (9) = (гп + ... + го) mod (9) и,
следовательно, У — (гп + . • • 4- го) s Omod (9). Утверж-
дение доказано.
Следствие. Если сумма цифр числа N делится на 9,
то и само число делится на 9.
Обратно, если число делится на 9, то кратна девяти
и сумма его цифр.
Действительно, если М — сумма цифр числа N, де-
лящаяся на 9, то из y = Almod(9) следует, что N =
0mod(9). Аналогично, если N = Omod(9), то из
= М mod (9) следует, что и А1 =0 mod (9).
Точно так же формулируется и доказывается признак
делимости на 3.
Теорема 2. Если разность между суммой цифр
числа N, стоящих на четных местах, и суммой цифр
этого же числа, стоящих на нечетных местах, делится
на 11, то и число N делится на 11. Верно и обратное:
если число N кратно 11, то разность между суммами
указанных цифр делится на 11.
Доказательство. Заметим, что 102fe == 1 mod (11) и
102t+i = ю mod (11). Поэтому, переходя от выражения
(1) к вычетам по модулю 11, получаем:
А/ == z*q 4” lO/ij 4“ г2 4- Югз • • • mod (11),
откуда
N s (гр 4* г2 4- • • •) 4* Ю (Г1 4* Гз 4* ..Omod (11).
Если (г0 4- г2 4- ...) = (Г1 4- гз 4- .. •) mod (11), то, конечно
N = (fi -+• гз 4" • • •) 4“ ГО (/"1 4~ гз 4- • • •) mod (11) =
^Omod (11).
52
Обратно, если М = Omod (11), то, учитывая сравнение
10 s—Imod(ll), получаем:
(го 4- г 2 + ...) 4* Ю (п + гз + .. Omod (11)
и
(го + г2+ • • •) — (И 4* 4" •. •) = Omod (11).
Как видим, при десятичной записи натурального
числа цифры стоят в совершенно строгом порядке как
остатки от деления на 10. Любое целое число записы-
вается точно так же, только перед записью отрицатель-
ного числа ставится знак минус.
Перейдем к числам рациональным — несократимым
дробям вида R — где для начала будем считать N
и М натуральными числами, а потом рассмотрим и от-
рицательные рациональные числа. Наша ближайшая цель
получить для такого числа разложение вида (1), совпа-
дающее с ним при М = 1.
Будем считать, что дробь R =	— правильная, т. е.
N <Л4. В противном случае мы могли бы выделить
целую часть, десятичное представление которой уже
описано, и после этого рассматривать правильную дробь.
Пусть 107V = qiM 4- а\, где 0 < а\ < М. Тогда 0 < q\<
< 9, потому что ЮМ < ЮМ и
Р — — — 1(W = qiM + 01 = Ю-’о. -4- Ю-1
* — м ЮМ юм 1U + 'и М"
Если at — 0, то десятичное представление для R выгля-
дит так:
R =10-41.	(2)
Если ai =h 0, то, аналогично,
^ = 10-42 4-10-^,
где опять 0 < <?2 < 9 и 0 < а2 < М. При а2 = 0 десятич-
ное представление для R имеет вид
R = 10-^1 4- 10-2?2.
Если а2 =h 0, то
|=10-4з4-Ю->|,
где 0 < q2 < 9 и 0 < а2 < М и т. д.
53
Возможны два случая: либо на одном из шагов оста-
ток обратится в 0, и мы получим конечную десятичную
дробь
R - 0, 9_^_2	= <7-1Ю-1 + <7_210-2 + ... +	.
+?-Л-‘	(3)
либо ak никогда не обратится в 0. Но так как остатков
от деления на число М всего лишь М, остатки ak (а
следовательно, частные qk) начнут повторяться: мы полу-
чим бесконечную периодическую десятичную дробь:
R =	+ 10-2(7-2 + ... + 10-*<7_* + ...
Остановимся на этом случае несколько подробнее,
чтобы установить длину периода. Пусть таблица вычис-
ления остатков имеет вид:
Юоо = Mqi + ai,
10ai = Mq2 -f- Й2,
10ай_2 = M<7ft-i + ak-\,	(4)
lOafe-i = Mqk + «о-
Здесь для простоты нумерация букв сразу выбрана та-
кой, чтобы первая цифра периода (т. е. некоторое част-
ное qb полученное в описанном выше процессе) имела
номер 1; в последней строке таблицы вновь во второй
раз появляется остаток «о» с которого было начато
перечисление в (4). Напоминаем, что остатки а0> ал, .. .,
а*_1 все отличны от 0, чего, конечно, нельзя сказать о
цифрах qt. Схематически соответствующий кусок десятич-
ной дроби выглядит так:
0, ... <71^2 ... 4k—iqk • • •
После того как мы запишем цифру qk, следующей вы-
численной цифрой будет вновь qc, следовательно, период
дроби начинается с цифры q\ и заканчивается на qk-
Всего таких цифр k. Рассмотрим (4) по модулю М:
1Ойо = ль
lOai =а2,
l0ak-2^ak-i	(5)
Юс*-1 == а0;
54
\
подставляя ai из первого сравнения во второе, затем а2
из второго в третье и т. д., получим:
1О*со «о-
Возможны два случая: (10, А4) = 1 и (10, А1)=#1.
В первом случае в равенстве 10N = Mq-{-a, где 0<
< а < М, числа а и М взаимно простые, потому что
любой их общий делитель, будучи взаимно простым с 10,
должен делить и N, a (N, М) = 1 по условию. Следо-
вательно, при (10, М) = 1 все остатки at взаимно просты
с М и, в частности, (ао, М) — 1. Это означает, что класе
ао mod (М) обратим, а потому
10* = Imod (Al).
Число k, для которого 10* = Imod (Al), является наи-
меньшим среди натуральных чисел п, для которых 10" ss
s imod (Al). Действительно, если бы 10" = Imod (А4) при
п < k, то из сравнений (5) следовало бы, что
ап = 1О"со -- ао mod (Al).
Но ап и Со — остатки от деления на М, поэтому сравне-
ние ап = ао mod (Al) означает равенство Сп = «о> а это
противоречит тому, что все остатки а0, at, ..., a*_i по-
парно различны (на этом были основаны равенства (4)).
Рассмотрим случай (10, М) #= 1. Пусть M=2r5sM',
где уже (10, М') = 1. Тогда R =	, домножим
числитель и знаменатель дроби R на такие степени двой-
ки и пятерки, чтобы знаменатель принял вид 10'АГ (на-
пример, рр = 22^77 = "10* . 7 = ПолУчим: # =
~ 10_/	, где (АГ, АГ) = 1 и (АГ, 10) = 1. По докааан-
ному период дроби ° равен тому наименьшему
натуральному числу k, для которого 10* == Imod (Al').
Но период дроби R = 10-' . R' таков же, он лишь на-
чинается на I знаков правее.
Мы доказали такую теорему:
Теорема 3. Пусть R — u М. = 2Г55А4', где (N,
Al) = 1 и (10, АГ) — 1. Тогда период дроби равен тому
наименьшему натуральному k, при котором
10* = Imod (АГ).
55
Прежде чем описать восстановление десятичных цифр
рациональных дробей, основанное, как и в случае на-
туральных чисел, на десятичном разложении
/? = г_1 • 10-1 + ... + г_„ • 10-« + ...,	(6)
где 0 < r_i < 9, отметим следующее обстоятельство, бла-
годаря которому будет введена однозначность представ-
ления (6):
10-s = 9 • 10-s-‘ 4- 9 • 10-s-2 4- ... + 9 • 10-s-° + ...
(т. e. О, 0 ... О 1 = 0, 0 ... О 9 9 ... 9...).
Доказательство. В соответствии с правилом сум-
мирования бесконечно убывающей геометрической про-
грессии имеем
9 . 1 o~s—1 + 9 • 10-s-2 + ... = 9 • 10~s (10-1 +
Ю"-*1
+ io-2 +...) = 9 • io-s • —----г = 10~s.
’	i — io-1
Поэтому естественно предположить, что всюду вместо
«девятки в периоде» можно писать единицу в предшест-
вующем периоду разряде, т. е.
О, г_1 ... г-к 9 9 ... — 0, г_1 ... г-k + 0, 0 ... О 1.
к
Восстановление десятичных знаков дроби R можно
теперь описать так.
Пусть
R = г-i • 10-1 + г-2 • 10-2 + ... + r-k • 10~* + ...
Тогда г—1—это целая часть числа 10/?, г—2 — целая
часть числа 10(10/?—r_i) и т. д. r—k— целая часть
числа
10*/? - 10-*-^-! — ... — 10г_*+1.
Рассмотрим на примерах полученный результат. Пусть
/? = -j. Длина периода I этой дроби в десятичном пред-
ставлении равна наименьшему из таких чисел k, что
10* = lmod(3). Очевидно, 1 = 1. Сам период легко опре-
деляется: /? = 0, 6 6 6 ....
А вот пример дроби с большей длиной периода в де-
сятичном представлении: /?/ = у. Здесь отыскать наи-
меньшее число I, для которого itfsl mod (г) лучше всего
так. Символ mod (7) в записях будем для удобства
56
опускать. В кольце Z? имеем: 10 = 3. Поэтому 10’s3"
и, следовательно,
3‘s3,
32 = 2,
З3 = 3.2 = 6,
З4 = 3 • 6 - 4,
З5 = 3.4 = 5,
36 = 3.5=1.
Таким образом, длина периода I равна 6.
У пражнения
1. Найти длину периода дроби 7? = 2- в десятичном представ-
лении.
Ответ. Длина периода равна 22.
2. Доказать, что существуют десятичные дроби с как угодие
большой длиной периода.
Указание. Пусть N — произвольное натуральное число. За-
пишем десятичную дробь R за несколько шагов по следующему
правилу: 1-й шаг — 0,10, 2-й шаг — 0,101100, 3-й шаг —
0,101100111000, ... и т. д. до тех пор, пока число цифр в дроб-
ной части не превзойдет W. После этого припишем к полученной
дроби ее дробную часть еще и еще раз, и т. д. Полученная беско-
нечная дробь будет, конечно, периодической. Остается лишь дока-
зать, что ее период равен переписываемой части.
Подводя итог, можно сказать, что любое рациональ-
ное число записывается либо в виде конечной, либо в
виде бесконечной, но обязательно периодической деся-
тичной дроби (целая часть которой может быть равна 0
или отлична от 0). Разумеется, верно и обратное: всякая
конечная десятичная или бесконечная, но периодическая
десятичная дробь есть рациональное число. Для конечной
дроби это утверждение просто очевидно, а для периоди-
ческой доказывается так. Данную периодическую дробь
можно представить в виде суммы конечной десятичной
дроби и дроби вида:
р = о, 0 ... 0 <71 ... ^„<71 ... д7,
где д\ ... дп — период. Как уже говорилось, первое сла-
гаемое (т. е. конечная дробь) — число рациональное; что
57
г.
касается второго, то, положив q\ ... qn = q, представим
его в виде:
р = q • 10-"-s 4- q . 10~2"-* + q . 10-3""s + • • • =
= q . 10-s (10-n + IO-2" + 10~3” + .. .).
Согласно правилу суммирования бесконечно убывающей
геометрической прогрессии, имеем
10-” + 10-2” 4-.. . = 10~— = ——.
1 — Ю-" ю" —1
Таким образом, р — рациональное число, а потому рацио-
нальна и данная дробь.
Обратимся, наконец, к иррациональным числам, под
которыми принято подразумевать бесконечные неперио-
дические десятичные дроби. Восстановление десятичных
цифр такого числа проводится в два этапа: сначала вос-
станавливаются цифры целой части (по правилу, опи-
санному для целых чисел), а потом цифры дробной
части.	’
Итак, произвольное (будем считать, что неотрица-
тельное) вещественное число R в десятичной системе ;
счисления записывается в виде	:
/?==10"а„+ ... 4-ICtai 4-ц0 + 10_1a_i+... 4-10-fta_*4-
4--.,	(7) г.
где ап.....аь а0, а_ь ..., a_k —десятичные цифры.
С учетом замечания, сделанного на стр. 56, запись (7) '
числа R единственна. Мы будем называть (7) десятичным
представлением (или десятичным разложением) числа R.
Предположим, что Р и Q — вещественные числа, за-
писанные в виде (7) и, как обычно, Р > 0, Q > 0. Опи- '
шем разложение (7) числа Р 4- Q. Строго говоря, получить ;
десятичное разложение числа Р 4- Q можно лишь посте-
пенно «повышая точность задания» слагаемых Р и Q.
Но, поскольку мы не ставим своей целью развить сейчас 1
арифметику вещественных чисел, а хотим всего лишь >
проиллюстрировать поведение цифр при сложении, нам
достаточно будет считать Р и Q — конечными десятич-
ными дробями:
Р — Itypn 4* • •. 4- 10rPr + • • • + Ро 4- 10— *р—1 4- . • • +
4- 10~тР-т,
Q = 1Oty 4“ - • • 4-10г^Л 4- • • • 4- ?о 4- 10“ 'q_ i 4- ♦ • • 4*	
4-	(8) ;
58

(среди цифр р-т и q-m хотя бы одна не равна 0).
В разложении (7) числа Р 4- Q при 10_*, & > т стоят
нулевые цифры. При 10~m стоит остаток от деления на 10
числа р-т + пусть р-т 4- q-m = 10a_m 4- b_m,
0 <	9. Тогда при Ю”"^1 стоит остаток отделения
на 10 числа p-m+i +q~m+i, сложенный с частным а_от
и вновь приведенный по модулю 10, и т. д. Цифры рг
и qr оказываются, таким образом, подчиненными сложе-
нию арифметики вычетов по модулю 10.
Обратимся к десятичному представлению числа Р — Q,
не считая, что Р и Q заданы в виде (8), но зато пред-
полагая известным процесс сложения в общем случае.
Пусть 10я < Q < 10”+* и Q — 10"+* — Q'. Таким обра-
зом, Р — Q = —10"+* + Р + Q' и десятичное разложение
числа Р — Q легко получить из десятичного разложения
числа P + Q'. Действительно, пусть an-i-i — цифра числа
Р 4- Q', стоящая в разложении (7) при 10”+*. Если
a„+i > 1, то ответ очевиден. Если же an+i = 0, то надо
рассмотреть два случая: 10”+* > Р 4- Q' и 10”+* < P+Q'.
В первом случае число Р 4- Q' — 10"+1 отрицательное и
его десятичная запись получается на основе представ-
ления
10»+i. = 9 • 10” 4- 9 • 10"-* 4- ... 4-9-104-94-
4-9 • 10-1 4-9 • 10—24-9 • 10~34- ...	(9)
Вычитать из такого представления число Р 4- Q' мож-
но просто поразрядно, а потом, при необходимости, вос-
пользоваться замечанием, сделанным на стр. 56. Что
касается случая 10”+’ < Р 4- Q' и ап-н = 0, то он раз-
бирается так. Пусть an+k — ближайшая слева к an+i
цифра, отличная от 0 (такая цифра существует ввиду
неравенства 10”+* < Р 4- Q')- Тогда вместо слагаемого
ап+ь.‘ Ю”+* можно написать сумму двух слагаемых:
(an+k —1)10”+* и 10”+*, но 10”+* представляется в виде,
аналогичном (9). После этого десятичная запись числа
Р 4- Q' — 10”+* получается в соответствии с правилами,
указанными для суммирования.
Уже на примере этих двух основных арифметических
операций над числами мы видим, что десятичные цифры
ведут себя как остатки от деления на 10. Умножение
и деление вещественных чисел в десятичной записи опре-
деляются на основе операций сложения и вычитания,
и поэтому цифры оказываются вновь подчиненными
арифметике вычетов по модулю 10.
59
§ 2. А-ИЧНАЯ СИСТЕМА СЧИСЛЕНИЯ
Из предыдущего параграфа можно заметить, что число
и способ, по которому его записывают (формула (7)),
связаны в основном лишь традицией. Мы начали с ал-
горитма вычисления десятичных цифр, взяв произволь-
ное натуральное число N, а не го, как это число за-
писано.
Заменим теперь десятку другим, произвольно фикси-
рованным натуральным числом N и повторим, по крайней
мере в существенных чертах, построения предыдущего
параграфа.
Во-первых, нужны цифры — всевозможные остатки ог
деления на N, т. е. числа 0, 1.......N — I. Кстати,
если N= 1 (это ведь тоже натуральное число), то 0 —
единственная цифра; конечно, располагая всего одной
цифрой, записывать бесконечное множество чисел нельзя.
Поэтому будем полагать, что М > 2.
Пусть А — произвольное натуральное число. Запишем
его с помощью остатков от деления на N, т. е. с по-
мощью чисел 0, 1, ..., N —1. Для этого разделим А
на N с остатком:
А = Nqo "Ь 0 < г0 < N.
Если qo = 0, то равенство
А = го
и будет искомым М-ичным представлением числа А
Если же qo #= 0, то разделим qo на N с остатком:
9о = М?1 + г\, 0,<Г1<М.
Тогда
А = N'qi 4- Nr{ + r0.
Если qi = 0, то искомым М-ичным представлением чис-
ла А будет
А = r^N + го-
Если же qi 0, то процесс следует продолжить. По-
скольку qi меньше qQ, a qo меньше А, постольку част-
ные qo, qi и т. д. уменьшаются, оставаясь целыми не-
отрицательными числами; следовательно, на каком-то
этапе мы получим нулевое частное <7* и одновременно
W-ичное представление натурального числа А:
А = rkNk 4- rk-iN^ + ... + nN +г0,	(Ю)
60
где r0, r\, .... г*_1, г*—целые неотрицательные числа,
не превосходящие N — 1; мы условились называть их
W-ичными цифрами.
Представление (10) натурального числа А единст-
венно, т. е. не зависит от описанного спссэба вычисле-
ния цифр го, Л.......fk-i, гк. Если бы
А = r'k-Nk' + r'k--xNk'~} + ... +r\N + rQ (10')
и tk', rk-\, ..., А, го быти бы целыми неотрицатель-
ными числами, не превосходящими N — 1, то го и го сов-
падали бы как остатки от деления на N числа Л» л и
Г1 — как остатки от деления на N числа --jj-* и т. д.
Примеры
1. Записать число А = 722 в двоичной системе.
Цифры 2-ичной системы — это числа 0 и 1. Нам, следовательно,
нужно записать А = 722 с помощью чисел 0 и 1. Чтобы было удоб-
ней вычислять остатки г0,	rk, мы будем последовательно
заполнять таблицу из двух столбцов: в левом будут стоять частные
qQi • • м а в правом — остатки г0,	rk. Итак,
722 I 0
361 I
т. е. го = О, частное q0 равно 361. Следующий шаг:
722
361
180
т. е. ri= 1 и qi == 180. Далее:
722 0
361	1
180 0
90
т. е. Г1 =0, <71 = 90. Далее:
722
361
180
90
45
22
И
5
2
1
0
0
1
о
о
1
о
1
1
о
1
(И)
61
Итак, в двоичной системе число 722 запишется так: «1011010010»
(правый столбец записи (И) нужно повернуть на 90° вокруг осно-
вания по часовой стрелке^-и получится ответ). А вот разложе-
ние (10) в этом случае:
722 = 0 - 2° + 1 . 21 + 0 - 22 + 0 • 23 1 . 24 + 0 • 25 + 1 . 2е +
+ 1 • 27 + 0 • 28 + 1 . 29 = 29 + 27 + 26 + 2* + 2.
2. Записать число А = 722 в 12-ичной системе (N 12).
Цифрами будут числа 0, 1, 2, ... 11. Вычисление остатков
r0, rf, ... и частных q0, qlt ... вновь удобно располагать в виде
таблицы (11).
722 2
Следовательно, в 12-ичной системе число 722 имеет вид: «502», т. е.
722 = 2. 120 4- 0.12 + 5- 122 = 5. 122 + 2.
3. Записать число А = 722 в 722-ичной системе (N = 722).
Таблица (11) здесь такова:
722 0
1 1
0
Следовательно, число 722 в этой системе имеет вид: «10», т. е.
722= 0 • 722°+ 1 • 722. Чтобы запись «10» не путать с числом
десять, будем писать 1 0, указывая на то, что 1 и б рассматрива-
ются как вычеты по модулю 722.
Любопытно отметить следующий факт:
В W-ичной системе число N записывается как 16.
Разумеется, записывать число А в десятичной системе
по его представлению в Af-ичной системе надо на основе
равенства (10), т. е. осуществив серию умножений и
сложений, а не делений с остатком. Объяснить это мож-
но тем, что в любом случае мы оперируем числами, за-
писанными в традиционной десятичной системе — ведь
у нас нет цифр ни для какой другой системы. Например,
2-ичное число 1611616616—это, конечно, обычное 2 +
+ 24 + 26 + 27 + 29 = 722. Но если бы мы попытались
получить запись этого числа в десятичной системе с по-
мощью описанного выше процесса деления с остатком,
то нам пришлось бы делить 1611616616 на число 10, ко-
торое, кстати, в двоичной системе выглядит так: 1616.
62
Для наглядности мы приведем соответствующую таблицу
вычисления остатков от деления на 1616.
ТоГюТобГо 1010	1010
	1001000
—1212
1010
616
Следовательно, частное равно
Следующий этап:
1001000, а остаток — 10.
Too1000	1010
1010	III
10000	
1610	
1100
1010
16
Ill, а остаток—10. Ha-
Частное в этом случае равно
конец, объединим это все в традиционной таблице остат-
ков и частных:
1011010016
166'1000
111
о
10
_16
111"
конечно, означает 722, только цифры
двоичной системе (об этом свидетель-
Запись 111 10 Ю,
здесь записаны в
ствуют верхние надстрочные черты).
Этот пример, показывающий способ перевода числа
из двоичной системы в десятичную, свидетельствует
о том, что обычные арифметические операции над числа-
ми можно производить в той системе, в которой они
записаны, не прибегая к десятичной системе.
Обобщим теперь наши рассуждения.	_
Пусть А = anan_i ... aiao и В = bmbm-i ... btb0 —
два натуральных числа, записанных в Л/-ичной систе-
ме (так, что ап, .... а0, Ьт ..., Ьо — Af-ичные цифры).
63
Записать сумму А + В удобнее всего, выполняя сложе-
ние «столбиком»:
 tyz&rt—1	• • • ^0	/1 п\
Ьт ... Мо _	k 7
Складывая и йо, получим_ Afd0+£о, где 0<c0<N — 1
и O<do< 1; поэтому под а$ и_&о в записи (12) надо
записать cq. Затем сложим аь Ь\ и doL вновь предста-
вив сумму в виде Nd\ +ci; под а\ и Ь\ в (12) запишем
и т. д.
Пример. Пусть М= 3, Л = 2ПГббТ, и В = 2010212. Найти сум-
му А и В
2П1001
+ 2010212
11121220
Обратимся к вычитанию. Здесь прежде всего нужно
выяснить, что больше: А или В. Если п > пг, то, как
следует из представления (10), А > В; если же п < tn,
то, конечно, А < В. При п — tn надо сравнить ап и Ьп.
Если_а„ > Ьп, то А > В, если_ ап < Ьп, то А < В. При
Оп — Ьп надо сравнить an-i и &„_] и_т. д. Если выяснит-
ся, что ап = Ьп, ап-\—Ьп-\........ ct-i	— bi, ао = Ьо, то
окажется, что А — В. Например, при N = 2 число
101101001001 больше числа 101101000111.
Для вычисления разности А — В нужно сначала
решить, какое из неравенств имеет место: Л > В или
А < В. Если имеет место второе, то надо искать раз-
ность В — А, а затем перед ответом поставить знак
минус. Будем считать, что Л > В. Вычисление разности
Л —В также удобнее всего описать «столбиком»
апйп—1 ...
ьт ... b2bibo
--------------------------------------,
подразумевая под каждой из строчек сокращенно запи-
санную правую часть формулы (10). Если а0 > Ьо, то
под а0 и Ьо запишем (V-ичную цифру со = ао— Ьо. Если
же ао < Ьо и at > 0, то «займем» у at «одну единичку»
и положим со = А?4-ао — Ьо- После этого, конечно, в
таблице вместо а, уже будет цифра ai — 1. Еслижеа1 =
64
= 0 и й2 > 0, то «занять единичку» нужно у Яг, т. е.
представить число в виде:
Д= ... +(о2 — 1)У2 + У2 + я0 =
— ... + (я2 — 1) N2 + N2 — N + N + <70 =
= ... +(a2-l)N2 + (N~l)N + N +a0.
Тогда c0 = N + a0 — b0, a Ci—цифра, стоящая под a}
и bi будет равна N — l—bt. Если же и «2 = 0, но
Оз > 0, то надо вновь повторить эти рассуждения, пред-
ставляя А в виде
А = ... + я3У3+я0 = ... +(оз — 1)У3 + У3+я0 =
= + (я3 — 1) У3 + У3 — У2 + У2 —У + У+я0 =
= + (я3-1)У3 + (У — V)N2 + (N -V)N + N +а0,
если же я3 = 0, то читатель уже, очевидно, догадался,
что нужно сделать.
Пример. Пусть N = 8, А = 724135 и В = 2635410. Найти А — В.
Поскольку В > 0, то:
263541'0
~~ 724135
_____________	17ТТ253
Ответ: — 1711253.
Мы рассмотрели сложение и вычитание натуральных
чисел в У-ичной системе. Поскольку умножение и деле-
ние с остатком основаны на сложении и вычитании,
то у нас есть теперь все необходимое для осуществле-
ния и этих операций в У-ичной системе.
Обратимся к дробям:
R = Г-1 • 10-1 + Г_2 • 10-2 + ...
Восстановление их десятичных знаков было описано
в предыдущем параграфе. Наша ближайшая цель —
представить указанную дробь 7? в виде
R = a-tN-' + а_2У-2 + ...,
где я_1, я_2, ...—У-ичные цифры. Очевидно, я_1—
это целая часть числа NR (конечно, я_1 < У, т. к.
R < 1 и поэтому NR < У; отсюда я_1 —У-ичная цифра).
Аналогично, а2— целая часть числа У (NR—a_i), т. е.
N2R—Na_t и, вообще, я_*— целая часть числа
N~kR — У‘-'я_1 - У*-2я_2 - ... - Уа_Л+1.
65
Пример. Записать дробь /? = 0,0875 в девятичной системе (W=9).
Результаты вычислений и здесь удобно заносить в таблицу из
двух столбцов: слева будут указываться дроби, а справа — целые
части их произведений с числом N — 9. Итак,
0875
7875
0 875
7 875
0 875
0
7
0
7
Следовательно, в девятичной системе конечная десятичная дробь
R = 0,0875 — является бесконечной пер иодической дробью
0, 0707 . . .
длина периода которой равна 2 — наименьшему натуральному числу
из таких чисел п, для которых 9rt = lmod (Л4), где М — знамена-
/	7
тель дроби /?, представленной в рациональном виде 1т. е. R = gQ
и М = 80^, являющийся взаимно простым с числом 9.
Превращение конечной десятичной дроби в бесконеч-
ную периодическую в другой системе записи заслужи-
вает специального внимания. Прежде всего отметим, что
если рациональное число 7? =	, (Д, В) = 1 является
бесконечной периодической десятичной дробью, то в
В-ичной системе эта дробь уже будет конечной. Соглас-
но теореме 3 из § 1, длину периода дроби R в десятич-
ной системе надо определять так: представить В в виде
2r. 5s . В', где (10, В') = 1, а затем найти такое наимень-
шее натуральное п, при котором 10л =е Imod (В'). Имеет
место следующая теорема:
Теорема 4. Пусть N >2 — натуральное число и
R =	— рациональное число в несократимой записи.
Пусть В^В'В"— такое представление числа В, что
(B't N) = 1 и каждый простой делитель сомножителя В"
делит N. Тогда период N-ичной дроби, представляющей
число R, равен наименьшему из таких натуральных
чисел п, что Nn = Imod (В').
Предлагаем читателю самостоятельно доказать эту
теорему, основываясь на доказательстве теоремы 3.
Таким образом, рациональное число в любой AZ-ичной
системе будет конечной или бесконечной периодической
дробью; иррациональное же число в любой системе пред-
ставляется как непериодическая дробь, потому что если бы
66
его можно было хотя бы в одной системе представить
периодической дробью, то преобразования, аналогичные
проведенным на стр. 58, привели бы нас к представле-
нию этого числа в виде отношения двух целых чисел,
а это из-за иррациональности невозможно.
Складывать и вычитать У-ичные конечные дроби
удобнее «столбиком» как целые числа.
Рассмотрим теперь признаки делимости. В теореме 1
этой главы заключена именно та информация, которую
успешно можно обобщить на случай У-ичной системы:
Теорема 5, Разность между натуральным числом А
и суммой его N-ичных цифр делится на N — 1.
Для доказательства достаточно воспользоваться пред-
ставлением (10), из которого следует, что
А — М = rk (Nk — 1) +	(У*-1 — 1) + ... + п (У — I),
где М = го + ... + гк.
Но
_ 1 = (У ~ 1) (уь-1 + №-2 4- ... + У + 1),
откуда следует требуемое.
Вот почему число А делится на какой-либо делитель
числа У — 1 тогда и только тогда, когда этому делителю
кратна сумма У-ичных цифр числа А. Например, рас-
полагая восьмеричным представлением любого числа А,
легко узнать делится ли оно на 7: надо сложить цифры
и определить, кратна ли 7 их сумма. Так, число 76125,
заданное в восьмеричной системе, конечно, делится на 7
(сумма цифр равна 21). В десятичной системе это число
записывается так: 31829.
При У = 2 только что описанные сведения становятся
тривиальными: ведь У —1 = 1. Поэтому в смысле тео-
ремы 5 двоичная система оказывается неудобной: для
проверки той или иной делимости здесь лучше всего
провести соответствующее деление с остатком или перей-
ти в другую систему, где получить ответ будет проще.
$ 8. У-ИЧНАЯ И УЛИЧНАЯ СИСТЕМЫ
Такие системы при У = 2 приобрели большое значе-
ние в связи с электронными вычислительными машина-
ми. Каждое двоичное число записывается всего лишь
двумя цифрами: 0 и 1. Так как простая электронная
лампа может находиться в одном из двух состояний:
67
быть выключенной и быть включенной, то если усло-
виться первое состояние считать воспроизведением нуля,
а второе — воспроизведением единицы, то набором из п
ламп можно будет воспроизводить любое n-значное двоич-
ное число. На этом принципе и основана работа элект-
ронных вычислительных машин: числа вводятся в них
в двоичной системе, а потом подвергаются определенным
арифметическим операциям.
При разборе примеров двоичной записи числа в
предыдущем параграфе читатель, наверное, заметил, что
даже небольшое число требует для своего изображения
довольно много двоичных знаков; так, число 722 в двоич-
ной системе является десятизначным. Естественно по-
этому представлять числа в двоичной системе лишь перед
их вводом в машину, а до этого записывать их в такой
системе, где, во-первых, для их изображения потребуется
меньше знаков, и, во-вторых, переход к двоичной системе
окажется более непосредственным, чем, скажем, в деся-
тичной.
Пусть, например, 4=30213 — число в четверичной
системе. Как записать его в двоичной системе? Восполь-
зуемся представлением (10):
А = 3 -44 +2 .42 Н- 1.4 + 3 = (2 + 1).28 + 2.24 + 1-22 +
+ (2 + 1) = 29 + 28 + 25 + 22 + 2 + 1.
Следовательно, А — 1100100111 —запись в двоичной си-
стеме. Иными словами, мы записали каждую четвертич-
ную цифру числа А двоичными цифрами и получили
ответ. Это легко проверить исходя из ответа.
Проведем соответствующие рассуждения в общем виде.
Пусть
А — й2п • 22л 4~ й2п—122л-1	... 4-а3-23 +
+ a2-22+a, .2+ао,	(12)
где, возможно, й2П = 0 (нам нужно четное число цифр)
и «о, а\.... а2п-ь «2п—двоичные цифры, т. е. числа
0 и 1. Число ai-2 + ло не превосходит 3, а потому
служит четвертичной цифрой. Рассмотрим следующую
пару слагаемых: аз • 23 4- я2 • 22 = (а3 • 2 4- Яг) 22, т. е.
это четвертичная цифра, умноженная на 4. Следующая
пара будет четвертичной цифрой, умноженной на 24 = 4
и т. д.
68
Используя представление, аналогичное представле-
нию (12), легко вывести следующее правило.
Правило. Чтобы перейти от N-ичной записи нату-
рального числа А к записи в №-ичной системе, нужно
разделить N-ичные цифры числа А в группы по k штук
справа налево и после этого каждую из групп записать
одной №-ичной цифрой. Обратный переход делается так:
каждую №-ичную цифру числа А надо записать в N-
ичной системе с помощью N-ичных цифр — тогда полу-
чится N-ичное представление для А.
Примечание. Каждое целое неотрицательное число М < Nfc (т. е.
Л^-ичная цифра) записывается не более, чем feAf-ичными цифра-
ми, потому что Nk в Af-ичной системе—это 100 ... 0. В данном
k нулей
случае предполагается, что если для М нужно I < k N-vmwz
цифр, то перед У-ичной записью приписывается k^l нулей. Это
находится в полном согласии с представлением (10).
Вместо доказательства, которое легко проводится
после введения соответствующих обозначений, мы про-
иллюстрируем это правило двумя примерами.
Пусть А = 975 — число в 27-ичной системе. Пред-
ставим его в троичной системе. Имеем: 27-ичное 9 — это
троичное ТОО; 27-ичное 7— это троичное 021, 27-ичное
5 — это троичное 012. Таким образом, 27-ичное 975 за-
пишется как троичное 100021612.
Пусть А = 7810 15 109 — число в 16-ичной системе.
Запишем его в 256-ичпой системе. Имеем: 16-ичное
10 9—это 256-ичное 169; 16-ичное 1015—это 256-ич-
ное 175, 16-ичное 78 — это 256-ичное 120. Следователь-
но, запись числа А такова: 120175169.
1.	Хинчин А. Я. Элементы теории чисел. ЭЭМ, кн. I, Арифметика.
М., Гостехиздат, 1951.
2.	МаркушевичА. И. Деление с остатком в арифметике и в алгеб-
ре. Сер. «Педагогическая библиотека учителя». Изд. Академии
педагогических наук РСФСР, 1949.
3.	Дэвенпорт Г. Высшая арифметика. М., «Наука». 1965.
4.	Виноградов И. М. Основы теории чисел. М., «Наука», 1965.
5.	А р н о л ь д И. В. Теоретическая арифметика. М., Учпедгиз, 1939.
6.	Бухштаб А. А. Теория чисел. М., «Просвещение», 1966.
7.	Хассе Г. Лекции по теории чисел. Изд-во иностр, лит, 1953.ч
8.	Воробьев Н. Н. «Признаки делимости». Сер. «Популярные
лекции по математике». М., «Наука», 1968.
9.	ФоминС. В. «Системы счисления», Сер. «Популярные лекции
по математике». М., «Наука», 1968.
10.	Д ын кин Е. Б., Успенский В. А. «Математическиебеседы».
М — Л., Гостехиздат, 1952.
ОГЛАВЛЕНИЕ
Глава I. Основная теорема арифметики . .	3
§ 1.	Деление с остатком и наибольший общий
делитель (НОД) двух чисел..................... 4
§ 2.	Основная теорема арифметики............. 9
§ 3.	Алгоритм Евклида и решение линейных дио-
фантовых уравнений с двумя неизвестными .	12
§ 4.	Пифагоровы тройки...................... 16
Глава II. Арифметика гауссовых чисел. . 20
§ 1. Гауссовы числа и целые гауссовы числа . . 20
§ 2. Простые гауссовы числа и представление це-
лых рациональных чисел в виде суммы двух
квадратов................................ 27
Глава III. Конечные арифметики........... 32
§ 1.	Классы вычетов......................... 32
§ 2.	Арифметика классов вычетов............. 34
§ 3.	Диофантовы уравнения и вычеты.......... 42
Глава IV. Системы счисления...............50
§ 1.	Десятичная система	счисления........... 50
§ 2.	/V-ичная система счисления...............60
§ 3.	W-ичная и А^-ичная	системы............. 67
Литература.............................. 70
Библиотечка физико-математической школы
Математика
Аркадий Александрович Бельский,
Лев Аркадиевич Калужнин
Деление с остатком
Издательское объединение «Вища школа»
Головное издательство
Киев — 1977
Редактор Г. Ф. Трофимчук
Обложка художника Е. В. Попова
Художественный редактор С. Р. Ойхман
Технический редактор И. И. Каткова
Корректор Н. В. Волкова
Сдано в набор 2.09.1976 г. Подписано к печати 6.12.1976 г. Фор-
мат бумаги 84Х1081/82. Бумага тип № 2. Усл. печ. л. 3,78. Уч.-
изд. л. 3,58. Тираж 25 000. Изд. № 2706.Цена 11 коп Зак- 6-364.
Головное издательство издательского объединения «Вища школа-»,
252054, Киев-54, Гоголевская, 7
Харьковская книжная фабрика «Коммунист» республиканского
производственного объединения «Полиграфкнига» Госкомиздата
УССР. Харьков, Энгельса, 11.