Калужнин Л. А. Основная теорема арифметики. — М. : Наука, 1969. — 32 с. — (Популярные лекции по математике ; вып. 47).

Поплярные лекции по математике

Л. А. КАЛУЖНИН

ОСНОВНАЯ ТЕОРЕМА АРИФМЕТИКИ

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

ВЫПУСК 47

Л. А. КАЛУЖНИН

ОСНОВНАЯ ТЕОРЕМА АРИФМЕТИКИ

ИЗДАТЕЛЬСТВО «НАУКА»

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

МОСКВА 1969

511 К 17

УДК 511

СОДЕРЖАНИЕ

Введение ..................... 3

§ 1. Основная теорема арифметики. Доказательство первой части............... 6

§ 2. Деление с остатком и наибольший общий делитель (НОД) двух чисел. Доказательство второй части основной теоремы ........ 9

§ 3. Алгоритм Евклида и решение линейных диофантовых уравнений с двумя неизвестными. . . 15

§ 4. Гауссовы числа и целые гауссовы числа .... 19

§ 5. Простые гауссовы числа и представление целых рациональных чисел в виде суммы двух квадратов .................... 27

§ 6. Еще одна «арифметика»............ 30

Литература..................... 32

Лев Аркадьевич Калужнин

Основная теорема арифметики

(Серия: «Популярные лекции по математике»)

М., 1969 г., 32 стр. с илл.

Редактор Ф. И. Кизнер

Технический редактор А. А. Благовещенская Корректор Т. А. Панькова

Сдано в набор 15,X1 1968 г. Подписано к печати 25/1II 1969 г. Бумага 84х1081,2. Физ. печ. л. 1. Условн печ. л. 1,68. Уч.-изд. л. 1,54.

Тираж 150 000 экз. Т-04848. Цена 5 коп. Заказ Кя 1455.

Издательство «Наука» Главная редакция физико-математической литературы Москва В-71, Ленинский проспект, 15.

2-я типография издательства «Наука». Москва, Шубинский пер., 10

2-2-2 165-69

ВВЕДЕНИЕ

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

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

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

420 = 2-2-3-5.7. (1)

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

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

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

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

420 имеем:

420 = 20-21, 420 = 15-28.

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

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

п = PiP2---Pk — Ц\-Цг-~Чи

то эти разложения совпадают с точностью до порядка сомножителей: оба они обладают одним и тем же числом сомножителей, k= /, и каждый сомножитель, встречающийся в первом разложении, встречается столько же раз во втором разложении1).

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

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

1) Если рассматривать произвольные целые числа (как положительные, так и отрицательные), то под единственностью разложения на простые множители следует понимать, что два разложения п = рх • р2... ... pkw п = q1-q2... Çi могут отличаться не только порядком сомножителей, но и знаками соответствующих сомножителей; см. § 1—формулировку основной теоремы.

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

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

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

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

§ 1. ОСНОВНАЯ ТЕОРЕМА АРИФМЕТИКИ. ДОКАЗАТЕЛЬСТВО ПЕРВОЙ ЧАСТИ

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

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

1) Иногда ее называют также «полной индукцией».

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

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

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

1 = 1

и есть разложение числа 1 в произведение простых чисел, причем число простых сомножителей в правой части равно 0. Эта условность напоминает определение нулевой степени а0 = 1 (число сомножителей а равно 0) и во многих отношениях удобно. Подобное соглашение мы принимаем и для числа —1.

2. В качестве второго замечания мы просто приведем пример, поясняющий понятие однозначности разложения целого числа на простые сомножители. Два разложения числа 18

18 = 2-3 3

и

18= (—3). (—2) • 3

мы считаем неразличимыми.

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

а) Для п = 1 1 = 1 и есть искомое представление: 1 является произведением пустого множества простых чисел.

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

п = п

и есть искомое разложение (один простой сомножитель). Пусть п — число сложное. Тогда оно является произведением п = п1-п2 двух целых чисел пг и пъ каждое из которых отлично от 1 и п и, следовательно, <^ п и п2 <С я. Но тогда, по предположению индукции, разложимость чисел ni и п2 в произведение простых чисел уже установлена:

«1 = Ргрг ---Рг,

где pj и Ц{ — простые числа. Имеем п = Pi-P2---Pr-<7i-<72--« ...qs, т. е. мы получили искомое разложение числа п.

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

—П = pfp2---Pk,

тогда

п = (— l)pi-p2...p*i

или, например,

п = (—Pi)-p2...p*

— искомое разложение числа п. Тем самым первая часть теоремы доказана.

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

§ 2. ДЕЛЕНИЕ С ОСТАТКОМ И НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ (НОД) ДВУХ ЧИСЕЛ. ДОКАЗАТЕЛЬСТВО ВТОРОЙ ЧАСТИ ОСНОВНОЙ ТЕОРЕМЫ

Исходным для наших рассмотрений является утверждение о возможности «деления с остатком» в области целых чисел. Точно это утверждение формулируется так:

Теорема 1. Пусть а и b — целые числа и b =f= 0. Тогда существуют такие целые числа q и г1), причем 0 ^ < Iг|< Ь, что

a = q.b + r. (1)

Равенство г = 0 в представлении (1) равносильно тому, что число а делится на b2). Этот факт мы в дальнейшем будем записывать так: b \ а — такая запись принята в теории чисел.

Докажем возможность такого представления. Заметим для этого, что для каждого рационального числа т найдется такое целое число /, что | т —1\ <^ 13). Пусть т = ^ ; а и b — целые числа. Подберем такое целое число q, чтобы I ~--<71 <Ч , и положим

Итак, г — целое число,

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

1) Остаток г может быть произвольным целым числом — положительным, отрицательным или нулем.

