ГЛАВА 2. Алгебраические основы теории чисел

Долгое время арифметика (наука о числах) развивалась как наука о свойствах конкретных чисел. И только Франсуа Виет (1540-1603) ровесник первого Бурбона Генриха IV Наваррского и его жены королевы Марго, систематически стал применять для обозначения произвольных чисел буквы. (В России в это время правил Иван Грозный и было не до алгебры). С помощью таких обозначений уже можно было формулировать утверждения о числах вообще, поэтому Виета называют отцом алгебры.

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

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

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

Основные понятия алгебры.

Начальные понятия.

Как начинается любая сказка? В тридевятом царстве в тридесятом государстве жили-были… Не только в сказках, но и в математике и программировании важно окружение, где разворачивается все действие - объемлющий универсум, среда программирования.

Два наших основных объекта - это числа и многочлены. Где же они живут? Как обычно принято в математике, они «живут» в некотором множестве, называемом алгебраической системой.

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

Что такое алгебраическая операция? Их очень много, нам потребуется бинарная алгебраическая операция.

Бинарной алгебраической операцией на множестве А называется любое отображение, которое каждой паре элементов из множества А ставит в соответствие элемент множества А.

В этом смысле суммы или произведения чисел, многочленов или матриц являются алгебраическими операциями. Бинарные алгебраические операции обычно называют сложением или умножением. Это сокращение для длинной тирады «бинарная алгебраическая операция». Обозначают их тоже по-разному. Приведем наиболее часто используемые обозначения: +, ·, ×, •, Ä, Å, *.

Если множество А содержит 10 элементов, то пар элементов будет 100. Так как любой паре из 100 можно поставить в соответствие любой из 10 элементов, то общее число различных алгебраических операций на множестве из 10 элементов будет равно 10¹⁰⁰. Как известно атомов в видимой части вселенной примерно 10⁵⁰, поэтому изучать все алгебраические операции нет никакой возможности.

Определение. Алгебраическая операция «+» называется:

Коммутативной на A, если a+b=b+a для всех a, b из A;

ассоциативной, если (a+b)+c=a+(b+c)для всех a, b, c из A;

имеющей нейтральный элемент, если e+a=a+e=a;

имеющей обратимые элементы, если a+b=b+a=e.

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

Пример 1.

На множестве натуральных чисел введем новую алгебраическую операцию (возведение в степень). Поскольку 3² = 9, а 2³ = 8, то операция не коммутативна. Далее, , в то же время , поэтому операция и неассоциативна. Нетрудно видеть, что нет нейтрального элемента, поскольку если , то е = 1, но . Если нет нейтрального, то об обратном нет и речи.

Пример 2.На множестве натуральных чисел с добавленным нулем введем новую операцию (модуль разности). Эта операция обладает свойством коммутативности, нейтральным элементом является ноль, и каждый элемент является сам к себе обратным. А вот ассоциативности нет: , но .

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

Пример 3. Множество натуральных чисел относительно операции обычного сложения является коммутативной полугруппой.

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

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

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

Определение. Если на множестве А задана ассоциативная операция, имеющая нейтральный элемент и все ее элементы имеют обратные, то множество А называется группой. Если операция к тому же коммутативная, то группа называется коммутативной или абелевой в честь Нильса Хенриха Абеля (1802-1829).

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

Пример 6. Множество ненулевых рациональных чисел относительно операции обычного умножения является коммутативной группой.

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

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

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

(a+b)c=ac+bc, c(a+b)=ca+cb,

В этом случае множество А называется кольцом. Если умножение коммутативно, то кольцо называется коммутативным.

Кстати, коммутативные кольца абелевыми никогда не называют.

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

.

Соединяя вместе обе дистрибутивности, получаем

.

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

с=1, получим, что . Явное противоречие. Таким образом, справедливость, т.е. симметричность определения кольца относительно сложения и умножения, невозможна принципиально.

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

Пример 8.Пусть К – кольцо, множество многочленов K[x] от переменной х с коэффициентами из кольца К относительно обычных операций сложения и умножения многочленов является кольцом. Если кольцо К коммутативно, то и кольцо K[x] тоже коммутативно.

Следствие.

