Глава I

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

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

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

утверждение:

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

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

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

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

,420 = 20.21, 420 = 15 . 28.

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

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

« = . Pk = q^ qi,

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

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

• 1. ДЕЛЕНИЕ С ОСТАТКОМ И НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ (НОД) ДВУХ ЧИСЕЛ

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

¹ Если рассматривать любые целые числа (как положительные, так и отрицательные), то под единственностью разложения на простые множители следует понимать, что два разложения п = p_Yp₂ . p_k an — q_Yq₂ qi могут отличаться не только порядком сомножителей, но и знаками соответствующих сомножителей.

Тогда b (q_t — q₂) = r₂ — f\. Так как 0 < r_z < | b |, то разность г₂ — r_t по абсолютной величине будет меньше, чем | b | и, следовательно, деление на b здесь возможно лишь при условии, что г_а—= 0. Но если г\ = г₂, то q_{b = q₂b и, таким образом, q_t = q₂.

Число 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. Для любой пары целых чисел а =£ Q и b =£ + 0 существует НОД.

Доказательство. Наряду с числами а и b мы будем рассматривать всевозможные числа вида ха 4- yb, где х и у какие-либо целые числа. Числа такого вида: о == ха 4- yb (2)

называют линейными комбинациями чисел а и Ь. Например, для а = 6, b = 22 линейными комбинациями будут числа 28 = 1 . 6 + 1 22, 10 = (—2) -6+1-22, —92 = = 3.6 + (—5) .22 ит. д. Вообще для заданных чисел а и b существует бесконечно много чисел, являющихся их линейными комбинациями. Обозначим множество таких чисел через М. Заметим, что множество М содержит,

в частности, и сами числа а (при х~ 1, у — 0) и b (при х = 0, у = 1), а также число 0 (при х = 0, у = 0). Все числа v из множества М являются, очевидно, целыми числами. Если v принадлежит М, то и —v тоже принадлежит М (если v = ха 4- yb, то — v = (—х) а + (—у) Ь). Отметим еще одно свойство чисел v из М, которое мы будем использовать: все эти числа делятся на все общие

делители чисел а и Ь. Действительно, если с | а и с | b и

пусть а — а' с и b — Ь' с, то v = ха 4- yb -- ха'с 4- yb'c =

= (ха + yb') с, т. е. с | о. Пусть теперь d =£ 0 — наимень

шее по модулю число среди всех чисел из М, отличных от 0.

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

Покажем, что d является НОД чисел а и Ь. Свойством 2) определения НОД оно обладает, так как им обладают все числа из М. Нужно только еще установить, что оно обладает и свойством 1), т. е. что d является общим делителем чисел а и Ь. Покажем, что d | а. Так как d принадлежит Л4, то d — sa + tb, где s и t — целые числа. Разделим а на d с остатком, т. е. найдем такие числа q и г, 0 < г < | d |, что

а — qd + г.

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

г — а — qd = а —q (sa -f- tb) = (1 —qs) a 4- tb.

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

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

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

Возникает вопрос: определен ли НОД чисел а и b однозначно? Ответ, конечно, отрицательный: если число

d обладает свойствами 1) и 2) определения НОД, то и—d тоже ими обладает. Но этим неоднозначность исчерпывается. Действительно, пусть d и d'—два НОД чисел а и Ь. Так как d обладает свойством 2), ad'—свойством 1), d 1

то d'\d. Но аналогично, d\d'. Итак, а —и =

= 1 — целые числа. Но единственные целые числа, обратные от которых также целые,—это числа 1 и —1. Итак, а = 1 или а — —1, откуда d‘ — d или d' ~ —d. Если бы в определении НОД было условие, что это число должно быть положительным (это иногда бывает удобным), то можно было бы сказать, что НОД двух отличных от нуля целых чисел существует и однозначно определен.

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

теории чисел.

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

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

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

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

1 = sa + tb, (3)

где s и i — целые числа. Обратно, если равенство (3) выполняется для соответственных s и t, то а и b взаимно просты. Действительно (см. доказательство теоремы 1), d — (а, Ь) —это наименьшее по модулю число среди отличных от нуля чисел вида ха 4- yb. Следовательно, если (3) выполняется, то |d| < 1 и d =/= 0, так что d = ± 1. Из сказанного непосредственно вытекает важнейшее свойство взаимно простых чисел:

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

Доказательство. Так как (a, b) — 1, то найдутся такие числа s и /, что 1 = sa + tb.