2) Для двух целых чисел а и b выражения «число а делится на число 6», «число а — кратное числа Ь», «число b является делителем числа а» или, наконец, «число b делит число а» имеют один и тот же смысл; мы будем пользоваться каждым из них.

3) В действительности ближайшее к числу т целое число отличается от него не больше, чем на ^, но нам это уточнение не понадобится.

4) Отметим, что в представлении (1) целые числа q и г определены не однозначно. Например, для а — 13 и b = 3 имеем 13 = 4 • 3 + 1 (q = 4, г = 1) или 13 = 5 • 3 + (—2) (q = 5, г = —2). Это видно также

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

Определение 1. Если а и b — два целых числа, отличных от нуля, и если число с таково, что с\а и с\Ь, то с называется общим делителем чисел а и Ь. Заметим, что произвольные два числа всегда обладают общими делителями; таковыми являются числа 1 и —1.Если других общих делителей нет, то числа а и b называются взаимно простыми. О взаимно простых числах мы поговорим ниже.

Определение 2. Число d называется наибольшим общим делителем чисел а и b (НОД), если: 1) d является общим делителем чисел а и b и 2) d делится на любой другой общий делитель чисел а и Ь. (Так, например, 6 есть НОД чисел 18 и 30, так как 61 18 и 61 30 и, с другой стороны, 6 делится на все общие делители этих чисел: 1, —1,2, —2, 3, -3, 6, -6).

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

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

Теорема 2. Для любой пары целых чисел a =f= 0 и b =f= 0 существует НОД.

Доказательство. Наряду с числами а к b мы будем рассматривать всевозможные числа вида ха -\-yb, где X и у — какие-либо целые числа. Числа такого вида

v =ха + yb (2)

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

из нашего доказательства. Действительно, если а не делится на Ь,то Ъ —дробное число, но тогда п < п + 1, где п — некоторое целое число. В качестве числа q можно выбрать q = п или q = п + 1, что и дает два представления вида (1). Только в случае, когда Ь\а, число q однозначно определено: a — q • b; при этом остаток г = 0.

Например, для а = 6, Ь = 22 линейными комбинациями будут числа 28 (28 = 1 - 6 + 1 -22), 10 (10 = (—2) -6 + + 1 - 22), — 92 (—92 = 3-6 + (—5) . 22) и т. д. Вообще для заданных чисел а и Ь существует бесконечно много чисел, являющихся их линейными комбинациями. Обозначим множество таких чисел через М. Заметим, что множество M содержит, в частности, и сами числа а (для у = 0, х = 1) и Ь (для # = 0, у= 1), а также число 0 (х = 0, у = 0). Все числа V из множества M являются, очевидно, целыми числами. Если V принадлежит М, то и —v тоже принадлежит M (если v = ха + yby то —и = (—х) а + (—у)Ь). Отметим еще одно свойство чисел v из М, которое нам сразу понадобится: все такие числа делятся на все общие делители чисел а и Ь. Действительно, если с \ а и с | ft, и, скажем, а = о!с и Ь = = We, то v = ха + yb = ха'с + уЪ'с = (ха' + yV) с, т. е. с I и. Пусть теперь d =f= 0 — наименьшее по модулю число среди всех чисел из М, отличных от 01). Мы покажем, что d и является НОД чисел а и Ь. Свойством 2) определения НОД оно обладает, так как им обладают все числа из М. Нужно только еще установить, что оно обладает и свойством 1), т. е. что d является общим делителем чисел а и Ь. Покажем, что d I а. Так как d принадлежит M, то оно представимо в виде d = sa + tb, где s и / — подходящие целые числа. Разделим а на d с остатком, т. е. найдем такие числа q и г, \ г\ < что

а = -f г.

Но тогда и остаток г должен принадлежать множеству М. Действительно,

г = а — qd = а — q (sa + /Ь) = (1 — (7s) а + tô.

Вспомним теперь, что d — наименьшее по модулю число среди отличных от нуля чисел множества M, а число г меньше d. Следовательно, г = 0 и d \ а. Дословно также доказывается делимость d \ b. Теорема доказана.

Мы установили существование НОД двух целых чисел, отличных от нуля. Более того, из доказательства мы

1) Такое число в множестве M действительно существует. Заметим, что в множестве M содержатся числа, не равные нулю (например, а или Ь), а их модули — положительные целые, т. е. натуральные, числа. Но одно из основных свойств натуральных чисел, принимаемое обычно за аксиому (см. И. С. Соминский, «Метод математической индукции», стр. 9, замечание), состоит в том, что во всякой непустой совокупности натуральных чисел всегда содержится наименьшее число.

усматриваем следующий важный факт, который нам вскоре понадобится:

Теорема 3. НОД чисел а и b представим в виде линейной комбинации этих чисел.

Возникает вопрос: определен ли НОД чисел а и Ь однозначно? Ответ, конечно, отрицательный: если число d обладает свойствами 1) и 2) определения НОД, то и —d тоже ими обладает. Но этим неоднозначность исчерпывается. Действительно, пусть dud' — два НОД чисел а и Ь. Так как d обладает свойством 2), ad' — свойством 1), то d d' 1 1 d'\d. Но аналогично, d\d'. Итак, а = 77-и — = -угтг- =-- целые числа. Но единственные целые числа, обратные от которых также целые,— это числа 1 и —1. Итак, а= 1 или а = —1, откуда d' = d или d' = — d. Если бы мы в определении НОД потребовали, чтобы это число было положительным — это иногда (но далеко не всегда) бывает удобным,— то можно было бы сказать, что НОД двух отличных от нуля целых чисел существует и однозначно определен.

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

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

Определение 3. Целые числа a =f= О и b ф О называются взаимно простыми, если их НОД равен 1.

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

