II.Основы теории делимости

Элементарную теорию чисел следует считать наилучшим предметом для первоначального математического образования.

Годфри Харди

Введение

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

Числовые кольца редко бывают факториальными (гауссовыми), т. е. кольцами, в которых выполняется основная теорема арифметики [1, 4, 8, 11-13]. По идее немецкого математика Э. Куммера, в ряде случаев единственность разложения на неприводимые множители удается восстановить за счет добавления идеальных чисел (дивизоров); для таких колец существует теория дивизоров. К ним относятся дедекиндовы кольца, названные так по имени другого немецкого математика Р. Дедекинда, определившего понятие идеала кольца и развившего теорию дивизоров числовых колец на основе теории идеалов (вторая половина XIX века). В качестве идеальных чисел у Дедекинда выступали неглавные идеалы кольца. См. [1, 2, 11].

В первой половине XIX века в трудах К. Гаусса [5] была создана теория сравнений, развивающая и обогащающая понятие делимости [1, 8, 11, 13].

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

В самом общем и чистом виде делимость можно изучать в группоидах. Наиболее приспособленными для этого являются целые полугруппы [3, 7, 9, Приложение III].

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

Впервые свойства делимости изучались в кольце Z целых рациональных чисел (для натуральных чисел). Напомним основополагающие факты о делимости целых чисел.

Теорема о делении с остатком. Для любого целого числа a и любого ненулевого целого числа b существуют однозначно определенные целые числа q и r, такие, что a = bq + r и 0 < r < Ibl.

При этом a делится (нацело) на b, т. е. a = bq для некоторого целого числа q, тогда и только тогда, когда остаток r от деления a на b равен 0; говорят также, что a кратно b, b - делитель a или b делит a (b | a).

Проиллюстрируем эту теорему на числах a и b с |a| = 23 и |b| = 7. Имеем следующие случаи:

1)  23 = 7-3 + 2,

2)  -23 = 7-(-4) + 5,

3)  23 = (-7)(-3) + 2,

4)  -23 = (-7)(-4) + 5.

Случаи 3) и 4) получаются из 1)

и 2) соответственно. Для наглядности возьмем окружность длины 7 и разделим ее на 7 равных частей. Точки деления обозначим по часовой стрелке числами 0, 1, 2, 3, 4, 5, 6 - это всевозможные остатки при делении на 7. Затем берем отрезок длины 23, закрепляем один его конец в точке окружности с риской 0 и наматываем этот отрезок на окружность по часовой стрелке. Тогда другой конец отрезка укажет число 2 - остаток, а число 3 полных оборотов есть неполное частное от деления 23 на 7 (случай 1)). При делении - 23 на 7 наматываем отрезок против часовой стрелки - в результате получаем случай 2).

Элементарные свойства отношения делимости приведены в § 2.

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

a = bq1 + r1, 0 < r1 < |b| b = rq + r2, 0 < r2 < Г1 Г1 = r2q3 + Г3, 0 < Г3 < Г2

rn-2 = rn-1qn + rn, 0 < rn < rn-1 rn-1 = rnqn+1.

Поскольку натуральные остатки строго убывают, то через конечное число делений (на n-м шаге, n < |b|) мы получим последний ненулевой остаток rn; в случае r1 = 0 имеем НОД(а, b) = |b|. С помощью этой схемы легко доказывается

Теорема об НОД. НОД(а, b) = rn.

Замечание 1. НОД целых чисел а и b можно определить двумя способами. Как наибольший по величине общий делитель этих чисел (тогда НОД не существует только для а = b = 0). Или как общий делитель чисел a и b, делящийся на любой их общий делитель (при этом НОД определен с точностью до знака и НОД(0, 0) = 0). Второе определение более общее, поскольку его можно дать для элементов произвольного группоида. Схема алгоритма Евклида показывает: если рассматривать только натуральные делители, то для любых двух целых чисел, одновременно не равных 0, оба определения НОД равносильны (дают один и тот же результат). Вопросы читателю. Верно ли это утверждение для любого непустого (возможно, бесконечного) семейства целых чисел? Как обстоит дело с наименьшим общим кратным (НОК) целых чисел?

Линейное представление НОД. НОД(а, b) = au + bv для подходящих целых чисел u, v. Причем, если числа а и b не делятся друг на друга, то числа u, v можно выбрать единственным образом так, чтобы jui < jb/di, fv/ < fa/d/ при d = НОД(а, b).