1. Если нейтральный элемент существует, то он единственный.

2. Если операция ассоциативна и у элемента а существует обратный элемент, то он тоже единственный и обозначается «-а», если операция называется сложением, и «а^-1» или «1/a», если операция называется умножением.

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

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

Доказательство.

1. Допустим, есть два нейтральных элемента x и y, тогда по определению нейтрального элемента x имеем xy=y и, с другой стороны, xy=x. Значит, x=y.

2. Пусть «b» и «c» – элементы обратные элементу «а». В силу аксиомы ассоциативности имеем b= b1=b(ас)=(ba)с=1с=с.

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

(Кстати, при сокращении обеих частей на элемент 0а, которое мы произвели в одно действие, на самом деле использовалось три аксиомы – наличие обратного по сложению, ассоциативность сложения, аксиома нейтрального элемента. Подробно это выглядит так. Пусть «b» - элемент обратный по сложению к элементу 0а, тогда из 0а=0а+0а, следует

0=0а+b=(0а+0а)+b=0а+(0а+b)=0а+0=0а.)

4. Вначале докажем, что (-а)b=-(ab). Для этого нужно проверить, что элемент (-a)b является обратным по сложению к элементу ab. В самом деле, ab+(-а)b=(a—a)b=0а=0. Здесь использовалась дистрибутивность, свойство обратного по сложению и свойство нуля, а также пункт 3 нашего доказательства.

Теперь, используя только что полученный результат, вычисляем

(-а)(-b)=-(а(-b))=-(-(ab)). Так как обратный к обратному есть исходный, то

–(-ab)=ab.

□

Познавательный смысл следствия в том, что оно объясняет, почему при умножении на 0 всегда получается 0 и почему «минус на минус дает плюс». Оба эти свойства выполняются, если верны четыре аксиомы: ассоциативность сложения, дистрибутивность, наличие нейтрального элемента и обратного элемента по сложению.

С точки зрения программирования доказанное выше следствие то же очень полезно. Аксиомы – это ассемблерные команды, элементарные операции, аппаратно реализованные в процессоре. Наши привычные преобразования, например, приведение подобных членов или умножение на 0, - это команды языка высокого уровня. Мы, фактически, выступили в роли компилятора. Это полезно сделать хотя бы один раз, что бы при изменении среды программирования значь, что нужно переделывать.

Пример 9.Пусть К – кольцо, M_n(K) – множество квадратных матриц размера n×n с коэффициентами из кольца К. Относительно обычных операций сложения и умножения матриц M_n(K) является кольцом.

Отметим, что в отличие от кольца многочленов К[x] кольцо M_n(K) не наследует коммутативность от кольца коэффициентов К.

Упражнение. Доказать, что при n>1 кольцо M_n(K) всегда некоммутативное.

Пример 10. Рассмотрим множество остатков (вычетов)

Z_n={0,1,2,…, n—1}от деления на натуральное число n. Введем на нем операции сложения и умножения

,

где a+b и ab обозначают обычные сложение и умножение целых чисел.

Относительно введенных операций множество Z_n является коммутативным кольцом с единицей.

Самое маленькое кольцо, и самое любимое программистами, это кольцо Z₂ = {0,1} вычетов по модулю 2. В дальнейшем мы не будем использовать обозначения Å, Ä, а пользоваться привычной плюсом и точкой.

Предупреждение. Нередко считают, что если n>m, то кольцо Z_n содержит кольцо Z_m . Это вредное заблуждение. Конечно, внешне кольцо Z₅={0,1,2,3,4} выглядит как подмножество кольца Z₈={0,1,2,3,4,5,6,7}. Однако, в первом кольце 3·3=4, 3+3=1, а во втором 3·3=1, 3+3=6. Элемент 3 в первом кольцо отличается от элемента 3 во втором, как Вася Петров от Васи Иванова. Это омонимы – одинаково звучащие слова с разным смыслом.

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

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

Пример 11.Множество Qрациональных чиселс обычными операциями сложения и умножения является полем.

МножествоR действительных чиселс обычными операциями сложения и умножения является полем.

Кольцо вычетов Z_p , где p – любое простое число, является полем. (Это мы докажем позже).

Упражнение.

