close

Вход

Забыли?

вход по аккаунту

?

505.Фундаментальная и компьютерная алгебра. Часть IV

код для вставкиСкачать
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ
БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ»
Р.Х. Вахитов, Е.В. Вахитова
ФУНДАМЕНТАЛЬНАЯ И КОМПЬЮТЕРНАЯ
АЛГЕБРА
Часть IV
Компьютерная алгебра
Учебно-методическое пособие для вузов
Издательско-полиграфический центр
Воронежского государственного университета
2012
1
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Утверждено научно-методическим советом факультета компьютерных наук
24 сентября 2012 г., протокол № 1
Рецензент канд. физ.-мат. наук, доцент И.Ю. Покорная
Учебно-методическое пособие подготовлено на кафедре цифровых технологий факультета компьютерных наук Воронежского государственного
университета.
Рекомендуется для студентов 1-го курса дневного отделения факультета
компьютерных наук.
Для направления 010200 – Математика и компьютерные науки
2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ВВЕДЕНИЕ
Содержание данного учебно-методического пособия «Фундаментальная и компьютерная алгебра. Часть IV. Компьютерная алгебра» составляет
материал нескольких тем базовой учебной дисциплины профессионального
цикла «Фундаментальная и компьютерная алгебра», изучение которой предусмотрено основной образовательной программой подготовки бакалавра
по направлению «Математика и компьютерные науки» для студентов факультета компьютерных наук ФГБОУ ВПО «Воронежский государственный университет». Целью учебной дисциплины является формирование
представлений о фундаментальной алгебре: структуры алгебры, линейная
алгебра, алгебра многочленов и о компьютерной алгебре. Основными задачами учебной дисциплины являются овладение фундаментальными базовыми знаниями в области фундаментальной и компьютерной алгебры, умением формулировать и доказывать теоремы, самостоятельно решать классические задачи фундаментальной алгебры.
Цель учебно-методического пособия состоит в том, чтобы помочь студентам, изучающим учебную дисциплину «Фундаментальная и компьютерная алгебра». формировать представления о компьютерной алгебре, приобрести навыки и умения практического использования математических методов при решении задач. В результате изучения учебной дисциплины студент должен знать теоретический материал и уметь формулировать результат, строго доказывать утверждение, грамотно пользоваться языком фундаментальной и компьютерной алгебры.
Учебно-методическое пособие состоит из пяти глав. В конце каждой
главы приведены вопросы для самоконтроля и упражнения для самостоятельной работы. Определения, теоремы и их доказательства иллюстрируются численными примерами, цель которых – пояснить общую теорию. В каждой главе определения, формулы и теоремы имеют независимую нумерацию.
При изложении глав 1 и 5 приняты за основу сведения из введения и
главы 1 книги Е.В. Панкратьева [35].
В первой главе рассмотрены следующие вопросы: отличия компьютерной алгебры, системы компьютерной алгебры, алгоритмы компьютерной
алгебры и о представлении данных.
Вторая глава посвящена исследованию вопросов: арифметические операции над целыми систематическими числами, перевод в десятичную систему счисления, перевод из десятичной системы счисления и перевод из gичной системы в h-ичную систему.
В третьей главе рассмотрены следующие вопросы: свойства сравнений
по натуральному модулю, полная система вычетов, аддитивная группа
классов вычетов и кольцо классов вычетов.
3
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Четвертая глава посвящена полю алгебраических чисел. В ней исследованы следующие вопросы: алгебраические числа, целые алгебраические
числа, операции над алгебраическими числами, поле алгебраических чисел
и минимальный многочлен алгебраического числа.
В пятой главе рассмотрено представление данных для целых чисел,
классов вычетов, рациональных чисел, алгебраических чисел и многочленов над полями.
В конце учебно-методического пособия приведен список литературы.
4
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Глава 1
СВЕДЕНИЯ О КОМПЬЮТЕРНОЙ АЛГЕБРЕ
§ 1. Об отличиях компьютерной алгебры
Компьютерная алгебра – это область математики, лежащая на стыке
алгебры и вычислительных методов. Термин «компьютерная алгебра» возник как синоним терминов «символьные вычисления», «аналитические вычисления», «формальные вычисления».
Компьютерная алгебра отличается от вычислительной математики, то
есть символьные вычисления отличаются от численных вычислений:
1. В вычислительных методах все вычисления выполняются в поле
действительных чисел или комплексных чисел. Всякая программа для ЭВМ
имеет дело только с конечным множеством рациональных чисел, так как
только такие числа представляются в компьютере. Это множество не замкнуто относительно арифметических операций, поэтому возникают различные переполнения, например при умножении достаточно больших чисел.
В вычислительной математике арифметические операции над числами,
выполняемые компьютером, отличаются от арифметических операций в поле
рациональных чисел. Кроме того, для компьютерных операций не выполняются основные аксиомы поля: ассоциативности, дистрибутивности. Эти особенности компьютерных вычислений оцениваются в терминах погрешности
или точности вычислений. Оценка погрешности является одной из основных
проблем вычислительной математики. Каждую задачу надо решать с использованием имеющихся ЭВМ, за обозримое время, с заданной точностью.
2. Набор объектов, применяемых в символьных вычислениях, очень
разнообразный: используется значительно большее множество рациональных чисел, оно остается конечным, но содержит больше чисел, ограничения
на допустимые размеры числа (количество знаков в его записи) связаны
обычно с размерами оперативной памяти ЭВМ. Это позволяет пользоваться
практически любыми рациональными числами, операции над которыми
выполняются за приемлемое время. При этом компьютерные операции над
рациональными числами совпадают с соответствующими операциями в поле рациональных чисел. Поэтому снимается одна из основных проблем вычислительных методов: оценка погрешности вычислений.
3. В компьютерной алгебре действительные числа и комплексные числа
практически не применяются, но широко используются алгебраические числа.
Алгебраическое число задается своим минимальным многочленом, а иногда для
его задания надо указать интервал на действительной прямой или область на комплексной плоскости, где содержится единственный корень данного многочлена.
4. Многочлены играют в символьных вычислениях очень важную роль.
Кроме того, в компьютерной алгебре рассматриваются такие объекты, как,
например, дифференциальные поля (функциональные поля), допускающие
показательные, логарифмические, тригонометрические функции, матричное
5
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
кольцо (элементы матрицы принадлежат кольцам общего вида). Даже при
арифметических операциях над такими объектами происходит увеличение
информации и для записи промежуточных результатов требуется большой
объем памяти ЭВМ. Ограничение по времени счета и памяти ЭВМ в символьных вычислениях более неудобно, чем в вычислительных методах.
В следующем параграфе рассмотрим важный продукт исследований
символьных вычислений – системы компьютерной алгебры.
§ 2. Системы компьютерной алгебры
Активная разработка систем компьютерной алгебры началась в конце
60-х годов XX века. Системы компьютерной алгебры можно разделить на:
1) системы общего назначения (универсальные),
2) специализированные системы.
1. Универсальные системы компьютерной алгебры: MACSYMA,
REDUCE, MATHEMATICA, MAPLE, AXIOM. Система MACSYMA, как и
система REDUCE, является «старой» системой. Система MAPLE (Канада,
80-е годы) в настоящее время широко применяется в Канаде, США, во всем
мире. В конце XX века в лидеры выдвинулась также система MATHEMATICA с широкими вычислительными и графическими возможностями, с
электронной документацией (как библиотека может быть использована),
посвященной различным разделам математики и информатики.
Особое место среди систем компьютерной алгебры занимает система
AXIOM. Она имеет высокую степень универсальности, имеет дело с объектами, более привычными для математиков: категории – это ключевое понятие современной математики (например, категории множеств, полугрупп,
дифференциальных колец, левых модулей).
Эта система требует для своей реализации мощных компьютеров, у
них очень высокая плата (дорогая, имеется только в ограниченном числе
мощных университетских и научных центров) в отличие от остальных систем, которые представляют собой пакеты программ, общение осуществляется на некотором алголоподобном языке.
2. Специализированные системы компьютерной алгебры отличаются
более высокой эффективностью, но область их применения ограничена:
CALEY, GAP – для вычислений в теории групп; MACAULEY, CoCoA, Singular – разной степени универсальности, для вычислений в кольце многочленов; SCHOONSHIP – для вычислений в физике высоких энергий, muMATH и ее правопреемница DERIVE – системы, широко используемые в
учебном процессе (например, в Австрии в средних школах).
§ 3. Алгоритмы компьютерной алгебры
Компьютерная алгебра имеет дело с алгоритмами, которые сильно отличаются от алгоритмов, используемых в вычислительной математике. Ал6
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
горитмы вычислительной математики должны давать возможность решать
задачу с требуемой точностью при заданных вычислительных ресурсах, наиболее существенными из которых являются ограничения по используемой
памяти и времени счета. В компьютерной алгебре вычисления производятся
без округления, мало внимания уделяется анализу сходимости, но используется значительно более широкий набор математических, в первую очередь
алгебраических, объектов сложной структуры, и ограничения по времени
счета и по используемой памяти становятся более обременительными.
Применение компьютеров в алгебраических исследованиях поставило
ряд новых задач перед специалистами и заставило заново пересмотреть задачи, которые считались решенными. К ним относились и задачи, для которых
был предложен метод, позволяющий решать их «за конечное число шагов».
Методы решения конкретных задач отличались большим разнообразием и не
использовались универсальные методы. С применением компьютеров для
алгебраических вычислений потребовалось реализовать универсальные алгоритмы в виде программ для ЭВМ и оказалось, что они позволяют решать
только небольшие задачи. С увеличением размера задачи резко возрастали
время счета и необходимая память компьютера. Это сделало актуальным поиск более эффективных алгоритмов решения алгебраических задач.
В конце XX века бурно развивались исследования в трех областях
компьютерной алгебры:
1) теории базисов Грёбнера,
2) теории факторизации многочленов,
3) теории интегрирования в конечном виде.
В компьютерной алгебре рассматриваются арифметические операции,
алгоритм вычисления наибольшего общего делителя целых чисел и многочленов, задачи: представления данных для фактор-колец кольца многочленов, разложение многочленов на неприводимые множители, проблемы
дифференциальной компьютерной алгебры.
Компьютерная алгебра используется также при нахождении решений
дифференциальных уравнений в виде степенных рядов и в других задачах
теории дифференциальных уравнений, при построении разностных схем
для численного решения дифференциальных уравнений.
§ 4. О представлении данных
Сформулируем проблему представления данных. Имеется множество
объектов А и на нем отношение эквивалентности. Требуется в каждом классе
эквивалентных объектов выбрать единственного представителя этого класса
для основных алгебраических областей: кольца целых чисел, поля рациональных чисел, конечных полей, кольца многочленов и поля рациональных
функций, алгебраических и трансцендентных расширений полей.
7
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Примеры. 1. A – множество натуральных чисел > 1, каждое из которых
можно записать в виде арифметического выражения. В качестве канонического выбираем выражение, которое является произведением простых чисел, расположенных в порядке неубывания. Основная теорема арифметики
утверждает, что любое натуральное число > 1 представляется в таком виде
и такое представление единственно. Поэтому задача разложения натурального числа на простые множители может рассматриваться как задача представления данных.
2. Предыдущий пример обобщается на любое кольцо с однозначным
разложением на множители, элементы которого можно упорядочить. В частности, на кольцо Z[x] (кольцо многочленов над Z), получается задача
факторизации многочленов.
3. Основная теорема алгебры утверждает, что любой многочлен положительной степени от одной переменной x с комплексными коэффициентами может быть представлен в виде a(x − α1)(x − α2)…(x − αп). Поэтому задача представления данных есть задача нахождения корней α1, …, αп многочлена, то есть задача решения алгебраического уравнения.
Будем требовать, чтобы выбор представления был каноническим, то
есть в множестве всех эквивалентных выражений нужно выбрать единственное выражение, которое представляло бы этот класс эквивалентности.
При этом предполагаем, что известен алгоритм проверки эквивалентности
двух выражений, так как такой алгоритм не всегда существует. Поэтому
иногда налагается требование более слабое, чем каноническое.
Условие нормальности, например недопустимо деление на нуль. Тем
самым нуль приобретает некоторое особое положение и возрастает значение задачи определения равенства элемента нулю. Нормальное представление – это представление, в котором все эквивалентные нулю выражения
представляются одним и тем же образом (0). Отметим, что любое каноническое представление является нормальным, но обратное верно не всегда.
Часто, зная нормальное представление, можно построить каноническое. Если рассматриваемая структура данных такая, что в ней, кроме нуля, есть и
другие «особые» элементы, то определение нормального представления
должно быть усложнено. Отметим, что понятие эквивалентности объектов
может быть различным.
Представление называется естественным, если представление каждого
элемента определяется одними и теми же правилами, не зависящими от того, в какой последовательности появляется этот элемент.
Будем рассматривать некоторые из основных структур данных, используемых в компьютерной алгебре, для них рассмотрим проблему представления данных. Отметим, что в общем случае эта проблема неразрешима, существуют отношения эквивалентности, для которых нет алгоритма
выбора канонического представителя в множестве эквивалентных выражений и даже проверки эквивалентности двух выражений.
8
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Вопросы для самоконтроля
1. Отличия компьютерной алгебры от вычислительной математики.
2. Типы чисел, применяемые в компьютерной алгебре.
3. Универсальные системы компьютерной алгебры.
4. Специализированные системы компьютерной алгебры.
5. Проблема представления данных.
6. Понятия натурального числа, целого числа, рационального числа,
действительного числа и комплексного числа.
7. Понятие алгебраического числа.
8. Целые систематические числа.
9. Сравнения по модулю, класс вычетов по модулю.
10. Понятия кольца и поля, кольца многочленов над полем.
11. Понятие бинарного отношения, свойства отношений, отношение
эквивалентности и отношение порядка.
Упражнения
1. Сформулировать задачу о решении системы линейных уравнений
над полем в виде задачи представления данных.
2. Сформулировать задачу нахождения наибольшего общего делителя
нескольких целых чисел в виде задачи представления данных.
3. Сформулировать задачу нахождения наибольшего общего делителя
нескольких многочленов от одной переменной над полем в виде задачи
представления данных.
4. Сформулировать задачу о разложении натуральных чисел в произведение простых множителей в виде задачи представления данных.
5. Сформулировать задачу о разложении многочлена в произведение
неприводимых множителей в виде задачи представления данных.
9
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Глава 2
ЦЕЛЫЕ СИСТЕМАТИЧЕСКИЕ ЧИСЛА
§ 1. Определение систематической записи
Определение 1. Систематической записью натурального числа a в позиционной системе счисления с основанием g называется представление
s −1
числа а в виде: a = as g + as −1 g + ... + a1 g + a0 , где g ∈ N, g > 1, s ∈ N∪{0},
a0, a1, …, as – цифры g-ичной позиционной системы счисления, то есть
s
ai ∈{0, 1, 2, ..., g − 1} , причем, as ≠ 0 , i = 0, 1, ..., s .
Обозначение: a = (as as−1...a1 a0 ) g .
3
2
Пример. a = (2345) 7 = 2 ⋅ 7 + 3 ⋅ 7 + 4 ⋅ 7 + 5 .
Теорема 1. Пусть g ∈ N, g > 1 , s ∈ N ∪ {0} . Тогда всякое натуральs
s −1
ное число а представимо в виде a = as g + as−1 g + ... + a1 g + a0 , где
ai ∈{0, 1, 2, ..., g − 1} ,
as ≠ 0 , i = 0, 1, ..., s , и притом единственным об-
разом.
Доказательство. I. Докажем существование представления для произвольного натурального числа а.
1. Если 1 ≤ a ≤ g − 1 , то в этом случае s = 0 , a = a0 , a0 < g , поэтому
a0 ∈ {0, 1, 2, ..., g − 1} .
2. Если a ≥ g , то применим метод математической индукции по а:
а) a = g , отсюда a = 1 ⋅ g + 0 , то есть s = 1 , a1 = 1 , a0 = 0 , поэтому при
a = g утверждение верно;
б) предположим, что для всех натуральных чисел, меньших a (a ≥ g),
существует представление, и докажем, что оно существует и для числа a.
Имеем: a = gb + a0 , где ai ∈ {0, 1, 2, ..., g − 1} ,
Следовательно, для числа b существует представление:
b
<
a
, так как g > 1 .
b = a s g s −1 + a s −1 g s −2 + ... + a2 g + a1 ,
где a i ∈ {0, 1, 2, ..., g − 1} , i = 1, ..., s , as ≠ 0 . Тогда существует представление и для числа a, так как
a = gb + a0 = as g s + as −1 g s −1 + ... + a2 g + a1 + a0 ;
в) вывод: на основании принципа математической индукции получим,
что утверждение верно для любого натурального а, большего g − 1 .
Таким образом, из 1) и 2) получим утверждение для любого n ∈ N .
II. Докажем единственность представления.
10
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1. Если 1 ≤ a ≤ g − 1 , то единственность очевидна: a = a .
2. Если a ≥ g , то применим метод математической индукции по а.
а) a = g , утверждение верно, так как a = 1 ⋅ g + 0 ;
б) предположим, что для всех чисел, меньших a (a ≥ g), утверждение
верно, и докажем, что тогда оно верно и для а. Докажем от противного.
Предположим, что для а существуют два различных представления:
a = as g s + as −1 g s −1 + ... + a1 g + a0 ,
(1)
a = bm g m + bm−1 g m−1 + ... + b1 g + b0 ,
где
s, m ∈ N ∪ {0} ,
ai , b j ∈{0, 1, 2, ..., g − 1} ,
i = 0, 1, ..., s ,
(2)
j = 0, 1, ..., m ,
as ≠ 0 , bm ≠ 0 .
Тогда получим: a = g (as g s−1 + ... + a1 ) + a0 = g (bm g m−1 + ... + b1 ) + b0 .
А тогда по теореме о делении с остатком получим, что
a0 = b0 , as g s −1 + ... + a1 = bm g m −1 + ... + b1 = c ,
где c < a . Но тогда для числа с представление единственно, отсюда s = m
и для всех i = 0, 1, ..., s будет ai = bi .
Следовательно, представления (1) и (2) одинаковые, что противоречит
предположению;
в) вывод: на основании принципа математической индукции получим,
что утверждение верно для всех a (a ≥ g).
Таким образом, из 1) и 2) получим единственность представления для
любого натурального числа а.
Теорема 1 доказана.
§ 2. Арифметические операции
Рассмотрим арифметические операции:
1) сложение (или вычитание) как и в 10-ичной системе: складываем
единицы, затем переходим к следующему разряду и так далее, при этом если сумма больше основания системы или равна ему, то надо сделать перенос в следующий разряд;
2) умножение (или деление) так же, как и в 10-ичной системе, при этом
надо знать таблицу умножения для g.
Примеры. g = 6. Цифры: 0, 1, 2, 3, 4, 5.
1. Приведем пример сложения и вычитания в 6-ричной системе:
2.
a)
( 4256) 6
б)
(3(11)7)12
+ ( 2542) 6 ,
(11235) 6
−
11
( 2 5 4)12 .
(1 6 3)12
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2. Чтобы рассмотреть примеры умножения и деления в 6-ричной системе, заполним вначале таблицу умножения в 6-ричной системе:
⋅
0
0
1
2 3 4
5
0
0
0 0 0
0
1
0
1
2 3 4
5
2
0
2
4 10 12 14
3
0
3 10 13 20 23
4
0
4 12 20 24 32
5
0
5 14 23 32 41
Теперь приведем примеры умножения и деления в 6-ричной системе:
a)
б)
235
343
1153
+ 1432
1153
135213
×
135213 343
1130
235
2221
1513
3043
3043
0
(235) 6 ⋅ (343) 6 = (135213) 6
(135213) 6 : (343) 6 = (235) 6
,
.
Отметим, что деление трудно выполнить без навыка.
§ 3. Перевод в десятичную систему счисления и обратно
1. Перевод в 10-ичную систему ( g → 10) :
а) представить в виде систематической записи;
б) выполнить действия.
Пример. ((10)6(11))12 = 10 ⋅12 2 + 6 ⋅12 + 11 = (1523)10 = 1523 .
2. Перевод из 10-ичной системы (10 → h) :
а) разделить на h сначала a, а затем неполные частные, пока не получим неполное частное, равное 0:
a = hq1 + b0 ,
q1 = hq2 + b1 ;
б) составить число а:
a = (bmbm−1...b1 b0 ) h ,
qm = h ⋅ 0 + bm .
12
↑
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Пример. a = 5378, h = 6.
53 78
48
57
54
38
36
2
6
896
6
29
24
56
54
2
6
149
12
29
24
5
6
24
24
0
6
4
0
4
6
0
5378 = (40522) 6 .
Проверка: (40522) 6 = 4 ⋅ 6 4 + 0 ⋅ 6 3 + 5 ⋅ 6 2 + 2 ⋅ 61 + 2 = 5378 .
§ 4. Перевод из g-ичной системы в h-ичную систему
Перевод из g-ичной системы в h-ичную систему ( g → h) :
а) из g-ичной системы перейти к 10-hичной;
б) из 10-ичной системы перейти к h-ичной.
Пример. (32014) 5 , 5 → 8 .
4
3
2
1
а) (32014 ) 5 = 3 ⋅ 5 + 2 ⋅ 5 + 0 ⋅ 5 + 1 ⋅ 5 + 4 = 2134 ;
б)
2 1 34 8
16
268 8
53
24 3 3 8
48
26 3 2 4 8
54
24
1 0 0
48
2
4
6
2134 = (4126) 8 , следовательно, (32014) 5 = (4126) 8 .
Рассмотрим перевод: 2 → 8 , 8 → 2 .
g =8 0
1
2
3
4
5
6
7
g = 2 000 001 010 011 100 101 110 111
а) если 8 → 2 , то надо каждую цифру заменить триадой из таблицы.
Пример. (25420 ) 8 = (010 101 100 010 000) 2 = (0101011000 10000 ) 2 ;
б) если 2 → 8 , то надо справа налево разбить на триады и заменить
триады из таблицы.
Пример. (11'010'001'101'000'111) 2 = (321507 ) 8 ;
13
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
в) если 10 → 2 , то лучше: 10 → 8 → 2 (а не по § 4).
(32014) 5 = 3 ⋅ 5 4 + 2 ⋅ 53 + 0 ⋅ 5 2 + 1 ⋅ 51 + 4 = 2134 .
Пример. a = 2567 , 10 → 2 .
2567
24
16
16
7
0
7
8
320
32
0
0
0
8
40
40
0
8
5 8
0 0
5
2567 = (5007 ) 8 = (101 000 000 111) 2 , следовательно, (32014 ) 5 = ( 4126) 8 .
Вопросы для самоконтроля
1. Определение систематической записи. Теорема о представлении натурального числа в виде систематической записи.
2. Арифметические операции над систематическими числами.
3. Перевод в десятичную систему.
4. Перевод из десятичной системы.
5. Перевод из g-ичной системы в h-ичную систему.
Упражнения
1. Представить в виде систематической записи: (51306)7.
2. Записать кратко: 4 ⋅ 83 + 6 ⋅ 82 + 3 ⋅ 8.
3. Перейти к десятичной системе счисления:
а) (1023)5; б) (14(11))12.
4. Перейти к двоичной системе счисления: n = 46 = (46)10.
5. Перейти к 12-ричной системе счисления: n = 19510.
6. Осуществить переход:
а) (37051)8 = x6; б) (3507)8 = x2; в) (1011001110001111)2 = x8; г) 582 = x2.
7. Составить таблицу умножения в 7-ричной системе счисления.
8. Выполнить умножение: (1203)7 · (354)7.
9. Найти x: 26 = (101)x.
10. В какой системе счисления возможны равенства:
а) (14)x + (12)x = (30)x; б) (3)x · (5)x = (14)x; в) (52)x = 32.
14
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
11. В какой системе счисления число 46 изобразится теми же цифрами,
но в обратном порядке?
12. Правильно ли выполнено действие:
× 243
+ ( 40(10)8)12
а)
(31(11)9)12
,
(72(10)5)12
б) g = 5,
34
.
2132
+
1334
20472
15
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Глава 3
КОЛЬЦО КЛАССОВ ВЫЧЕТОВ
§ 1. Определение сравнения по натуральному модулю
Понятие сравнения было введено впервые Гауссом. Несмотря на свою
кажущуюся простоту, это понятие очень важно и имеет много приложений.
Пусть N – множество натуральных чисел, N = {..., 1, 2, ..., n, ...} , Z –
множество целых чисел, Z = {..., − n, − 2, − 1, 0, 1, 2, ..., n, ...} .
Определение 1. Целые числа а и b называются сравнимыми по натуральному модулю т, если разность а − b делится на т.
Запись: a ≡ b(mod m) , чтение: «а сравнимо с b по модулю т».
Заметим, что целое число x делится на целое число y , если существует
целое число z , такое, что x = yz. Запись: x # y. При этом будем говорить, что
число y делит число x, запись: y | x . Например, a = 25, b = 5, m = 10. Здесь
25 − 5 = 20, 20 # 10, следовательно, 25 ≡ 5(mod 10) . Сравним остатки от деления чисел 25 и 5 на модуль 10 (a = bq + r , q, r ∈ Z, 0 ≤ r < | b |) .
25 = 2 ⋅ 10 + 5, r1 = 5, 5 = 0 ⋅ 10 + 5, r 2 = 5, r1 = r 2 .
Теорема 1. Целые числа а и b сравнимы по натуральному модулю т
тогда и только тогда, когда числа а и b имеют одинаковые остатки при делении на т.
Доказательство. По теореме о делении с остатком целые числа а и b
можно единственным образом представить в виде:
a = mq1 + r1 , q1 , r1 ∈ Z, 0 ≤ r1 < m,
a = mq2 + r2 , q 2 , r21 ∈ Z, 0 ≤ r2 < m.
1) Докажем, что если a ≡ b(mod m ) , то r1 = r2 .
Доказательство. Так как a ≡ b(mod m) , то (a − b)# m . Но
a − b = (mq1 + r1 ) − (mq2 + r2 ) = m(q1 − q2 ) + (r1 − r2 ) .
Тогда так как (a − b) # m и m(q1 − q2 )# m , то
(r1 − r2 ) # m .
Из неравенств на остатки:
0 ≤ r1 < m, 0 ≤ r2 < m
(1)
получим, что
0 ≤ r1 − r2 < m .
(2)
Из (1) и (2) следует, что r1 − r2 = 0 , отсюда r1 = r2 .
2) Докажем, что если r1 = r2 , то a ≡ b(mod m) .
Доказательство. Так как r1 = r2 = r ( r – натуральное число или 0), то
a = mq1 + r , b = mq2 + r , тогда
a − b = m(q1 − q2 ) + (r − r ) = m(q1 − q2 ) + 0 = m(q1 − q2 ) ,
16
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
следовательно, a − b # m , а поэтому a ≡ b(mod m) .
Теорема 1 доказана.
Согласно этой теореме 1 сравнимость целых чисел a и b по натуральному m эквивалентна утверждению: «числа а и b имеют одинаковые остатки при делении на т».
Определение 2. Целые числа а и b называются сравнимыми по натуральному модулю т, если остатки от деления этих чисел на т равны.
Так как определения 1 и 2 эквивалентны, то при решении задач можно
пользоваться тем, которое дает более простое решение задачи.
Пример. Проверить истинность сравнений:
а) 75 ≡ 18(mod 13) ; б) 174 ≡ 18(mod 13) .
Решение. 1-й способ: а) 75−18=57, 57 не делится на 13, поэтому сравнение 75 ≡ 18(mod 13) ложно.
б) 75−18=57, 57 делится на 13, поэтому сравнение 174 ≡ 18(mod 13)
истинно.
1-й способ. а) 75=13⋅18+10, r1 = 10, 18=13⋅1+5, r1 = 5 , r1 ≠ r2 , следовательно, сравнение 75 ≡ 18(mod 13) ложно.
а) 174=13⋅13+5, r1 = 5, 18=13⋅1+5, r1 = 5 , r1 = r2 , следовательно,
сравнение 174 ≡ 18(mod 13) истинно.
В дальнейшем для записи сравнения, принимающего истинностное значение «ложно». будем использовать знак « ≡/ ». Например, 75 ≡/ 18(mod 13) .
Таким образом, запись a ≡/ b(mod m) означает, что целые числа а и b
не являются сравнимыми по натуральному модулю i.
Далее без доказательства приведем простейшие свойства сравнений по
натуральному модулю i.
Свойство 1. Отношение сравнимости рефлексивно:
(∀a ∈ N )(a ≡ a(mod m)) .
Свойство 2. Отношение сравнимости симметрично:
(∀a, b ∈ N )(a ≡ b(mod m) ⇒ b ≡ a(mod m)) .
Свойство 3. Отношение сравнимости транзитивно:
(∀a, b, c ∈ N )((a ≡ b(mod m) ∧ b ≡ c(mod m)) ⇒ a ≡ c(mod m)) .
Свойство 4. Для любых целых чисел a, b и k, если a ≡ b(mod m) , то
ka ≡ kb(mod m) :
(∀a, b, k ∈ N )(a ≡ b(mod m) ⇒ ka ≡ kb(mod m)) .
Свойство 5. Для любых целых чисел a, b и k, если ka ≡ kb(mod m)
при k ≠ 0 и взаимно простым с m, то a ≡ b(mod m) :
(∀a, b, k ∈ N )((ka ≡ kb(mod m) ∧ k ≠ 0 ∧ (k , m) = 1) ⇒ a ≡ b(mod m)) .
Свойство 6. Для любых целых чисел a и b и любого натурального k,
если a ≡ b(mod m) , то ka ≡ kb(mod km) :
17
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
(∀a, b, k ∈ N)(a ≡ b(mod m) ⇒ ka ≡ kb(mod km)) .
Свойство 7. Для любых целых чисел a и b и любого натурального k,
если ka ≡ kb (mod km ) , то a ≡ b(mod m) :
(∀a, b, k ∈ N )(ka ≡ kb(mod km) ⇒ a ≡ b(mod m)) .
Свойство 8. Сравнения по одинаковому модулю можно почленно
складывать и вычитать:
(∀a, b, c, d ∈ N )((a ≡ b(mod m) ∧ c ≡ d (mod m)) ⇒
⇒ (a + c ≡ b + d (mod m) ∧ a − c ≡ b − d (mod m))).
Свойство 9. Сравнения по одинаковому модулю можно почленно умножать:
(∀a, b, c, d ∈ N )((a ≡ b(mod m) ∧ c ≡ d (mod m)) ⇒ ac ≡ bd (mod m)).
Свойство 10.
(∀a , a ,..., a , b , b ,..., b
1
2
n
1
2
n
∈ N)
(((a1 ≡ b 1 (mod m)) ∧ ( a2 ≡ b 2 (mod m)) ∧ (an ≡ b n (mod m))) ⇒
⇒ (a1 + a2 + ... + an ≡ b1 + b2 + ... + bn (mod m)) ∧
∧ ( a1 a2 ... an ≡ b1 b2 ... bn (mod m))).
В частности,
(∀a, b ∈ N )(a ≡ b(mod m) ⇒ a n ≡ b n (mod m) ).
n
n −1
Свойство 11. Если a ≡ b (mod m ) , f ( x) = an x + an−1 x + a1 x + a0 , где
a, b, a 0 , a1 , ..., a n – целые числа, a n ≠ 0 , то f ( a ) ≡ f (b)(mod m) .
Свойство 12. Любое слагаемое из одной части можно переносить в другую с противоположным знаком: если a ≡ b + c (mod m ) , то a − b ≡ c (mod m ) .
Свойство 13. В сравнении можно отбрасывать или прибавлять слагаемые, кратные модулю:
а) если a ≡ b + mk (mod m) , то a ≡ b(mod m) , где k ∈ Z ;
б) если a ≡ b(mod m) , то a ≡ b + mn (mod m ) , где n ∈ Z ;
Свойство 14. Если a ≡ b (mod m ) и d | m , то a ≡ b(mod d ) .
Свойство 15. Если a ≡ b(mod m) , то ОД(а,т) = ОД(b,т).
В частности, НОД(а,т) = НОД(b,т).
Свойство 16. Если a ≡ b (mod m1 ), …, a ≡ b(mod ms ), то a ≡ b(mod m) ,
где m = НОК(m1, …, ms).
§ 2. Полная система вычетов
Отношение сравнимости вызывает разбиение множества целых чисел
Z на классы эквивалентности, которые называют классами вычетов по натуральному модулю m.
18
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Определение 3. Классом вычетов a по натуральному модулю m называется множество целых чисел, сравнимых с некоторым данным целым
числом a по модулю m.
def
a = {x ∈ Z | x ≡ a (mod m)}.
Пример. m = 7 . При делении числа a на 7 получим следующие возможные остатки:
0, 1, 2, 3, 4, 5, 6 ( a = 7 q + r , q, r ∈ Z , 0 ≤ r < 7 ).
1. Все целые числа, дающие остаток 0 при делении на 7 (то есть кратные 7), будут сравнимы между собой по модулю 7, следовательно, такие
числа принадлежат одному классу вычетов по модулю 7. Этот класс вычетов можно записать так: 0 (поскольку x ≡ 0(mod 7) ) или
0 = {0, 7, 14, ..., − 7, − 14, ...} . Этот же класс можно записать еще иначе: 7
(поскольку x ≡ 7(mod 7) ), 14 (поскольку x ≡ 14(mod 7) ) и т.д.
2. Все целые числа, дающие остаток 1 при делении на 7, будут сравнимы между собой по модулю 7, следовательно, такие числа принадлежат одному классу вычетов по модулю 7: 1 = {1, 8, 15, ..., − 6, − 13, ...}, или
x ≡ 1(mod 7) .
Заметим, что, например − 6 = 7 ⋅ ( −1) + 1 , следовательно, − 6 ∈ 1 . Но
− 7 = 7 ⋅ ( −1) + 0 , r = 0 , поэтому − 7 ∉ 1 , − 7 ∈ 0 .
3. Рассуждая аналогично, получим остальные классы вычетов по модулю 7:
2 = {2, 9, 16, ..., − 5, − 12, ...} или x ≡ 2(mod 7),
3 = {3, 10, 17, ..., − 4, − 11,...} или x ≡ 3(mod 7),
4 = {4, 11, 18, ..., − 3, − 10, ...} или x ≡ 4(mod 7),
5 = {5, 12, 19, ..., − 2, − 9, ...} или x ≡ 5(mod 7 ),
6 = {6, 13, 20, ..., − 1, − 8, ...} или x ≡ 6(mod 7).
Следовательно, классов вычетов по модулю 7 будет всего 7:
0 , 1 , 2, 3, 4, 5 , 6 .
Отметим следующие свойства классов вычетов.
Свойство 1. Любые два класса вычетов по модулю m или совпадают,
или не пересекаются. Объединение всех классов вычетов по модулю m есть
множество Z.
Доказательство. Пусть классы вычетов a и b по модулю m имеют
общий элемент c . Покажем, что тогда a = b .
1. Докажем, что ∀x(( x ∈ a ) ⇒ ( x ∈ b )). Имеем:
x ∈ a , следовательно, x ≡ a (mod m),
19
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
c ∈ a , следовательно, c ≡ a (mod m) ,
поэтому по симметричности a ≡ c (mod m) . Но тогда по транзитивности
получим,
что
x ≡ c (mod m) .
Кроме
того,
c∈b ,
следовательно,
c ≡ b(mod m) , поэтому по транзитивности x ≡ b(mod m) . Значит, x ∈ b .
2. Аналогично доказывается, что ∀x(( x ∈ b ) ⇒ ( x ∈ a )) .
Из 1) и 2) получим, что a = b (по определению равных множеств).
Если x ∈ Z , то x = mq + r , q, r ∈ Z, 0 ≤ r < m , и x ∈ r , т.е. множество
Z совпадает с объединением всех классов вычетов по модулю m.
Свойство 1 доказано.
Свойство 2. Если a и b – классы вычетов по модулю m, x ∈ a , y ∈ b ,
то a = b тогда и только тогда x ≡ y (mod m) .
Доказательство. 1. Если a = b , то из x ∈ a следует, что x ∈ b , но так
как и y ∈ b , то x ≡ y (mod m) .
2. Если x ≡ y (mod m) , то по симметричности y ≡ x(mod m) ; из x ∈ a
следует, что x ≡ a(mod m) , по транзитивности y ≡ a(mod m) , поэтому y ∈ a .
Таким образом, по свойству 1, классы вычетов a и b , как содержащие общий элемент y, будут совпадать: a = b .
Свойство 2 доказано.
Свойство 3. Если a – класс вычетов по модулю m, то
a = {a + mk | k ∈ Z} .
Доказательство. Имеем если x ∈ a , то x ≡ a(mod m) , отсюда получим,
что ( x − a) # m, следовательно, (∃k ∈ Z)( x − a = mk ) . Поэтому
x = a + mk , где k – целое число. Но тогда
a = {x | x ≡ a(mod m)} = {a + mk | k ∈ Z} .
Свойство 3 доказано.
Любое число из класса вычетов a по модулю m называется вычетом
по модулю m. Число a называется представителем класса a . Любое число
из класса a может быть представителем класса a : если x ∈ a , то x = a .
Определение 4. Полной системой вычетов по модулю m называется
множество m целых чисел, содержащее точно по одному представителю из
каждого класса вычетов модулю m .
Пример. m = 7 , 0, 1, 2, 3, 4, 5, 6 – классы вычетов по модулю 7.
1. {7, 8, 16, 3, 11, 26, 48} – полная система вычетов по модулю 7, так как
всего 7 чисел и они взяты точно по одному из каждого класса по модулю 7,
а именно 7 ∈ 0 , 8 ∈ 1 , 16 = 7 ⋅ 2 + 2 , поэтому 16 ∈ 2 , 3∈ 3 , 11 = 7 ⋅ 1 + 4 , поэтому 11∈ 4 , 26 = 7 ⋅ 3 + 5 , поэтому 26 ∈ 5 , 48 = 7 ⋅ 6 + 6 , поэтому 48 ∈ 6 ;
2. {0, 1, 2, 3, 4, 5, 6} – полная система вычетов по модулю 7.
20
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Заметим, что полных систем вычетов по модулю 7 (как и по произвольному модулю m) существует бесконечное множество. Среди них выделяется полная система наименьших неотрицательных вычетов
{0, 1, 2, 3, 4, 5, 6} и полная система наименьших по абсолютной величине
вычетов {0, 1, 2, 3, − 1, − 2, − 3} .
Определение 5. Множество {0, 1, 2, 3, ..., m − 1} называется полной системой наименьших неотрицательных вычетов по модулю m.
Теорема 2. Любые m целых чисел a0 , a1 , ..., am−1 , попарно несравнимые по модулю m, образуют полную систему вычетов по модулю m.
Доказательство. 1. Так как числа a0 , a1 , ..., am−1 попарно несравнимые
по модулю m, то они принадлежат различным классам вычетов по модулю m.
2. Всего этих чисел m. Это число совпадает с количеством классов вычетов по модулю m.
3. Следовательно, в каждый класс вычетов по модулю m попадает по
одному числу.
Таким образом, числа a0 , a1 , ..., am −1 образуют полную систему вычетов по модулю m.
Теорема 2 доказана.
Теорема 3. Если a и b – произвольные целые числа, m – натуральное, НОД(a,b) = 1 и число x пробегает полную систему вычетов по модулю
m, то число y, где y = ax + b , тоже пробегает полную систему вычетов по
модулю m.
Доказательство. 1. Так как число x пробегает полную систему вычетов по модулю m, то x принимает m значений x0 , x1 , ..., xm−1 несравнимых
попарно по модулю m, а, следовательно, число y, где y = ax + b , также будет принимать m значений.
2. Докажем, что любые два целых числа y k , где y k = axk + b, и
y n , где y n = axn + b, где xk , xn ∈ {x0 , x1 , ..., xm−1} , вида ax + b несравнимы по модулю m.
Докажем от противного. Предположим, что y k ≡ y n (mod m) , поэтому
axk + b ≡ axn + b(mod m) . Отсюда получим, что axk ≡ axn (mod m) .
Однако НОД(a,m) = 1. Следовательно, xk ≡ xn (mod m) , что противоречит условию о том, что числа x0 , x1 , ..., xm −1 попарно несравнимы по
модулю m.
Таким образом, из 1) и 2), применяя теорему 2, получим, что число y,
где y = ax + b , тоже пробегает полную систему вычетов по модулю m.
Теорема 3 доказана.
21
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
§ 3. Аддитивная группа классов вычетов
Пусть m ∈ N . Классы вычетов по модулю m: 0 , 1 , 2 , …, m − 1 . Определим следующие операции над классами вычетов по модулю m:
1) сложение: a + b = a + b или a + b = x + y , где x ∈ a , y ∈ b ;
2) умножение: a ⋅ b = ab или a ⋅ b = pq , где p ∈ x , q ∈ b .
Пример. m = 5 , классы вычетов по модулю 5: 0 , 1 , 2 , 3 , 4 .
1. Найдем сумму 2 + 4 . По определению 2 + 4 = 2 + 4 = 6 . А так как
6 ≡ 1(mod 5) , то 6 = 1 , поэтому получим, что 2 + 4 = 1 .
Заметим, что можно рассуждать иначе: 2 ∈ 2 , 9 ∈ 4 , поэтому
2 + 4 = 2 + 9 = 11 . Но 11 ≡ 1(mod 5) , следовательно, 11 = 1 , тогда 2 + 4 = 1 .
2. Найдем произведение классов вычетов 2 ⋅ 4 . Имеем: 2 ⋅ 4 = 2 ⋅ 4 = 8 . Но
8 ≡ 3(mod 5) , поэтому 8 = 3 , следовательно, 2 ⋅ 4 = 3 .
Обозначим через G множество всех классов вычетов по модулю m :
G = {0, 1 , 2, ..., m − 1} .
(3)
Теорема 4. Множество G всех классов вычетов по модулю m образует
группу относительно сложения классов вычетов.
Доказательство. Сложение классов вычетов по модулю m замкнуто в
множестве G, то есть (∀a , b ∈ G)(∃!c ∈ G)(c = a + b ) . Надо проверить единственность: определение суммы классов вычетов не должно быть зависимым
от выбора представителей классов вычетов. Пусть a = x и b = y . Тогда:
a ≡ x(mod m) , b ≡ y (mod m) , (a − x ) # m , (b − y ) # m , (a − x ) + (b − y ) # m ,
(a + b) − ( x + y ) # m , (a + b) ≡ ( x + y)(mod m) , a + b = x + y ,
a +b = a +b, x + y = x + y , a +b = x + y.
Значит, сумма классов вычетов a + b не зависит от выбора представителей классов a и b .
Проверим выполнимость аксиом, определяющих группу.
1) Ассоциативность сложения: (∀a , b , c ∈ G)((a + b ) + c = a + (b + c )) .
Преобразуем отдельно суммы, стоящие в левой и правой частях равенства: (a + b ) + c = a + b + c = (a + b) + c ,
a + (b + c ) = a + b + c = a + (b + c) . Но (a + b) + c = a + (b + c) , так как сложение в
Z ассоциативно, поэтому (a + b ) + c = a + (b + c ) , следовательно, аксиома
1) выполнена.
2) Существование в G нейтрального элемента:
(∃e ∈ G )(∀a ∈ G )(a + e = e + a = a ) .
Найдем нейтральный элемент e для сложения в G: по определению
сложения классов вычетов a + e = a + e , по условию a + e = a . Тогда полу22
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
чим уравнение a + e = a . Эти два класса равны, если a + e ≡ a(mod m) , отсюда e ≡ 0(mod m) , следовательно, e = 0 . Так как 0 ∈ G , a + 0 = 0 + a = a ,
то аксиома 2) выполнена.
3) Существование в G для каждого элемента симметричного ему элемента: (∀a ∈ G )(∃a ′ ∈ G )(a + a ′ = a ′ + a = 0) .
Чтобы найти a ′ = x , запишем a + x = a + x , a + x = 0 , тогда получим
a + x = 0 , отсюда a + x ≡ 0(mod m) , следовательно, x ≡ −a(mod m) , тогда
x = − a , a ′ = − a (класс вычетов, содержащий симметричный элемент для
элемента a). a ′ + a = ( − a ) + a = 0 . Итак, аксиома 3) выполнена.
Таким образом, G , + – группа.
Теорема 4 доказана.
Замечание. Заметим, что в G выполнена еще одна аксиома:
4) Коммутативность сложения: (∀a , b ∈ G)(a + b = b + a ) .
Действительно, так как a + b = a + b , а b + a = b + a , то, в силу коммутативности сложения в Z получим, что a + b = b + a .
Следовательно, группа G , + – абелева группа. Эту группу называют
аддитивной группой классов вычетов по модулю m.
Пример. m = 5 , G = {0, 1, 2, 3, 4} . Сложение классов вычетов по модулю 5 запишем в виде следующей таблицы:
+
0
1
2
3
4
0
0
1
2
3
4
1
1
2
3
4
0
2
2
3
4
0
1
3
3
4
0
1
2
4 4 0 1 2 3
На пересечении строки, начинающейся с класса вычетов 3 , и столбца,
начинающегося с класса вычетов 4 , находится сумма 3 + 4 :
3 + 4 = 3+ 4 = 7 = 2 .
Отметим противоположные (симметричные) элементы:
− 0 = 0 , − 1 = 4 , − 2 = 3 , − 3 = 2 , − 4 = 1.
§ 4. Кольцо классов вычетов
Пусть m ∈ N , множество G определено равенством (3):
G = {0 , 1 , 2, ..., m − 1}
23
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Теорема 5. Множество G всех классов вычетов по модулю m образует
кольцо относительно сложения и умножения классов вычетов.
Доказательство. Сложение классов вычетов по модулю m замкнуто в
множестве G, то есть (∀a , b ∈ G )(∃!c ∈ G )(c = a + b ) . Умножение классов
вычетов по модулю m замкнуто в множестве G, то есть
(∀a , b ∈ G )(∃!c ∈ G )(c = a ⋅ b ) . Надо проверить единственность: определение произведения классов вычетов не должно быть зависимым от выбора
представителей классов вычетов. Пусть a = x и b = y . Тогда:
a ≡ x (mod m ), b ≡ y (mod m), ( a − x) # m, (b − y )# m ,
(a − x)b + x(b − y )# m , (ab − xb + xb + xy)# m , ( a ⋅ b) ≡ ( x ⋅ y )(mod m) ,
a ⋅b = x ⋅ y , a ⋅b = a ⋅b , x ⋅ y = x ⋅ y , a ⋅b = x ⋅ y .
Значит, произведение классов вычетов a ⋅ b не зависит от выбора представителей классов a и b .
Проверим выполнимость аксиом, определяющих кольцо.
1) G, + – абелева группа. Эта аксиома выполнена (по теореме 2 из § 4
и замечанию к ней).
2) Левая и правая дистрибутивность умножения относительно сложения: а) (∀a , b , c ∈ G )(c (a + b ) = c a + c b ) ;
б) (∀a , b , c ∈ G )((a + b )c = a c + b c ) .
Имеем: а) c ( a + b ) = c ⋅ a + b = c ( a + b) , c a + c b = ca + cb = ca + cb .
Но c ( a + b) = ca + cb , так как умножение в Z дистрибутивно относительно сложения, поэтому c ( a + b ) = c a + c b ;
б) aналогично. Следовательно, аксиома 2) выполнена.
Таким образом, G, ⋅, + – кольцо.
Теорема 5 доказана.
3) Умножение ассоциативно в G: (∀a , b , c ∈ G )((a b )c = a (b c )) .
Преобразуем отдельно произведения, стоящие в левой и правой частях
равенства: ( a b )c = abc = ( ab )c , a (b c ) = a bc = a (bc ) . Но ( ab )c = a (bc ) ,
так как умножение в Z ассоциативно, следовательно, (a b )c = a (b c ) . Аксиома 3) выполнена. Поэтому кольцо G, ⋅, + является ассоциативным.
Заметим, что умножение в G коммутативно, то есть:
4) (∀a , b ∈ G )(a b = b a ) .
Действительно, a b = ab , b a = ba . Но ab = ba в силу коммутативности умножения в Z , поэтому a b = b a , следовательно, аксиома 4)
24
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
выполнена. Поэтому кольцо G, ⋅, + является коммутативным. Это кольцо
называется кольцом классов вычетов по модулю m и обозначается Z m .
Кроме того, в G выполнена еще одна аксиома:
5) (∃e ∈ G )((e ≠ 0 ) ⇒ (∀a ∈ G )( a e = e a = a )) .
Следовательно, кольцо G, ⋅, + является кольцом с единицей (e = 1 ) .
Если модуль m = p – простое число, то кольцо G, ⋅, + является полем.
Пример. m = 5 , Z 5 = {0 , 1 , 2, 3, 4} .
Приведем таблицы сложения и умножения в кольце
тов по модулю 5:
Z 5 классов выче-
+
0
1
2
3
4
⋅
0
1
2
3
4
0
0
1
2
3
4
0
0
0
0
0
0
1
1
2
3
4
0
1
0
1
2
3
4
2
2
3
4
0
1
2
0
2
4
1
3
3
3
4
0
1
2
3
0
3
3
4
2
4
4
0
1
2
3
4
0
4
3
2
1
В таблице умножения на пересечении строки, начинающейся с класса
вычетов 3 , и столбца, начинающегося с класса вычетов 4 , находится произведение 3 ⋅ 4 : 3 ⋅ 4 = 3 ⋅ 4 = 12 = 2 .
Множество Z5 замкнуто относительно сложения и умножения,
Z 5 , + является абелевой группой, Z 5 , +, ⋅ является ассоциативным и коммутативным кольцом с единицей, отличной от нуля. Для всякого
ненулевого элемента существует симметричный (обратный) ему элемент
относительно умножения, то есть всякий ненулевой элемент обратим. Поэтому кольцо Z 5 , +, ⋅ является полем.
Заметим, что если, например, m = 6 , то Z 6 образует кольцо, которое
не является полем.
Кольцо классов вычетов по простому модулю p образует поле.
Вопросы для самоконтроля
1. Сравнение в кольце целых чисел.
2. Свойства сравнений.
3. Классы вычетов по натуральному модулю.
25
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
4. Свойства классов вычетов.
5. Полная система вычетов.
6. Аддитивная группа классов вычетов.
7. Кольцо классов вычетов.
Упражнения
1. По какому модулю все целые числа сравнимы между собой?
2. Привести примеры целых чисел, сравнимых по модулю 8.
3. Привести примеры целых чисел, имеющих с модулем 6 один и тот
же НОД, но несравнимых по этому модулю.
4. Применить понятие сравнения к доказательству того, что числа 210
и 858 имеют с модулем 12 один и тот же НОД. Применим ли этот прием относительно чисел 385 и 77 и модуля 6?
5. Какие из следующих сравнений являются верными:
а) 1 ≡ –5(mod 6),
в) 23 ≡ 1(mod 4),
б) 546 ≡ 0(mod 3),
г) 3m ≡ –1(mod m).
6. Доказать, что следующие сравнения являются верными:
а) 121 ≡ 13145(mod 2),
б) 121347 ≡ 92817(mod 10),
г) (m–1)2 ≡ 1(mod m),
в) 31 ≡ –9(mod 10),
д) 2m+1 ≡ (m + 1)2(mod m).
7. Доказать, что следующие сравнения являются неверными:
а) 51812 ≡ 1964(mod 25),
б) 7103 ≡ 3(mod 27),
г) 30 ⋅ 17 ≡ 81 ⋅ 19(mod 6),
в) 41965 ≡ 25(mod 10),
д) (2m + 1)(2n + 1) ≡ 2k(mod 6), где m, n, k ∈ Z.
8. Доказать, что каждое число сравнимо со своим остатком по данному
модулю.
9. Число х удовлетворяет условию x ≡ 2(mod10). Записать это условие в
виде уравнения с параметром и найти несколько значений х.
10. Найти все значения х, удовлетворяющие сравнению:
а) x ≡ 0(mod 3),
б) x ≡ 1(mod 2).
11. Найти все значения m, удовлетворяющие условию:
а) 20 ≡ 8(mod m),
26
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
б) 3p + 1 ≡ p + 1(mod m), где p – простое число.
12. Указать возможное значение модуля в сравнении x ≡ 5(mod m),если
известно, что этому сравнению удовлетворяет x0 = 13.
13. Записать в виде сравнений все классы по модулю 10.
14. Записать все классы по модулю 10 при помощи формулы:
x = 10q+r, где 0≤r<10.
15. Найти полные системы вычетов по модулю 10: наименьших неотрицательных вычетов и наименьших по абсолютной величине вычетов.
16. По какому модулю числа 20, –4, 22, 18, –1 составляют полную систему вычетов?
17. Доказать, что множество чисел 20, 31, –8, –5, 25, 14, 8, –1, 13, 6 не
являются полной системой вычетов по модулю 10.
18. Найти одну полную систему вычетов вида 5x по модулю 4.
27
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Глава 4
ПОЛЕ АЛГЕБРАИЧЕСКИХ ЧИСЕЛ
§ 1. Определение алгебраического числа
Определение 1. Алгебраическим числом называется комплексное (в
частности, действительное) число α , которое является корнем некоторого
многочлена от одной переменной
f ( x) = an x n + an−1 x n−1 + ... + a0
(1)
с рациональными коэффициентами a i , i = 0, 1, ..., n , a n ≠ 0 .
Приведя коэффициенты многочлена (1) к общему знаменателю, можно
получить многочлен с целыми коэффициентами, корнем которого будет α .
Однако при этом старший коэффициент a n не обязательно равен 1.
Рациональные числа и квадратичные иррациональности представляют
собой корни многочленов 1-й и 2-й степени с целыми коэффициентами. В
этой главе будем рассматривать корни многочленов с целыми коэффициентами любой степени.
Определение 2. Алгебраическое число α называется целым алгебраическим числом, если является корнем многочлена (1) с целыми коэффициентами ai , i = 0, 1, ..., n , со старшим коэффициентом, равным 1 : a n = 1 .
Далее будем рассматривать только те целые алгебраические числа, которые принадлежат множеству действительных чисел R .
Из равенства f (α ) = 0 следует равенство f (α ) g (α ) = 0 , где в качестве
g (α) можно взять произвольный многочлен с целыми коэффициентами.
Поэтому для любого алгебраического числа α существует бесконечное
множество многочленов с рациональными коэффициентами, корнями которых является α.
Многочлен наименьшей степени с рациональными коэффициентами и
со старшим коэффициентом 1, корнем которого является алгебраическое
число α, называется минимальным.
Определение 3. Число n называется степенью целого алгебраического
числа α, если α есть корень некоторого многочлена n -й степени с целыми
коэффициентами, со старшим коэффициентом 1, и не существует многочлена с целыми коэффициентами, со старшим коэффициентом 1, степени,
меньшей чем n, корнем которого являлось бы число α.
Короче, степень минимального многочлена называется степенью алгебраического числа. Рациональные числа, и только они являются алгебраическими числами 1-й степени. Целые числа и только они являются целыми алгебраическими числами 1-й степени.
28
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Любая квадратичная иррациональность представляет собой алгебраическое число 2-й степени, так как, являясь корнем квадратного уравнения с целыми коэффициентами, она не является корнем какого-либо уравнения 1-й степени с целыми коэффициентами.
Пример. 2 – целое алгебраическое число степени 2, оно является
корнем многочлена f ( x) = x 2 − 1 и не является корнем никакого многочлена
первой степени с рациональными коэффициентами.
Отметим, что алгебраические числа 3-й степени часто называют кубическими иррациональностями.
Пример. 3 2 – целое алгебраическое число 3-й степени, то есть кубическая
иррациональность. Действительно, это число – корень многочлена 3-й степени
f ( x) = x 3 − 2 с целыми коэффициентами и не является корнем какого-либо
многочлена 1-й или 2-й степени с целыми коэффициентами.
Приведем примеры целых алгебраических чисел степени n = 2 .
1. Алгебраическое число α1 = i ∈ C , оно является целым алгебраическим числом степени 2 и f ( x) = x 2 + 1 .
2. Алгебраическое число α 2 = 1 + 2 является целым алгебраическим
числом степени 2 ( f ( x) = x 2 − 2 x − 1) .
§ 2. Минимальный многочлен алгебраического числа
Далее рассматриваем алгебраические числа, не обязательно целые.
Определение 4. Многочлен f(х) называется минимальным многочленом для алгебраического числа α, если f(х) – многочлен наименьшей степени с рациональными коэффициентами и старшим коэффициентом 1, корнем
которого является число α.
Если вместо многочлена f(х) взять какой-либо другой многочлен с рациональными коэффициентами степени п, корнем которого является α, то
многочлен f(х) может быть получен из него делением всех коэффициентов
на коэффициент старшего члена.
3
Пример. Алгебраическое число
2
является корнем как многочлена
2
1
, так и многочлена f 2 ( x) = 4 x 3 − 1 . Минимальный многочлен
4
3
2
1
f1 ( x ) = x 3 −
для алгебраического числа
получается из многочлена
2
4
f 2 ( x) = 4 x 3 − 1 делением всех коэффициентов на 4.
f1 ( x ) = x 3 −
29
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Теорема 1. Если f(х) – минимальный многочлен для алгебраического
числа α и F(х) – многочлен с рациональными коэффициентами, такой, что
F(α) = 0, то f(х) – делитель F(x), то есть F(x) = f(x)g(х), где g(х) также многочлен с рациональными коэффициентами.
Доказательство. Согласно известной теореме алгебры (о делении с остатком для многочленов) многочлен F(x) можно представить в следующем
виде: F(x) = f(x)g(х) + r(x), где g(x) и r(х) – многочлены с рациональными коэффициентами, а степень многочлена r(х) меньше степени многочлена f(x)
или r(х) = 0. Так как F(α) = 0 и f(α) = 0, то, при x = α, получим:
r (α ) = F (α ) − f (α ) g (α ) = 0 − 0 ⋅ g (α ) = 0 .
Значит, α – корень многочлена r(х) с рациональными коэффициентами
степени, меньшей, чем у минимального для α многочлена, то есть меньшей,
чем степень α. Это может быть только, если r(х) тождественно равно нулю:
r(х) = 0. Следовательно, F(x) = f(x)g(х).
Теорема 1 доказана.
Для данного алгебраического числа α существует единственный минимальный многочлен. Из теоремы 1 следует, что если F(х) и f(х) – минимальные многочлены для данного алгебраического числа α, F(x) = f(x)g(х), частное g(х) от деления F(x) на f(x) равно 1, что означает равенство F(x) = f(x).
Теорема 2. Для любого алгебраического числа α минимальный многочлен неприводим над полем рациональных чисел.
Доказательство. Пусть f(x) – минимальный многочлен степени п для
алгебраического числа α. Предположим, что f(x) приводим над полем рациональных чисел, то есть что f(x) = f1(x)f2(х), где f1(x) и f2(х) – многочлены
положительной степени с рациональными коэффициентами степени, меньшей чем п.
Из числового равенства f1(α)f2(α) = f(α) = 0 следует, что f1(α) = 0 или
f1(α) = 0. Если f1(α) = 0, то в силу теоремы 1 f(x) делит f1(x), что невозможно.
Аналогично, для случая f2(α) = 0. Предположение, что многочлен f(x) приводим над полем рациональных чисел, оказалось неверным, поэтому f(x)
неприводим над этим полем.
Теорема 2 доказана.
Теорема 3. Если α – корень неприводимого над полем рациональных
чисел многочлена F(x) с рациональными коэффициентами степени п, то α –
алгебраическое число степени п.
Доказательство. Число α как корень многочлена F(x) с рациональными
коэффициентами является алгебраическим числом. Обозначим минимальный
многочлен для алгебраического числа α через f(x). По теореме 1 имеем: F(x) =
= f(x)g(х); где g(х) – многочлен с рациональными коэффициентами. Так как
F(x) является неприводимым над полем рациональных чисел и f(x) не является
30
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
постоянной, то g(x) = C, где C – рациональное число, F(x) = Cf(x), поэтому степень f(x) равна п и, следовательно, α – алгебраическое число п-й степени.
Теорема 3 доказана.
Пример. Пусть р – простое число, а – целое число, а > 1, a ≠ b
p
для
p
любого целого числа b . Тогда a – алгебраическое число степени р, так
как это число есть корень неприводимого над полем рациональных чисел
p
многочлена f ( x) = x − a .
§ 3. Операции над алгебраическими числами
Если α – алгебраическое число степени п и f(x) – минимальный многочлен для α, то все корни α1, α2, …, αп многочлена f(x), отличные от α, называются сопряженными с α.
Один из корней α1, α2, …, αп (будем ставить его на первое место) совпадает с α, так что α = α1.
α
Теорема 4. Сумма α + β , разность α − β , произведение α ⋅ β и частное
β
(для частного при β ≠ 0) двух алгебраических чисел α и β являются алгебраическими числами.
Доказательство. 1) Пусть α – корень многочлена f(х) степени п с целыми коэффициентами, корни которого α1, α2, …, αп, а β – корень многочлена g(х) степени т с целыми коэффициентами, корни которого β1, β2, …,
βп (β=β1). Рассмотрим многочлен:
n
F ( x) = ∏
i =1
m
∏ ( x − (α
i
+ β j )) =
j =1
= ( x − α1 − β1 )( x − α1 − β 2 )...( x − α1 − β m ) ×
× ( x − α 2 − β1 )( x − α 2 − β 2 )...( x − α 2 − β m ) ×
. . .
(2)
× ( x − α n − β1 )( x − α n − β 2 )...( x − α n − β m ).
Если в этом произведении сделать какую угодно подстановку величин
α1, α2, …, αп, то некоторые строки будут переставлены местами, но произведение в целом не изменится. Поэтому F(x) – симметрический многочлен
по отношению к α1, α2, …, αп.
Точно так же подстановка величин β1, β2, …, βп будет менять только
порядок столбцов в правой части выражения (2), так что F(x) – симметрический многочлен по отношению к β1, β2, …, βп.
В целом F(x) – симметрический многочлен от двух систем аргументов:
α1, α2, …, αп и β1, β2, …, βп.
31
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Согласно известным теоремам о симметрических многочленах коэффициенты многочлена F(x) могут быть выражены рационально через элементарные симметрические функции от α1, α2, …, αп и β1, β2, …, βп, то есть
через целые коэффициенты f(x) и g(х). Это значит, что коэффициенты F(x)
рациональны и, следовательно, число α + β = α1 + β1, являющееся, что непосредственно видно из формулы (2), корнем F(x), есть алгебраическое
число.
2) Для доказательства того, что произведение двух алгебраических чисел α и β есть алгебраическое число аналогично пункту 1) для многочлена
(2), рассмотрим многочлен
n
F ( x) = ∏
i =1
m
∏ ( x − (α β
i
j
)).
(3)
j =1
Этот многочлен с целыми коэффициентами имеет в качестве одного из
своих корней αβ = α1β1.
3) Пусть β – корень многочлена g ( x) = bn x n + bn−1 x n−1 + ... + b0 , ( bi – целые
числа), тогда −β является корнем многочлена с целыми коэффициентами
g (− x) = (−1) n bn x n + (−1) n−1 bn−1 x n−1 + ... + b0 ,
а если β ≠ 0, то
1
– корень многочлена
β
g
1
= bn + bn−1 x + ... + b0 x n .
x
Таким образом, вместе с β алгебраическими числами являются (−β) и
1
. Разность α − β может быть представлена в виде α + (−β), то есть в виде
β
суммы двух алгебраических чисел, а потому также представляет собой алгебраическое число.
При β ≠ 0 частное
α
1
= α , являясь произведением двух алгебраических
β
β
чисел, представляет собой также алгебраическое число.
Если степени алгебраических чисел α и β равны т и п, то, взяв в качестве f(х) и g(х) соответствующие минимальные многочлены, будем в (2) и
(3) иметь многочлены степени mn , поэтому α + β и αβ – алгебраические
числа степени, не большей чем mn .
⎛1⎞
⎝ x⎠
n
Многочлены g(х), g(−х) и x g ⎜ ⎟ одинаковой степени, следовательно,
1
– алгебраические числа одной и той же степени. Отсюда следует,
β
α
что и α − β, и имеют степени, не больше чем mn .
β
β, −β и
32
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Теорема 4 доказана.
Примеры. 1) 2 и 3 – алгебраические числа 2-й степени, а 2 + 3 –
алгебраическое число 4-й степени. Действительно, если α = 2 + 3 , то α2 =
= 5+2 6 , а α4 − 10α2 + 1 = 0, поэтому α – корень многочлена
f ( x) = x 4 − 10 x 2 + 1 с целыми коэффициентами и
f ( x ) = ( x − 2 − 3 )( x − 2 + 3 )( x + 2 − 3 )( x + 2 + 3 ) .
(4)
Из теоремы о единственности разложения многочлена на неприводимые множители следует, что любые неприводимые над полем рациональных чисел множители f(х) должны являться произведением каких-то множителей правой части равенства (4). Из этих множителей нельзя составить
многочлен с рациональными коэффициентами степени, меньшей чем 4, поэтому f(х) – неприводимый над полем рациональных чисел многочлен, следовательно, по теореме 3,
2 + 3 – алгебраическое число 4-й степени.
6
2) α = 3 и β = 6 12 – алгебраические числа 6-й степени, а произведение αβ = 3 6 – алгебраическое число 3-й степени.
§ 4. Поле алгебраических чисел
Теорема 5. Множество A всех действительных алгебраических чисел
образует поле.
Доказательство. Множество A непустое. По теореме 4 получим, что
операции (+) и (⋅) замкнуты, то есть являются бинарными алгебраическими
операциями на множестве A.
Числа 0 и 1 – алгебраические числа, как корни многочленов f ( x ) = x и
f ( x ) = x − 1 соответственно. Операция нахождения противоположного числа (−α) по теореме 4 тоже определена на множестве A.
Легко убедиться, что выполнены все аксиомы поля. Перечислим их.
1. (∀α, β, γ∈A) (α + (β + γ) = (α + β) + γ).
2. (∀α ∈ A) (α + 0 = α).
3. (∀α ∈ A) (α + (−α) = 0).
4. (∀α, β ∈ A) (α + β = β + α).
5. (∀α, β, γ ∈ A) ((α + β)γ) = αγ + βγ).
6. (∀α, β, γ ∈ A) (α (βγ) = (αβ)γ).
7. (∀α, β ∈ A) (αβ = βα).
8. (∀α ∈ A) (α⋅1 = α).
9. (∀α ∈ A)(α ≠ 0 ⇒ (∃β ∈ A)(αβ = 1)).
10. 1 ≠ 0.
33
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Аксиома 9 выполняется тоже по теореме 4. Остальные аксиомы истинны, так как имеют место для всех действительных чисел.
Таким образом, множество A всех действительных алгебраических чисел образует поле.
Теорема 5 доказана.
Вопросы для самоконтроля
1. Определение алгебраического числа.
2. Определение целого алгебраического числа.
3. Минимальный многочлен для алгебраического числа.
4. Степень алгебраического числа.
5. Операции над алгебраическими числами.
6. Поле алгебраических чисел.
Упражнения
1. Доказать, что число αα = 5 – алгебраическое число:
а) α = 5 ; б) α = 3 + 4 ; в) α = 3 + 4 .
2. Показать, что целые алгебраические числа образует кольцо.
3. Привести пример алгебраического числа степени 3, не являющегося
целым алгебраическим числом.
4. Найти минимальный многочлен для алгебраического числа:
а) α = 1+ 3 ; б) α = 1+ 3 2 .
5. Привести пример многочлена f (x ) с целыми коэффициентами, корнем которого является число α , причем степень многочлена f (x ) должна
быть больше степени числа α .
6. Найти сумму, произведение и частное двух алгебраических чисел:
α = 2 + 3 2 и β = 1− 23 2 .
34
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Глава 5
ПРЕДСТАВЛЕНИЕ ДАННЫХ
§ 1. Представление целых чисел
Системы компьютерной алгебры имеют дело с большими целыми числами, в частности, любая такая система умеет вычислять и выводить в десятичной записи числа вида 1000! (более 1000 знаков). Рассмотрим представление целых чисел в символьном виде и не будем вдаваться в подробности,
какая память отводится для записи одного символа (бит, байт или другая).
Наиболее распространенным является представление целых чисел в
позиционных системах счисления. Такая система определяется выбором
основания счисления, например, 10. Множество десятичных целых чисел
обычно описывается следующим образом:
= = <натуральное число>|0|
−<натуральное число>
натуральное число
= = <значащая цифра> |
<значащая цифра> <цифры>
= = 1|2|3|4|5|6|7|8|9
значащая цифра
цифры
= = <цифра> |
<цифра> <цифры>
= = 0 | <значащая цифра>
цифра
целое число
Выписанное определение целых чисел дает однозначность представления каждого такого числа, и аналогичное определение (возможно, с другим
основанием) используется в большинстве систем компьютерной алгебры.
Пользуясь таким представлением, удобно реализовать арифметические операции над целыми числами.
Отметим, что наряду с каноническими представлениями в системах
компьютерной алгебры используются и другие представления. В частности,
желательно, чтобы наличие или отсутствие знака «+» перед целым числом
не влияло на восприятие его компьютером. Таким образом, для положительных чисел получается неоднозначное представление, хотя форма отрицательных чисел определена однозначно.
= = <натуральное число> |
<положительное целое>
+ <натуральное число>
<отрицательное целое>
= = − <натуральное число>
Другое требование: на восприятие числа не должно влиять наличие нулей перед первой значащей цифрой.
35
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
§ 2. Представление классов вычетов
Кольца вычетов и конечные поля представляют собой наиболее простые объекты с точки зрения задачи представления данных. Каждому элементу такого кольца или поля, состоящего из n элементов, соответствовать,
например, взаимно-однозначно неотрицательное целое число из отрезка
[0, n − 1]. Операции выполняются в кольце вычетов по модулю n.
В поле арифметические операции сложно определяются. Можно для
конечного поля использовать другие формы представления, например, при
n = p (p – простое число) использовать систему вычетов по модулю p и операции как в кольце вычетов по модулю p.
Существует два разных подхода к построению канонического представления элементов конечного поля:
1) векторное представление: x – такой элемент, что его степени x0=1, x1,
x2, … , xk − 1 порождают поле как векторное пространство;
2) степенное представление: α – элемент, порождающий мультипликативную группу этого поля.
Отметим, что переход от 1) к 2) достаточно прост, а от 2) к 1) (вычисление дискретного логарифма) – очень сложен. Сложность этой задачи используется в криптографии для построения систем кодирования с открытым
ключом.
§ 3. Представление рациональных чисел
Множество рациональных чисел Q определяется как фактор-множество множества пар (a, b), (a, b) ∈ Z × Z, b ≠ 0, по отношению эквивалентности:
(a, b) ∼ (c, d) ⇔ ad − bc = 0.
Если фиксирована каноническая форма целого числа, то каноническую
форму рационального числа можно получить, например, выбирая из эквивалентных пар целых чисел (a, b) такую, у которой b > 0 и НОД(a, b) = 1.
Все сказанное выше о представлении целых чисел относится и к представлению рациональных чисел.
Такая каноническая форма рационального числа не является единственно возможной. Например, любое рациональное число можно представить в виде бесконечной десятичной периодической дроби, причем соответствие между рациональными дробями и бесконечными десятичными периодическими дробями не является взаимно-однозначным: рациональные
числа, знаменатели которых имеют вид 2n5m, могут быть представлены периодическими дробями с периодами (0) и (9).
Часто рациональные числа представляют в виде суммы целого числа и
правильной дроби, то есть положительного рационального числа 0 < α < 1.
36
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
В компьютерной алгебре вычисления обычно производятся точно, без
округления, тем не менее в ней рассматриваются и задачи, которые требуют
приближенного решения. Например, нахождение действительных корней
многочлена. В отличие от численного анализа ответ в таких задачах представляется не в виде числа, а в виде интервала на вещественной оси (области в комплексной плоскости). С такими интервалами можно производить
арифметические действия. Соответствующая арифметика известна под названием интервальной. Интервальная арифметика комбинируется с арифметикой многократной точности, так как требуемая точность обычно очень
высока.
§ 4. Представление алгебраических чисел
Представление алгебраических чисел является значительно более
трудной задачей. Для алгебраического числа надо знать минимальный многочлен, корнем которого является данное число. Иногда надо еще указывать
интервал на вещественной оси или область в комплексном пространстве, в
котором содержится единственный корень указанного многочлена. При
этом арифметические операции над алгебраическими числами оказываются
очень трудоемкими.
Нахождение минимального многочлена для суммы или произведения
алгебраических чисел представляет собой нетривиальную задачу (есть метод с помощью базисов Гребнера).
При работе с конкретным полем алгебраических чисел используется
представление чисел этого поля, связанное с фиксированием примитивного
элемента и с однозначностью представления элементов этого поля через
фиксированный примитивный элемент. Сложности возникают, если надо
производить операции над элементами из различных конечных расширений
поля рациональных чисел. И тогда можно не брать один примитивный элемент, а рассматривать поле алгебраических чисел как расширение поля рациональных чисел с многими образующими.
Действия с многочленами лежат в основе любой системы компьютерной алгебры. Пусть K – некоторое кольцо, задача представления элементов
которого уже решена. Представление элементов кольца многочленов K[x]
можно выбирать различными способами. Наиболее распространенным является представление многочлена в виде последовательности коэффициентов, упорядоченной по возрастанию или убыванию степеней одночленов.
Представление многочленов, при котором запоминаются все коэффициенты, включая нулевые, называется плотным. Плотное представление используется в задачах, где рассматриваемые многочлены имеют сравнительно
небольшое количество нулевых коэффициентов.
37
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Если степени многочленов достаточно высоки, а количество ненулевых коэффициентов мало (разреженные многочлены), то удобнее использовать разреженное представление многочленов, в котором указываются
только ненулевые коэффициенты и соответствующие степени одночленов.
При этом алгоритмы работы с такой формой записи становятся более сложными, но значительно экономится память ЭВМ, а во многих случаях – и
время работы программы. Если кольцо коэффициентов является полем, то
одночлены составляют базис кольца многочленов, рассматриваемого как
бесконечномерное векторное пространство над полем коэффициентов.
Многочлены от переменных x1, …, xn кольца K[x1, …, xn] можно рассматривать как многочлены от одной переменной x1, но с коэффициентами
из кольца многочленов K[x2, …, xn] (рекурсивное представление).
Поле рациональных функций K(x2, …, xn), где K – некоторое поле,
обычно определяется как поле частных кольца многочленов K[x2, …, xn].
Каноническое представление рациональных функций можно получить,
если наибольший общий делитель числителя и знаменателя равен 1 и если
старший коэффициент знаменателя равен 1 (нормированный многочлен).
Вопросы для самоконтроля
1. Представление целых чисел.
2. Представление классов вычетов.
3. Представление рациональных чисел.
4. Представление алгебраических чисел.
5. Представление многочленов.
Упражнения
1. Оценить количество одноразрядных умножений, используемых при
умножении столбиком m-значного числа на n-значное.
2. Показать, что два двузначных числа можно перемножить, используя
только три умножения однозначных чисел и увеличивая число сложений.
3. Составить таблицу умножения для кольца Z 7 .
4. Составить таблицу умножения для кольца Z 9 .
5. Доказать, что рациональные числа могут быть представлены бесконечными периодическими m-ичными дробями, причем неоднозначно.
38
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ЛИТЕРАТУРА
1. Акритас А. Основы компьютерной алгебры с приложениями /
А. Акритас. – М. : Мир, 1994. – 544 с.
2. Алгебра и теория чисел / под. ред. Н.Я. Виленкина. – М. : Просвещение, 1984. – 192 с.
3. Бухштаб А.А. Теория чисел / А.А. бухштаб. – СПб. : Лань, 2008. –
384 с.
4. Варден ван дер Б.Л. Алгебра. – М. : Наука, 1979. – 623 с.
5. Варпаховский Ф.Л. Алгебра / Ф.Л. Вахраповский, А.С. Солодовников. – М. : Просвещение, 1981. – 167 с.
6. Вахитова Е.В. Векторные пространства, линейные отображения и
линейные операторы / Е.В. Вахитов. – Стерлитамак : СГПА, 2005. – 159 с.
7. Вахитова Е.В. Многочлены над кольцами и полями / Е.В. Вахитов. –
Стерлитамак : СГПА, 2005. – 166 с.
8. Вахитова Е.В. Системы линейных уравнений, матрицы и определители / Е.В. Вахитов. – Стерлитамак : СГПА, 2005. – 169 с.
9. Вахитова Е.В. Теория сравнений и ее приложения / Е.В. Вахитов. –
Стерлитамак : СГПА, 2000. – 414 с.
10. Винберг Э.Б. Алгебра многочленов / Э.Б. Винберг. – М. : Просвещение, 1980. – 175 с.
11. Виноградов И.М. Основы теории чисел / И.М. Виноградов. – СПб. :
Лань, 2006. – 3176 с.
12. Глухов М.М. Задачник-практикум по курсу высшей алгебры /
М.М. Глухов, А.С. Солодовников. – М. : Просвещение, 1965. – 207 с.
13. Годунов С.К. Современные аспекты линейной алгебры / С.К. Годунов. – Новосибирск : Научная книга, 1997. – 388 с.
14. Дэвенпорт Дж. Компьютерная алгебра: символьные и алгебраические вычисления / Дж. Дэвенпорт, И. Сирэ, Э. Тунье. – М. : Мир, 1991. –
350 с.
15. Жевлаков К.А. Кольца, близкие к ассоциативным / К.А. Жевлаков
[и др.]. – М. : Наука, 1978. – 431 с.
16. Ильин В.А. Линейная алгебра / В.А. Ильин, Э.Г. Позняк. – М. :
Наука, 1978. – 302 с.
17. Каргаполов М.И. Основы теории групп / М.И. Каргаполов, Ю.И.
Мерзляков. – М. : Наука, 1996. – 287 с.
18. Кострикин А.И. Введение в алгебру / А.И. Кострикин. – М. : Наука, 1977. – 495 с.
19. Кострикин А.И. Введение в алгебру / А.И. Кострикин. – М. : Физматлит, 2004. – Ч. 1: Основы алгебры. – 271 с.
20. Кострикин А.И. Введение в алгебру / А.И. Кострикин. – М. : Физматлит, 2004. – Ч. 2: Линейная алгебра. – 367 с.
39
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
21. Кострикин А.И. Введение в алгебру. Основы алгебры / А.И. Кострикин. – М. : Наука, 1994. – 317 с.
22. Кострикин А.И., Манин А.Ю. Линейная алгебра и геометрии /
А.И. Кострикин, А.Ю. Манин. – М. : МГУ, 1980. – 319 с.
23. Кук Д. Компьютерная математика / Д. Кук, Г. Бейз. – М. : Наука,
1990. – 384 с.
24. Куликов Л.Я. Алгебра и теория чисел / Л.Я Куликов. – М. : Высш.
школа, 1979. – 559 с.
25. Куликов Л.Я. Сборник задач по алгебре и теории чисел / Л.Я Куликов, А.И. Москаленко. – М. : Просвещение, 1993. – 288 с.
26. Курош А.Г. Курс высшей алгебры / А.Г. Курош. – М. : Наука,
1971. – 431 с.
27. Курош А.Г. Курс высшей алгебры / А.Г. Курош. – СПб. : Лань,
2008. – 432 с.
28. Ламбек И. Кольца и модули /И. Ламбек. – М. : Мир, 1971. – 279 с.
29. Ленг С. Алгебра / С. Ленг. – М. : Мир, 1968. – 564 с.
30. Мальцев А.И. Основы линейной алгебры / А.И. Мальцев. – М. :
Наука, 1975. – 400 с.
31. Матрос Д.Ш. Основы абстрактной и компьютерной алгебры /
Д.Ш. Матрос, Г.Б. Поднебесов. – М. : Академия, 2004. – 240 с.
32. Нечаев В.А. Задачник-практикум по алгебре / В.А. Нечаев. – М. :
Просвещение, 1983. – 120 с.
33. Общая алгебра. Справ.-матем. Библиотека : в 2 т. / под ред.
Л.А. Скорнякова. – М. : Наука, 1990. – Т. 1. – 591 с.
34. Общая алгебра. Справ.-матем. Библиотека : в 2 т. / под ред.
Л.А. Скорнякова. – М. : Наука, 1991. – Т.2. – 479 с.
35. Панкратьев Е.В. Элементы компьютерной алгебры / Е.В. Панкратов. – М. : БИНОМ. Лаборатория знаний, 2007. – 247 с.
36. Практические занятия по алгебре и теории чисел / М.П. Лельчук,
И.И. Полевченко, А.М. Радьков. – Минск : Высш. школа, 1986. – 302 с.
37. Прасолов В.В. Задачи и теоремы линейной алгебры / В.В. Прасолов. – М. : Наука, 1984. – 304 с.
38. Проскуряков И.В. Сборник задач по линейной алгебре / И.В. Проскуряков. – М. : Наука, 1984. – 336 с.
39. Сборник задач по алгебре / под ред. А.И. Кострикина. – М.: Наука,
1987. – 351 с.
40. Сборник задач по алгебре / под ред. А.И. Кострикина. – М. : Факториал, 1995. – 453 с.
41. Скорняков Л.А. Элементы алгебры / Л.А. Скорняков. – М. : Наука,
1980. – 240 с.
42. Фаддеев Д.К. Лекции по алгебре / Д.К. Фаддеев. – М. : Наука,
1984. – 416 с.
40
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
43. Фаддеев Д.К. Лекции по алгебре / Д.К. Фаддеев. – СПб. : Лань,
2004. – 415 c.
44. Фаддеев Д.К. Сборник задач по высшей алгебре / Д.К. Фаддеев,
И.С. Соминский. – М. : Наука, 1977. – 288 с.
45. Фаддеев Д.К. Задачи по высшей алгебре / Д.К. Фаддеев, И.С. Соминский. – СПб. : Лань, 2005. – 287 с.
46. Херcтейн И. Некоммутативные кольца / И. Херстейн. – М. : Мир,
1972. – 191 с.
47. Числа и многочлены / сост. А.А. Егоров. – М. : Квантум, 2000. –
127 с.
48. Шевцов Г.С. Линейная алгебра / Г.С. Шевцов. – М. : Гардарики,
1999. – 359 с.
49. Шнеперман Л.Б. Сборник задач по алгебре и теории чисел /
Л.Б. Шнеперман. – М. : Высш. школа, 1982. – 223 с.
41
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ.................................................................................................. 3
Глава 1. СВЕДЕНИЯ О КОМПЬЮТЕРНОЙ АЛГЕБРЕ ......................... 5
§ 1. Об отличиях компьютерной алгебры ................................................ 5
§ 2. Системы компьютерной алгебры ....................................................... 6
§ 3. Алгоритмы компьютерной алгебры ................................................... 6
§ 4. О представлении данных..................................................................... 7
Вопросы для самоконтроля ........................................................................ 9
Упражнения ................................................................................................. 9
Глава 2. ЦЕЛЫЕ СИСТЕМАТИЧЕСКИЕ ЧИСЛА ............................... 10
§ 1. Определение систематической записи ............................................ 10
§ 2. Арифметические операции ............................................................... 11
§ 3. Перевод в десятичную систему счисления и обратно ................... 12
§ 4. Перевод из g-ичной системы в h-ичную систему ........................... 13
Вопросы для самоконтроля ...................................................................... 14
Упражнения ............................................................................................... 14
Глава 3. КОЛЬЦО КЛАССОВ ВЫЧЕТОВ ............................................. 16
§ 1. Определение сравнения по натуральному модулю ........................ 16
§ 2. Полная система вычетов ................................................................... 18
§ 3. Аддитивная группа классов вычетов ............................................... 22
§ 4. Кольцо классов вычетов .................................................................... 23
Вопросы для самоконтроля ...................................................................... 25
Упражнения ............................................................................................... 26
Глава 4. ПОЛЕ АЛГЕБРАИЧЕСКИХ ЧИСЕЛ....................................... 28
§ 1. Определение алгебраического числа ............................................... 28
§ 2. Минимальный многочлен алгебраического числа ......................... 29
§ 3. Операции над алгебраическими числами........................................ 31
§ 4. Поле алгебраических чисел .............................................................. 33
Вопросы для самоконтроля ...................................................................... 34
Упражнения ............................................................................................... 34
Глава 5. ПРЕДСТАВЛЕНИЕ ДАННЫХ................................................. 35
§ 1. Представление целых чисел ............................................................. 35
§ 2. Представление классов вычетов....................................................... 36
§ 3. Представление рациональных чисел ............................................... 36
§ 4. Представление алгебраических чисел ............................................. 37
Вопросы для самоконтроля ...................................................................... 38
Упражнения ............................................................................................... 38
Литература ................................................................................................. 39
42
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Учебное издание
Вахитов Риф Хамзиевич,
Вахитова Екатерина Васильевна
ФУНДАМЕНТАЛЬНАЯ И КОМПЬЮТЕРНАЯ
АЛГЕБРА
Часть IV
Компьютерная алгебра
Учебно-методическое пособие для вузов
Редактор Л.В. Новикова
Компьютерная верстка Е.Н. Комарчук
Подп. в печ. 14.11.2012. Формат 60×84/16.
Усл. печ. л. 2,5. Тираж 100 экз. Заказ 904.
Издательско-полиграфический центр
Воронежского государственного университета.
394000, г. Воронеж, пл. им. Ленина, 10. Тел. (факс): +7 (473) 259-80-26
http://www.ppc.vsu.ru; e-mail: pp_center@ppc.vsu.ru
Отпечатано с готового оригинал-макета в типографии
Издательско-полиграфического центра
Воронежского государственного университета.
394000, г. Воронеж, ул. Пушкинская, 3. Тел. +7 (473) 220-41-33
43
1/--страниц
Пожаловаться на содержимое документа