Линейное представление НОД(а, b) = rn можно получить из схемы алгоритма Евклида, двигаясь по ней снизу вверх. Другой подход дает

следующее утверждение: наименьшее натуральное число вида ах + by,

2 2

схема алгоритма Евклида

х, y eZ, является НОД(а, b) (при а + b Ф0).

В качестве иллюстрации применим алгоритм Евклида к числам a = 120 и b = - 33: 120 = (-3)(-33) + 21, - 33 = 21-(-2) + 9, 21 = 9-2 + 3, 9 = 3-3. Значит, Н0Д(120, - 33) = 3. Для нахождения линейного представления НОД будем последовательно выражать 3, начиная с предпоследнего равенства:

3 = 21 + (-2)-9 = 21 + (-2)-(-33 + 2-21) = (-2)(-33) + (-3)-21 = = (-2)(-33) + (-3)(120 + 3-(-33)) = 120-(-3) + (-33)(-11).

Рассмотрим теперь наглядную интерпретацию НОД и НОК двух натуральных чисел a < b. Возьмем правильные a-угольник и b-угольник, которые можно вписать в окружность единичного радиуса. Расположим их рядом на горизонтальной прямой (a-угольник левее) так, чтобы они касались друг друга вершинами А и B соответственно. Из этого положения начнем вращать многоугольники вокруг их центров: a-угольник - по часовой стрелке, b-угольник - против часовой стрелки. Сначала совершим один полный оборот, вращая многоугольники с одинаковой по величине угловой скоростью. При этом число касаний многоугольников, не считая исходного, равно НОД (a, b). Далее будем вращать многоугольники таким образом, чтобы они последовательно касались соседними вершинами (скорость вращения a-угольника в b/a раз больше скорости вращения b-угольника).

D

С

Вращение завершим, как только вершины А и B вернутся в первоначальное положение. Если при этом a-угольник совершил m полных оборотов, а b-угольник - п оборотов, то общее число am = bn касаний вершин равно НОК^, b). Заметим также, что a/n = b/m = НОД^, b).

На рисунке показаны правильные шестиугольник и восьмиугольник. При их вращении на 360° с равными скоростями многоугольники коснутся дважды - вершинами C и D, A и B. Если же вращать шестиугольник в 8/6 = 4/3 раза быстрее восьмиугольника, то вершины A и B снова совпадут при 24-м касании многоугольников, шестиугольник сделает 4 полных оборота, а восьмиугольник - 3 полных оборота.

Критерий взаимной простоты. Целые числа a и b взаимно просты тогда и только тогда, когда au + bv = 1 для некоторых целых чисел u, v.

Этот критерий позволяет легко доказать основные свойства взаимно простых чисел (т. е. чисел, НОД которых 1). Отметим два из них:

1)  если произведение целых чисел a и b делится на целое число d, взаимно простое с a, то b делится на d;

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

С помощью 1) выводится:

Формула для НОК. НОД(a, b)-НОК(a, b) = ab. Значит, если числа a и b не равны 0 одновременно, то НОК(a, b) = ab/НОД(a, b).

Так, НОК(120, - 33) = 120-(-33)/3 = - 1320 или 1320.

Далее определяются простые (имеют ровно 2 натуральных делителя) и составные числа. Все целые числа разбиваются на 4 класса: простые числа и противоположные им; составные и противоположные им; 1 и - 1; 0.

Существование простых делителей. Наименьший отличный от 1 натуральный делитель p целого числа a, iai>1, является простым числом. Причем, если iai ^p, то p <iai

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

Характеризации (критерии) простого числа. Для любого натурального числа p #1 эквивалентны следующие свойства:

(1)
p - простое;

(2)
если произведение двух целых чисел делится на p, то хотя бы одно из них делится на p;

(3)
каждое целое число либо делится на p, либо взаимно просто с

ним;

(4)
кольцо Zp классов вычетов по модулю p является полем;

(5)  число (p-1)! + 1 делится на p (критерий Вильсона).