Из сказанного выше (теорема 3) следует, что если (а, Ь) = 1, то 1 представима в виде

1 = sa + tb (3)

с подходящими целыми числами s и t. Обратно, если равенство (3) выполняется для подходящих s и /, то а и b взаимно просты. Действительно (см. доказательство теоремы 1), d = (а, Ь) — это наименьшее по модулю число среди отличных от нуля чисел вида ха + yb. Следовательно, если (3) выполняется, то \d \ <^ 1 и d =f= 0, так что d = + 1.

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

Теорема 4. Если a\bc и (а, Ь) = 1, то а\с (это свойство читается так: если число а делит произведение двух чисел и взаимно просто с одним из сомножителей, то оно делит другой сомножитель).

Доказательство. Так как (а, Ь) = 1, то найдутся такие числа s и /, что

1 = sa + tb. (4)

Умножим последнее равенство на с. Имеем с = (sc)a + t (be).

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

Полезно также следующее утверждение.

Теорема 5. Если число а взаимно просто с числами b и с, то оно взаимно просто с произведением be.

Доказательство. Так как (а, Ь) = 1, то найдутся целые числа sut, удовлетворяющие равенству

1 = sa + tb.

Аналогично, так как (а, с) = 1, то

I = иа + vc

для подходящих и и v. Перемножив почленно два последних равенства, получаем

1 = (sa + tb) (иа + vc) = = sua2 + save + tbua + tbvc = = (sua + sve + tbu) a + (tv) • (be).

Положим m = sua + sve + tbu и n = tv, тогда тип — целые числа и

1 = та + п (be),

и это показывает, что а и be взаимно просты.

Утверждение последней теоремы легко обобщается на произвольное число сомножителей:

Теорема 6. Если а взаимно просто с числами Ьи Ь2»---bky то а взаимно просто с произведением bi • Ьг... bk.

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

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

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

а) Если \п \ = 1, то п = + 1 и

1 = 1, -1 = -1,

т. е. имеет место единственность разложения для чисел 1 и —1.

б) Предположим, что доказываемое свойство уже установлено для всех чисел m, для которых \т \ <^ \п\. Пусть

п = Pi-p2... Pk = qi • qi...qi

— два разложения числа п в произведение простых чисел Piy и <7i, q2y-y qi соответственно. Мы утверждаем,

что простое число pk встречается среди простых чисел qu <72>---» qi (или, быть может, противоположно какому-то из них). Действительно, если бы это было не так, т. е. pk =/= + qly i = 1, 2,..., /, то pk было бы взаимно просто со всеми числами qif а следовательно, согласно теореме 6 оно было бы взаимно просто с их произведением, т. е. с числом п. Но это невозможно, так как рк \п, т. е. (pk, п) = = pk. Итак, рк равно какому-то из простых чисел + Можно считать, что pk = qi, так как в противном случае такого равенства можно было бы добиться перестановкой сомножителей а затем, если все же pk = — qu изменением знака у qt с изменением его у какого-либо другого qt. Итак, получаем:

п = Pi-pi---Pk-\'Pk = qi • <72... qi-i • Рк>

откуда

т = ~- = Pi'p2 • •• Pk-i = qi-q2--.qi i-

Но \m \ <^ \n\ и, по предположению индукции, для m утверждение теоремы уже доказано, т. е. k— 1 = 1— 1, последовательности ри р2>-.., Pk-i и qi9 q2, содержат

с точностью до знаков одни и те же простые числа, и соответствующие простые числа встречаются в обоих представлениях одно и то же число раз, а так как pk = qh то это же верно и для последовательностей ри р2>--.> Pk-ъ Рк и <7ь <72э---> ft- Теорема доказана.

§ 3. АЛГОРИТМ ЕВКЛИДА И РЕШЕНИЕ ЛИНЕЙНЫХ ДИОФАНТОВЫХ УРАВНЕНИЙ С ДВУМЯ НЕИЗВЕСТНЫМИ

Согласно теореме 2 два целых числа а и Ь обладают НОД. Опишем сейчас одну процедуру нахождения НОД, которая была указана еще в «Элементах» Евклида и называется алгоритмом Евклида.

При этом будем считать, что \а\ ^ \Ь\.

Первый шаг. Делим а на Ь с остатком:

a = qi.b + rit Ы< \Ь\. (1)

