ГЛАВА 2. Алгебраические основы теории чисел.
Долгое время арифметика (наука о числах) развивалась как наука о свойствах конкретных чисел. И только Франсуа Виет (1540-1603) ровесник первого Бурбона Генриха IV Наваррского и его жены королевы Марго, систематически стал применять для обозначения произвольных чисел буквы. (В России в это время правил Иван Грозный и было не до алгебры). С помощью таких обозначений уже можно было формулировать утверждения о числах вообще, поэтому Виета называют отцом алгебры.
Алгебра возникла как наука о математических системах, в которых можно производить алгебраические операции. Операции эти обычно, что бы не придумывать новых терминов, называют сложением и умножением. Первым и главным объектом изучения алгебры первое время были числа, позже к ним добавились многочлены и матрицы.
Было обнаружено, что у чисел, многочленов и матриц, самых полезных для естествознания математических объектов, много общего. Поэтому проще изучать их все разом, используя обще алгебраические обозначения, позволяющие точнее и яснее пояснить основную идею, лежащую в основе упомянутых общих свойств.
Образно говоря, не стоит отдельно развивать науку о столах, отдельно о табуретках, отдельно о тумбочках. Лучше изучать предмет из дерева на четырех ножках, с несущей поверхностью и дополнительными отделами. Если налагать некоторые дополнительные условия, то будет получаться стол, стул или шкаф соответственно. Ведь с точки зрения математики спагетти и блины почти неразличимы – это цилиндры, у которых разное отношение высоты цилиндра к радиусу основания: у спагетти 100:1, а у блина 1:100.
§1. Основные понятия алгебры.
1.1. Начальные понятия.
Как начинается любая сказка? В тридевятом царстве в тридесятом государстве жили-были… Не только в сказках, но и в математике и программировании важно окружение, где разворачивается все действие - объемлющий универсум, среда программирования.
Два наших основных объекта - это числа и многочлены. Где же они живут? Как обычно принято в математике, они «живут» в некотором множестве, называемом алгебраической системой.
Алгебраическая система – это непустое множество, в котором задана одна или несколько алгебраических операций.
Что такое алгебраическая операция? Их очень много, нам потребуется бинарная алгебраическая операция.
Бинарной алгебраической операцией на множестве А называется любое отображение, которое каждой паре элементов из множества А ставит в соответствие элемент множества А.
В этом смысле суммы или произведения чисел, многочленов или матриц являются алгебраическими операциями. Бинарные алгебраические операции обычно называют сложением или умножением. Это сокращение для длинной тирады «бинарная алгебраическая операция». Обозначают их тоже по-разному. Приведем наиболее часто используемые обозначения: +, ·, Ч, •, , , *.
Если множество А содержит 10 элементов, то пар элементов будет 100. Так как любой паре из 100 можно поставить в соответствие любой из 10 элементов, то общее число различных алгебраических операций на множестве из 10 элементов будет равно 10100. Как известно атомов в видимой части вселенной примерно 1050, поэтому изучать все алгебраические операции нет никакой возможности.
Определение. Алгебраическая операция «+» называется:
Коммутативной на 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.
На множестве натуральных чисел введем новую алгебраическую операцию (возведение в степень). Поскольку 32 = 9, а 23 = 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. Пусть К – кольцо, Mn(K) – множество квадратных матриц размера nЧn с коэффициентами из кольца К. Относительно обычных операций сложения и умножения матриц Mn(K) является кольцом.
Отметим, что в отличие от кольца многочленов К[x] кольцо Mn(K) не наследует коммутативность от кольца коэффициентов К.
Упражнение. Доказать, что при n>1 кольцо Mn(K) всегда некоммутативное.
Пример 10. Рассмотрим множество остатков (вычетов)
Zn={0,1,2,…, n—1} от деления на натуральное число n. Введем на нем операции сложения и умножения
,
где a+b и ab обозначают обычные сложение и умножение целых чисел.
Относительно введенных операций множество Zn является коммутативным кольцом с единицей.
Самое маленькое кольцо, и самое любимое программистами, это кольцо Z2 = {0,1} вычетов по модулю 2. В дальнейшем мы не будем использовать обозначения , , а пользоваться привычной плюсом и точкой.
Предупреждение. Нередко считают, что если n>m, то кольцо Zn содержит кольцо Zm . Это вредное заблуждение. Конечно, внешне кольцо Z5={0,1,2,3,4} выглядит как подмножество кольца Z8={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 действительных чисел с обычными операциями сложения и умножения является полем.
Кольцо вычетов Zp , где p – любое простое число, является полем. (Это мы докажем позже).
Упражнение.
Проверить, что кольцо многочленов K[x] не является полем. (Подсказка. Какой многочлен является обратным к многочлену х2 по умножению?).
Проверить, что кольцо матриц Mn(K) при n>1 не является полем.
1.2. Делимость в кольцах.
Неформально говоря, в полугруппе можно только умножать (или прибавлять). В группе можно умножать и делить (или прибавлять и вычитать). В кольце можно прибавлять, вычитать и умножать. В поле можно прибавлять и вычитать, умножать и делить.
Когда в поле рациональных чисел мы говорим, что «делим число 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. По определению делимости найдутся b1, c1 , принадлежащие К, такие, что b=ab1, c=ac1, поэтому , следовательно, элемент а делит элемент . Кроме определения делимости здесь использовалась дистрибутивность.
2. Так как b=ab1, то bc=(ab1)c=a(b1c) в силу ассоциативности умножения.
3. Если b=ab1, c=bc1, то c=bc1=(ab1)с1=a(b1с1) опять использовалась ассоциативность умножения.
4. Последнее свойство следует из свойств 1 и 2.
Третье свойство обычно называют транзитивностью. Кроме транзитивности среди свойств бинарных отношений, а делимость – это бинарное отношение, популярны рефлексивность и симметричность.
Чтобы выяснить, когда эти свойства имеют место, нам потребуется еще ряд определений.
Определение. Элемент a кольца К называется обратимым (или единицей), если существует элемент b, принадлежащий кольцу К, такой что, ab=1, где 1 – нейтральный элемент по умножению.
Теорема.
Множество К* обратимых элементов кольца К является группой относительно операции умножения.
Доказательство очевидно.
Определение. Элемент a≠0 кольца К называется делителем нуля, если существует элемент b≠0 кольца К, такой, что ab=0.
Упражнение. Проверить, что кольца вычетов по составному модулю и кольца матриц Mn(K), при n >1, имеют делители нуля.
Благодаря тому печальному для потребителей обстоятельству, что кольца матриц имеют делители нуля, многие математики имеют работу. Причина в том, что решение систем линейных уравнений над кольцами с делителями нуля очень хлопотное дело и каждое кольцо требует отдельного исследования.
Пример 1.
Рассмотрим кольцо Z8 и два уравнения с коэффициентами в этом кольце: 4x=0 и x2+x+1=0. Как легко проверить первое уравнение имеет четыре решения – 0, 2, 4, 6, а второе ни одного.
Определение. Элементы a и b кольца К называются ассоциированными, если a\b и b\a.
Исследуем подробнее ассоциированные элементы. Если a\b и b\a, то одновременно выполняются два равенства b=ab1, a=ba1. Следовательно, . Таким образом, b(1—a1b1) = 0, и a(1—b1a1)=0. Если кольцо К не имеет делителей нуля, то получается, что
a1b1=1. То есть ассоциированные элементы отличаются друг от друга на обратимый элемент. Например, в кольце целых чисел группа обратимых элементов состоит из двух элементов Z*={1, -1}, поэтому ассоциированными элементами будут, например, 3 и -3, 5 и -5.
Фундаментальную роль в алгебре и теории чисел, а также в криптографии, играют простые элементы кольца. В случае кольца целых чисел – простые числа.
Определение. Элемент p кольца К без делителей нуля называется простым, если он делится только на обратимые элементы и на ассоциированные с ним.
Если ограничится только натуральными числами, то определение простого элемента будет звучать так: «простой элемент делится только на себя и на единицу», поскольку среди натуральных чисел обратимым элементом является только 1.
У колец без делителей нуля есть одного замечательное свойство.
Основное свойство колец без делителей нуля.
Пусть К – кольцо без делителей нуля и a≠0, тогда из равенства ab=ac следует, что b=c.
Доказательство.
Из равенства ab=ac следует, что a(b—c)=0. Так как элемент а ненулевой, то b–c=0, т.е. b=c.
Обратим внимание, что данное свойство означает логическое сокращение, а не умножение на элемент, обратный к элементу «а». Кстати, такого обратного может и не существовать.
1.3. Деление с остатком.
Помните фильм про Буратино и знаменитый диалог Лисы Алисы и Кота Базилио: “Пять на два не делится! Вот тебе, Базилио, один золотой, а вторую неделящуюся половину я забираю себе!” Кот ничего не понял, но почувствовал, что его обманывают.
Что означает «делится», мы выше видели, это когда есть дополнительный множитель и он восстанавливает равенство. А если множителя нет. Тут мы вступаем на зыбкую почву приближений.
При делении целых чисел и многочленов разные числа и многочлены можно легко сравнивать. У чисел сравнение ведется путем сравнения их модулей, а у многочленов – сравнением их степеней. Поэтому при неполном делении стремятся, что бы степень остатка была меньше, чем степень делителя.
Формально понятие степени можно ввести так.
Определение. Пусть К – кольцо без делителей нуля. Степенью элементов кольца К называется отображение ненулевых элементов кольца во множество натуральных чисел такое, что выполняется условие монотонности: Другими словами, степень произведения не меньше степени сомножителя. (Обратим внимание, что для нуля степень не определена!)
Если определено понятие степени элемента, то можно говорить о делении с остатком.
Определение Кольцо К называется кольцом с алгоритмом деления с остатком или евклидовым, если или r=0.
Евклидовых колец не очень много. Нас же будут в основном интересовать два из них.
Пример 1.
Кольцо целых чисел Z является евклидовым, при этом степенью целого числа является его модуль. Алгоритм деления с остатком в кольце целых чисел изучался в школе.
Пример 2.
Пусть P – поле, тогда кольцо многочленов P[x] является евклидовым, при этом степенью является обычная степень многочлена. Алгоритм деления с остатком – обычное деление многочленов уголком.
Сейчас мы докажем самую полезную теорему о евклидовых кольцах, которая применяется чуть не всей классической алгебре и криптографии.
Но прежде введем понятие наибольшего общего делителя (НОД) и двойственное ему наименьше обще кранное (НОК).
Определение. Элемент d=НОД(a,b) называется наибольшим общим делителем элементов a и b, если выполняются два условия:
1) d\a, d\b – т.е. d - общий делить,
2) Если s\a, s\b , то s\d – наибольший делитель, в том смысле, что он делится на все остальные делители.
Понятие наименьшего общего кратного НОК не так важно как НОД, но его введение поучительно в силу свой двойственности к НОД. «Наибольший» заменяется на «наименьший», «делится» на «делит».
Определение. Элемент m=НОК(a,b) называется наименьшим общим кратным элементов a и b, если выполняются два условия:
1) m: a\m, b\m - общий кратный,
2) Если a\n, b\n , то m\n – наименьшее кратное, в том смысле, что оно делит все остальные кратные.
Фундаментальный факт состоит в том, что в евклидовых кольцах, а значит в кольце целых чисел и кольце многочленов над полем, – НОД существует и его можно выразить через исходные элементы.
Теорема (Основная теорем о евклидовых кольцах).
Пусть К – евклидово кольцо, тогда любые элементы имеют наибольший общий делитель и, более того, такие, что d=НОД(a,b)=au +bv.
Доказательство.
а) Применяя свойство деления с остатком получим табличку уменьшающихся остатков. Так как степень каждого остатка – натуральное число, а натуральные числа не могут убывать бесконечно, то табличка будет конечной, а последний остаток нулевым.
В нашей табличке получилось n+2 строки. Какой же из участвующих в ней элементов является долгожданным НОД? Это последний ненулевой остаток rn. Для того, чтобы убедиться, что d=rn, нужно проверить оба свойства НОД. Прежде всего, просматривая табличку снизу вверх, убеждаемся, что rn делит a и b. В самом деле, последняя строка нам гарантирует, что rn\rn-1. Из предпоследней строки следует, что rn\rn-2 и т.д. Из третьей строки следует, что rn\r, из второй, что делит b, а из первой, что rn\a.
Теперь проверим, что rn - наибольший делитель, т.е., что он делится на любой s такой, что s\a и s\b. Теперь просматриваем нашу табличку сверху вниз. Из первой строчки следует, что s\r, из второй, что s\r1 и т.д. Из предпоследней строки следует, что s\rn. Таким образом, последняя строка даже не понадобилась.
б) Осталось выразить остаток rn через исходные элементы a и b. Для этого опять просматриваем нашу табличку снизу вверх. Из предпоследней строки получаем rn =rn-2+(-qn)rn-1, из третьей снизу rn-1=rn-3+(-qn-1)rn-2, поэтому
rn=rn-2+(-qn)rn-1=rn-2+(-qn)(rn-3+(-qn-1)rn-2)=rn-2(1+(-qn)(-qn-1))+rn-3(-qn).
Поднимаясь снизу вверх, мы последовательно выразим rn через rn-2 и rn-1, потом через rn-3 и rn-2 и т.д. И, наконец, через a и b.
Таким образом, в кольце целых чисел и кольце многочленов над полем всегда можно эффективно найти НОД. Алгоритм, приведенный выше, его называют алгоритмом Евклида, реализован в большинстве компьютерных систем, в том числе и в тех, что используются для нужд криптографии.
Данная теорема имеет массу приложений, например, с ее помощью строятся поля Галуа.
Теорема (Первая теорема о поле Галуа).
Если натуральное число p является простым, то кольцо вычетов Zp на самом деле является полем.
Эта теорема была доказана в п.5 §3 Главы 1 как утверждение.
Упражнение. Найдите обратные по умножению к остатку 5 в полях Z7, Z17, Z127. Проще всего обратный искать по алгоритму Евклида.
1.4. Основная теорема арифметики.
Название это несколько устарело, но сама теорема об однозначном разложении на простые множители не устарела. Теорема эта несколько суховата и аккуратно ее сформулировать не так-то просто. Но на ней, как на фундаменте держится вся арифметика, и все приложения теории чисел. Эта же теорема имеет место и для кольца многочленов над полем, а более широко для всех евклидовых колец. Для них мы ее и докажем.
Однозначность далеко не всегда имеет место. Например, игрушку Лего как не разбирай, простейшие детали окажутся одни и те же. А вот огурец можно разрезать вдоль, а можно и поперек.
Что понимать под однозначностью разложения на простые множители. Например, число 10 можно записать разными способами в виде произведения
.
Можно предложить и другие. Однако, различия в этих представлениях не очень существенные. Минус единица и единица, это единственные обратимые элементы в кольце целых чисел (на обратимые элементы делятся любые элементы), а числа 2 и -2, 5 и -5 – ассоциированные, т.е. отличаются друг от друга на обратимые. То, что 2 и 5 в разных записях числа 10 переставлены местами тоже не существенно, поскольку имеем место коммутативность умножения. Все эти наблюдения подсказывают определение.
Определение. Два разложения элемента “a” коммутативного кольца К на простые множители
называются ассоциированными, если - обратимые элементы, n=m, простые элементы pi и qj, возможно после перестановки, попарно ассоциированы, т.е. p1 ассоциирован с q1, p2 ассоциирован с q2 и т.д.
В кольце многочленов простые элементы обычно называют неприводимыми многочленами. Так сложилось исторически, поскольку в прежние времена, разложение многочленов на множители называлось приведением к простому виду. Поэтому, если разложить не удавалось, то и называли неприводимым. Это примерно то же самое, почему у моряков не повар, а кок. Поскольку говорить, что неприводимые элемент кольца многочленов – это простой элемент кольца многочленов, излишний педантизм, то приведем и явное определение.
Определение. Многочлен называется неприводимым, если он не раскладывается в произведение многочленов меньшей степени.
Поиск простых элементов, в том числе и простых чисел и неприводимых многочленов, весьма нетривиальная задача, над которой в мире работают тысячи специалистов и миллионы микропроцессоров. Нам нужно доказать, что в кольце целых чисел Z и кольце P[x] многочленов над полем имеет место однозначное разложение на простые множители. Кстати, на этом факте держится вся криптография с открытым ключом, в том числе и знаменитый RSA.
Как обычно, сделаем это сразу для всех евклидовых колец.
Определение. Говорят, что кольца К является кольцом с однозначным разложением на простые множители, если в нем любой элемент имеет хотя бы одно разложение на простые множители и любые два такие разложения ассоциированы.
Кратко такие кольца называются факториальными. Но можно это слово и не запоминать. Некоторые племена Африки не знают слова зонтик, они просто говорят: “Домик, который белый человек носит в руках и раскрывает над головой, когда идет дождь.”
Фраза в определении факториального кольца о том, что каждый элемент должен иметь хотя бы одно разложение, не ритуальная. Не факт, что такие разложения есть вообще, а про то, чего нет можно доказать все что угодно. Например, я утверждаю, что все алмазы, хранящиеся у меня в доме, имеют вес больше 10 кг. (50 тыс. карат). Что бы меня опровергнуть требуется найти хотя бы один алмаз, который бы весил меньше 10 кг. Такого алмаза найти невозможно потому, что алмазов у меня нет вообще!
Теорема.
В евклидовом кольце любой элемент имеет разложение на простые множители.
Доказательство.
Идея доказательства очень проста. Поскольку каждый элемент евклидова кольца имеет степень, а степень сомножителя не больше чем степень произведения, то мы не сможем бесконечно раскладывать на множители. Неразложимые множители и будут простыми элементами. Теперь реализуем эту идею аккуратно. Запустим индукцию по степени элемента “a”. База индукции – неразложимые элементы (независимо от их степени, так что, фактически, имеет место двойная индукция).
Шаг индукции. Пусть , тогда, по предположению индукции сомножители b и c имеют разложение на простые множители, а значит, разложим и исходный элемент “a”.
Самый трудный случай. Пусть , т.е. один из сомножителей не уменьшил свою степень, это допускается определением степени. Тогда применим деление с остатком, «непокорный» элемент “b” поделим на элемент a: .
Следовательно, . Чтобы не возникло противоречия , остается согласиться, что 1–cq=0, т.е. cq=1. Значит элементы a и b ассоциированы, т.е., “а” – и принадлежит базе индукции.
Для кольца с разложением на простые множители есть простой критерий, когда оно является факториальным. Доказательство критерия можно посмотреть, например, в учебнике А.И. Кострикина Введение в алгебру.
Теорема. (Критерий факториальности)
Если кольцо имеет разложение на простые множители, то оно факториально тогда и только тогда, когда для любого простого элемента p из того, что p\(ab) следует, что p\a или p\b.
Критерий кажется очевидным и даже несколько наивным. Однако, если Петю (p) смогли поднять вдвоем Антон (a) и Борис (b) не обязательно, что это они смогут сделать по отдельности.
Теорема (факториальность евклидовых колец).
Любое евклидово кольцо, в частности кольцо целых чисел и кольцо многочленов над полем, являются кольцам с однозначным разложением на простые множители.
Доказательство.
Применим критерий факториальности. Пусть простой элемент p делит произведение ab, но не делит элемент a. Так как элемент p простой, то НОД(p,a) = 1 и, значит, в силу алгоритма Эвклида найдутся элементы такие, что ua+vp=1. Умножая это равенство почленно на элемент b, получаем uab+vpb=b. Так как оба слагаемых в левой части равенства делятся на элемент p, то и правая часть делится на p. Значит p\b. Если элемент p не делит b, то аналогично получим, что p\a.
Следствие. В евклидовом кольце число простых элементов бесконечно. В частности, бесконечно число простых чисел и неприводимых многочленов.
Идея использовать метод Евклида для получения новых простых чисел не безнадежна, но мало эффективна. Начнем с первых трех простых чисел 2, 3, 5. Далее получаем , имея четыре числа 2, 3, 5, 31 получим . Вновь появляющиеся числа не только не обязаны быть простыми, но даже и не обязательно дают простые множители, превосходящие предыдущие.
|