Теорема Евклида. Простых чисел бесконечно много. Имеем ряд простых чисел p1 = 2, p2 = 3, p3 = 5, p4 = 7, p5 = 11, p6 = 13, p7 = 17, p8 = 19, p9 = 23, p10 = 29,. . Возьмем первые n простых чисел и рассмотрим число a = p1-p2-.-pn + 1. Существует наименьший простой делитель p числа a, он не равен ни одному из первых п простых чисел. Например, при п = 1 имеем p = a = 3, при п = 2 имеем p = a = 2-3 + 1 = 7, при п = 3 имеем p = a = 2-3-5 + 1 = 31 = p11, при п = 4 снова имеем простое число a = 211. А когда появляется первое составное число a?

Характеризация (2) позволяет доказать единственность в следующей теореме, известной еще древним грекам.

Основная теорема арифметики. Всякое натуральное число a^1 разлагается в произведение a = p1-p2-.-pn простых чисел, причем однозначно с точностью до порядка сомножителей pi (это верно и для отрицательных целых чисел, отличных от - 1, только надо взять множитель - 1).

Пусть p - фиксированное простое число и a - произвольное

ненулевое целое число. Неотрицательное целое число k = 0p(a)

k

называется p-показателем числа a, если a делится на p , но не делится

k+1 k

на p , т. е. a = p q для некоторого целого числа q, не кратного p. Положим также 0p(0) = В результате получаем функцию 0p: Z ^ Nu{0, обладающую свойствами:

0p(ab) = 0p(a) + 0p(b) и 0p(a + b) > min(0p(a), 0p(b)) для всех целых чисел a, b. Основная теорема арифметики принимает вид

a = П p°p(a) для любого натурального a.

p - простое

Зная канонические разложения натуральных чисел a и b на простые множители, легко найти канонические разложения их НОД и НОК:

НОД (a, b) = П p min(Op(a),°p(b)) и НОК^, b) = П p max(Op(a),°p(b)).

p-простое                                                                           p-простое

Например, для a = 5500 и b = 3300 имеем разложения

a = 22-30-53-70-111-130-... = 22-53-11 и b = 22-3-52 11, откуда 02(a) = 2, 05(a) = 3, 011(a) = 1 и 0p(a) = 0 при других простых p, Н0Д(5500, 3300) = 22-52-11 = 1100 и Н0К(5500, 3300) = 22-3-53 11 = 16500.

Замечание 2. Множество N натуральных чисел с отношением «делит» является упорядоченным множеством с наименьшим элементом 1. Более того, < N, |) есть полная снизу атомная дистрибутивная решетка с условием минимальности (см. [3]). Атомами в ней служат

простые числа. Добавив 0 к N, получим полную атомную дистрибутивную решетку < N0, |) с наибольшим элементом 0, 4 " 6 не содержащую коатомов. В No только числа 1 и 0 обладают дополнениями.

Для любых элементов a, b

решетки N0 inf(a, b) = НОД^, b)

и sup(a, b) = НОК^, b).

Утверждение. Если для взаимно простых натуральных чисел a, b и натуральных чисел с, п верно равенство ab =
сп, то a = dn для некоторого натурального d.

Это утверждение вытекает из основной теоремы арифметики. Оно не обязано выполняться в подполугруппах мультипликативной полугруппы N всех натуральных чисел. Например, в полугруппе N{2} 4-9 = 36 = 6 и НОД(4, 9) = 1, но 4 не является квадратом никакого элемента полугруппы.

Аналогичная элементарная классическая теория делимости имеет место в некоторых других числовых кольцах и в кольце Р[х] многочленов от одного неизвестного х с коэффициентом из произвольного поля P; это евклидовы кольца [13].

,3 /

1

К основам делимости принадлежит и отношение сравнимости целых чисел по данному модулю. Целые числа a и b называются

сравнимыми по модулю натурального числа n (a = b(mod n)), если a-b делится на n. Принципиальным является тот факт, что сравнение a = b(mod n) эквивалентно равенству a = b в кольце Zn классов вычетов по модулю n. Отношение сравнимости по модулю n обладает рядом важных свойств, применяемых, в частности, при установлении признаков делимости на n. Можно назвать также малую теорему Ферма, сравнения Эйлера и Вильсона, китайскую теорему об остатках, квадратичный закон взаимности, решение диофантовых уравнений, теорию p-адических чисел.

2. Делимость в целостных кольцах

Начнем с определений. Целостным кольцом (или областью целостности) называется любое коммутативное кольцо с 1 Ф 0 без делителей нуля (ab=0 влечет a=0 или b=0).