Если гА = 0, то Ь\а и (а, Ь) = Ь. Если г{ =f= 0, то делаем Второй шаг. Делим Ь на г{:

b = q2.ri + r2t |г2|< |п|. (2)

Если г2 =/= 0, то делаем Третий шаг.

П = Яз'Г2 + г3, |г3|< |г2| (3)

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

\Ь\> Ы> |г2|>...,

и на каком-то й-м шаге (k < \Ь\) остаток станет равным нулю:

k-и шаг.

г*__2 = qk • rk^. (k)

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

(1) a = qt - b + ru

(2) b = q2 . r4 + г2,

(3) n = q3 - r2 + г3,

(й — 1) rk.3 = qk-x • rfe_2 + Tk-ъ

{k) = qk • ?k-\.

Из последнего равенства имеем rk.x\rk 2, из предпоследнего—r^lr^ и r*_i|r*_2 и, следовательно, rfe_x|гд;_3. Из предшествующего равенства аналогично заключаем, что Гк-iVk-4 и» поднимаясь таким образом к все более и более

ранним равенствам, заключаем,что...,rk-\ |г2, rk~\ [гх, \rk-i\b, г^\а. Мы видим, что rh-i—общий делитель чисел а и Ь.

Пусть теперь с\а и с\Ь. Тогда из (1), (2),..., (k — 1) последовательно получаем: с|гь c\r2,...,c\rk-i. Таким образом, 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 • а + / • 6,

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

Итак, нужно найти такие целые числа s и /, что 11 =s . 858 + / . 253. Из (4), (3), (2), (1) последовательно получаем:

11 = 55 + (—1) . 44,

44 = 99 + (—1) . 55,

55 = 253 + (—2) - 99,

99 = 858 + (—3) . 250.

Подставляя теперь в первое из выписанных сейчас равенств выражение для 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. Окончательно: s = — 5, / = 17.

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

d = ха + yb,

(где d = (а, &)).

Вообще, уравнение вида

ха + yb = с,

где а, Ь, с — заданные целые числа, для которого ищется целочисленное решение х, у, называется линейным диофантовым уравнением с двумя неизвестными. Линейным оно называется потому, что неизвестные х и у входят в него в первой степени. Термин «диофантово»1) указывает на то, что коэффициенты уравнения — целые числа и что решения также ищутся целочисленные.

Заметим, что мы в действительности уже научились решать линейные диофантовы уравнения вида

ха + yb = с. (I)

Но мы должны обсудить вопрос о всех решениях уравнения (I) более детально. Отметим сначала, что не всякое уравнение такого вида имеет решение. Действительно, если уравнение (I) имеет решение в целых числах, скажем, х = х0, у = у0: с = Xcß + уф, и если d = (а, Ь), то, так как d\a, d\b, d делит оба слагаемых в правой части и, следовательно, также делит с. Отсюда заключаем, что

Для существования целочисленного решения уравнения (I) необходимо, чтобы правая часть уравнения делилась на НОД чисел а и Ь.

Например, уравнение

9х + 15у = 7

решения не имеет, так как 7 не делится на 3 = (9,15). Наоборот, если d\c, то уравнение (I) имеет целочисленное решение и мы даже знаем, как такое решение найти. Действительно, пусть с = dd, и пусть sut — такие целые числа (их

1) По имени древнегреческого математика Диофанта (около 250 г. до н. э.), который в своей книге «Арифметика» исследовал целочисленные уравнения. В конце нашего изложения мы немного остановимся на квадратичных диофантовых уравнениях.

можно найти с помощью алгоритма Евклида), что d = as + bt.

Тогда

с = c'd = a (s с') + b (te'),

т. е. х0 = se', у о = te' — решение уравнения (I). Решим, например, диофантово уравнение

33 = 858л: + 253*/. (II)

Выше мы показали, что

11 = 858 . (—5) + 253 - 17.

Умножая это равенство почленно на 3, получаем

33 = 858 - (—15) + 253 . 51.

Итак, X = —15, у = 51 — решение уравнения (II). Не следует думать, что найденное решение единственно. Вообще, оказывается, что если диофантово уравнение вида (I) имеет решение, то оно имеет бесконечно много решений. Мы сейчас исследуем этот вопрос более подробно: докажем сформулированное утверждение и найдем общий вид всевозможных решений уравнения (I). Начнем с выяснения общего вида. Предположим, что мы уже знаем, что наряду с целочисленным решением x0i Уо уравнение (I) имеет еще и решение хи у{. Имеем:

с = ах0 + by о,

с = axi + by{.

Вычитая второе равенство из первого, получаем: а (х0 — + b (уо — yt) = О,

или

а (х0 — Xi) = b (yt — уо). (III)

Если d = (a, b), то положим а' = a/d, b' = b/d, т. е.

а = a'd, b = b'd,

где а' и b' — взаимно простые числа. Сокращая равенство (III) на d, приходим к равенству

а' (х0 — хх) = Ь' (yt — у о).

Но тогда, так как а', V взаимно просты, — у0) и, аналогично, Ь'\(х0 — Xi). Положив

Hi — Уо = а'ки Xq — Xi = Ъ'кч,

имеем a'b'ki = a'b'k2> откуда ki = k2 = k. Таким образом, окончательно

(IV) (V)

где k — некоторое целое число. Обратно, легко проверить, что если лг0, Уо — решение уравнения (I), то все пары чисел (IV), (V) при произвольном целочисленном k дают решение уравнения (I). Действительно,

Итак, если х0, у0 —(решение уравнения (I), то все числа вида х° — Ч ^° 11 * являются также решениями (значит, решений, во всяком случае, бесконечно много — по одному для каждого k) и других решений нет.

§ 4. ГАУССОВЫ ЧИСЛА И ЦЕЛЫЕ ГАУССОВЫ ЧИСЛА

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

Определение 4. Целым гауссовым числом называется комплексное число, вещественная и мнимая части которого суть целые рациональные числа. Иначе говоря, это комплексные числа а вида

а = а + M, (1)

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

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

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

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

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

Небольшого пояснения требует последнее утверждение. Пусть а = а + Ы и ß = с + di — целые гауссовы числа (т. е. а, Ь, с, d— целые рациональные числа) и пусть ß =/= 0. Покажем, что у = a/ß — гауссово число. Действительно,

тт ас-у od ос — аа

Числа 9 и —9 , м--вещественная и мнимая части числа у — числа рациональные и, следовательно, y — гауссово число.

Отметим, наконец, что, очевидно, всякое рациональное число является гауссовым (мнимая часть равна 0) и что всякое целое рациональное число является целым гауссовым числом.

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

Они лежат в вершинах сетки квадратов со стороной, равной 1, покрывающей комплексную плоскость.

Из теории комплексных чисел нам понадобятся понятия нормы и модуля комплексного числа. Напомним, что нормой комплексного числа а = х + iy называется неотрицательное вещественное число N (а) = х2 + у2; модулем комплексного числа а, обозначаемым |а|, называется вещественное число Ух2 + у2. Геометрически модуль комплексного числа — это расстояние соответствующей точки на комплексной плоскости от начала координат. Норма N (а) числа а представима как произведение N (а) = а- 5с, где 5с — комплексно сопряженное число х — iy числа а. Известным предполагается также свойство мультипликативности нормы, т. е. что

N (а . ß) = N (а) . N (ß). (2)

Отметим сразу, что если а — гауссово число, то N (а) — неотрицательное рациональное число, а если а — даже целое гауссово число, то N (а) — неотрицательное целое число1).

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

Рис. 1.

1) Модуль |а| гауссова числа уже не обязан быть рациональным числом, поэтому в дальнейшем мы в основном будем пользоваться не модулем, а нормой.

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

Доказательство. Если а = а + Ы — целое гауссово число, то N (а) = а2 + Ъ2 — сумма квадратов целых чисел а и Ь. Наоборот, если с = х2 + у2у где х и у — целые рациональные числа, то с = N (х + yi), где х + yi — целое гауссово число. Теорема доказана.

Нетрудно показать, что не всякое положительное целое число представимо в виде суммы двух квадратов. Покажем, например, что нечетное положительное целое число t, представимое в виде суммы двух квадратов целых чисел, дает при делении на четыре остаток, равный 1, т. е. является числом вида t = 4k + 1. Действительно, пусть t = х2 + + у2, тогда одно из чисел, скажем, х, должно быть четным, другое — у — нечетным. Пусть х = 2т и у = 2п + 1. Тогда x2 = 4/л2 и у2 = 4 (п2 + п) + 1 и, окончательно," t = 4 (m2 + п2 + п) + 1, что и доказывает наше утверждение. Таким образом, числа 7, 11, 15 и др. непредставимы в виде суммы двух квадратов и не являются, следовательно, нормами гауссовых чисел.

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

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

Мы будем говорить, что целое гауссово число а делит целое гауссово число ß — и записывать этот факт через а I ß—если для некоторого целого гауссова числа у имеет место равенство

ß = a- v- (3)

Так как из (3) следует N (ß) = N (а) • N (у), то необходимым условием для a|ß является делимость N(a)\N (ß), тде N (а) и N (ß) — целые рациональные числа.

В случае целых рациональных чисел имеются только два числа, которые делят все целые числа: +1 и —1: в случае целых гауссовых чисел таких чисел имеется четыре:

+ 1, —1, -H, —i. Сразу видно, что указанные четыре числа этим свойством обладают. Действительно,

а = а • 1,

сс = (-а) • (-1),

а = (—ai) • i,

а = (ai) • (—i).

Других чисел с данными свойствами среди целых гауссовых чисел нет. Действительно, если некоторое целое гауссово число I делит все целые гауссовы числа, то оно, в частности, должно делить число 1 (поэтому такие числа называются делителями единицы). Из N (£)| 1 следует, что N (I) — 1. Если \ = X + yi, то х2 + у2 = 1. Очевидно, что это уравнение имеет в целых рациональных числах в точности четыре решения: х = 1, у = 0; х = —1, у = 0; х = 0, у = 1; X = 0, у = — 1.Эти четыре решения как раз и соответствуют целым гауссовым числам +1, —1, i, —i.

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

Определение 5. Целое гауссово число я называется простым, если в любом его разложении я = т • о в произведение двух целых гауссовых чисел один из сомножителей (т или о) является делителем единицы (при этом делители единицы простыми числами не считаются).

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

Согласно этому определению простыми гауссовыми числами будут, например, числа nt = 2 + i (N (ях) = 5), п2 = 3 + 2i (N (я2) =13). Вообще, простыми числами будут все числа, нормы которых являются простыми рациональными числами. В дальнейшем мы увидим, что этими примерами простые гауссовы числа не исчерпываются. В ходе наших исследований мы опишем все простые гауссовы числа.

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

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

а = Я!-я2... ftfc (4)

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

а = ai- (т2... Oi (5)

— другое разложение числа а в произведение простых гауссовых чисел а/, то оба разложения обладают одним и тем же числом сомножителей, k= I, и разложения (4) и (5) могут отличаться друг от друга только порядком следования сомножителей и множителями, являющимися делителями единицы.

Относительно части формулировки, касающейся однозначности разложения, сделаем еще одно замечание. Если, скажем,

OL = jxj[ • Я2 • зх3

— произведение простых чисел яь я2, я3, то, например,

а = (—я3) • (ш2) • (uii) (= п{ • я2 • я3)

— «другое» представление числа а в виде произведения простых чисел—я3, /я2, inu отличных от простых чисел я1э я2, я3. Однако легко заметить, что любое из чисел —я3, in2, iit\ получается умножением какого-то из чисел яь я2, я3 на некоторый делитель единицы; при этом изменен также первоначальный порядок чисел. Такие различия в разложениях одного и того же числа допускаются. Вторая часть формулировки теоремы как раз и утверждает, что подобного рода различными разложениями неоднозначность представления исчерпывается. Это обстоятельство ничем не отличается от ситуации в арифметике целых рациональных чисел. Оно лишь усложняется тем, что в случае арифметики целых гауссовых чисел мы располагаем большим числом делителей единицы1). Утверждение об однозначности

1) Отметим, что однозначность разложения с точностью до знаков сомножителей, о которой шла речь в случае целых рациональных чисел, и означает как раз однозначность с точностью до множителей, являющихся делителями единицы, так как +1 и —1—единственные делители единицы в этом случае.

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

Определение 6. Два целых гауссовых числа называются ассоциированными, если они отличаются друг от друга на сомножитель, равный делителю единицы, т. е. ß, —ß, iß, —iß — ассоциированные целые гауссовы числа, если ß — произвольное целое гауссово число.

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

Если сс = Л{ • я2... nk и а = at • а2... oh где m (i = = 1,2,..., k) и Oj (/=1,2,..., /) — простые числа, то I = k и сомножители 07 можно так переставить, что каждое о} будет ассоциировано с соответствующим простым числом Я/.

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

Первое утверждение теоремы —о существовании разложения — можно провести индукцией по норме числа:

а) ЕслиМ(а)= 1,тоа=1,—1, i, —i, т. е. число а разложимо в произведение пустого множества простых чисел1).

б) Пусть N (а) = я, a для всех целых гауссовых чисел с меньшей нормой утверждение уже доказано. Тогда или а — простое число и все доказано, или а = р • т, где N (р) <я и N (т) <^ п. По предположению индукции, для р и % разложения существуют: р = nt • я2... nk и т = аА • а2... аь тогда а = щ • я2... я* • а4 • а2...а/ — разложение для а.

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

Пусть а, ß (ß =f= 0) — два целых гауссовых числа, тогда существуют такие целые гауссовы числа у и р, причем N (Р) < N (ß), что

а = у • ß + р.

1) Относительно «разложимости» делителей единицы в произведение простых сомножителей мы принимаем то же соглашение, что и для ± 1 в случае целых рациональных чисел; см. стр. 7.

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