Проверить, что кольцо многочленов K[x] не является полем. (Подсказка. Какой многочлен является обратным к многочлену х² по умножению?).

Проверить, что кольцо матриц M_n(K) при n>1 не является полем.

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

Неформально говоря, в полугруппе можно только умножать (или прибавлять). В группе можно умножать и делить (или прибавлять и вычитать). В кольце можно прибавлять, вычитать и умножать. В поле можно прибавлять и вычитать, умножать и делить.

Когда в поле рациональных чисел мы говорим, что «делим число 2 на число 3», то это является вольным изложением более правильного выражения «умножаем число 2 на число обратное по умножению к числу 3». Почему нельзя делить на 0? Поскольку, 0a=0, то 0 не имеет обратного по умножению и поэтому делить не на что.

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

Определение. Элемент а кольца К делит элемент b кольца K, если существует элемент c кольца K, такой что b=ac. Точнее делит слева, т.к. кольцо может быть некоммутативным. Если b=ca, то а делит элемент b справа.

Обратим внимание, что в этом определении наличие обратного элемента у элемента «а» не предполагается.

Поскольку 0a=0, то по этому определению получается, что 0 делит 0. Получается лингвистическое противоречие. Ноль делит ноль, но ноль на ноль не делится!

В дальнейшем мы будем иметь дело только с коммутативными кольцами, то правую и левую делимость мы различать не будем. Если элемент a делит элемент b, то это обозначается a/b.

Свойства делимости. Пусть К – кольцо, a,b,c – его элементы.

1. Если a/b, a/c, то a/(b+c), a/(b-c).

2. Если a/b, то для любого с из К a/(bc).

3. Если a/b, b/c, то a/c.

4. Если , то

Доказательство.

1. По определению делимости найдутся b₁, c₁ , принадлежащие К, такие, что b=ab₁, c=ac₁, поэтому , следовательно, элемент а делит элемент . Кроме определения делимости здесь использовалась дистрибутивность.

2. Так как b=ab₁, то bc=(ab₁)c=a(b₁c) в силу ассоциативности умножения.

3. Если b=ab₁, c=bc₁, то c=bc₁=(ab₁)с₁=a(b₁с₁) опять использовалась ассоциативность умножения.

4. Последнее свойство следует из свойств 1 и 2.

□

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

Чтобы выяснить, когда эти свойства имеют место, нам потребуется еще ряд определений.

Определение. Элемент a кольца К называется обратимым (или единицей), если существует элемент b, принадлежащий кольцу К, такой что, ab=1, где 1 – нейтральный элемент по умножению.

Теорема.

Множество К^* обратимых элементов кольца К является группой относительно операции умножения.

Доказательство очевидно. □

Определение. Элемент a≠0 кольца К называется делителем нуля, если существует элемент b≠0 кольца К, такой, что ab=0.

Упражнение.Проверить, что кольца вычетов по составному модулю и кольца матрицM_n(K), при n >1, имеют делители нуля.

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

Пример 1.

Рассмотрим кольцо Z₈ и два уравнения с коэффициентами в этом кольце: 4x=0 и x²+x+1=0. Как легко проверить первое уравнение имеет четыре решения – 0, 2, 4, 6, а второе ни одного. □

Определение. Элементы a и b кольца К называются ассоциированными, если a\b и b\a.

Исследуем подробнее ассоциированные элементы. Если a\b и b\a, то одновременно выполняются два равенства b=ab₁, a=ba₁. Следовательно, . Таким образом, b(1—a₁b₁) = 0, и a(1—b₁a₁)=0. Если кольцо К не имеет делителей нуля, то получается, что

a₁b₁=1. То есть ассоциированные элементы отличаются друг от друга на обратимый элемент. Например, в кольце целых чисел группа обратимых элементов состоит из двух элементов Z^*={1, -1}, поэтому ассоциированными элементами будут, например, 3 и -3, 5 и -5.

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

Определение. Элемент p кольца К без делителей нуля называется простым, если он делится только на обратимые элементы и на ассоциированные с ним.

Если ограничится только натуральными числами, то определение простого элемента будет звучать так: «простой элемент делится только на себя и на единицу», поскольку среди натуральных чисел обратимым элементом является только 1.

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