Пусть далее R - целостное кольцо. Непустое подмножество I в R называется идеалом кольца R, если a + b el и ar el для любых a, b el и r eR. Идеал l Ф R называется собственным (эквивалентно, 1 £l). Собственный идеал l в R называется простым, если ab el влечет a el или b el для всех a, b eR. Идеал aR = {ar: r eR} называется главным идеалом, порожденным элементом aeR. Если каждый идеал в R является главным, то R называется кольцом главных идеалов. Элемент aeR называется обратимым, если ab = 1 для некоторого b eR, называемого обратным к a и обозначаемого a"1. Обратимые элементы кольца R относительно умножения образуют группу - мультипликативную группу кольца R.

Пусть a, b eR. Элемент b называется делителем элемента a в R, если существует такой элемент c eR, что a = bc; в обозначениях, bla. Итак,

bla означает 3 c eR a = bc.                 (1)

Говорят также, что a делится на b или a кратно b. Элемент c называется частным от деления a на b. В результате на кольце R получаем бинарное отношение «делит» I, обладающее следующими свойствами (для любых a, b, d, r, s eR):

1.  ala (рефлексивность).

2.  dlb, bla ^ dla (транзитивность).

3.  0
- единственный элемент в R, делящийся на любой его элемент.

4.  Обратимые элементы - это в точности делители всех элементов

из R.

5.  Ыа ^ brlar (при гФ0 верно и обратное) и blar.

6.  Если в формуле (1) Ьф0, то частное c определено однозначно (выполняются обычные свойства частных c = а/b).

7.  аlb, bla ^ а = bu для некоторого обратимого элемента u eR; такие элементы а и b называются ассоциированными (а ~ b).

8.  bla ^aR abR, откуда а ~ b ^aR = bR.

9.  dla, dlb ^ dl(ar + bs).

10.  aR + bR = dR ^d есть НОД(а, b), т. е. d делит элементы а и b и делится на любой их общий делитель.

11.  aR n bR = kR ^к = НОК(а, b), т. е. к делится на а и b и делит любое их общее кратное.

Здесь aR + bR = {ar + bs: r, s eR}. Если для любых a, beR идеал aR + bR является главным, то кольцо R называется кольцом Безу. Кольца Безу - это такие кольца, в которых любые два элемента а и b имеют НОД, представимый в виде ar + bs (в них верна теорема о линейном представлении НОД). Кольцо R называется нетеровым, если каждый его идеал конечно порожден. Кольца главных идеалов - это в точности нетеровы кольца Безу.

С отношением делимости на кольце тесно связано отношение сравнимости по модулю идеала. Пусть в кольце R выделен идеал I. Элементы а и b кольца R называются сравнимыми по модулю идеала I, если а - b el. Тем самым, на R возникает отношение сравнимости, обобщающее сравнимость целых чисел по модулю n и являющееся конгруэнцией на кольце R.

3. Евклидовы кольца

Целостное кольцо R называется евклидовым, если существует такая функция ф: R{0}—> Nu{0}, что для любых а и b Ф 0 из R найдутся q, r eR, для которых

а = bq + r, r = 0 или ф(г) < ф(Ь). (2) Примеры

1.  Кольцо Z с ф = l l.

2.  Кольцо P[x], P - поле, с ф = deg (deg f - степень ненулевого многочлена feP[x]).

3. Кольцо Z[i] целых гауссовых чисел а = a + bi (a, beZ). Здесь

22

у

b+1

b

a+1

0

х

a

ф(а) = п(а) = a + b - норма комплексного числа а. В кольцах многочленов Р[х] для любых a и b^0 (неполное) частное q и остаток r (см. (2)) находятся однозначно. Заметим, что в классе целостных колец это единственные кольца с однозначным делением с остатком. В кольце Z в качестве r можно взять и число r - IbI < 0. В кольце Z[i] пары (q, r) могут принимать от 1 до 4 значений. Возьмем а и /3^0 в Z[i] и рассмотрим их частное а/fieQ[i]. Число а]в попадает в некоторый единичный квадрат (возможно, на его границу) координатной плоскости с целочисленными вершинами (а, b), (a, b+1), (a+1, b+1) и (a+1, b), где a, beZ. Расстояние I аа в - ql = ^п(а/ в - q) от этого числа хотя бы до одного из чисел