Из этого простого утверждения теперь сразу же видно, что для любой точки т комплексной плоскости найдется точка у с целыми координатами — точка, представляющая целое гауссово число,— отдаленная от т меньше, чем на 1 (рис. 2). Иначе говоря, для всякого комплексного числа т существует такое целое гауссово число уу что N (т — Y) <С < 1. Найдем такое у для числа т = a/ß и положим р = = a — vß. Тогда р — целое гауссово число,

iV(p) = ^(ß).^V (-g--r)<^V(ß)

и

a = vß + p. Утверждение доказано.

Имея уже теорему о делении с остатком, все остальные свойства можно доказать так же, как мы это делали выше в случае рациональных чисел: 1) доказывается существование НОД двух целых гауссовых чисел a, ß как числа ô =j= О

Рис. 2.

с наименьшей нормой из множества чисел, представимых в виде а£ + ßr] (£ и т] — целые гауссовы числа), 2) вводится понятие взаимно простых гауссовых целых чисел и доказывается основная лемма: если а взаимно просто с ßA и а взаимно просто с ß2, то а взаимно просто с ßA • ß2. Затем уже совсем просто индукцией по норме доказывается однозначность разложения на простые сомножители.

§ 5. ПРОСТЫЕ ГАУССОВЫ ЧИСЛА И ПРЕДСТАВЛЕНИЕ ЦЕЛЫХ РАЦИОНАЛЬНЫХ ЧИСЕЛ В ВИДЕ СУММЫ ДВУХ КВАДРАТОВ

