2.2. Наибольшие общие делители целых чисел

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

2.2.1. Делимость целых чисел

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

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

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

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

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

Одно из основных свойств целых чисел — это свойство делимости или евклидовости, которое хорошо известно из арифметики.

Теорема 2.2.1 (свойство евклидовости). Для любого а и любого ненулевого b существуют единственные (целые) частное q и остаток , такие, что

Доказательство. Рассмотрим множество целых чисел вида , где k пробегает все множество целых чисел, положительных и неположительных; т.е. рассмотрим прогрессию

Выберем в этой последовательности наименьшее неотрицательное число и обозначим его , и пусть q обозначает соответствующее

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

Для доказательства единственности допустим, что

и что . Пусть для определенности , так что тогда

что противоречит неравенствам

Определение 2.2.2. Пусть a и b одновременно не равны нулю. Целое число называется наибольшим общим делителем а и b, если

Наибольший общий делитель чисел а и b обозначается через или b). Последнее обозначение можно спутать с парой чисел, поэтому его смысл должен определяться из контекста. Единственность наибольшего общего делителя следует из свойства b в определении и того, что он положителен: если d — другой наибольший общий делитель, то по свойству поэтому поскольку оба положительны. Например, Наибольший общий делитель двух целых чисел, одновременно не равных нулю, всегда существует и мажет быть представлен в следующем виде.

Теорема 2.2.3 (существование ). Если а и b одновременно не равны нулю, то существуют целые числа х и у, такие, что .

Доказательство. Пусть d — наименьшее положительное целое число вида например, где не обязательно определены однозначно. (Как и в доказательстве теоремы 2.2.1, существование такого d следует из полной упорядоченности.) Очевидно, что и d обладает свойством b из определения 2.2.2. От противного мы докажем, что d обладает также свойством а.

Допустим, что свойство а не выполняется, и предположим для определенности, что d не делит b. Тогда и, следовательно, что противоречит минимальности

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

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

Теорема 2.2.4. Рассмотрим уравнение в котором a и b не равны нулю одновременно, и пусть . Тогда

a. Уравнение разрешимо относительно тогда и только тогда, когда .

b. Если — частное решение, то все решения имеют вид для всех .

Доказательство. Мы докажем только часть а, оставив часть b читателю в качестве упражнения. Предположим, что х и у — целые числа, такие, что тогда, так как , то с. Предположим теперь, что с, т.е. для некоторого целого k. По теореме 2.2.3 существуют целые числа s, t, такие, что Умножая это равенство на к, получим откуда следует, что удовлетворяют уравнению

Пример: уравнение разрешимо, поскольку Одним его решением является пара , а все остальные имеют вид

Два целых числа а и b называются взаимно простыми, если По теореме 2.2.3 это эквивалентно существованию целых чисел s, t, таких, что Справедлива следующая теорема.

Теорема 2.2.5. Пусть целые числа а и b не равны нулю одновременно, и пусть . Тогда взаимно просты.

Доказательство. По теореме 2.2.3 существуют целые числа s, t, такие, что Разделив на d, получим что влечет за собой

Теорема 2.2.6. Пусть — целые числа и . Если а делит то делит с.

Доказательство. Если , то . Однако по теореме и по теореме 2.2.3 существуют целые числа s, t, такие, что умножив это равенство на с, получим . Поскольку делит оно делит с.

Определение 2.2.7. Пусть a и b — ненулевые целые числа. Целое число называется наименьшим общим кратным чисел a и b, если

Наименьшее общее кратное чисел a и b обозначается через или Единственность наименьшего общего кратного следует из части b и положительности .

Теорема 2.2.8 (существование ). Если a и b — ненулевые числа, то их наименьшее общее кратное существует и справедливо равенство

Доказательство. Так как a и b не равны нулю, их наибольший общий делитель отличен от нуля. Из равенства и того, что числа целые, следует, что — положительное общее кратное чисел a и b. Пусть — любое другое общее кратное чисел a и b; тогда для некоторых целых чисел s, t. Поскольку , то по теореме для некоторого целого числа . Из равенства вытекает, что , поэтому — наименьшее общее кратное чисел a и b. Как уже упоминалось выше, единственность следует из части b определения 2.2.7 и того, что положительно.