л/2

q = х + yi (х = a или а + 1, y = b или b + 1) не превосходит —< 1.

2

Обозначим r = а - eqeZ[i]. Учитывая свойство мультипликативности нормы  комплексных                                чисел,                                  получаем

n(r) = п(( а1 в - q )в) = п(а1 в - q )п(в) < п(в). Это и означает евклидовость кольца целых гауссовых чисел. Если а/в оказывается в

1 1

центре квадрата, т. е. а!в = (a+—) + (b+—)i, то в качестве q можно

2 2

взять любое из четырех указанных чисел.

4. Пример кольца главных идеалов, не являющегося евклидовым.

a +

Таково числовое кольцо {

bV-19

: a, b - целые числа одинаковой

2

четности} [10].

Теорема 1. Любое евклидово кольцо является кольцом главных идеалов.

Доказательство имеется в [4, 8, 9, 11].

4. Факториальные кольца

Пусть p - ненулевой необратимый элемент целостного кольца R. Элемент p называется простым, если plab влечет pla или plb для любых a, beR. Легко видеть, что простота элемента p равносильна простоте идеала pR кольца R. Элемент p называется неприводимым, если его делителями являются лишь обратимые элементы и ассоциированные с p элементы (p=ab влечет обратимость a или b). Простые элементы неприводимы; обратное верно далеко не всегда.

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

ki k2 k„

записать каноническое разложение a = up^ - p^ -... - pnn, где u -

обратимый элемент, p1, p2, ..., pn - попарно не ассоциированные неприводимые элементы, k1, k2, ...., kn eN.

Замечание 3. Мультипликативно факториальные кольца очень похожи на кольцо обычных целых чисел. Отношение ассоциированности ~ является конгруэнцией на мультипликативной полугруппе R* всех ненулевых элементов целостного кольца R, а соответствующая фактор-полугруппа будет целой полугруппой. Если кольцо R факториально, то фактор-полугруппа R*/~ является гауссовой целой полугруппой (см. [3, 9]). В факториальных кольцах НОД и НОК нескольких элементов находятся стандартно по их каноническим разложениям, а все неприводимые элементы являются простыми.

Теорема 2. Каждое кольцо главных идеалов факториально.

Теорема 3. Кольцо многочленов от одного или нескольких неизвестных над факториальным кольцом факториально.

Доказательства теорем 2 и 3 можно найти в учебниках [8, 9]. Из теорем 1 и 2 следует факториальность евклидовых колец.

Теорема 4. Для любого целостного кольца R эквивалентны следующие условия:

1) 
любые два элемента в R имеют НОД;

2) 
любые два элемента кольца R обладают НОК.

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

Пример 5. Кольцо многочленов Z[x] факториально. Его идеал 2Z[x] + xZ[x], состоящий из всех целочисленных многочленов с четным свободным членом, не является главным. Получили факториальное кольцо, не являющееся кольцом Безу.

Пример 6. Кольцо всех аналитических функций на комплексной плоскости является кольцом Безу, но не факториально.

Пример 7. Рассмотрим кольцо                   3] = {a + bV3i: a, beZ).

Норма элемента a= a + i равна n(a) = a2 + 3b2. Норма обратимых элементов равна 1, что возможно только при a = 1 или - 1 и b = 0. Значит, 1 и - 1 - единственные обратимые элементы кольца Z[V-3 ]. Поэтому в Z[V-3] ассоциированность элементов а и в означает, что а= в или а= - в. Возьмем разложения 4 = 2-2 = (1 + V3i)(1 - V3i). Элементы 2, 1 + V3 i и 1 - V3 i неприводимы в

не ассоциированы друг с другом и не являются простыми элементами. Следовательно, кольцо

3 ] не факториально и, стало быть, не евклидово, но в нем каждый ненулевой необратимый элемент разлагается в произведение конечного числа неприводимых элементов. Именно эту систему чисел использовал Л. Эйлер в 1768 году при своем оригинальном, но не совсем корректном доказательстве Великой теоремы Ферма (для любого целого n > 2 уравнение xn + yn = zn неразрешимо в натуральных числах) для показателя n = 3, предвосхитив тем самым создание теории алгебраических чисел (см. [11, 14]).

Расширенное числовое кольцо R = { a + b; a и b - целые числа

2

bS+S

O

a

a+1