Перейдем теперь к описанию всех простых гауссовых чисел. Докажем сначала несколько вспомогательных утверждений — лемм.

Лемма 1. Всякое простое гауссово число является делителем простого рационального числа1).

Действительно, так как N (а) = а - ät то всякое целое гауссово число делит свою норму, а \ N (ос). Пусть теперь я — простое гауссово число, тогда n\N (я), и пусть N (я) = = pi • р2... Рг — разложение числа N (я) в произведение простых рациональных чисел. Имеем: я| /vp2... р0 следовательно, я делит одно из простых чисел pi. Действительно, если бы простое целое гауссово число я не делило бы ни одно из чисел р,-, то оно было бы взаимно просто с каждым из них, а следовательно, и с их произведением N (я). Но это невозможно, так как n\N (я). Итак, число я является делителем одного из простых целых рациональных чисел piy — и лемма доказана.

Лемма 2. Норма N (я) простого гауссова числа я является или простым рациональным числом или квадратом простого рационального числа.

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

1) Заметим, что простое рациональное число является всегда и целым гауссовым числом, но как гауссово число оно не обязательно простое, а может делиться на целые гауссовы числа с меньшей нормой. Так, например, число 2 — простое, если его рассматривать как целое рациональное число, но оно не простое, если его рассматривать как целое гауссово число. Действительно, в области целых гауссовых чисел число 2 допускает разложение 2 = (1 + i) • (1 — t) и ни один из сомножителей 1 + i и 1 — t не является делителем единицы. Очевидно, что и 5 не является простым в области гауссовых чисел, так как 5 = (2 + i) (2— i).

к нормам: N (п) - N (у) = р2. Возможны только два случая: 1) N (я) = N (у) = р и 2)N (я) = p2 = N (р), а N (у) = 1. Лемма доказана.

Случай 2) означает, что у — делитель единицы и что справедливо одно из равенств: я = р, я = — р, я = ip, я = — ip. Следовательно, р — такое простое рациональное число, которое одновременно является и простым гауссовым числом. В случае 1) 7 — простое гауссово число, так как N (у) = р. Можно утверждать, что у = я. Действительно, N (я) = р = я • я и я — простое число. Но мы имеем также р = я • у, так что я = у.

С другой стороны, пусть р — какое-либо простое рациональное число, тогда, если оно не является простым гауссовым числом, то оно делится на какое-либо простое гауссово число, отличное от р, и при этом, как мы видели, р= = я • я, т. е. р является произведением двух простых гауссовых комплексно сопряженных чисел. В этом случае р является нормой целого гауссового числа и, следовательно, представимо в виде суммы двух квадратов. Такое простое число, если оно нечетное (т. е. р =f= 2),— число вида 4п + 1. Можно показать, что все простые числа вида An + 1 представимы в виде суммы двух квадратов, т. е. являются нормами некоторых целых гауссовых чисел, а потому не являются простыми гауссовыми числами и, следовательно, принадлежат к классу тех простых рациональных чисел, которые разложимы в произведение двух комплексно сопряженных простых гауссовых чисел. Доказательство этого утверждения мы приводить не будем1). Все простые рациональные числа, отличные от чисел вида 4п + 1 и от числа 2, т. е. числа вида 4п + 3, и составляют как раз множество простых рациональных чисел, остающихся простыми и в области гауссовых чисел.

