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

DjVu

      ВВЕДЕНИЕ
      Принято считать, что арифметика предшествует алгебре, что это более элементарная часть математики. В школе арифметике учат начиная с первого класса, а алгебре — только с пятого. Так как подавляющее большинство людей знает о математике главным образом то, что они услышали в школе, то мнение об элементарности арифметики глубоко укоренилось. Между тем арифметика, если ее понимать как учение о свойствах целых чисел и о действиях над ними, — трудный и далеко не элементарный раздел математики. Прайда, в таком общем понимании этот раздел принято скорее называть высшая арифметика» или «теория чисел», чтобы противопоставить его школьной арифметике. Го эти названия не должны затемнять суть дела. А она состоит в том, что и школьная арифметика и высшая арифметика относятся к одной и той же области знания. На мой взгляд, было бы очень полезно, если бы школьники старших классов, имеющие склонность к математике, углубляли тот набор знаний, который они приобрели в младших классах. Такое углубление необходимо, впрочем, и для того, чтобы в дальнейшем познакомиться с высшей арифметикой. Цель нашей брошюры — помочь в этом деле.
      В качестве отправного пункта мы рассмотрим так называемую основную теорему арифметики. Это несколько наукообразное название не должно отпугивать: все эту теорему хорошо знают и при арифметических вычислениях часто ею пользуются (например, при нахождении общего знаменателя дробей), не сознавая порой того, что это — глубокая теорема, требующая внимательного и подробного доказательства. Поясним, о чем идет речь;
      Каждое целое число мы умеем раскладывать в произведение простых чисел. Например,
      420 = 2-2-3-5-7. (1)
      При этом, если число достаточно велико, для нахождения соответствующего разложения нужно иногда потратить немало времени. Тем не менее, во всех случаях мы это разложение при желании всегда устанавливаем. Но, может быть, нам до сих пор просто везло? Уверены ли мы в том, что произвольное целое число можно всегда представить в виде произведения простых чисел? Это действительно так, но этот факт требует доказательства. Первую часть основной теоремы как раз и составляет утверждение:
      Всякое целое число может быть представлено в виде произведения простых чисел.
      Доказательство этого утверждения приводится в брошюре. Впрочем, оно довольно простое и читателю было бы полезно провести его самостоятельно. Труднее доказывается второе утверждение теоремы (которое, однако, в школе считают очевидным). Прежде чем переходить к его формулировке, обратимся опять к рассмотренному выше примеру разложения числа 420 на простые сомножители. Процедура, хорошо известная со школы и схематически изображающаяся так:
     
      как раз и дает разложение (1). Но может быть существуют и другие методы разложения? Как знать, дадут ли они тот же результат. Естественно, например, пытаться разложить данное число в произведение двух меньших чисел (не обязательно взаимно простых), а затем каждое из них — в произведение меньших чисел и т. д., до тех пор, пока мы не придем к числам, уже не разложимым далее (т. е. к простым). Однако уже из первого шага ясно, что такой процесс неоднозначен. Действительно, например, для того же числа
      420 имеем:
      420 = 20-21, 420= 15-28.
      Таким образом, совершенно естествен вопрос: быть может существуют целые числа, которые можно разложить различными способами в произведение простых чисел? Оказывается, что таких целых чисел нет, и соответствующее утверждение — утверждение об однозначности разложения числа в произведение простых сомножителей — составляет как раз вторую часть основной теоремы:
      Если некоторое целое число п разложено двумя способами в произведение простых сомножителей
      п = PiPz---Pk = qi-qz-.-qi,
      то эти разложения совпадают с точностью до порядка сомножителей: оба они обладают одним и тем же числом сомножителей, k = I, и каждый сомножитель, встречающийся в первом разложении, встречается столько же раз во втором рйзложении *).
      Доказательство этого утверждения мы приведем довольно подробно. Оно, как уже отмечалось, существенно труднее, чем доказательство первого утверждения. Эта трудность не случайна, а связана с глубокими свойствами арифметики целых чисел. Оказывается, что наряду с этой привычной арифметикой существуют, и очень полезны, многочисленные другие «арифметики». В одних арифметиках утверждения основной теоремы справедливы, в других — нет, причем не выполняется как раз утверждение об однозначности разложения. Мы приведем примеры арифметик как первого, так и второго рода.
      Более подробно мы рассмотрим одну арифметику первого рода — арифметику целых комплексных чисел, или, как их обыкновенно называют, целых гауссовых чисел. Отметим, кстати, что обычные целые числа (чтобы не спутать их с целыми гауссовыми числами) мы будем иногда называть целыми рациональными числами. Однако там, где это не может вызвать недоразумений, мы будем
      х) Если рассматривать произвольные целые числа (как положительные, так и отрицательные), то под единственностью разложения на простые множители следует понимать, что два разложения п = рх р2...... рккп= Qi могут отличаться не только порядком сомножите-
      лей, но н знаками соответствующих сомножителей; см. § 1 — формулировку основной теоремы.
      говорить просто о целых числах, имея в виду целые рациональные числа. В арифметике целых гауссовых чисел основная теорема также выполняется и ее выполнимость влечет за собой целый ряд интересных и далеко не очевидных свойств целых рациональных чисел
      В конце брошюры мы приведем пример арифметики, в которой основная теорема не выполняется: правда, рассматриваемые там числа можно разложить в произведение простых сомножителей, но при этом может оказаться, что простые числа, встречающиеся в двух разложениях, различны. Более детально мы не будем исследовать эту арифметику: это потребовало бы введения ряда новых понятий и изучения их свойств, что возможно только в рамках серьезного университетского курса.
      Для понимания нашего изложения читателю не потребуется познаний, отличных от тех, которые излагаются в школьном курсе математики, за одним важным исключением. При доказательстве теорем мы будем широко пользоваться методом математической индукции 4). Этот центральный для математики метод, к сожалению, редко рассматривается в школе. Подробное обоснование и пояснение этого метода завело бы нас слишком далеко от нашей темы. Читателю, который хочет познакомиться с методом доказательства по индукции, мы можем порекомендовать брошюру И. С. Соминского «Метод математической индукции», вышедшую в серии «Популярные лекции по математике», либо книгу И. С. Соминского, Л. И. Головиной и И. М. Яглома «О математической индукции» («Наука», 1967).
      В конце брошюры мы укажем некоторые книги, излагающие в доступной форме теоретико-числовые факты, более или менее тесно примыкающие к изучаемому здесь вопросу.
     
      § 1. ОСНОВНАЯ ТЕОРЕМА АРИФМЕТИКИ.
      ДОКАЗАТЕЛЬСТВО ПЕРВОЙ ЧАСТИ
      Дадим единую формулировку для высказанных во введении утверждений, т. е. сформулируем полностью основную теорему арифметики.
      Всякое целое число, отличное от нуля, мо жет быть представлено в виде произведения простых чисел, причем такое
      *) Иногда ее называют также «полной индукцией».
      представление единственно с точностью до порядка сомножителей и их знаков.
      Как уже говорилось, указанная теорема содержит два утверждения: во-первых, утверждение о существовании представления произвольного числа в виде произведения простых чисел, и во-вторых, утверждение о единственности такого представления. Оба утверждения будут нами доказаны: в настоящем параграфе — только первое из них. Предварительно сделаем два простых замечания.
      1. Число 1 по многим причинам не принято считать простым числом, несмотря на то, что оно не разложимо в произведение меньших чисел. Тогда возникает вопрос: в каком же смысле указанная выше теорема верна для числа 1? Или, иначе, в каком смысле 1 представима в виде произведения простых чисел? Математика, в отличие, скажем, от грамматики, не любит исключений. Мы будем считать, что
      1 = 1
      и есть разложение числа 1 в произведение простых чисел, причем число простых сомножителей в правой части равно 0. Эта условность напоминает определение нулевой степени а0 = 1 (число сомножителей а равно 0) и во многих отношениях удобно. Подобное соглашение мы принимаем и для числа — 1.
      2. В качестве второго замечания мы просто приведем пример, поясняющий понятие однозначности разложения целого числа на простые сомножители. Два разложения числа 18
      18 = 2-3-3
      и
      18= (-3)- ( — 2) 3
      мы считаем неразличимыми.
      Доказательство существования разложения целого рационального числа в произведение простых чисел. Ограничимся сначала случаем положительных целых чисел. Возможность их разложения на простые сомножители доказывается методом математической индукции