Несколько особое положение занимает простое число 2. Легко видеть, что

2 = i . (1 — О2,

N (1 — i) = 2. Таким образом, 2 делится на квадрат простого гауссова числа (1 — i).

1) Доказательство этого факта, основанное на теории сравнений и восходящее к Л. Эйлеру, можно найти почти во всех учебниках по теории чисел. Особенно подробно оно изложено в книге [3] из приведенного в конце брошюры списка литературы.

Предполагая известным, что все простые числа вида An + 1 представимы в виде суммы двух квадратов, мы можем теперь установить, каковы все целые рациональные числа, представимые в виде суммы двух квадратов. Как мы уже знаем, для всякого числа t с таким свойством необходимо и достаточно, чтобы оно было нормой некоторого целого гауссового числа a: t = N (а). Число а разлагается в произведение простых гауссовых чисел:

(X = • Яг*-* (6)

Разобьем все простые числа щ (i = 1, 2,..., г) на два класса: в первый класс соберем те числа л/, нормы которых — простые числа, а во второй, соответственно, числа, нормы которых — квадраты простых чисел1). Обозначим различные числа первого класса через <Х/ (/ = 1, 2,..., /), а все различные числа второго класса — через pk(k = 1, 2,..., s). Имеем: N (of} = pj9 N (pk) = ql> где р,- — простое число вида An + 1 или 2, a qk — простое число вида 4п + 3. Объединяя равные простые числа в правой части (6), запишем это произведение в виде степеней простых чисел а; и pk

а = аГ'...а;'.р*'...р5\ (7)

и, переходя к нормам, имеем

N{a) = t=N (a?) ...N (в"1) . N (pf1) ...N (p*s),

t = p°*.. .patlq2^ .. .q*bs. (8)

Мы видим, что простые числа qk входят в разложение числа t в четных степенях. Обратно, пусть число t представимо в виде (8), где каждое ру- — простое число вида An + 1 или число 2, qk — простые числа вида An + 3 и fli,..., а/, bs — целые неотрицательные числа. Тогда, поскольку каждое ру является суммой двух квадратов, можно подобрать оу так, чтобы N (of) = р/. Положив, далее, pfe = ^ и, наконец, а = . . . а^-р*1.... ps4 получим t = N (а), т. е. / представимо в виде суммы двух квадратов. Окончательно имеем следующую теорему:

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

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

необходимо и достаточно, чтобы простые числа вида 4/г+З входили в разложение этого числа на простые сомножители в четных степенях1).

Как мы видим, эта теорема дает критерий того, чтобы диофантово уравнение второй степени вида

X2 + у2 = t

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

ах2 + 2Ьху + су2 = t

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

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

§ 6. ЕЩЕ ОДНА «АРИФМЕТИКА»

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

а = х + уУ'=^^ (1)

где л: и — цельте рациональные числа. Легко видеть, что сумма, разность и произведение чисел вида (1) опять являются числами такого же вида. Обозначим совокупность всех чисел вида (1) через Г. Очевидно, что Г содержит все целые рациональные числа (при у=0). Так же как в случаях целых рациональных и целых гауссовых чисел, можно говорить о делимости в Г: а делит ß (а | ß), если ß/а — опять число из Г, т. е. представимо в виде (1). Как и в случае целых гауссовых чисел, в вопросе делимости важную роль играют нормы чисел из Г:

N(a) = N(x + yV=E)= (х + у У-5)(х-уУ-Б) = х* + Ьу*.

Таким образом, норма всякого числа из Г есть целое рациональное число и, так как N (£-т)) = N (£)•# (л). то необходимым (но вообще говоря, не достаточным) условием для a|ô является условие N(a)\ |АУ(Р)._

1) Такая формулировка охватывает и случай, когда простых чисел вида 4п + 3 нет в разложении рассматриваемого числа, — ведь число О также является четным!

Так же как и в случае целых гауссовых чисел, естественно вводится понятие делителей единицы и простых чисел. В отношении делителей единицы дело обстоит здесь даже проще, чем для целых гауссовых чисел. А именно, делителями единицы являются только числа ±1. Действительно, для делителей единицы £ = и + v Y—5 должно выполняться условие N (£) = и2 + 5v2 = 1. Но это диофантово уравнение, очевидно, не может иметь решений, отличных от и = = ± 1 и о = 0.

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

Покажем сначала, что числа 2 = 2 + 0-1^—5, 3 = 3 + 0* Y —5, 1 + Y—5, 1 Y—5 —простые числа в Г. Действительно, N(2) = = 4, #(3)=9, N(1+ У=5)= (1— У=Ч5) = 6. Если бы одно из этих чисел не было простым в Г, то оно могло бы делиться только на некоторое число а = х + у Y—5, для которого N (а) = х2 + 5у2= = 2 или N (а) = X2 + by2 == 3. Но таких чисел в Г нет, так как очевидно, что уравнения

х2 + Ъу2 = 2 (2)

х2 + Ъу2=3 (3)

не имеют целочисленных решений.

Итак, указанные четыре числа — простые числа в Г. Отметим теперь легко проверяемое равенство

в = 2-3 = (1+ /=5) (1- У=5). (4)

Оно показывает, что число 6 из Г имеет два различнык представления в виде произведения простых чисел.

С отмеченным явлением столкнулся немецкий математик Э. Куммер (1810—1893) при своих попытках решить так называемую великую теорему Ферма. В дальнейшем трудности, возникающие в связи с невыполнением основной теоремы арифметики в некоторых важных областях чисел, были успешно преодолены как самим Куммером, так и другими математиками — Р. Дедекиндом, Е. Золотаревым, Л. Кронекером и др. Возникла большая новая область в математике — теория алгебраических чисел, которая успешно развивается вплоть до наших дней.

ЛИТЕРАТУРА

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

1. А. Я. Хинчин, Элементы теории чисел, Энциклопедия элементарной математики, кн. I, Арифметика, Гостехиздат, 1951.

Эта статья крупного советского математика А. Я. Хинчина написана с большим мастерством и может быть рекомендована как учителям, так и школьникам старших классов. Глава I «Делимость и простые числа» содержит, в частности, подробное доказательство основной теоремы арифметики. Глава II «Метод сравнений» является, на наш взгляд, одним из лучших введений в теорию сравнений — раздел теории чисел, имеющий очень большое число приложений как в арифметике, так и в современной алгебре.

2. А. И. Маркушевич, Деление с остатком в арифметике и в алгебре (сер. «Педагогическая библиотека учителя»), изд. Академии педагогических наук РСФСР, 1949.

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

3. Г. Дэвенпорт, Высшая арифметика, «Наука», 1965.

Подзаголовок книги «Введение в теорию чисел» уже указывает на то, что в ней дается систематическое изложение начал этой области. Написана она крупным английским специалистом по теории чисел. Книга Дэвенпорта не предполагает познаний, выходящих за пределы школьной математики. Она особенно может быть рекомендована студентам-математикам младших курсов, но доступна и не математикам. От последних, правда, потребуются некоторые навыки для хорошего понимания изложения. Для читателей нашей брошюры, несомненно, интересной будут глава II «Сравнения», а также глава V «Суммы квадратов», в которой дается полное доказательство представимости простых чисел вида An -f 3 в виде суммы двух квадратов.

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

4. И. Н. Виноградов, Основы теории чисел, «Наука», 1965.

5. И. В. Арнольд, Теоретическая арифметика, Учпедгиз, 1939.

6. А. А. Бухштаб, Теория чисел, «Просвещение», 1966.

7. Г. Хассе, Лекции по теории чисел, ИЛ, 1953.

Цена 5 коп.

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

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

Вып. I.A. И. Маркушевич. Возвратные последовательности.

Вып. 2. И. П. Натансон. Простейшие задачи на максимум и минимум.

Вып. 3. И. С. Соминский. Метод математической индукции.

Вып. 4. А. И. Маркушевич. Замечательные кривые.

Вып. 5. П. П. Коровкин. Неравенства.

Вып. 6. H. Н. Воробьев. Число Фибоначчи.

Вып. 7. А. Г. Курош. Алгебраические уравнения произвольных степеней.

Вып. 8. А. О. Гельфонд. Решение уравнений в целых числах

Вып. 9. А. И. Маркушевич. Площади и логарифмы.

Вып. 10. А. С. Смогоржевский. Метод координат.

Вып. 11. Я. С. Дубнов. Ошибки в геометрических доказательствах.

Вып. 12. И. П. Натансон. Суммирование бесконечно малых величин.

Вып. 13. А. И. Маркушевич. Комплексные числа и конформные отображения.

Вып. 14. А. И. Фетисов. О доказательствах в геометрии

Вып. 15. И. Р. Шафаревич. О решении уравнений высших степеней

Вып. 16. В. Г. Шерватов. Гиперболические функции.

Вып. 17. В. Г. Болтянский. Что такое дифференцирование?

Вып. 18. Г. М. Миракьян. Прямой круговой цилиндр.

Вып. 19. Л. А. Люстерник. Кратчайшие линии.

Вып. 20. А. М. Лопшиц. Вычисление площадей ориентированных фигур

Вып. 21. Л. И. Головина и И. М. Яглом. Индукция в геометрии.

Вып. 22. В. Г. Болтянский. Равновеликие и равносоставленные фигуры

Выи. 23. А. С. Смогоржевский. О геометрии Лобачевского.

Вып. 24. Б. И. Аргунов и Л. А. Скорняков. Конфигурационные теоремы.

Вып. 25. А. С. Смогоржевский. Линейка в геометрических построениях.

Выи. 26. Б. А. Трахтенброт. Алгоритмы и машинное решение задач.

Вып. 27. В. А. Успенский. Некоторые приложения механики к математике.

Вып. 28. Н. А. Архангельский и Б. И. Зайцев. Автоматические цифровые машины.

Вып. 29. А. Н. Костовский. Геометрические построения одним циркулем.

Вып. 30. Г. Е. Шилов. Как строить графики.

Выи. 31. А. Г. Дорфман. Оптика конических сечений

Вып. 32. Е. С. Вентцель. Элементы теории игр.

Вып. 33. А. С Парсов. Что такое линейное программирование.

Вып. 34. Б. Е. Маргулис. Системы линейных уравнений.

Вып. 35. Н. Я. Виленкин. Метод последовательных приближении

Вып. 36. В. Г. Болтянский. Огибающая.

Вып. 37. Г. Е. Шилов. Простая гамма (устройство музыкальном шкалы).

Вып. 38. Ю. А. Шрейдер. Что такое расстояние^

Вып. 39. H. Н. Воробьев. Признаки делимости

Выи. 40. С. В. Фомин. Системы счисления.

Вып. 41. Б. Ю. Коган. Приложение механики к геометрии.

Вып. 42. Ю. И. Любич и Л. А. Шор. Кинематический метод в геометрических задачах.

Вып. 43. В. А. Успенский. Треугольник Паскаля

Вып. 44. И. Я. Бакельман. Инверсия.

Вып. 45. И. М. Яглом. Необыкновенная алгебра

Вып. 46. И. М. Соболь. Метод Монте-Карло.

Вып. 47. Л. А. Калужнин. Основная теорема арифметики