ALGEBRA

СЪДЪРЖАНИЕ

ЧАСТ ПЪРВА - АРИТМЕТИЧЕН УВОД

Глава 1. Делимост в множеството на целите числа. Най-голям общ делител и най-малко общо кратно. Прости числа и основна теорема на аритметиката

Глава 2. Сравнения по модул и свойства на сравненията. Класове по даден модул

Глава 3. Аритметични приложения на сравненията

ЧАСТ ВТОРА - АЛГЕБРИЧНИ СИСТЕМИ

Глава 4. Общи понятия. Алгебрични операции. Морфизми

Глава 5. Групи

Глава 6. Пръстени и полета

Глава 7. Алгебра на полиномите над дадено поле

Глава 8. Векторни пространства

Глава 9. Прости разширения на алгебрични полета. Поле на разлагане. Полета на Галоа

АЗБУЧЕН УКАЗАТЕЛ

ЛИТЕРАТУРА

ПРЕДГОВОР

Изложението съдържа материала, предвиден в учебната програма по дисциплината "Алгебра" за студентите от специалност "Информатика" в УНСС - София, но може да бъде от полза за всички, интересуващи се от основни понятия и резултати от общата алгебра, представени в достатъчно кратка и достъпна форма. За разбирането и овладяването на този материал се предполагат минимални познания от следните предхождащи математически дисциплини: теория на множествата, логика, аритметика и елементарна алгебра. Епизодично се използуват и понятия от линейната алгебра и математическия анализ.

Изложението е в 2 части, 9 глави, като всяка глава е илюстрирана с примери и упражнения за самостоятелна работа. Дефинициите, твърденията, примерите и упражненията са еднообразно номерирани, например ТВЪРДЕНИЕ 6.2 означава второ твърдение от шеста глава. Не всички твърдения са доказани, а само някои със сравнително просто и кратко доказателство; за други доказателството се предлага като упражнение - често в такива случаи във формулировката на упражнението думите "да се докаже, че" са пропуснати за краткост. Самите упражнения са разнородни по важност и трудност: по-трудните имат знак [*] след номера си, а [!] означава, че упражнението настоятелно се препоръчва на читателя.

Курсив в текста е използуван за привличане на вниманието: при въвеждане на нови понятия (например в дефиниции), при използуване на по-рано въведени и т.н. С дребен шрифт са дадени забележки от по-странично естество, както и текстът на упражненията. Накрая има азбучен указател и библиографска справка.

При четене на настоящия HTML-докумкент се препоръчва максимизиране на текстовия прозорец за да се избегне нежелателното пренасяне на формули или части от изрази на нов ред. За извеждане на стандартно използуваните в печатни издания означения за множествата съответно от естествените, целите, рационалните, реалните и комплексните числа /с "кухи" или "двойни" букви/ е необходимо да бъде инсталиран шрифтът Euclid Math Two.

Авторът изразява благодарност на проф. Ангел Попов и проф. Николай Божинов за съветите, препоръките и забележките към текста.

София, 2003

Oбратно към СЪДЪРЖАНИЕ

ИЗПОЛЗУВАНИ ОЗНАЧЕНИЯ

P ::= Q	равенство по дефиниция (обектът P се дефинира като равен на стойността на предварително дефинирания обект или израз Q);
c	начало на доказателство;
g	край на доказателство;
*{ a, b, c, ...}*	множество, състоящо се от елементите *a, b, c* и т.н.;
N, Z, Q, R, C	множества съответно от естествените, целите, рационалните, реалните, комплексните числа;
x О M	елементът x принадлежи на множеството M;
x П M	елементът x не принадлежи на множеството M;
#(M)	брой на елементите на множеството M;
*M М N, N* Й M**	множеството M е истинско подмножество на N;
*M Н N, N* К M**	множеството M е подмножество или съвпада с N;
M И N	обединение на множествата M и N;
M З N	сечение на множествата M и N;
M \ N	разлика на множествата M и N;
M ® N	съответствие (изображение, функция) на множеството M в множеството N;
a b	елемент a се изобразява в елемент b (при изображение между множества);
M « N	еднозначно обратимо съответствие между множествата M и N;
a « b	елемент a еднозначно обратимо съответствува на елемент b;
"x	квантор за общност (за всеки елемент x);
$ x	квантор за съществуване (съществува елемент x);
a Ю b	логическа импликация /от a следва b/;
a Ы b	логическа еквиваленция /a точно тогава, когато b/;
a \| b	делимост на цели числа (a се дели на b);
НОД(a, b)	най-голям общ делител на a и b;
НОК(a, b)	най-малко общо кратно на a и b;
a є b (mod m)	сравнимост/конгруенция (a е сравнимо с b по модул m);
S @ S'	изоморфизъм между алгебричните системи S и S'

Oбратно към СЪДЪРЖАНИЕ

ЧАСТ ПЪРВА - АРИТМЕТИЧЕН УВОД

1. ДЕЛИМОСТ В МНОЖЕСТВОТО НА ЦЕЛИТЕ ЧИСЛА. НАЙ-ГОЛЯМ ОБЩ ДЕЛИТЕЛ И НАЙ-МАЛКО ОБЩО КРАТНО. ПРОСТИ ЧИСЛА И ОСНОВНА ТЕОРЕМА НА АРИТМЕТИКАТА

ДЕФИНИЦИЯ 1.1. Релация делимост на цели числа: нека a, b О Z, b № 0. Числото a се дели на b (означение a | b) ако съществува c О Z такова, че a = bc (казва се още, че b е делител или дивизор на a, или че a е кратно на b).

Например 20 | 4, 2001 | 3, -10 |-2, a | 1, a |-1 за всяко a О Z и други цели числа, освен ±1 с това свойство няма. Числата ±a и ±1 се наричат тривиални делители на a. Останалите делители на a (ако има такива) се наричат собствени.

Забележка: в някои литературни източници по алгебра символът a | b означава "a дели b", вместо "a се дели на b.

ТВЪРДЕНИЕ 1.1. Свойства на релацията делимост: нека a, b, c, x, y О Z, като всеки делител е различен от 0. Тогава са в сила следните свойства:
1) a | a /рефлексивност/;
2) a | b и b | c Ю a | c /транзитивност/;
3) a | b Ю -a | b, a |-b, -a |-b;
4) a | b и b | a Ю a = ±b;
5) a | b Ю ac | b;
6) a | b и c № 0 Ю ac | bc;
7) a | c и b | c Ю (ax + by) | c;
8) 0 Ј a < b и a | b Ю a = 0;
9) 0 < a Ј b и a | b Ю a = b.

Елементарното доказателство на горните свойства се предоставя на читателя. Свойство 3) позволява да се възприеме следният подход, който често ще бъде използуван по-нататък: някои елементи от теорията на делимостта ще бъдат изграждани за естествените числа с последващо евентуално пренасяне или обобщаване на резултатите за целите числа.

Разбира се релацията делимост не е валидна за всеки две цели числа, но е в сила:

ТВЪРДЕНИЕ 1.2. Теорема за деление с остатък: ако a, b О Z, b > 0, то съществуват единствени q, r О Z, такива, че a = bq + r, като 0 Ј r < b /числата q и r се наричат съответно непълно частно (или накратко само частно) и остатък/.

c Съществуване: Числото a или съвпада с някое от целочислените кратни на b:

..., -3b, -2b, -b, 0, b, 2b, 3b, ... ,

или се намира между две последователни от тях, тоест qb Ј a < (q + 1)b за q О Z. Оттук 0 Ј a - qb < b и означавайки r = a - qb, се получава търсеното представяне.

Единственост: предполагайки, че съществуват две различни представяния:

a = bq + r, 0 Ј r < b и a = bq' + r', 0 Ј r' < b,

с изваждането им се получава b.| q - q' | = | r' - r |, което означава, че (r' - r) | b, но тъй като | r' - r | < b, според ТВЪРДЕНИЕ 1.1.8) това е възможно само при | r' - r | = 0, откъдето r = r' и q = q'. g

Твърдението се обобщава по очевиден начин и за отрицателен делител, като за остатъка ще бъде изпълнено 0 Ј r < | b | при b < 0.

Забележка: в изразителните означения на алгоритмичния език Pascal участвуващите в ТВЪРДЕНИЕ 1.2 величини изглеждат така:

q = a div b, r = a mod b, a/b = q + r/b, q = int (a/b), r/b = frac (a/b)

/операциите целочислено деление и целочислен модул и функциите цяла част и дробна част/.

ДЕФИНИЦИЯ 1.2. Общ делител: нека a, b О Z. Всяко d О Z, d № 0 със свойството, че a | d и b | d се нарича общ делител на a и b.

Общи делители съществуват за всеки две цели числа - такива са например ±1. Освен това, ако поне едното от двете числа е различно от 0, общите им делители са краен брой.

Например всичките делители на числото 12 са: ±1, ±2, ±3, ±4, ±6, ±12; всичките делители на числото 20 са: ±1, ±2, ±4, ±5, ±10, ±20; всичките делители на числото 21 са: ±1, ±3, ±7, ±21. Следователно общи делители на 12 и 20 са ±1, ±2, ±4; общи делители на 20 и 21 са ±1. От общите делители на 12 и 20 числото 4 има следните свойства: то е положително и се дели на всеки друг техен общ делител. От общите делители на 20 и 21 подобни свойства има числото 1.

Тези наблюдения дават основание за следната

ДЕФИНИЦИЯ 1.3. Най-голям общ делител, взаимно прости числа: нека a и b са цели числа, поне едно от които е различно от 0. Онзи техен положителен общ делител, който се дели на всеки друг техен общ делител, се нарича най-голям общ делител /означения НОД(a, b), GCD(a, b) от Greatest Common Divisor, понякога само (a, b) /.

Числа с най-голям общ делител, равен на 1, се наричат взаимно прости.

Например НОД(12, 20) = 4, НОД(20, 21) = 1, тоест числата 20 и 21 са взаимно прости.

Най-голям общ делител не съществува единствено ако и двете числа са равни на 0, в противен случай при a № 0 и b = 0 НОД(a, 0) = | a |, най-сетне очевидно НОД(a, b) = НОД(| a |, | b |), поради което, без ограничение на общността, занапред може да се разглеждат естествени числа.

ТВЪРДЕНИЕ 1.3. За всеки две естествени числа a и b съществува единствен най-голям общ делител.

c Единственост: ако d' и d" са два най-големи общи делители на a и b, то d' | d", също d" | d' и според ТВЪРДЕНИЕ 1.1.4) d' = ±d". Но d' > 0 и d" > 0 по дефиниция, значи d' = d".

Съществуване: ако a | b, то очевидно НОД(a, b) = b, затова нека a не се дели на b. Тогава НОД(a, b) може да се получи с известния от близо 2300 години алгоритъм на Евклид, чиято същност се състои в поредица от последователни деления с остатък: делимото (a) на делителя (b), делителя на първия остатък, първия остатък на втория, втория на третия и така нататък до получаване на нулев остатък:

a = bq₁ + r₁;	0 < r₁ < b;
b = r₁q₂ + r₂;	0 < r₂ < r₁;
r₁ = r₂q₃ + r₃;	0 < r₃ < r₂;
r₂ = r₃q₄ + r₄;	0 < r₄ < r₃;
. . . . . . . . . . . . .	. . . . . . . . .
r_k-2 = r_k-1 q_k + r_k;	*0 < r_k* < r_k-1**
r_k-1 = r_kq_k+1 + 0.

Горната поредица от последователни деления обезателно ще приключи с получаване на нулев остатък след краен брой стъпки, тъй като остатъците r₁ > r₂ > r₃ > ... і 0 образуват строго намаляваща редица от неотрицателни цели числа и такава редица не може да има безбройно много членове. Тогава НОД(a, b) = r_k /предпоследния остатък, който е ненулев/, действително последното равенство от веригата означава, че r_k-1 | r_k, дясната страна на предпоследното равенство се дели на r_k, следователно r_k-2 | r_k, аналогично от следващото по-горно равенство се получава, че r_k-3 | r_k, и, по същия начин стигайки до второто и първото равенства, следва, че b | r_k, и a | r_k, тоест r_k е общ делител на a и b. Ако d е произволен общ делител на a и b, от първото равенство на горната верига поради a | d и b | d следва, че r₁ | d; от второто следва, че че r₂ | d и т.н. до предпоследното, от което следва, че r_k | d. И така r_k е общ делител на a и b, който се дели на всеки друг техен общ делител, което доказва, че НОД(a, b) = r_k. g

ТВЪРДЕНИЕ 1.4. Свойства на най-големия общ делител (по-нататък a, b, c, d О Z):
1) ако d = НОД(a, b) Ю $ x, y О Z такива, че d = ax + by /тъждество на Безу/;
2) a и b са взаимно прости Ы $ x, y О Z такива, че ax + by = 1;
3) ако ab | c и a и c са взаимно прости Ю b | c;
4) ако d = НОД(a, b) Ю НОД(a/d, b/d) = 1.

c 1) следва от Евклидовия алгоритъм, действително от първото равенство от веригата, представено във вида: r₁ = a - bq₁ се вижда, че r₁се изразява в посочената форма като линейна комбинация на a и b с цели коефициенти; от второто, аналогично представено като r₂= b - r₁q₂, следва, че същото важи и за r₂и така нататък до r_k= НОД(a, b) /тоест Евклидовият алгоритъм дава и ефективна изчислителна процедура за определяне на x, y в представянето d = ax + by/. Може да се докаже /вижте коментара след ТВЪРДЕНИЕ 3.1 по-нататък/, че подобно представяне на най-големия общ делител е възможно по безбройно много начини;

2) следва от 1) и от дефиницията на взаимно прости числа;

3) ax + cy = 1 за някои x, y О Z според 2) и с умножение по b се получава abx + bcy = b. Лявата страна на последното равенство се дели на c тъй като abx | c и bcy | c, следователно b | c;

4) нека a = a'd, b = b'd, където a', b' О Z. Според 1) d = ax + by = a'dx + b'dy, откъдето 1 = a'x + b'y, което означава, че a' = a/d и b' = b/d са взаимно прости съгласно 2). g

Понятията общ делител, най-голям общ делител и взаимно прости числа могат да се обобщят по естествен начин за повече от две цели числа, например НОД(a₁, a₂, . . , a_n), където a₁, a₂, . . , a_n О Z, поне едно от които не е 0, се нарича онзи техен положителен общ делител, който се дели на всеки друг техен общ делител. Целите числа a₁, a₂, . . , a_n се наричат взаимно прости (в съвкупност), ако НОД(a₁, a₂, . . , a_n) = 1. Намирането на най-голям общ делител на повече от две числа може да се сведе до многократно намиране на най-голям общ делител на две числа съгласно следното

ТВЪРДЕНИЕ 1.5. НОД(a₁, a₂, . . , a_n) = НОД(НОД(a₁, a₂, . . , a_n-1), a_n)

Забележка: за целите числа понятията взаимно прости в съвкупност и две по две взаимно прости не са идентични, например НОД(4, 5, 6) = 1, но НОД(4, 6) = 2 > 1!

Дуални на понятията общ делител и най-голям общ делител са понятията общо кратно и най-малко общо кратно на две различни от 0 цели числа.

ДЕФИНИЦИЯ 1.4. Общо кратно и най-малко общо кратно: нека a, b О Z, a № 0, b № 0. Всяко M О Z със свойството, че M | a и M | b се нарича общо кратно на a и b. Положително общо кратно на a и b, което е делител на всяко друго тяхно общо кратно, се нарича най-малко общо кратно на a и b /означения: НОК(a, b), LCM(a, b), понякога [a, b]/.

Например 120 е общо кратно на 12 и 20, докато НОК(12, 20) = 60, 4200 е общо кратно на 20 и 21, но НОК(20, 21) = 420.

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

ТВЪРДЕНИЕ 1.6. За " a, b О N е изпълнено: НОК(a, b).НОД(a, b) = ab.

c Нека d = НОД(a, b) и a = a'd, b = b'd за някои a', b' О N. Числото M = a'b'd = ab' = a'b е очевидно общо кратно на a и b. Ако M' е друго тяхно общо кратно, M' = ax = by за някои x, y О Z, то ax/b = y О Z, тоест ax | b и оттук последователно a'dx | b'd, a'x | b' и поради НОД(a', b') = 1 следва, че x | b'. Тогава ax | ab', тоест M' | M, или M = НОК(a, b). От M = ab' следва Md = ab'd = ab. g

От доказаното следва, че най-малкото общо кратно на две естествени числа е равно на тяхното произведение точно тогава, когато те са взаимно прости.

Както понятието най-голям общ делител, така и понятието най-малко общо кратно допуска обобщение: НОК(a₁, a₂, . . , a_n) е онова положително общо кратно на ненулевите цели числа a₁, a₂, . . , a_n, което е делител на всяко друго тяхно общо кратно.

Аналогично на ТВЪРДЕНИЕ 1.5 е в сила:

ТВЪРДЕНИЕ 1.7. НОК(a₁, a₂, . . , a_n) = НОК(НОК(a₁, a₂, . . , a_n-1), a_n)

По отношение на броя на естествените си делители естествените числа могат да се разделят на три множества: в първото се съдържа само числото 1, което има единствен естествен делител - себе си; във второто са числата с два естествени делителя - единицата и себе си (например 2, 3, 5); и в третото се съдържат всички числа с повече от два естествени делители. Това дава основание за следващата добре известна

ДЕФИНИЦИЯ 1.5. Прости и съставни числа: естествено число, по-голямо от 1, което се дели само на 1 и на себе си, се нарича просто. Естествено число с повече от два различни естествени делители се нарича съставно.

Числото 1 е уникално съгласно тази дефиниция - то нито е просто, нито е съставно.

ТВЪРДЕНИЕ 1.8. Свойства на простите числа (нататък a, b, n, p О N; p - просто):
1) или a | p, или a и p са взаимно прости;
2) ако ab | p и a не се дели на p Ю b | p;
3) най-малкият естествен делител на a, по-голям от 1, е просто число;
4) (Евклид) съществуват безбройно много прости числа;
5) в N съществуват интервали с произволна дължина, състоящи се само от съставни числа.

c 1) ако p е просто, положителните делители на p са 1 и p, тогава или НОД(a, p) = 1, или НОД(a, p) = p. В първия случай a и p са взаимно прости, във втория a | p;

2) следва от 1), тъй като a и p са взаимно прости и от ТВЪРДЕНИЕ 1.4.3);

3) ако a е просто, твърдението е вярно, в противен случай ако най-малкият собствен делител p на a е съставно число, то p = p₁p₂ като 1 < p₁< p и от a | p и p | p₁ следва, че a | p₁ - противоречие с условието, че p е най-малък собствен делител. От доказаното следва, че всяко естествено число, по-голямо от 1, се дели на поне едно просто число;

4) ако се предположи, че всички прости числа са краен брой, например p₁, p₂, . . , p_n, то числото q = p₁p₂...p_n + 1, както лесно се вижда, при деление на всяко p_i / i = 1, 2, . . , n / дава остатък 1, следователно не се дели на нито едно от p_i. Тогава q или е просто, или съгласно 3) се дели на други прости числа, различни от p_i - противоречие;

5) за n > 2 поредица от n - 1 последователни съставни числа са n! + 2, n! + 3, . . , n! + n: първото се дели на 2, второто на 3 и т.н. g

Свойства 4) и 5) от ТВЪРДЕНИЕ 1.8 означават, че в редицата 1, 2, 3, ... от естествените числа с нарастването им прости числа се срещат все по-рядко и неравномерно, но според изложеното елегантно доказателство на Евклид, което заслужено се счита за шедьовър на античната математика, никога няма да престанат да се срещат. Разпределението на простите числа е породило някои от най-трудните математически проблеми, сред които има все още нерешени. Най-голямото просто число, известно до 2001, е 2^{13 466 917}- 1 (актуална информация може да се намери на адрес http://www.utm.edu/research/primes/largest.html). Десетичният му запис съдържа над 4 милиона цифри.

Ефективен алгоритъм за намирането на неголеми прости числа /всички до дадена граница/, основан на своеобразно "пресяване" на последователните естествени числа, е предложен от древногръцкия учен Ератостен /така нареченото решето на Ератостен/.

ТВЪРДЕНИЕ 1.9. Основна теорема на аритметиката: всяко естествено число, по-голямо от 1, се разлага в произведение на прости числа и това разлагане е единствено с точност до реда на множителите.

c Съществуване: нека n О N, n > 1. Ако n е просто, твърдението е доказано, тъй като въпросното произведение се състои от единствен прост множител, затова нека n е съставно. Според ТВЪРДЕНИЕ 1.8.3) n = p₁n₁, където p₁ - просто като най-малък собствен делител, а n₁ О N, n₁ < n. Ако n₁ е просто, n се разлага в произведение на 2 прости множителя, затова нека n₁ е съставно. Аналогично n₁ = p₂n₂, където p₂ - просто /може да се случи p₂ = p₁/, а n₂ О N, n₂ < n₁. Отново ако n₂ е просто, n се разлага в произведение на 3 прости множителя, иначе n₂ = p₃n₃, където p₃ - просто и т.н. Този процес на отделяне на прости множители задължително приключва след краен брой стъпки, защото строго намаляващата редица n > n₁ > n₂ > n₃ > ... от съставни естествени числа не може да има неограничен брой членове. Тогава

n = p₁n₁= p₁p₂n₂ = ... = p₁ p₂ p₃...p_m ,

като простите множители в това разлагане не са задължително различни.

Единственост: ако се предположи, че има две различни разлагания:

n = p₁ p₂ p₃...p_k = q₁ q₂ q₃...q_l /p₁, p₂, . . , p_k,q₁, q₂, q₃, . . , q_l - прости/,

то простото число p₁ дели произведението q₁q₂q₃...q_l, което според ТВЪРДЕНИЕ 1.8.2) е възможно само ако p₁съвпада с някое от числата q₁, q₂, q₃, . . , q_l , например /след евентуално преномериране/ нека p₁ = q₁. Съкращавайки на p₁ се получава

p₂ p₃...p_k = q₂ q₃...q_l

и със същите разсъждения например p₂ = q₂ и т.н. В крайна сметка излиза, че броят на множителите в двете разлагания е един и същи и всеки множител от едното съвпада с някой от другото, което доказва единствеността. Обединявайки евентуални кратни множители, крайният резултат може да се представи в следната форма:

където простите числа p₁, p₂, . . , p_s са две по две различни. g

ДЕФИНИЦИЯ 1.6. Канонично разлагане: единственото разлагане на естествено число, по-голямо от 1, на прости множители съгласно основната теорема на аритметиката се нарича канонично разлагане.

Например 2000 = 2⁴*5³; 2001 = 3*23*29; 2002 = 2*7*11*13; 2003 = 2003 (просто число);2004 = 2²*3*167; 2005 = 5*401; 2006 = 2*17*59.

Каноничното разлагане се обобщава за всички цели числа, освен 0 и ±1 с добавяне на знаковия множител ±1.

ТВЪРДЕНИЕ 1.10. Формули за най-големия общ делител и най-малкото общо кратно на две естествени числа: нека

са каноничните разлагания на a, b О N /може да се счита, че в тях участвуват едни и същи прости множители, ако се допусне a₁, a₂, . . , a_s, b₁, b₂, . . , b_s і 0, цели/. Тогава

Упражнения към глава 1:

1.1. От всеки k на брой последователни цели числа точно едно се дели на k.

1.2. Всеки две или повече последователни естествени числа са взаимно прости; всеки две последователни нечетни числа са взаимно прости; най-големият общ делител на всеки две последователни четни числа е равен на 2.

1.3. В редицата 1, 1, 2, 3, 5, 8, 13, ..., в която първите два члена са единици, а от третия нататък всеки е равен на сумата от предходните два (числа на Фибоначи), всеки два съседни члена са взаимно прости.

1.4[!]. С алгоритъма на Евклид да се намерят НОД(12, 20), НОД(36, 63), НОД(120, 620, 325), НОД(40, 60, 80, 100); да се представи НОД(12, 20) във формата 12x + 20y; x, y О Z.

1.5. Ако a₁, a₂, . . , a_n О Z, то НОД(a₁, a₂, . . , a_n) = a₁ x₁ + a₂ x₂+ ... + a_n x_n за някои x₁, x₂, . . , x_nО Z; да се представи НОД(40, 60, 80, 100) във формата 40x₁ + 60x₂ + 80x₃ + 100x₄.

1.6[!]. Ако поне три цели числа са две по две взаимно прости, те са и взаимно прости. Съществуват ли поне три взаимно прости числа, никои две от които не са взаимно прости?

1.7. Часовата, минутната и секундната стрелки на часовника сочат в една точка само в 12 часа на обяд и в 12 часа в полунощ.

1.8. НОД(ac, bc) = |c|.НОД(a, b) за a, b, c О Z.

1.9. НОК(a, b, c).НОД(ab, bc, ca) = abc за a, b, c О N.

1.10. Строявайки за поход войниците си в колона по 10, офицерът забелязал, че само в последната редица липсвал един войник за да бъде тя пълна. Тогава той решил да ги построи в колона по 9, но това не помогнало - последната редица отново била непълна с един войник. Престроявайки ги в колона по 8, 7, 6, 5, 4, 3 и 2 ситуацията в последната редица се повтаряла. Колко са били войниците?

1.11. При означенията от ТВЪРДЕНИЕ 1.9 броят на естествените делители на естественото число

е равен на ( k₁+ 1) ( k₂+ 1) ... ( k_s + 1).

1.12[!]. Да се определи на колко нули окончава числото 1000!

1.13[!]. Най-малкият прост делител на съставното число a О N не надминава

1.14. Необходимо условие (което не е достатъчно!) числото 2ⁿ - 1 да бъде просто /n О N/, е n да бъде просто /най-големите понастоящем известни прости числа са именно от този вид - така наречените прости числа на Мерсен - например 7 = 2³ - 1, 31 = 2⁵ - 1/

1.15. Необходимо условие (също не достатъчно) числото 2ⁿ + 1 да бъде просто /n О N/ е n да има формата n = 2^k, k = 0, 1, 2, ... /така наречените прости числа на Ферма - например 5 = 2² + 1, 17 = 2⁴ + 1, 257 = 2⁸ + 1/

Oбратно към СЪДЪРЖАНИЕ

2. СРАВНЕНИЯ ПО МОДУЛ И СВОЙСТВА НА СРАВНЕНИЯТА. КЛАСОВЕ ПО ДАДЕН МОДУЛ.

ДЕФИНИЦИЯ 2.1. Сравнимост (конгруентност, равноостатъчност): нека a, b О Z и m О N. Числата a и b се наричат сравними (конгруентни, равноостатъчни) по модул m /означение a є b (mod m) /, ако (a - b) | m, или, в еквивалентна формулировка, когато a и b дават равни остатъци при деление на m.

Еквивалентността на формулировките следва от факта, че ако

a = mq₁ + r₁ и b = mq₂+ r₂, /q₁, q₂, r₁, r₂ О Z, 0 Ј r₁, r₂ < m /,

то a - b = m (q₁ - q₂) + r₁- r₂, и (a - b) | m Ы r₁- r₂= 0. Последното означава още, че a є b (mod m) Ы a = b + mq за някое q О Z; също a є 0 (mod m) Ы a | m /още един начин за изразяване на релацията делимост/.

Например 20 є 41 (mod 7); 9 є 21 (mod 12); 2001 є 0 (mod 3); 17 є -3 (mod 5); 9 є -1 (mod 10), 1989 є 89 (mod 100); 123456 789 є 789 (mod 1000).

Тъй като 1 е делител на всяко цяло число, сравнимостта по модул 1 е безсъдържателна, поради което по-нататък всички модули могат да се предполагат по-големи от 1.

ТВЪРДЕНИЕ 2.1. Свойства на сравненията (a, b, c, k и т.н. О Z; m, m₁, m₂О N);
1) a є a (mod m) /рефлексивност/;
2) a є b (mod m) Ы b є a (mod m) /симетричност/;
3) a є b (mod m) и b є c (mod m) Ю a є c (mod m) /транзитивност/;
4) a₁ є b₁(mod m) и a₂ є b₂(mod m) Ю a₁ ± a₂ є b₁ ± b₂(mod m) и a₁a₂ є b₁b₂(mod m);
5) a є b (mod m) Ю a - b є 0 (mod m); a є b + cm (mod m); ka є kb (mod m); при k > 0 също a^k є b^k(mod m);
6) a є b (mod m) и d - общ делител на a, b, m Ю a/d є b/d (mod m/d); ka є kb (mod km) /d, k > 0/;
7) ad є bd (mod m) и НОД(d, m) = 1 Ю a є b (mod m);
8) a є b (mod m) Ю НОД(a, m) = НОД(b, m);
9) a є b (mod m₁) и a є b (mod m₂) Ю a є b (mod НОК(m₁, m₂))

c Първите 3 свойства директно следват от дефиницията. От a₁ = b₁ + mq₁и a₂ = b₂ + mq₂ следва a₁ ± a₂ = b₁ ± b₂+ m (q₁± q₂) и също a₁a₂ = b₁b₂ + m (b₁q₂ + b₂q₁ + mq₁q₂), което доказва 4). Прилагайки 4) k пъти към сравнението a є b (mod m), се получава 5). Ако a є b (mod m) и d е общ делител на a, b, m, то a = a'd, b = b'd, m = m'd и от a'd = b'd + m'dq следва a' = b' + m'q, също ka = kb + kmq, което доказва 6). Свойство 7) следва от (ad - bd) | m, тоест (a - b)d | m и ТВЪРДЕНИЕ 1.4.3), тъй като d не се дели на m. От a = b + mqследва, че всеки общ делител на b и m, а следователно и НОД(b, m) дели и лявата страна - числото a, и поради симетричната роля на a и b следва 8). Свойство 9) следва от (a - b) | m₁, (a - b) | m₂ и дефиницията на най-малко общо кратно и се обобщава по очевиден начин за повече от два модула. g

Свойства 1) - 3) означават изключително важния за по-нататъшното изложение факт, че сравнимостта по модул е релация на еквивалентност. Оттук например следва, че всяка целочислена величина, участвуваща в коя да е страна на едно сравнение, може да се замени с друга, сравнима с нея.

Свойства 4) - 7) описват аритметичните операции със сравнения: сравнения по един и същи модул могат да се събират, изваждат и умножават; двете страни на едно сравнение могат да се умножават с произволно цяло число, да се повдигат в цяла положителна степен, или да се разделят на техен общ делител, взаимно прост с модула; накрая двете страни и модулът могат да се умножат с положително цяло число или да се разделят с техен положителен общ делител. От 4) и 5) следва, че ако е даден полином с цели коефициенти:

F(x) = a₀xⁿ + a₁xⁿ-1 + a₂xⁿ-2 + ... + a_n-1 x + a_n, /a₀, a₁, . . , a_n О Z; n О N/

и ако x₁ є x₂ (mod m) за x₁, x₂ О Z, то F(x₁) є F(x₂) (mod m).

Друго полезно следствие е, че полиномното сравнение

a₀xⁿ + a₁xⁿ-1 + a₂xⁿ-2 + ... + a_n-1 x + a_n є 0 (mod m)

с целочислено неизвестно x е еквивалентно на уравнението с 2 неизвестни (x, y О Z):

a₀xⁿ + a₁xⁿ-1 + a₂xⁿ-2 + ... + a_n-1 x + a_n = my,

което ще бъде използувано по-нататък.

От теорията на множествата е известно, че всяка релация на еквивалентност в едно множество осъществява разлагане на това множество на непресичащи се класове /то е тяхно обединение/, като всеки клас съдържа еквивалентни помежду си елементи на множеството, докато никои два елемента от различни класове не са еквивалентни помежду си. Множеството от тези класове е известно като фактор-множество на изходното множество спрямо релацията на еквивалентност. Тъй като сравнимостта е релация на еквивалентност в Z и тъй като при деление на m едно цяло число може да даде според ТВЪРДЕНИЕ 1.2 точно един от следните m на брой различни остатъци: 0, 1, 2, . . , m-1, това означава, че всяко цяло число е сравнимо по модул m с точно един от тях и така множеството Z от целите числа се разлага на m на брой класове.

ДЕФИНИЦИЯ 2.2. Класове по модул: нека m О N. Множеството от всички цели числа, сравними помежду си по модул m, се нарича клас от остатъци по модул m (или накратко клас по модул m). За класовете по модул m ще се използуват означенията: [0], [1], [2], . . , [m-1]:

[0] ::= { x О Z, x є 0 (mod m) } = {..., -3m, -2m, -m, 0, m, 2m, 3m, ...};
[1] ::= { x О Z, x є 1 (mod m) } = {..., -2m + 1, -m + 1, 1, m + 1, 2m + 1, 3m + 1, ...};
[2] ::= { x О Z, x є 2 (mod m) } = {..., -2m + 2, -m + 2, 2, m + 2, 2m + 2, 3m + 2, ...};
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
[m-1] ::= { x О Z, x є m -1 (mod m) } = {..., -2m -1, -m -1, -1, m -1, 2m -1, 3m -1, ...}

Иначе казано, всеки клас се състои от целите числа, които при деление на m дават един и същи даден остатък - съответно 0, 1, 2, . . , m - 1 /числата от всеки клас образуват безкрайна в двете посоки аритметична прогресия с разлика m/.

Например класовете по модул 2 са: [0] - всички четни числа, и [1] - всички нечетни числа.

Множеството от класове по модул m /тоест фактор-множеството на Z спрямо релацията сравнимост по модул m/ ще се означава по-нататък постоянно с Z_m, тоест

Z_m::= { [0], [1], [2], . . , [m-1] }.

Резюмирайки цитираните от теорията на множествата резултати, се получава

ТВЪРДЕНИЕ 2.2. Всяко цяло число принадлежи на точно един клас по модул m; различните класове нямат общи елементи; обединението на класовете съвпада със Z.

ДЕФИНИЦИЯ 2.3. Пълна система от остатъци по модул m: ако от всеки клас по модул m се избере по един представител, получените числа образуват пълна система от остатъци по модул m.

От ДЕФИНИЦИЯ 2.3 и ТВЪРДЕНИЕ 2.2 следва, че необходимо и достатъчно условие няколко цели числа да образуват пълна система от остатъци по модул m е техният брой да е равен на m и никои две от тях да не са сравними помежду си по модул m.

Например пълна система от остатъци по модул 2 образуват произволно четно число и произволно нечетно число. Най-често за представители на пълна система по модул m се избират или най-малките неотрицателни представители: числата 0, 1, 2, . . , m-1, или най-малките положителни представители: числата 1, 2, . . , m, или най-малките представители по абсолютна стойност, например в целочислената машинна аритметика стойностите 0, 1, . . , 255 (тип byte) и -128, -127, . . , -1, 0, 1, . . ,127 (тип short integer) образуват пълни системи от остатъци /най-малки неотрицателни, респективно най-малки по абсолютна стойност/ по модул 256 = 2⁸; аналогично стойностите от типовете word (0, . . , 65535) и small integer (-32768, . . , 32767) образуват пълни системи от остатъци по модул 65536 = 2¹⁶ и т.н.

Упражнения към глава 2:

2.1[!]. (Теорема за остатъците на линейната функция): Ако a, b О Z, m О N и x приема всички стойности от пълна система от остатъци по модул m, то съответните стойности на линейната функция ax + b при НОД(a, m) = 1 също образуват пълна система от остатъци по модул m.

2.2[!]. (Малка теорема на Ферма) Ако a, p О N, p - просто и a не се дели на p Ю a^p- 1 є 1 (mod p).

2.3[!]. От Малката теорема на Ферма да се изведе, че за a, p О N и p - просто Ю a^p є a (mod p).

2.4[*]. (Теорема на Уилсън) Числото p О N е просто Ы (p - 1)! + 1 є 0 (mod p).

2.5. От теоремата на Уилсън да се изведе, че p О N е просто Ы (p - 2)! є 1 (mod p).

2.6[*]. (Китайска теорема за остатъците) Ако m₁, m₂, . . , m_k О N са две по две взаимно прости, то $ x О N, което при деление на m_i /i =1, 2, . . , k/ дава предварително определени остатъци r₁, r₂, . . , r_k О Z.

2.7[!]. За полиномни сравнения с едно неизвестно от вида:

a₀xⁿ + a₁xⁿ-1 + a₂xⁿ-2 + ... + a_n-1 x + a_n є 0 (mod m),

/a₀, a₁, . . , a_n О Z; n О N; a₀ не се дели на m/

решение се нарича " x О Z, удовлетворяващо сравнението. Позовавайки се на коментара след ТВЪРДЕНИЕ 2.1 по повод на свойства 4) и 5) да се обоснове процедура за решаване на такива сравнения, основана на краен брой проби, и да се решат сравненията:

x² + x + 1 є 0 (mod 2), x² + 6x + 8 є 0 (mod 7) и x⁵- x є 0 (mod 5).

2.8[!]. (Сравнения от първа степен с едно неизвестно) За сравнението ax є b (mod m) нека a не се дели на m и d = НОД(a, m). Да се докаже, че:

сравнението няма решение, ако b не се дели на d;
има за решения всички числа от единствен клас по mod m при d = 1;
има за решения всички числа, принадлежащи на d различни класа по mod m при d > 1 и b | d.

2.9[!]. Да се решат сравненията: 7x є 3 (mod 5), 4x є 12 (mod 20), 6x є 7 (mod 9).

2.10. Да се определят:

последната цифра на числото 2¹⁰⁰⁰;
последната цифра на 7 ^{777 777};
последните две цифри на 2¹⁰⁰.

Oбратно към СЪДЪРЖАНИЕ

3. АРИТМЕТИЧНИ ПРИЛОЖЕНИЯ НА СРАВНЕНИЯТА

Тук ще бъдат разгледани накратко следните приложения:

извеждане на признаци за делимост;
проверка на резултатите от аритметични действия;
определяне на дължината на периода при обръщане на обикновени дроби в систематични;
изследване на Диофантови уравнения

Приложение 1: извеждане на признаци за делимост.

Признаците за делимост най-общо се подразделят на два вида: признаците от първия вид позволяват да се определи остатъкът от делението на цяло число на определен делител, докато признаците от втория дават само отговор на въпроса дали делението е без или с остатък, като в последния случай няма възможност за определяне на остатъка. Всички признаци от първия вид са основани на следната обща схема: нека се търси остатъкът от делението на естественото число N (по-нататък се предполага представено в десетична система, като измененията при използуване на друга бройна система лесно се съобразяват):

N = a₀ + a₁.10 + ... + a_n-1.10ⁿ-1 + a_n.10ⁿ

/цифрите a₀, a₁, . . , a_n-1, a_n= 0, 1, . . , 9 като a_n > 0/

на естествен делител d. Намират се остатъците r₁, r₂, . . , r_n-1, r_n по модул d на последователните степени на 10 (сред тях има не повече от d различни!):

10⁰ є 1 (mod d), 10¹ є r₁ (mod d), . . ,10ⁿ-1 є r_n-1 (mod d), 10ⁿ є r_n(mod d),

тогава, съгласно свойствата на сравненията:

N = a₀ + a₁.10 + ... + a_n-1.10ⁿ-1 + a_n.10ⁿ є a₀ + a₁ r₁ + ... + a_n-1 r_n-1 + a_n r_n(mod d).

От последното сравнение могат да се изведат познатите признаци за делимост на 2, 5, 4, 25, 3, 9, 11 и пр. Например по модул 2 или 5: 10 є 10² є ... є 0, откъдето r₁ = r₂= ... = 0 и N є a₀, тоест числото дава същия остатък, какъвто цифрата на единиците му (признаци за делимост на 2 и 5).

По модул 4 или 25: 10² є 10³є ... є 0, откъдето r₂= r₃= ... = 0 и тогава N є a₀ + a₁.10, тоест числото дава същия остатък, какъвто двуцифреното число, съставено от цифрите на десетиците и единиците му (признаци за делимост на 4 и 25).

Аналогично изглеждат признаците за делимост на 8 и 125, както и на по-високите степени на 2 и 5.

По модул 3 или 9: 10 є 10² є ... є 1, откъдето r₁ = r₂= ... = 1 и тогава N є a₀ + a₁ + ... + a_n-1 + a_n, тоест числото дава същия остатък, какъвто сумата от цифрите му (признаци за делимост на 3 и 9).

По модул 11: 10⁰ є 10² є 10⁴ є ... є 1 и 10¹ є 10³ є 10⁵ є ... є -1, откъдето r₀ = r₂= ... = 1 и r₁ = r₃= ... = -1 и тогава N є a₀ - a₁ + a₂ - a₃ + ... + (-1)ⁿa_n, тоест числото дава същия остатък, какъвто сумата от цифрите му в четните разряди (отдясно наляво като цифрата на единиците е нулев разряд!), намалена със сумата от цифрите му в нечетните разряди (признак за делимост на 11).

По модул 7 най-сетне 10⁰ є 1, 10¹ є 3, 10² є 2, 10³ є 6 є -1, 10⁴ є 4 є -3, 10⁵ є 5 є -2, след което редицата от остатъци 1, 3, 6, 2, 4, 5 (или по-удобната 1, 3, 2, -1, -3, -2) се повтаря, откъдето:

N є a₀ + 3a₁ + 2a₂ - a₃ - 3a₄ - 2a₅+ a₆ + 3a₇ + 2a₈ - a₉ - 3a₁₀ - 2a₁₁ + ...

(признак за делимост на 7)

Например числото 142857 се дели на 3, 9 и 11 (7 + 5 + 8 + 4 + 2 + 1 = 27, 7 - 5 + 8 - 2 + 4 - 1 = 11), а при деление на 7 дава остатък 1 (7 + 3*5 + 2*8 - 2 - 3*4 - 2*1 = 22 є 1).

Признаците от втория вид ("да" или "не") са по-разнообразни и обикновено са по-лесни за употреба, но имат споменатия недостатък - не позволяват да се определи остатъкът от делението при деление с остатък. Например посоченият по-горе признак за делимост на 7 изисква запомняне на 6 остатъка поради което не е особено практичен, затова ето друг по-прост: естествено число се дели на 7 точно тогава, когато броят (а не цифрата!) на десетиците му, събран с петкратната цифра на единиците, се дели на 7. Наистина от 10x + y є 0 (mod 7) с умножение по 5 се получава

50x + 5y є 49x + x + 5y є x + 5y є 0 (mod 7);

обратно, от последното сравнение с умножение по 10 се получава първото. Например за проверка на 45654 се пресмятат 4565 + 5*4 = 4585, 458 + 5*5 = 483, 48 + 5*3 = 63, което се дели на 7.

* * * * * * *

Приложение 2: проверка на резултатите от аритметични действия.

Проверката е основана на факта, че всеки две равни числа са сравними по фиксиран модул, като за числа, представени в десетична бройна система е най-удобно да се премине към сравнение по модул 9 или 11. Например сумата:

9 + 99 + 999 + 9 999 + 99 999 + 999 999 + 9 999 999 + 99 999 999 + 999 999 999 = 1 111 111 111

не е пресметната правилно, тъй като събираемите са кратни на 9, а резултатът не е /проверката по модул 9 със сумата от цифрите е известна като "отстраняване на деветките"/.

* * * * * * *

Приложение 3: определяне на дължината на периода при обръщане на обикновени дроби в систематични.

Както е известно, при обръщане в десетични дроби на несъкратими обикновени дроби, в каноничното разлагане на чиито знаменатели участвуват прости множители, различни от 2 и 5, се получават периодични десетични дроби като:

1/3 = 0.3333... = 0.(3)	1/6 = 0.16666... = 0.1(6)
1/7 = 0.142857142857... = 0.(142857)	1/9 = 0.1111... = 0.(1)
1/11 = 0.090909... = 0.(09)	1/12 = 0.083333... = 0.08(3)
1/13 = 0.076923076923... = 0.(076923)	1/14 = 0.07142857142857... = 0.07(142857)

Може да се докаже, че ако p/q е несъкратима рационална дроб (p, q О Z, q > 0, НОД(p, q) = 1), дължината на периода въобще не зависи от числителя. По-нататък, ако q = 2^m. 5ⁿ. q' където q' е взаимно просто с 2 и с 5, то при q' = 1 се получава крайна десетична дроб, при q' > 1 и m = n = 0 се получава чиста периодична дроб (периодът започва непосредствено след десетичния знак като при 1/3, 1/7, 1/9, 1/11 и 1/13), накрая при q' > 1 и поне един положителен показател m или n - смесена периодична дроб (периодът се предшествува от група цифри след десетичния знак като при 1/6, 1/12 и 1/14). В случаите на периодични дроби дължината на периода е равна на най-малкия естествен показател k със свойството, че

10^k є 1 (mod q' ).

За горните примери 10¹ є 1 (mod 3 или 9), 10² є 1 (mod 11), 10⁶ є 1 (mod 7 или 13) /вижте по-горе остатъците на поредните степени на 10 по модулите 3, 7, 9 и 11/.

Казаното важи и за систематични дроби с друга основа, различна от 10, като на читателя се предоставя да съобрази подробностите. Така в широко използуваната в информатиката двоична бройна система с крайни двоични дроби (тоест изискващи краен брой битове от оперативната памет) се представят само така наречените двоично-рационални числа от определен диапазон /floating point values или машинни числа/. Това са числата, чиито знаменатели са точни степени на двойката, тоест числата от вида a/2^k, където a О Z, k = 0, 1, 2, ... Всички останали реални числа от съответния диапазон се представят с двоично-рационални приближения.

* * * * * * *

Приложение 4: изследване на Диофантови уравнения.

Едно от най-съдържателните приложения на сравненията се състои в изследването на някои неопределени уравнения или системи, при които броят на уравненията е по-малък от броя на неизвестните. Обикновено в такива случаи се налагат допълнителни ограничения за неизвестните, например да бъдат цели (или понякога естествени, или рационални) числа. Първи писмени сведения за подобни задачи има в частично запазената до наши дни книга "Аритметика" от античния математик Диофант Александрийски, в чиято чест са наречени.

Изследването на някои прости Диофантови уравнения може понякога да се извърши като уравнението се замени с подходящо сравнение (или няколко сравнения), чието изследване е по-лесна задача. Например за уравнението 3x² + 2 = y² (което в реални числа очевидно има безбройно много решения) може лесно да се докаже, че няма целочислени решения с преход към сравнение по модул 3, действително от 3x² + 2 є y² (mod 3) и 3x²є 0 (mod 3) би следвало y² є 2 (mod 3), а последното е невъзможно, действително за трите алтернативи:

y є 0,	y є 1,	y є 2 (mod 3) се получава съответно:
y² є 0² є 0,	y²є 1²є 1,	y²є 2²є 1 (mod 3)

тоест всеки целочислен точен квадрат е сравним по модул 3 само с 0 или 1 и никога с 2.

Особено лесен е анализът на линейните Диофантови уравнения с 2 неизвестни.

ТВЪРДЕНИЕ 3.1. Уравнението: ax + by = c, където a, b, c О Z, a № 0, b № 0 има целочислени решения точно тогава, когато c | НОД(a, b).

c Без ограничение на общността може да се предположи, че b > 0. Както е отбелязано в коментара след ТВЪРДЕНИЕ 2.1 даденото уравнение ax + by = c е еквивалентно на сравнението:

ax є c (mod b)

1) Нека НОД(a, b) = 1; тогава съгласно теоремата за остатъците на линейната функция съществува единствен клас [x₀] от остатъци по модул b, удовлетворяващ сравнението. Нека x₀ е представител на [x₀], тогава всяко x є x₀(mod b) се представя като x = x₀+ bt /t О Z/ и тогава

ax + by = c; a(x₀+ bt) + by = c; ax₀+ abt + by = c; b(at + y) = c - ax₀

От последното се вижда, че c - ax₀ | b, и означавайки цялото число (c - ax₀)/b = y₀ се получава b(at + y) = by₀, откъдето y = y₀ - at, което заедно с x = x₀+ bt дава всички решения:

x = x₀+ bt ; y = y₀ - at /t О Z - произволно/.

2) Нека НОД(a, b) = d > 1 и c | d. Разделяйки двете страни на уравнението ax + by = c на d се получава:

a'x + b'y = c', където a = a'd; b = b'd; c = c'd, НОД(a', b' ) = 1

за което важат резултатите от 1).

3) Нека c не се дели на d = НОД(a, b). Допускайки съществуването на решения се получава противоречие: лявата страна на уравнението се дели на d, а дясната не се дели. g

Друго доказателство /предлагащо и конкретен изчислителен алгоритъм, подобен на Евклидовия, основан на така наречените верижни дроби/ се получава с позоваване на ТВЪРДЕНИЕ 1.4.1) /тъждеството на Безу/.

От доказаното личи, че (x₀, y₀) е едно частно решение на уравнението, и ако съществува едно, съществуват и безбройно много решения, образуващи според изведените формули:

x = x₀+ bt, y = y₀ - at /t О Z/

две безкрайни аритметични прогресии, тоест на езика на аналитичната геометрия ако на правата с уравнение ax + by = c има една точка с целочислени координати, има и безбройно много целочислени точки, равноотдалечени една от друга, а формулите за общото решение наподобяват познатите параметрични уравнения на права през точка (x₀, y₀), с колинеарен вектор (b, -a) при t О R.

Примери за линейни Диофантови уравнения:

3.1. Да се реши уравнението 2x + 5y = 12:

а) в цели числа;
б) в неотрицателни цели числа.

Решение: а) НОД(2, 5) = 1 и решения съществуват. Преминавайки към сравнение 2x є 12 (mod 5) се получава x є 6 є 1 (mod 5), откъдето x₀ = 1, y₀ = 2, x = 1 + 5t, y = 2 - 2t при t О Z;

б) от неравенствата 1 + 5t і 0, 2 - 2t і 0 се получава t О [-1/5, 1], тоест t може да бъде само 0 или 1, откъдето x = 1, y = 2 или x = 6, y = 0 /тези две решения илюстрират двата възможни начина за изплащане на сума от 12 парични единици с номинали по 2 и 5 единици/.

3.2. По колко начина може да се облепи с пощенски марки от 30 и 40 стотинки колет, чието изпращане струва 2 лева?

Решение: уравнението 30x + 40y = 200 след деление на двете страни на 10 = НОД(30, 40) придобива вида 3x + 4y = 20 с взаимно прости коефициенти. По модул 4 се получава 3x є 0 (mod 4), x є 0 (mod 4), следователно x₀ = 0, y₀ = 5, x = 4t, y=5 - 3t и поради 4t і 0, 5 - 3t і 0 следва, че t = 0 или t = 1 и задачата има двете решения: x = 0, y = 5 или x = 4, y = 2.

3.3. (Средновековна задача) Фермер купил крави, кози и кокошки - общо 100 животни за 100 талера. Една крава струва 10 талера, една коза - 5, кокошка - 1/2 талер. Известно е, че фермерът е купил и от трите вида животни. По колко животни от всеки вид е купил?

Решение: ако x, y, z означават съответно броя на закупените крави, кози и кокошки, то задачата се свежда до решаването на системата:

в естествени числа. С елиминиране на z се получава уравнението 19x + 9y = 100, от което с преминаване към сравнение по модул 9 се достига до x є 1 (mod 9), откъдето x = 1 + 9t при t і 0 - цяло. Но още при t = 1 се получава y < 0, следователно t = 0 и единственото решение е x = 1, y = 9, z = 90.

Упражнения към глава 3:

3.1. (Комбиниран признак за делимост на 7, 11 и 13) Използувайки каноничното разлагане на числото 1001 = 7*11*13, да се докаже, че ако естествено число се раздели на трицифрени групи отдясно наляво и се образува сумата от групите на четни позиции, намалена със сумата от групите на нечетни, полученото число се дели на 7, 11 или 13 точно тогава, когато и първоначалното.

3.2. (Признаци за делимост на 19 и 29) Естествено число се дели на 19 (29) точно тогава, когато броят на десетиците му, събран с удвоената (утроената) цифра на единиците, се дели на 19 (29).

3.3. (Признаци за делимост на шестнайсетични числа) В шестнайсетична бройна система признаците за делимост на 3, 5 и 15 са аналогични на познатия признак за делимост на 3 или 9 в десетична, тоест сумата от шестнайсетичните цифри /0, 1, . . , 9, A, B, C, D, E, F/ на числото да се дели съответно на 3, 5, или 15 /например 64-битовото число (1234 5678 9ABC DEF0)_HEX се дели на тези делители/. Да се изведе признак за делимост на 10 и да се провери с него числото (ABCDE)_HEX.

3.4[!]. Да се определят дължините на периодите при обръщане на обикновените дроби 1/17 и 1/19 в десетични; на 1/3, 1/5 и 1/10 в двоични; на 1/15 и 1/17 в шестнайсетични.

3.5[*]. Питагоров триъгълник се нарича правоъгълен триъгълник с целочислени дължини x, y, z на страните, които са решения на уравнението x²+ y²= z² в естествени числа, например 3, 4, 5; 5, 12, 13; 8, 15, 17 и т.н. (такива тройки числа - Питагорови тройки - има безбройно много). Да се докаже, че в Питагоров триъгълник:

поне един от катетите е кратен на 3;
поне един от катетите е кратен на 4;
поне една от страните е кратна на 5.

3.6. Да се определи броят на целочислените точки в първи квадрант, лежащи на правата с отрезово уравнение:

3.7. Да се определи при какво условие дробта c/ab, където a, b, c О Z, a, b № 0 може да се представи като сума от две "по-прости" дроби

с някакви x, y О Z; да се представи 5/12 като алгебрична сума от дроби със знаменатели 3 и 4.

3.8. Да се обоснове възможността за еднозначно познаване на дата (от 1 януари до 31 декември), ако е известна сумата S = 12d + 31m, където d - номер на деня от 1 до 31, m - номер на месеца от 1 до 12;

3.9. (Задача за маймунката и кокосовите орехи - по М. Гарднър). След корабокрушение край бреговете на необитаем остров от екипажа на един кораб се спасили само трима моряци и една маймунка. Остатъка от злощастния ден те прекарали в търсене на храна и до залез слънце набрали куп кокосови орехи, каквито на острова имало в изобилие. Моряците решили да отложат подялбата за следващия ден и легнали да спят. През нощта единият от тях се събудил и, страхувайки се от евентуална кавга при предстоящата подялба, решил веднага да отброи своя дял. Той дал един орех на маймунката, която обикаляла наоколо, след което останалият брой орехи се оказал точно кратен на 3, отделил своята третина, която скрил настрани и легнал да спи. След малко се събудил вторият и историята се повторила. След още известно време се събудил и третият, който постъпил по същия начин. На сутринта тримата робинзоновци се събрали пред силно намалялата купчинка за финалната подялба. Те дали един орех на маймунката, след което броят на орехите се оказал точно кратен на 3, в резултат на което всичко завършило благополучно. Колко са били орехите?

3.10[*]. (Целочислени точки върху равнина) Да се докаже, че уравнението с 3 неизвестни:

ax + by + cz = d, където a, b, c, d О Z, a, b, c № 0,

има целочислени решения точно тогава, когато d | НОД(a, b, c); да се решат в цели числа уравненията:

3x + 2y + 7z = 20, 5x + 8y + 11z = 20 и x + 2y + 5z = 12

/неотрицателните решения на последното илюстрират всички възможни начини за изплащане на сума от 12 парични единици с номинали от 1, 2 и 5 единици/.

Oбратно към СЪДЪРЖАНИЕ

ЧАСТ ВТОРА - АЛГЕБРИЧНИ СИСТЕМИ

4. ОБЩИ ПОНЯТИЯ. АЛГЕБРИЧНИ ОПЕРАЦИИ. МОРФИЗМИ.

ДЕФИНИЦИЯ 4.1. Алгебрична операция, операнди, резултат: нека S = {a, b, c, ...} е непразно множество, S² = S ґ S, S³ = S ґ S ґ S и т.н. са съответните Декартови произведения. Всяко съответствие (изображение или функция в смисъла, познат от теорията на множествата) U: S ® S, при което на "x О S се съпоставя единствен елемент y О S, се нарича едночленна (едноместна, унарна) операция в S. Елементът x се нарича операнд; y = U(x) - резултат от операцията U. Всяко съответствие B: S² ® S, при което на "(x, y) О S² се съпоставя единствен z О S, се нарича двучленна (двуместна, бинарна) операция в S. Елементите x и y се наричат операнди /съответно ляв и десен/; z = B(x, y) - резултат от операцията B. Всяко съответствие T: S³ ® S, при което на "(x, y, z) О S³ се съпоставя единствен t О S, се нарича тричленна (тернарна) операция в S с операнди x, y, z и резултат t = T(x, y, z).

Аналогично могат да се дефинират n-членни операции /n О N/. Понятието n-членна операция е равносилно на задаването на n+1-членна релация в същото множество S, действително например за двучленна операция B в S, за която B(x, y) = z може да се въведе тричленна релация R в S, като (x, y, z) О R точно тогава, когато B(x, y) = z. Тази равносилност е поради същественото изискване резултатът от операцията да бъде елемент от същото множество, на което принадлежат и операндите (така нареченото свойство затвореност на операцията).

Примери за алгебрични операции:

4.1. Едночленна операция в Z е обръщането на знака, при което на " n О Z, n -n.

4.2. Едночленна операция в C е комплексното спрягане, при което на " z О C,

4.3. Нека M_2x2е множеството от всички квадратни матрици от втори ред с комплексни елементи; едночленна операция в M_2x2е познатото от линейната алгебра транспониране на матрица при което на "A О M_2x2

4.4. Нека R_2x2е множеството от всички неизродени (неособени, регулярни) квадратни матрици от втори ред с комплексни елементи; едночленна операция в R_2x2е обръщането (инвертирането) на матрица, при което на "A О R_2x2

4.5. Двучленни операции в C са събирането и умножението на комплексни числа, при които на " (u, v) О C²

(u, v) u + v, респективно (u, v) uv

4.6. Двучленни операции в множеството M_2x2 са събирането и умножението на матрици.

4.7. Двучленни операции в множеството от всички тримерни вектори са познатите от геометрията събиране и векторно умножение.

4.8. Двучленни операции в множеството от всички подмножества на дадено непразно множество (неговия булеан) са обединението и сечението.

4.9. n-членни операции в R са операциите min и max, при които на " ( x₁, x₂, . . , x_n) О Rⁿ( x₁, x₂, . . , x_n) min ( x₁, x₂, . . , x_n), респективно ( x₁, x₂, . . , x_n) max ( x₁, x₂, . . , x_n)

По-нататък ще се разглеждат само едночленни и двучленни алгебрични операции.

ДЕФИНИЦИЯ 4.2. Алгебрична система (структура): непразно множество, в което е дефинирана поне една алгебрична операция, се нарича алгебрична система (структура). За разглежданите по-нататък алгебрични системи ще бъдат използувани следните означения:

S ::= {a, b, c, ... ; ¤₁, ¤₂, ...},

където a, b, c, ... са елементите; ¤₁, ¤₂, ... - операциите в S.

В някои литературни източници се среща и терминът универсална алгебра вместо алгебрична система, за множеството от елементите се използува терминът носител, а за множеството от операциите - сигнатура на алгебричната система.

Забележка за означенията: в алгебрична система символът, използуван за означаване на дефинирана в системата операция може:

да предхожда операнда (операндите), например при знаковото обръщане - такива означения се наричат префиксни;
да следва операнда (операндите), например при транспониране или обръщане на матрици - такива означения се наричат постфиксни;

При двучленни алгебрични операции значително по-често от префиксните /¤ ab/ и постфиксните /ab ¤/ означения се използуват инфиксни, при които символът за операцията е между левия и десния операнд /a ¤ b/, явявайки се по този начин и разделител за операндите. Даже в някои случаи (умножение) се практикува символът за операцията изобщо да се пропуска.

В алгебрична система с дефинирана поне една двучленна операция ¤ е възможно образуването на изрази при съчетаване на няколко операнда, например a ¤ b ¤ c. По дефиниция се приема, че при такова съчетаване на произволен брой операнди операциите се извършват по реда на записването им отляво надясно, а за изменение на реда на извършването на операциите се използуват скоби по известния на читателя начин - операциите в скобите се извършват преди останалите, а при вложени скоби се започва с операциите в най-вътрешните. Според казаното следователно

a ¤ b ¤ c ¤ d ::= ((a ¤ b) ¤ c) ¤ d.

В алгебрична система с повече от една операция често се практикува (и това трябва да бъде изрично уговорено!) операциите да имат различен приоритет (да бъдат йерархично подредени), тогава във всеки израз, където участвуват операции с различен приоритет, операциите с най-висок приоритет се извършват най-рано. Обикновено, но не задължително едночленните операции са с по-висок приоритет пред двучленните, например в матричната алгебра изразът AB^-1 се интерпретира като произведение на матрицата A с предварително изчислената обратна матрица на матрицата B /тоест обръщането предхожда умножението, в противен случай изразът би трябвало да бъде записан като (AB)^-1/. Стандартно е прието в числовите системи умножението да има по-висок приоритет от събирането, например 3 + 4*5 = 3 + (4*5) =23, докато (3 + 4)*5 = 35.

ДЕФИНИЦИЯ 4.3. Видове двучленни операции: нека S е алгебрична система с двучленна операция ¤. Операцията ¤ се нарича:

комутативна, ако a ¤ b = b ¤ a за " a, b О S /това равенство се нарича комутативен закон на двучленната операция/;
асоциативна, ако (a ¤ b) ¤ c = a ¤ (b ¤ c) за " a, b, c О S /това равенство се нарича асоциативен закон на двучленната операция/;
идемпотентна, ако a ¤ a = a за " a О S.

Нека S е алгебрична система с две двучленни операции ¤₁ и ¤₂. Операцията ¤₂ се нарича дистрибутивна отляво/отдясно спрямо операцията ¤₁, ако

(a ¤₁ b) ¤₂ c = (a ¤₂ c) ¤₁ (b ¤₂ c), респективно
c ¤₂ (a ¤₁ b) = (c ¤₂ a) ¤₁ (c ¤₂ b) за " a, b, c О S

/ляв и десен дистрибутивни закони на ¤₂ спрямо ¤₁/.

ДЕФИНИЦИЯ 4.4. Неутрални елементи: нека S е алгебрична система с двучленна операция ¤. Елементът e О S се нарича:

ляв неутрален елемент за операцията ¤, ако e ¤ a = a за " a О S;
десен неутрален елемент за операцията ¤, ако a ¤ e = a за " a О S;
неутрален елемент за операцията ¤, ако е едновременно ляв и десен неутрален, тоест ако e ¤ a = a ¤ e = a за " a О S.

От горните примери числовото събиране, матричното събиране, векторното събиране и числовото умножение са комутативни и асоциативни операции. Матричното умножение е асоциативна и некомутативна операция. Векторното умножение е некомутативна и неасоциативна операция. Идемпотентни операции са min(x₁, x₂), max(x₁, x₂), обединението и сечението на множества.

Неутрален елемент за числовото събиране е числото 0, за матричното събиране - нулевата матрица, за векторното събиране - нулевият вектор; за числовото умножение - числото 1, за матричното умножение - единичната матрица. Векторното умножение е пример за двучленна операция без неутрален елемент.

Числовото (матричното) умножение е дистрибутивно спрямо числовото (матричното) събиране. Всяка от операциите обединение и сечение на множества е дистрибутивна спрямо другата.

Асоциативният и комутативният закони търпят индуктивни обобщения в следния смисъл: може да се докаже, че в асоциативна алгебрична система резултатът от съчетаване на краен брой операнди е еднозначно определен, независимо от разположението на скобите; в асоциативна и комутативна алгебрична система е допустимо и произволно разместване на местата на операндите.

Например за асоциативна операция ¤ е изпълнено

a ¤ ((b ¤ c) ¤ d) = a ¤ b ¤ c ¤ d.

Следващите примери са много важни за по-нататъшното изложение.

Пример 4.10: в множеството от всички точкови преобразувания на равнината (пространството) в себе си може да се въведе двучленна операция композиция на преобразувания по следния начин: нека j₁ и j₂ са преобразувания, като j₁: X Y и j₂: Y Z, /X, Y, Z - точки/, тогава j₁ ¤ j₂: X Z, тоест ефектът от композицията j₁ ¤ j₂ се състои в последователното прилагане първо на j₁, после на j₂. Получава се асоциативна и некомутативна алгебрична система с неутрален елемент идентичното преобразувание (идентитет), при което X X за " X.

Пример 4.11: множеството Z₄ = { [0], [1], [2], [3] } от класовете от остатъци по модул 4 може да се превърне в алгебрична система, като се дефинира следната операция Е (събиране по модул 4):

[x] Е [y] ::= [x + y],

тоест сума на всеки два класа с представители x и y е класът с представител обикновената сума на числата x и y. От свойствата на сравненията следва, че сумата на класове е коректно дефинирана, тъй като не зависи от избора на конкретните представители x и y, например

[2] Е [3] = [5] = [1], тъй като 2 + 3 = 5 є 1 (mod 4)

Лесно се проверява, че се получава комутативна и асоциативна алгебрична система с неутрален елемент [0]. Всички суми могат да бъдат нагледно изобразени в таблична форма:

Е	[0]	[1]	[2]	[3]
[0]	[0]	[1]	[2]	[3]
[1]	[1]	[2]	[3]	[0]
[2]	[2]	[3]	[0]	[1]
[3]	[3]	[0]	[1]	[2]

Такова представяне, при което в клетка (i, j) се намира резултатът от левия операнд (в i-тия ред отляво) и десния операнд (в j-тия стълб отгоре) се нарича таблица на Кейли и е особено удобно при алгебрични системи с малък брой елементи.

Очевидно пример 4.11 може да се обобщи като за всяко m О N в множеството Z_m = { [0], [1], . . , [m-1] } от класове по модул m аналогично се въведе операция събиране по модул m /по-нататък за нея ще се използува стандартният знак "плюс"/.

ДЕФИНИЦИЯ 4.5. Морфизми: нека са дадени две алгебрични системи:

S = { a, b, c, ...; U; ¤ } с едночленна операция U и с двучленна операция ¤, и

S' = { a', b', c', ...; U'; ¤'} с едночленна операция U' и с двучленна операция ¤'.

Нека j : S ® S' е съответствие (изображение или функция в смисъла, познат от теорията на множествата) на S в S', като j(a) = a', j(b) = b' и т.н., при което на операцията U в S съответствува операцията U' в S', а на операцията ¤ в S съответствува операцията ¤' в S'.

Съответствието j се нарича хомоморфизъм, ако:

(1) U(a) U'(a'), тоест j(U(a)) = U'(a') = U'(j(a)) за "a О S;

(2) a ¤ b a' ¤' b', тоест j(a ¤ b) = a' ¤' b' = j(a) ¤' j(b) за " a, b О S,

или, казано с други думи, ако резултатът от всяка операция между оригиналите се изобразява при j в резултата от съответната операция между образите.

Хомоморфизъм, който е еднозначно обратимо съответствие, се нарича изоморфизъм, а съответните алгебрични системи - изоморфни /означение S @ S' /.

Изоморфизъм на една алгебрична система в себе си се нарича автоморфизъм.

Понятието хомоморфизъм се обобщава за еднотипни алгебрични системи, които имат еднакъв брой едночленни и еднакъв брой двучленни операции /възможно е някой от тези два броя да е 0/ като условието (1) се изисква да бъде изпълнено за всяка съответна двойка едночленни, а условието (2) - за всяка съответна двойка двучленни операции от двете системи.

Хомоморфизъм на една алгебрична система в себе си (тоест при S = S') се нарича ендоморфизъм. Хомоморфизъм, който е обратимо съответствие (инективен хомоморфизъм) е известен още с термина мономорфизъм, а сюрективен хомоморфизъм - с термина епиморфизъм.

Примери за морфизми:

4.12. Нека R^* = { (0, Ґ), * } е алгебричната система от положителните реални числа с операцията умножение и R⁺ = { (-Ґ, Ґ), + } е алгебричната система от реалните числа с операцията събиране. Тогава съответствието x ln x; x О R^*, ln x О R⁺ /логаритмично съответствие/ е хомоморфизъм, тъй като от x ln x и y ln y следва, че xy ln(xy) = ln x + ln y.

4.13. Съответствието h: Z ® Z₄, при което z [z] /тоест на всяко цяло число се съпоставя съответният му клас от остатъци по модул 4 - вижте пример 4.11/ е хомоморфизъм, тъй като от m [m] и n [n] следва, че m + n [m + n] = [m] + [n].

4.14. Нека E₄ ::= { 1, i, -1, -i; * } е множеството от 4-те стойности на комплексния корен от четвърта степен от 1 с обичайното умножение на комплексни числа с таблица на Кейли:

*	1	i	-1	-i
1	1	i	-1	-i
i	i	-1	-i	1
-1	-1	-i	1	i
-i	-i	1	i	-1

Нека по-нататък T₄ е множеството всички еднаквости в равнината, които оставят непроменена следната фигура /тоест отделни нейни части могат да се преобразуват една в друга, но фигурата като цяло се изобразява в себе си/:

с алгебрична операция ¤ - композицията на преобразувания (вижте пример 4.10). T₄ съдържа: I - идентитет, R₁ - ротация на прав ъгъл около центъра на квадрата в положителна посока; R₂ - ротация на 2 прави ъгъла, R₃ - ротация на 3 прави ъгъла, тоест T₄ ::= { I, R₁, R₂, R₃; ¤ }. Таблицата на Кейли за T₄ е:

¤	I	R₁	R₂	R₃
I	I	R₁	R₂	R₃
R₁	R₁	R₂	R₃	I
R₂	R₂	R₃	I	R₁
R₃	R₃	I	R₁	R₂

Лесно се вижда, че алгебричните системи Z₄, E₄ и T₄ са изоморфни - техните таблици на Кейли се различават само по символите, които си съответствуват по следния начин:

[0]	«	1	«	I
[1]	«	i	«	R₁
[2]	«	-1	«	R₂
[3]	«	-i	«	R₃

4.15. Съответствието E₄ « E₄,при което на всяко число от E₄ се съпоставя неговото комплексно спрегнато, е автоморфизъм.

4.16. Нека C е алгебричната система от комплексните числа с едночленни операции комплексното спрягане и намиране на реципрочно на различно от 0 комплексно число и двучленни операции събиране, изваждане и умножение на комплексни числа. По-нататък нека C_2x2 е множеството от квадратните матрици от втори ред от вида.

с едночленни операции матричното транспониране и обръщане на неизродена матрица и двучленни операции събиране, изваждане и умножение на матрици. Тогава C @ C_2x2 при съответствието:

Лесно се установява, че на комплексно-спрегнатото число съответствува транспонирана матрица; на сума, разлика и произведение на комплексни числа съответствуват сума, разлика и произведение на матрици; на реципрочно на различно от 0 комплексно число съответствува обратна матрица.

Понятието изоморфизъм е от изключителна важност в алгебрата. Изоморфните алгебрични системи евентуално се различават по конкретния вид на елементите си, но не и по начина за манипулиране с тях, тоест всяко свойство на една алгебрична система, което не зависи от естеството на елементите й ще важи и за всяка друга алгебрична система, изоморфна с първата. Поради това изоморфните алгебрични системи могат да се считат за несъществено различни екземпляри или реализации на една и съща абстрактна алгебрична система и често се отъждествяват. Това е оправдание за терминология като например "съществува единствена алгебрична система от даден вид с точност до изоморфизъм" - последното трябва да се разбира в смисъл, че всеки две системи от посочения вид са изоморфни помежду си.

Така алгебричните системи Z₄ @ E₄ @ T₄ от пример 4.14 могат да се считат за конкретни реализации на абстрактната алгебрична система {e, a, b, c; ¤}, с чиито елементи e, a, b, c /които са от произволно естество!/ се оперира съгласно таблицата на Кейли:

¤	e	a	b	c
e	e	a	b	c
a	a	b	c	e
b	b	c	e	a
c	c	e	a	b

Например e, a, b, c могат да се интерпретират с числата 0, 1, 2, 3 от пълната система от най-малки неотрицателни остатъци по модул 4, вместо с класовете [0], [1], [2], [3]. Такава опростена представа за Z_m ще бъде използувана и занапред.

Упражнения към глава 4: в алгебричните системи от упражнения 4.1 - 4.7 да се установи дали дефинираните в тях двучленни операции са комутативни, асоциативни, идемпотентни и дали притежават неутрални елементи.

4.1[!]. S = { a, b, ... ; ¤ }, a ¤ b ::= f, където f е фиксиран елемент от S.

4.2[!]. S = { N; ¤ }, a ¤ b ::= min (a, b).

4.3[!]. S = { N; ¤ }, a ¤ b ::= max (a, b).

4.4[!]. S = { N; ¤ }, a ¤ b ::= a ^b.

4.5[!]. S = { N; ¤ }, a ¤ b ::= НОД(a, b).

4.6[!]. S = { N; ¤ }, a ¤ b ::= НОК(a, b).

4.7[!]. Нека е дадено непразно множество от символи /азбука/. Поредица от нула или повече символи от азбуката се нарича стринг. В множеството от всички стрингове се въвежда двучленна операция конкатенация (съчленяване, съединяване) с означение Е, която присъединява след края на първия стринг символите от втория /например "alpha" Е "bet" = "alphabet"/.

4.8. Таблицата на Кейли за комутативна алгебрична система е симетрична относно главния си диагонал.

4.9[*]. Да се посочи пример (ако съществува) за алгебрична система с двучленна операция:

която е комутативна и неасоциативна;
само с ляв неутрален елемент, който не е десен (само с десен неутрален елемент, който не е ляв);
с ляв и десен неутрални елементи, които са различни;
с два различни неутрални елемента.

Oбратно към СЪДЪРЖАНИЕ

5. ГРУПИ

Това са най-важните алгебрични системи с една двучленна операция, изучавани в обширен раздел от алгебрата - теория на групите.

ДЕФИНИЦИЯ 5.1. Група: алгебрична система G ::= { a, b, c, ...; ^-1; ¤ }, в която са дефинирани една едночленна операция: ^-1 (инвертиране или обръщане), която на "a О G съпоставя инверсен (обратен) елемент a^-1 О G и една двучленна операция: ¤, съпоставяща на "a, b О G резултата a ¤ b О G, като при това са изпълнени следните аксиоми:

(a ¤ b) ¤ c = a ¤ (b ¤ c) за "a, b, c О G /асоциативен закон на двучленната групова операция/;
съществува елемент e О G, такъв, че e ¤ a = a ¤ e = a за "a О G /аксиома за съществуване на неутрален елемент/;
a ¤ a^-1 = a^-1 ¤ a = e за "a О G /аксиома за реципрочност/,

се нарича група.

Ако освен това a ¤ b = b ¤ a за "a, b О G групата се нарича комутативна или Абелева.

Ред на група се нарича броят на елементите й /#(G)/ в случай, че е краен, в противен случай групата е от безкраен ред.

Ако двучленната групова операция е наречена събиране, резултатът от нея се нарича сума, групата се нарича адитивна, нейният неутрален елемент се нарича нулев (и се означава обикновено с 0), инверсният на всеки елемент a, получен с обръщане на знака, се нарича противоположен (означение -a); при групова операция умножение се говори съответно за произведение, мултипликативна група, единичен елемент (1) и реципрочен елемент. Ето как изглеждат груповите аксиоми в адитивни и мултипликативни означения:

Комутативен закон:	a + b = b + a	ab = ba
Асоциативен закон:	*(a + b) + c = a +* (b + c)**	*(ab)c = a(bc)*
Неутрален елемент:	a + 0 = 0 + a = a	a.1 = 1.a = a
Реципрочност:	a + (-a) = (-a) + a = 0	aa^-1 = a^-1a = 1

Ако не се използува специална терминология и символика, адитивни означения се използуват обикновено за Абелеви групи, а в общия случай се използуват мултипликативни. Тази уговорка, както и означението e за неутралния елемент ще важи и занапред, освен ако в конкретно място изрично е уговорено друго.

ТВЪРДЕНИЕ 5.1. Основни следствия от груповите аксиоми:

резултатът abc...d от двучленната операция за краен брой елементи, по-голям от 3, е еднозначно определен, независимо от разположението на скобите;
неутралният елемент на всяка група е единствен;
инверсният на инверсния елемент съвпада с изходния: (a^-1)^-1 = a;
за инверсния елемент на произведение важи: (ab)^-1 = b^-1a^-1;
във всяка група е валидно правилото за съкращаване: от ac = bc Ю a = b; от ca = cb Ю a = b;
уравненията: ax = b и ya = b при дадени a и b имат единствени решения.

c Първото следствие е споменатото в предната глава обобщение на асоциативния закон.

Ако e и e' са два неутрални елемента, то от ee' = e'e = e' и ee' = e'e = e следва e = e'.

Умножавайки отляво двете страни на равенството a^-1 (a^-1)^-1 = e по a се получава последователно

a (a^-1 (a^-1)^-1) = ae, (aa^-1 )(a^-1)^-1 = a, e(a^-1)^-1 = a, (a^-1)^-1 = a.

Формулата (ab)^-1 = b^-1a^-1 се проверява директно:

(ab)(b^-1a^-1) = a(bb^-1)a^-1 = aеa^-1 = aa^-1 = е,

и се обобщава по естествен начин за повече от два елемента:

(ab...c)^-1 = c^-1...b^-1a^-1.

От ac = bc с умножение на двете страни отдясно с c^-1 се получава последователно

(ac)c^-1 = (bc)c^-1, a(cc^-1) = b(cc^-1), ae = be, a = b.

С умножение на двете страни на уравнението ax = b отляво с a^-1 се получава a^-1(ax) = a^-1b, и тъй като a^-1(ax) = (a^-1a)x = ex = x, следва, че x = a^-1b е решение. Предполагайки, че x₁ и x₂ са две решения на това уравнение, от ax₁ = b и ax₂ = b, следва, че ax₁ = ax₂ и според правилото за съкращаване x₁ = x₂. Аналогично y = ba^-1 е единственото решение на второто уравнение /и не е задължително да съвпада с решението на първото при същите a и b/. g

Забележка: аксиомите, участвуващи в ДЕФИНИЦИЯ 5.1 могат да бъдат частично отслабени, без това да се отрази на съдържанието на понятието група, както и да се използува друга еквивалентна система от аксиоми, но този факт няма да бъде използуван в следващото изложение. При още по-сериозно отслабване на залегналите в дефиницията изисквания, се получават някои по-прости алгебрични системи: например оставяйки само двучленната операция и асоциативния закон, се получава полугрупа /такива са някои от алгебричните системи от упражненията към глава 4/, а полугрупа с неутрален елемент се нарича моноид /моноиди са например: N по отношение на умножението с неутрален елемент 1 - комутативен; множеството от всички стрингове от упражнение 4.7 с неутрален елемент празния стринг - некомутативен/. Следователно група е моноид с дефинирана едночленна операция инвертиране, подчинена на аксиомата за реципрочност.

В повечето литературни източници за ред на група се използува означение |G| вместо #(G).

Примери за групи:

5.1. Всяко от познатите числови множества Z, Q, R, C е група по отношение на събирането (адитивни групи на Z, Q, R, C).

5.2. По отношение на умножението всяко от множествата Q\{0}, R\{0}, C\{0} е група (мултипликативни групи на Q, R, C).

5.3. Квадратните матрици от един и същи ред образуват адитивна група.

5.4. Квадратните неизродени матрици от един и същи ред образуват мултипликативна група.

5.5. Множеството Z_m от класовете от остатъци по модул m /m О N/ е адитивна група.

5.6. Множеството от всички комплексни стойности на /n О N/:

{ cos(2kp /n) + i.sin(2kp /n), k = 0, 1, 2, . . , n-1 }

е мултипликативна група.

5.7. Ако е дадена произволна геометрична фигура (равнинна или пространствена), то множеството от всички преобразувания на еднаквост на равнината, респективно на пространството, запазващи фигурата неизменна, както лесно се проверява, е група относно композицията на геометрични преобразувания (вижте пример 4.14) - тя се нарича група от симетриите на дадената фигура. За фигурата от цитирания пример /квадрат с "опашки"/ групата от симетриите е T₄ = { I, R₁, R₂, R₃; ¤ }. От таблицата на Кейли за T₄ следва, че инверсните преобразувания са както следва:

I ^-1 = I, R₁^-1 = R₃, R₂^-1 = R₂, R₃^-1 = R₁.

За правилен n-ъгълник с "опашки" /n О N/ T_n = { I, R₁, R₂, . . , R_n-1; ¤}, тоест групата от симетриите му съдържа идентитета и n-1 ротации около центъра му на ъгли, кратни на 2p/n.

5.8. Нека е даден равностранен триъгълник ABC с медицентър M:

Групата от симетриите му съдържа следните преобразувания: I - идентитет, R₁ - ротация на 120° около M (в положителна посока - обратно на посоката на въртене на часовниковата стрелка), R₂ - ротация на 240° около M в същата посока, S₁, S₂ и S₃ - осеви симетрии относно правите AM, BM и CM. Таблицата на Кейли е:

¤	I	R₁	R₂	S₁	S₂	S₃	инверсни:
I	I	R₁	R₂	S₁	S₂	S₃	I ^-1 = I
R₁	R₁	R₂	I	S₂	S₃	S₁	R₁^-1 = R₂
R₂	R₂	I	R₁	S₃	S₁	S₂	R₂^-1 = R₁
S₁	S₁	S₃	S₂	I	R₂	R₁	S₁^-1 = S₁
S₂	S₂	S₁	S₃	R₁	I	R₂	S₂^-1 = S₂
S₃	S₃	S₂	S₁	R₂	R₁	I	S₃^-1 = S₃

Получава се пример за неабелева група от 6-ти ред, която се нарича диедрална група от трета степен (означение D₃). Последният пример се обобщава по естествен начин - диедрална група от n-та степен D_n /n = 3, 4, .../ се нарича групата от симетриите на правилен n-ъгълник - тя съдържа идентитета, n-1 на брой ротации около центъра на многоъгълника на ъгли, кратни на 2p/n, и n осеви симетрии относно оси, минаващи през центъра му. Тази група може да се дефинира и абстрактно за "n О N, тя е от ред 2n и има приложения в геометрията. При n = 2 е известна още като група на Клайн, а за n і 3 не е комутативна.

5.9. Субституция на числата /номерата/ 1, 2, . . , n /n О N/ се нарича съответствие, при което на 1, 2, . . , n се съпоставя произволна пермутация i₁, i₂, . . , i_n на тези номера /тоест същите числа 1, 2, . . , n, наредени евентуално в друг ред/. Субституцията, при която 1 i₁, 2 i₂, . . , n i_n ще се означава символично така:

Нека S_n е множеството от всички субституции на числата 1, 2, . . , n. S_n може да се превърне в мултипликативна група, въвеждайки инверсна (обратна) субституция:

единична субституция:

и произведение на субституции:

S_n се нарича симетрична група от n-та степен /от комбинаторния факт, че съществуват n! пермутации от n елемента, следва, че #(S_n) = n!/. Тя има съдържателни комбинаторни приложения и не е комутативна при n і 3.

От посочените примери се вижда, че съществуват групи от произволен ред - както краен /Z_m от пример 5.5 - #(Z_m) = m; също пример 5.6/, така и безкраен /пример 5.1/ - в последния случай групата може да бъде изброимо или неизброимо множество.

ДЕФИНИЦИЯ 4.5 за морфизми при общите алгебрични системи има следния вид в конкретния случай за групи:

ДЕФИНИЦИЯ 5.2. Хомоморфизъм, изоморфизъм и автоморфизъм на групи:
нека j: G ® G' е съответствие (изображение) на групата G в групата G'. Съответствието j се нарича хомоморфизъм (на групи), ако

j(a^-1) = (j(a))^-1 и j(ab) = j(a) j(b) за " a, b О G.

Еднозначно обратим хомоморфизъм се нарича изоморфизъм /означение за изоморфни групи: G @ G'/.

Изоморфизъм на една група в себе си се нарича автоморфизъм.

По-рано споменатите в примери 4.13 и 4.14 хомоморфизъм: Z ® Z₄ и изоморфизъм: Z₄ @ E₄ @ T₄ са всъщност примери за хомоморфизъм, респективно изоморфизъм на групи.

Освен че всеки хомоморфизъм изобразява инверсен елемент в инверсен, също е валидно

ТВЪРДЕНИЕ 5.2. Всеки хомоморфизъм на групи изобразява неутрален елемент в неутрален.

c Нека j: G ® G' е хомоморфизъм на групи с неутрални елементи e О G и e' О G'. Щом j е хомоморфизъм, от ee = e следва, че

j(e) j(e) = j(e), но j(e) = j(e).e', и от j(e) j(e) = j(e).e'

след съкращаване се получава j(e) = e'. g

ДЕФИНИЦИЯ 5.3. Степени /кратни/ на елемент: нека G е мултипликативна група и a О G. Степени на елемента a с показатели 1, 2, ... се дефинират индуктивно:

a¹::= a, a²::= aa, a³::= a²a = aa², a⁴::= a³a = aa³ и т.н.

По-нататък a⁰::= e, а за цели отрицателни показатели

a^-2::= (a^-1)², a^-3::= (a^-1)³ и т.н.,

тоест те са степените с цели положителни показатели на обратния елемент a^-1.

Ако G е адитивна група се говори за кратни на елемент вместо за степени и се употребяват означенията:

..., -2a, -a, 0, a, 2a, 3a, ... вместо ..., a^-2, a^-1, a⁰, a¹, a², a³, ...

Дадената дефиниция е коректна поради асоциативния закон: a²a = (aa)a = a(aa) = aa² и т.н.; по-общо a^m.aⁿ = aⁿ.a^m= a^{m + n} за "m, n О Z, тоест степените на всеки елемент са комутативни помежду си.

От последното следва още, че и (a^m)ⁿ = a^mn за " m, n О Z.

ДЕФИНИЦИЯ 5.4. Ред на елемент: нека G е мултипликативна група и a О G. Ако съществува естествено число k със свойството a^k = e, то най-малкото естествено число с това свойство се нарича ред на елемента a. В противен случай /тоест единствено при a⁰ = e/ a се нарича елемент от безкраен ред.

Коректността на дефиницията се обуславя от факта, че ако a^k = e за k О Z, k < 0, то a^-k = e^-1 = e.

ДЕФИНИЦИЯ 5.5. Циклична група, образуващ елемент: ако за групата G съществува елемент a О G със свойството, че всеки елемент от G е равен на някоя степен на a, групата G се нарича циклична, а елементът a - образуващ елемент.

От горните примери циклични групи са адитивната група на Z (безкрайна, с образуващи елементи ±1 - всяко цяло число е кратно на ±1, всеки от двата образуващи елемента е от безкраен ред), а циклични групи от краен ред са: адитивната група на Z_m (образуващ елемент е например [1] от ред m), мултипликативната група на корените от n-та степен от 1 /с образуващ елемент например cos(2p/n) + i.sin(2p/n)/, групата T_n от симетриите на правилния n-ъгълник с "опашки" (образуващ елемент - ротация на ъгъл 2p/n, от ред n). Примерът с адитивната група на Z сочи, че една циклична група може да има и повече от един образуващ елемент.

От забележката след ДЕФИНИЦИЯ 5.3 за комутативните степени на всеки елемент следва

ТВЪРДЕНИЕ 5.3. Всяка циклична група е Абелева.

Но не всяка Абелева група е циклична - най-прост пример е споменатата по-горе група на Клайн (диедралната група D₂) от четвърти ред.

ТВЪРДЕНИЕ 5.3 заедно със следващите две дава достатъчно пълна представа за структурата на цикличните групи.

ТВЪРДЕНИЕ 5.4. Структура на крайните циклични групи: нека G е крайна циклична група от ред m с образуващ елемент a, тогава

G = { e = a⁰, a, a², a³, . . , a^m-1 },

тоест G се изчерпва със степените на образуващия елемент /от нулева до m-1-ва/, които са всички различни помежду си.

c Тъй като неутралният елемент може да бъде образуващ само на група от първи ред, за която твърдението е очевидно, нека a № е. Ако a е от безкраен ред, всички целочислени степени на a:

..., a^-3, a^-2, a^-1, a⁰ = e, a¹, a², a³, ...

са различни помежду си, иначе от a^u= a^v за u № v би следвало противоречието a^u-v= e за u - v № 0. Но при крайна група G горните степени не могат да бъдат всичките различни, следователно образуващият елемент е от краен ред k > 0. Тогава степените:

a⁰= e, a¹ = a, a², a³, . . , a^k-1

са всичките различни помежду си, а всяка друга степен съвпада с някоя от тях. Наистина допускането a^u= a^v за 0 Ј u < v Ј k -1 води до a^{v - u}= e за v - u < k, което противоречи на минималността на k. Ако w О Z, то разделяйки w на k с остатък, се получава w = kq + r, където 0 Ј r < k и тогава

a^w = a^{kq + r} = a^kq.a^r = (a^k)^q.a^r = e^q.a^r = ea^r = a^r

За приключване на доказателството остава да се забележи, че k = m = #(G), тъй като в G има точно m различни елементи. От доказаното следва полезният факт, че a^m-1 = a^-1 g

ТВЪРДЕНИЕ 5.5. Всяка циклична група е изоморфна или на адитивната група на Z, ако е от безкраен ред, или на Z_m, ако е от краен (m-ти) ред.

c Нека G е циклична група от безкраен ред с образуващ елемент a № е. Елементът a също е от безкраен ред и според доказаното в ТВЪРДЕНИЕ 5.4 всички целочислени степени на a:

..., a^-3, a^-2, a^-1, a⁰ = e, a¹, a², a³, ...

са различни помежду си. Поради a^u.a^v = a^{u + v} за u, v О Z следва, че съответствието G « Z, при което aⁿ « n, е изоморфизъм.

За крайна циклична група от m-ти ред с образуващ елемент a според доказаното в ТВЪРДЕНИЕ 5.4

G = { a⁰, a, a², a³, . . , a^m-1 } @ { [0], [1], [2], [3], . . , [m-1] } = Z_m

при a^k « [k] за k = 0, 1, 2, . . , m-1. g

От доказаните твърдения следва, че от всеки възможен ред съществува циклична група, и то единствена с точност до изоморфизъм.

ДЕФИНИЦИЯ 5.6. Подгрупа: нека G е група и H е непразно подмножество на G. Ако подмножеството H е също група по отношение на същите алгебрични операции, които са дефинирани в G, H се нарича подгрупа на G.

Според тази дефиниция всяка подгрупа заедно с всеки свой елемент съдържа и неговия инверсен, а заедно с всеки два свои елемента съдържа и резултата от двучленната операция между тях /вижте и упражнение 5.7/.

Всяка група притежава подгрупи: непосредствено се проверява например, че подмножеството {e}, състоящо се само от неутралния елемент на G, както и самата G, са подгрупи на G - тези подгрупи се наричат тривиални. По-съдържателен пример се получава, ако се избере произволен елемент, различен от неутралния, и се разгледат всичките му степени - лесно се проверява, че те образуват циклична подгрупа, която не винаги е тривиална.

ТВЪРДЕНИЕ 5.6. Всяка подгрупа на Абелева група е също Абелева. Всяка подгрупа на циклична група е също циклична.

c Твърдението за подгрупите на Абелевите групи е очевидно, затова нека G е циклична група с образуващ елемент a и нека H е подгрупа на G. Ако H = {e} твърдението е очевидно, затова нека k е най-малкият положителен показател, за който a^k О H № {e} /такъв има, защото ако a^k О H за k О Z, k < 0, то и a^-k О H/. Тогава H се състои от всички степени на a с показатели, целочислено кратни на k, действително ако a^s О H, разделяйки s на k с остатък, се получава s = kq + r, където 0 Ј r < k и тогава поради a^s, a^k О H елементът a^r = a^{s - kq} = a^s .a^-kq = a^s.(a^k)^-q О H, което е възможно само при r = 0, иначе се получава противоречие с предположението за k като най-малък положителен показател със свойството a^k О H. Но от r = 0 Ю s | k и щом H = { a^kt, t О Z }, това означава, че H е циклична с образуващ елемент a^k. g

ДЕФИНИЦИЯ 5.7. Ляв/десен съседен клас на група по своя подгрупа, породен от даден елемент: нека G е произволна група, a О G , и H = {h₁, h₂, h₃, ...} е подгрупа на G. Множеството aH ::= {ah₁, ah₂, ah₃, ...} от произведенията на елемента a като ляв множител с всевъзможни елементи h₁, h₂, h₃, ... от подгрупата H се нарича ляв съседен клас на G по H, породен от елемента a. Аналогично множеството Ha ::= {h₁a, h₂a, h₃a, ...} се нарича десен съседен клас на G по H, породен от елемента a.

Очевидно за Абелева група няма разлика между понятията ляв и десен съседен клас /при адитивни означения a + H = H + a/, а за произволна група и нейна подгрупа H последната може да се счита за ляв или десен съседен клас, породен от неутралния елемент e: H = eH = He.

Например за споменатата адитивна група Z₄ = {[0], [1], [2], [3]} от класове от остатъци по модул 4 подмножеството H = { [0], [2] } е, както лесно се проверява, подгрупа. Тогава всичките съседни класове на Z₄ по H, породени от елементите на Z₄изглеждат така:

[0] + H = H + [0] = { [0] + [0], [0] + [2] } = { [0], [2] } = H

[1] + H = H + [1] = { [1] + [0], [1] + [2] } = { [1], [3] }

[2] + H = H + [2] = { [2] + [0], [2] + [2] } = { [2], [0] } = H

[3] + H = H + [3] = { [3] + [0], [3] + [2] } = { [3], [1] },

тоест има само 2 различни съседни класа: { [0], [2] } и { [1], [3] }, първият от които съвпада с H.

За диедралната група D₃ = { I, R₁, R₂, S₁, S₂, S₃}, която не е Абелева /пример 5.8/, една нейна подгрупа е K = { I, S₁}. Съседните класове на D₃ по K са:

IK = S₁K = KI = KS₁ = K = { I, S₁}

R₁K = { R₁, S₂} = S₂K № KR₁ = { R₁, S₃} = KS₃

R₂K = { R₂, S₃} = S₃K № KR₂ = { R₂, S₂} = KS₂

Както се вижда, в този случай съществуват по три различни леви и десни съседни класове, като ляв и десен съседни класове, породени от един и същи елемент, не винаги съвпадат.

ТВЪРДЕНИЕ 5.7. Свойства на съседните класове:
1) всички съседни класове по една и съща подгрупа имат равен брой елементи (или са равномощни ако са безкрайни множества);
2) всеки съседен клас се поражда от всеки свой елемент;
3) два съседни класа или нямат общ елемент, или съвпадат.

c Нека G е група, a, b О G, H = { h₁, h₂, h₃, ...} - подгрупа на G /h₁, h₂, h₃, ... са всичките различни елементи от H/. Доказателство за левите съседни класове /за десните е аналогично/:

1) в съседния клас aH = { ah₁, ah₂, ah₃, ...} всичките елементи ah₁, ah₂, ah₃, ... са също различни, иначе от ah' = ah" според правилото за съкращаване би се получило противоречието h' = h". Това доказва, че #(aH) = #(H), тоест всеки съседен клас е равномощен с подгрупата;

2) нека ah О aH, тогава ah е някой от елементите ah₁, ah₂, ah₃, ... и съседният клас, породен от него, изглежда така:

(ah)H = { (ah)h₁, (ah)h₂, (ah)h₃, ...} = { a(hh₁), a(hh₂), a(hh₃), ...}

но тъй като H е подгрупа, произведенията hh₁, hh₂, hh₃, ... съвпадат с всичките елементи h₁, h₂, h₃, ... (евентуално в друг ред) на H, което означава, че

(ah)H = { a(hh₁), a(hh₂), a(hh₃), ...} = { ah₁, ah₂, ah₃, ...} = aH,

или всеки съседен клас се поражда от всеки свой елемент;

3) накрая ако aH З bH № Ж нека x О aH и x О bH, тогава според 2) x поражда aH и bH като xH = aH и xH = bH, откъдето aH = bH. g

Доказаното ТВЪРДЕНИЕ 5.7 означава, че всеки елемент на G принадлежи на точно един съседен клас - на класа, породен от самия елемент, а принадлежността на два елемента a, b О G на един и същи съседен клас по подгрупата H /иначе казано, a = bh, респективно a = hb за някой h О H/, е релация на еквивалентност, фактор-множеството спрямо която е множеството от съседните класове и осъществява разлагане на групата G.

ТВЪРДЕНИЕ 5.8. Разлагане по съседни класове: нека G е група и H е подгрупа на G. Тогава:

G = H И aH И bH И cH И ... = H И Ha И Hb И Hc И ... ,

тоест всяка група е обединение от всички различни непресичащи се (според ТВЪРДЕНИЕ 5.7.3) леви/десни съседни класове по подгрупата H. Тук a, b, c, ... са различни елементи от групата G, не принадлежащи на H.

Ако броят на всички леви съседни класове на една група G по нейна подгрупа H е краен, може да се докаже, че броят на всичките десни съседни класове на G по H е същият, което е повод за

ДЕФИНИЦИЯ 5.8. Индекс на подгрупа в дадена група: ако G е група, H - такава подгрупа на G, че броят на съседните класове на G по H е краен, този брой се нарича индекс на подгрупата H в групата G и се означава с (G : H).

ТВЪРДЕНИЕ 5.9. Теорема на Лагранж за крайните групи: нека G е крайна група и H е произволна подгрупа на G. Тогава редът на подгрупата е делител на реда на групата.

c Доказателството следва от твърдения 5.7 и 5.8 - в разлагането по съседни класове последните са краен брой: (G : H) и съдържат по равен брой елементи - #(H), следователно #(G) = #(H).(G : H), откъдето #(G) | #(H). g

От теоремата на Лагранж следва, че група от ред, равен на просто число, притежава само тривиалните подгрупи. По-нататък, ако a е произволен елемент от такава група, различен от неутралния, цикличната подгрупа, породена от степените на a, не може да бъде от първи ред. Тогава остава единствено възможността въпросната циклична подгрупа да е от същия ред като реда на групата, което означава, че те съвпадат, тоест изходната група е циклична. Сега според ТВЪРДЕНИЕ 5.5 следва, че съществува единствена с точност до изоморфизъм група от ред, равен на просто число - цикличната.

Друго следствие е, че редът на всеки елемент в крайна група е също делител на реда на групата.

ДЕФИНИЦИЯ 5.9. Инвариантна подгрупа: нека G е група и H е подгрупа на G. Подгрупата H се нарича инвариантна (нормален делител), ако всеки ляв съседен клас на G по H съвпада със съответния десен /тоест, породен от същия елемент/, или, иначе казано, ако двете разлагания на G по леви и по десни съседни класове съвпадат.

Тривиалните подгрупи на произволна група са очевидно инвариантни, а за Абелевите групи това е валидно даже за всички техни подгрупи. Пример за инвариантна подгрупа на некомутативната диедрална група D₃ е подгрупата R = { I, R₁, R₂} от ротациите, действително:

IR = RI = R₁R = RR₁ = R₂R = RR₂ = R = { I, R₁, R₂}

S₁R = RS₁ = S₂R = RS₂ = S₃R = RS₃ = { S₁, S₂, S₃}

ТВЪРДЕНИЕ 5.10. Критерий за инвариантна подгрупа: нека G е група и H е подгрупа на G. Подгрупата H е инвариантна Ы за "g О G и за "h О H елементът g^-1hg О H.

c За произволни g О G и h О H нека елементът hg О Hg съвпада с някой от елементите от левия съседен клас gH, например нека hg = gh', откъдето с умножаване отляво с инверсния на g се получава g^-1hg = h' О H и обратно. g

Както е отбелязано по-горе, принадлежността на два елемента от една група G към един и същи съседен клас по нейна подгрупа H е релация на еквивалентност и фактор-множеството на G по тази релация е множеството от всички съседни класове на G по H. Във важния частен случай, когато H е инвариантна подгрупа, въпросното фактор-множество може да се превърне в група като се въведат операциите инвертиране на съседен клас (едночленна) и умножение на съседни класове (двучленна) по следния начин:

(aH)^-1 ::= a^-1H и (aH)(bH) ::= (ab)H за a, b О G,

тоест обратен на съседния клас, породен от a, е съседният клас, породен от a^-1; произведение на класовете, породени от a и b е класът, породен от произведението ab. Коректността на въведените операции (тоест независимостта на резултатите от избраните представители) следва именно от факта, че H е инвариантна подгрупа, действително за произволни елементи a, b О G, h₁, h₂, h, h' О H е изпълнено:

(ah₁)(bh₂) = a(h₁b)h₂ = a(bh')h₂ = (ab)(h'h₂) = (ab)h /h₁b = bh' поради bH = Hb/

(aH)(a^-1H) = (aa^-1)H = H

Както се вижда още, неутрален съседен клас при така дефинираното умножение е самата подгрупа H поради (aH)H = (aH) (eH) = (ae)H = aH, а изпълнението на асоциативния закон при умножението на съседни класове следва от изпълнението му в G. Така се стига до

ДЕФИНИЦИЯ 5.10. Фактор-група: нека G е група и H е инвариантна подгрупа на G. Множеството от всички съседни класове на G по H с описаните по-горе операции "инвертиране" и "умножение" на съседни класове се нарича фактор-група на G по H (означение G/H).

Според тази дефиниция фактор-групата е фактор-множество в познатия от теорията на множествата смисъл, снабдено с групова структура /и операциите над съседни класове в G/H "наследяват" съответните операции в G/. От теоремата на Лагранж следва, че ако G е крайна група, #(G/H) = #(G) / #(H) = (G : H).

Например в адитивната група на Z класът [0] по модул m /m О N/ е, както лесно се проверява, подгрупа (и то инвариантна, тъй като Z е Абелева). Тогава фактор-групата Z/[0] се състои от всичките класове от остатъци по модул m, тоест Z/[0] = { [0], [1], . . , [m-1] } = Z_m.

В диедралната група D₃ подгрупата R = { I, R₁, R₂} от ротациите е инвариантна. Тогава D₃/ R = { R, S }, където S = { S₁, S₂, S₃} е съседният клас от симетриите. Таблицата на Кейли за D₃ / R е:

D₃/ R	R	S
R	R	S
S	S	R

Вижда се, че D₃/ R е изоморфна на цикличната група от втори ред.

С всяка фактор-група на дадена група може да се асоциира един хомоморфизъм. Ако G е група и H е инвариантна подгрупа на G, на "g О G може да се съпостави съседния клас gH, породен от g, Тогава съпоставяйки на произведението g₁g₂ О G съседния клас (g₁g₂)H, се получава, както лесно следва от описаната конструкция на фактор-групата /вижте дефинираното по-горе умножение на съседни класове/, хомоморфизъм на G в G/H.

ДЕФИНИЦИЯ 5.11. Естествен (каноничен) хомоморфизъм: нека G е група и H е инвариантна подгрупа на G. Хомоморфизмът G ® G/H при който всеки елемент се изобразява в съседния клас, породен от самия него /тоест g gH за " g О G/, се нарича естествен (каноничен) хомоморфизъм.

Например ако m О N, естественият хомоморфизъм Z ® Z_m се получава съпоставяйки на всяко цяло число z класа от остатъци [z] по mod m.

ДЕФИНИЦИЯ 5.12. Ядро на хомоморфизъм: нека j: G ® G' е хомоморфизъм на групи. Множеството от всички елементи на G, изобразяващи се при j в неутралния елемент e' на G', се нарича ядро на j (означение Ker j), тоест Ker j ::= { k О G; j (k) = e' О G' }.

ТВЪРДЕНИЕ 5.11. Ядрото на всеки хомоморфизъм е инвариантна подгрупа.

c Нека j: G ® G' е хомоморфизъм на групата G в групата G' и Ker j = { k О G; j(k) = e' О G' }. Проверката, че Ker j е подгрупа на G, е тривиална. За "g О G и за "k О Ker j е изпълнено

j(g^-1kg) = (j(g))^-1. j(k). j(g) = (j(g))^-1. e'. j(g) = (j(g))^-1. j(g) = e',

тоест g^-1kg О Ker j и според критерия от ТВЪРДЕНИЕ 5.10 Ker j е инвариантна. g

ТВЪРДЕНИЕ 5.12. Теорема за хомоморфизмите: нека j: G ® G' е хомоморфизъм на групата G върху цялата група G' (епиморфизъм). Тогава G' @ G/Ker j, тоест хомоморфният образ на една група е изоморфен на нейната фактор-група по ядрото на хомоморфизма.

Тази наситена с терминология теорема твърди по същество, че всички хомоморфизми се изчерпват с естествения, или в духа на коментара преди ДЕФИНИЦИЯ 5.11 следва, че и с всеки хомоморфизъм може да се асоциира една фактор-група.

Упражнения към глава 5:

5.1[!]. Да се конструират директно всички групи до четвърти ред включително с точност до изоморфизъм.

5.2. Латински квадрат от n-ти ред в комбинаториката се нарича квадратна таблица с n реда и n колонки, като всяка клетка е запълнена с един от n възможни символа без да се повтарят в никой ред и в никой стълб. Да се докаже, че таблицата на Кейли за произволна крайна група е латински квадрат (но не всеки латински квадрат е таблица на Кейли за група). Ако групата е циклична, елементите й могат да се наредят така, че всеки ред (стълб) на таблицата на Кейли може да се получи от предишния с циклично изместване на първия елемент в края.

5.3. Използувайки упражнение 5.1 и теоремата на Лагранж, да се докаже, че всяка група от ред, по-малък или равен на 5, е Абелева.

5.4[!]. Да се опишат групите от симетриите на следните фигури: разностранен триъгълник; равнобедрен неравностранен триъгълник; квадрат; правоъгълник, различен от квадрат; ромб, различен от квадрат; правилен тетраедър; куб.

5.5. Да се докаже, че групите от симетриите на равностранния триъгълник и правилния тетраедър са изоморфни със симетричните групи от 3-та, респективно 4-та степен.

5.6. В циклична група от ред, равен на просто число, всеки елемент, различен от неутралния, е образуващ; в крайна циклична група броят на образуващите елементи е равен на броя на естествените числа, по-малки от реда на групата, и взаимно прости с него.

5.7[!]. Нека G е група и H е непразно подмножество на G. Необходимо и достатъчно условие H да бъде подгрупа на G е за " x, y О H произведението " xy^-1 О H.

5.8[!]. Да се намерят всички подгрупи на цикличните и на диедралните групи с 4, 6 и 8 елемента. Да се установи кои от тях са инвариантни.

5.9. Нека G е крайна група от четен ред и H е подгрупа на G от ред #(G) /2, тоест подгрупа от индекс 2. Използувайки разлагането по съседни класове, да се докаже, че H е инвариантна.

5.10. Нека G е произволна група. Център Z на G се нарича множеството от елементи на G, комутативни с всички останали , тоест Z ::= { z О G; zx = xz за " x О G }. Да се докаже, че центърът на всяка група е инвариантна подгрупа.

5.11. Всяка фактор-група на Абелева/циклична група е също Абелева/циклична.

5.12. Нека G е произволна група и g - фиксиран елемент от G. Съответствието j:G ® G, при което j(x) = g^-1xg за " x О G, е автоморфизъм на G.

5.13[!] Да се намерят всички хомоморфизми на Z₄ в Z₂, на Z₆ в Z₃; всички автоморфизми на Z₃, на Z₄.

Oбратно към СЪДЪРЖАНИЕ

6. ПРЪСТЕНИ И ПОЛЕТА

Това са алгебрични системи, в които са дефинирани две двучленни операции.

ДЕФИНИЦИЯ 6.1. Пръстен: алгебрична система R = { a, b, c , ...; Е; Д} с две двучленни операции: Е и Д, които удовлетворяват аксиомите:

относно Е R е Абелева група /така наречената адитивна група на пръстена/;
за " a, b, c О R са изпълнени двата дистрибутивни закона /ляв и десен/:

(a Е b) Д c = (a Д c) Е (b Д c),
c Д (a Е b) = (c Д a) Е (c Д b),

се нарича пръстен.

Обикновено двете двучленни операции се наричат събиране и умножение и тази позната терминология, както и обичайните знаци "плюс /+/" за събирането и "звездичка /*/", "точка /./" или без знак за умножението ще се използуват по-нататък. Ще бъде също валидна стандартната уговорка за по-висок приоритет на умножението спрямо събирането. От ДЕФИНИЦИЯ 6.1 и ДЕФИНИЦИЯ 5.1 следва, че събирането е комутативна и асоциативна операция, чийто неутрален елемент ще се означава с 0 /нулев елемент/, като от контекста ще бъде ясно дали означението се отнася за нулевия елемент на разглеждания пръстен или за цялото число нула. Инверсният елемент на елемента a относно събирането ще се означава с -a /противоположен елемент/. Сумата b + (-a) се означава накратко b - a и се нарича разлика на елементите b и a, а получаването на разликата - изваждане.

ТВЪРДЕНИЕ 6.1. Елементарни следствия от аксиомите за пръстен:
1) 0.a = a.0 = 0;
2) (-a).b = a.(-b) = -ab;
3) (a + b + ... + c)z = az + bz + ... + cz ; z(a + b + ... + c) = za + zb + ... + zc;
4) (a - b)c = ac - bc; c(a - b) = ca - cb.

c 1) ab = a.(0 + b) = a.0 + ab откъдето a.0 = 0; ba = (b + 0).a = ba + 0.a откъдето 0.a = 0;
2) 0 = 0.b = (a + (-a)).b = ab + (-a)b = ab + (-ab) откъдето (-a)b = -ab.
3) се доказва индуктивно. g

Примери за пръстени:

6.0. Ако в адитивна Абелева група се въведе нулево умножение: ab ::= 0, тя се превръща в пръстен.

В следващите примери 6.1 - 6.5 двучленните операции са обичайните числово събиране и числово умножение.

6.1. Множествата Z, Q, R, C.

6.2. Множеството { 0, ±2, ±4, ±6, ...} от всички четни числа.

6.3. Множеството от числата от вида { a + b; a, b О Z }.

6.4. Множеството от комплексни числа от вида { a + bi; a, b О Z } /така наречените цели Гаусови числа/.

6.5. Множеството от двоично-рационалните числа от вида a/2^k, където a О Z, k = 0, 1, 2, ...

6.6. Множеството от всички квадратни матрици от фиксиран ред с комплексни елементи относно матричното събиране и матричното умножение.

6.7. Множеството от всички вектори в тримерното пространство относно векторното събиране и векторното умножение.

6.8. Множеството Z_m от класовете от остатъци по даден модул m може да се превърне в пръстен, ако наред с по-рано дефинираното събиране на класове /пример 4.11/ се въведе и умножение на класове по следния начин: [x].[y] ::= [xy], тоест произведение на всеки два класа с представители x и y е класът с представител xy /коректността на така дефинираното умножение се установява елементарно/. Ето как изглеждат например таблиците за събиране и умножение в Z₄ и Z₅, инверсните елементи относно двете операции /за краткост скобите не са изписани - вижте коментара в края на глава 4!/:

пръстен Z₄:

+	0	1	2	3	противоположни:	*	1	2	3	реципрочни:
0	0	1	2	3	-0 = 0	0	0	0	0
1	1	2	3	0	-1 = 3	1	1	2	3	1^-1 = 1
2	2	3	0	1	-2 = 2	2	2	0	2
3	3	0	1	2	-3 = 1	3	3	2	1	3^-1 = 3

пръстен Z₅:

+	0	1	2	3	4	противоположни:	*	1	2	3	4	реципрочни:
0	0	1	2	3	4	-0 = 0	0	0	0	0	0
1	1	2	3	4	0	-1 = 4	1	1	2	3	4	1^-1 = 1
2	2	3	4	0	1	-2 = 3	2	2	4	1	3	2^-1 = 3
3	3	4	0	1	2	-3 = 2	3	3	1	4	2	3^-1 = 2
4	4	0	1	2	3	-4 = 1	4	4	3	2	1	4^-1 = 4

Настоятелно се препоръчва на читателя да разгледа внимателно тези примери, тъй като аналогичните на Z₄ пръстени Z₂₅₆, Z₆₅₅₃₆, Z₂32и Z₂64 /256 = 2⁸, 65536 = 2¹⁶/ точно илюстрират машинната целочислена аритметика на 8-,16-, 32- и 64-битовите цели числа (byte, word, double word и double longword).

Оставяйки настрани не особено съдържателния пример 6.0 се вижда, че съществуват пръстени с произволен брой елементи - както краен (Z_m), така и безкраен (примери 6.1 - 6.7). Така "най-малкият" възможен пръстен има единствен елемент - нулевия /нулев пръстен/. Освен това в повечето примери умножението има свойства, които не са залегнали в дефиницията, като асоциативност, комутативност, наличие на неутрален елемент, на инверсен елемент. Особено внимание заслужават примери 6.6 - 6.8 в следното отношение: в тези пръстени съществуват ненулеви елементи, чието произведение е равно на нулевия елемент (ситуация, невъзможна в числовите пръстени 6.1 - 6.5), действително

векторното произведение на ненулеви колинеарни вектори, както е известно от геометрията, е нулев вектор; в Z₄ примерно [2].[2] = [0], а в Z₆₅₅₃₆ [1024].[64] = [0] - последното означава, че в машинната целочислена аритметика ако произведението на две стойности от тип word е стойност от същия тип, то без препълване резултатът от умножението на 1024 по 64 би бил равен на 0.

Тези обстоятелства са основания за въвеждане на

ДЕФИНИЦИЯ 6.2. Делители на нулата: ненулеви елементи на пръстен, чието произведение е равно на нулевия елемент, се наричат делители на нулата /тоест a № 0, b № 0 и аb = 0/.

ДЕФИНИЦИЯ 6.3. Видове пръстени: един пръстен се нарича:

асоциативен, ако умножението удовлетворява асоциативния закон /(ab)c = a(bc)/;
комутативен, ако умножението удовлетворява комутативния закон /ab = ba/;
с/без единица, ако умножението притежава/не притежава неутрален елемент - последният ще се означава занапред обикновено с 1;
с/без делители на нулата, ако в пръстена съществуват/не съществуват делители на нулата по смисъла на ДЕФИНИЦИЯ 6.2;
цялостен, ако е ненулев, комутативен, асоциативен и без делители на нулата.

От посочените примери единствено пръстенът от тримерните вектори /пример 6.7/ не е асоциативен. Некомутативни са пръстените от примери 6.6 и 6.7. Пръстенът от четните числа /пример 6.2/ и пръстенът от тримерните вектори /пример 6.7/ са без единица. Цялостни са числовите пръстени /примери 6.1 - 6.5/ и пръстенът Z₅.

Неасоциативни пръстени се срещат в приложения относително по-рядко и няма да бъдат предмет на следващото изложение. Затова всички оттук нататък разглеждани пръстени ще се предполагат асоциативни без това да бъде специално уговаряно.

В дефиницията на понятието пръстен прави впечатление сериозната асиметрия между събирането и умножението - събирането е подчинено на силни изисквания (пръстенът да бъде адитивна Абелева група), каквито липсват за умножението. Двете операции могат да бъдат равнопоставени единствено в нулевия пръстен, защото иначе нулевият елемент според ТВЪРДЕНИЕ 6.1.1) не може да има инверсен относно умножението /0*0^-1 = 1 № 0 в ненулев пръстен е невъзможно/. Споменатата асиметрия не трябва да изглежда изненадваща, тъй като в дистрибутивните закони събирането и умножението не участвуват равноправно. Най-многото, което може да се постигне в опитите за равнопоставяне на двете двучленни операции се илюстрира от пръстените Q, R, C и Z₅ - във всеки от тях, както се вижда, ненулевите елементи образуват мултипликативна Абелева група (вижте пример 5.2). Така се стига до въвеждане на следващата важна алгебрична система.

ДЕФИНИЦИЯ 6.4. Поле: ненулев пръстен, чиито ненулеви елементи образуват мултипликативна Абелева група, се нарича поле, а групата от ненулевите елементи - мултипликативна група на полето. Инверсният на всеки ненулев елемент относно умножението се нарича реципрочен елемент /за разлика от противоположния, който е инверсен относно събирането/.

Според тази дефиниция събирането и умножението в едно поле са "почти" равнопоставени - единствено нулевият елемент на полето е в по-особено положение поради факта, че не притежава реципрочен. Освен това всяко поле съдържа най-малко 2 различни елемента: 0 и 1 - неутралните елементи за двете операции - събирането и умножението, които са комутативни и асоциативни. За реципрочния на всеки елемент a № 0 ще се употребяват обичайните означения a^-1 или 1/a, а произведението xy^-1 се нарича частно на елементите x и y (означавано още x/y). Намирането на частното е известно като операция деление.

Забележка: ако в ДЕФИНИЦИЯ 6.4 се изостави изискването мултипликативната група да бъде Абелева, получената алгебрична система е известна като пръстен с деление или тяло. Тогава понятието поле може да се дефинира като комутативно тяло. В следващото изложение тела няма да се разглеждат.

Примерите с полетата Q, R, C и Z₅ показват, че съществуват полета както с безбройно много, така и с краен брой елементи - последните са известни като полета на Галоа и се означават обикновено със символа GF(q) /от Galois Field/, където q е броят на елементите на полето /този брой, както ще бъде установено по-нататък, може да бъде само степен на просто число/. Още примери за полета се дават от следните множества:

6.9. { a + b; a, b О Q }

6.10. { a + bi; a, b О Q; i = - имагинерната единица }

6.11. Z_p = { [0], [1], [2], . . , [p-1] } е крайно поле при p - просто число, тъй като умножението на класове от остатъци е комутативно и асоциативно и всеки ненулев клас има реципрочен. Наистина ако [a] № [0], това означава, че НОД(a, p) = 1 при p - просто, и тогава сравнението ax є 1 (mod p) има единствен клас [x₀] от решения. В терминологията на класовете от остатъци това сравнение означава, че [a].[x₀] = [1], откъдето [a]^-1 = [x₀]. Така "най-малкото" възможно поле GF(2) е полето Z₂ с "двоичните" елементи 0 и 1 /класовете от остатъци [0] и [1] без изписани скоби/, което илюстрира аритметиката по модул 2:

0 + 0 = 0; 0 + 1 = 1 + 0 = 1; 1 + 1 = 0; 0 * 0 = 0, 0 * 1 = 1 * 0 = 0; 1 * 1 = 1;

Противоположните и реципрочните елементи са както следва:

-0 = 0; -1 = 1; 1^-1= 1.

Разглеждайки едно крайно поле, например Z₅ = { [0], [1], [2], [3], [4] } /вижте дадената в пример 6.8 негова таблица за събиране/, лесно се установява, че

[1] + [1] = [2],
[1] + [1] + [1] = [3],
[1] + [1] + [1] + [1] = [4],
[1] + [1] + [1] + [1] + [1] = [0],

тоест сумата от 5 единични елемента на полето /или 5-кратният на единичния елемент/ съвпада с нулевия елемент на Z₅. Последното равенство няма аналог в познатите числови полета и е основание за въвеждане на

ДЕФИНИЦИЯ 6.5. Характеристика на поле: нека K е произволно поле. Ако съществува естествено число n със свойството, че сумата от n на брой единични елемента на полето K е равна на нулевия елемент, най-малкото естествено число с това свойство се нарича характеристика на полето K /означение Char(K)/. Ако такова число не съществува, K се нарича поле с характеристика нула.

Иначе казано, характеристиката на едно поле е равна на адитивния ред на единичния му елемент /в адитивната група на полето/ по смисъла на ДЕФИНИЦИЯ 5.4, когато този ред е краен. Тогава за горния пример Char(Z₅) = 5, аналогично лесно се съобразява, че Char(Z_p) = p при p - просто число. Полета с характеристика 0 са споменатите числови полета Q, R, C, { a + b; a, b О Q}, {a + bi; a, b О Q} и т.н. - във всяко от тях никое естествено кратно на единицата не е равно на 0.

Забележка: понятието характеристика може да се въведе не само за поле, но също така и за пръстен, обаче това няма да бъде използувано в следващото изложение.

ТВЪРДЕНИЕ 6.2. Свойства на полетата:
1) в никое поле няма делители на нулата;
2) характеристиката на всяко поле е 0 или просто число;
3) за поле с характеристика p p-кратният на всеки елемент е равен на 0;
4) в поле на Галоа GF(n) за всеки негов елемент е изпълнено: xⁿ = x.

c Нека K е произволно поле с единичен елемент e и a, b О K;

1) от ab = 0 и a № 0 следва, че a^-1 съществува; тогава

a^-1(ab) = (a^-1a)b = e.b = b = 0;

2) нека Char(K) = k № 0, и k = mn, където k, m, n О N, 1 < m < k, 1 < n < k. Тогава дистрибутивният закон позволява ke = mn.e да се представи като (me)(ne), където според ДЕФИНИЦИЯ 5.3 ke е съкратено означение за сумата e + e + ... + e от k единици на полето, аналогична забележка важи за me и ne и, разбира се, ke, me, ne О K. Тогава от ke = mn.e = (me) (ne) = 0 и от 1) следва me = 0 или ne = 0, което противоречи на факта, че k е най-малкото естествено число, за което ke = 0;

3) нека Char(K) = p № 0 /иначе за p = 0 също и pa = 0/; според 2) p е просто число, тогава pe = 0 и за " a О K важи pa = p(ea) = (pe)a = 0a = 0;

4) нека GF(n) = { 0, x₁, x₂, . . , x_n-1 }. За нулевия елемент на полето xⁿ = x е очевидно изпълнено, затова нека x № 0. Произведенията xx₁, xx₂, . . , xx_n-1 са всичките различни, иначе от xx_i = xx_j след съкращаване би следвало противоречието x_i= x_j, тоест тези произведения изчерпват отново същите ненулеви елементи x₁, x₂, . . , x_n-1 /евентуално в друг ред/. Тогава

(xx₁) (xx₂)...(xx_n-1) = x₁x₂... x_n-1 , или xⁿ-1(x₁x₂... x_n-1) = x₁x₂... x_n-1,

тоест xⁿ-1 = e и след умножение с x се получава желаното. g

От доказаното в 1) следва, че всяко поле е цялостен пръстен. Друго следствие е, че пръстенът Z_n не е поле при n - съставно число, тъй като тогава има делители на нулата /ако n = pq, то [p].[q] = [0] - вижте и упражнение 6.3 по-долу/. Според 3) всички ненулеви елементи са от един и същи адитивен ред, равен на характеристиката на полето, когато тя е просто число. От 4) при n - просто число следва Малката теорема на Ферма /упражнение 2.2/.

Познатото от теорията на групите понятие подгрупа има свои аналози: подпръстен и подполе, а ролята на инвариантна подгрупа играе понятието идеал.

ДЕФИНИЦИЯ 6.6. Подпръстени и идеали; подполета и разширения: нека R е пръстен (поле) и R' Н R. Непразното подмножеството R' на R се нарича подпръстен (подполе) на R, ако R' е пръстен (поле) относно същите алгебрични операции, дефинирани в R.

Ако R' е подпръстен (подполе) на R, то R се нарича разширение на R'.

Подполето F' на полето F се нарича собствено, ако F' № F. Поле без собствени подполета се нарича просто поле.

Подпръстенът J на пръстена R се нарича ляв (десен) идеал, ако за всеки два елемента a О R и j О J произведението aj О J (съответно ja О J). Ляв идеал, който е едновременно и десен, се нарича двустранен.

Всеки пръстен R притежава подпръстени и идеали - такива са например тривиалните подпръстени {0} и R /същите са и двустранни идеали/.

По-съдържателни примери дават познатите числови пръстени Z М Q М R М C: в тази верига от включвания всеки е подпръстен на следващия и разширение на предишния /тъй като Q, R и C са също и полета, следва, че Q и R са подполета на C/. Полетaта { a + b; a, b О Q } и { a + bi; a, b О Q } са разширения на Q - елементите на последното се получават при b = 0.

Множеството от четните числа /или от всички целочислени кратни на произволно m О N/ е (двустранен) идеал в Z, по-общо, ако R е комутативен пръстен с единица, a О R е фиксиран негов елемент, множеството { ax; x О R } е идеал в R.

Очевидно всички идеали в комутативен пръстен са двустранни.

Примери за ляв идеал, който не е десен, респективно десен идеал, който не е ляв, са множествата от квадратните матрици от вида:

тоест с ненулеви елементи само в първия стълб, респективно ред в некомутативния пръстен от квадратните матрици от втори ред.

ДЕФИНИЦИЯ 6.7. Главен идеал, пръстен на главни идеали: нека R е комутативен пръстен с единица и J е идеал в R. Ако съществува елемент j О J, такъв, че J = { jx; x О R }, J се нарича главен идеал, породен от елемента j /означения J = ( j) или J = jR/.

Ако всички идеали в R са главни, R се нарича пръстен на главни идеали.

Казано другояче, един главен идеал се състои от всичките произведения на пораждащия елемент с елементите на пръстена. Във всеки комутативен пръстен с единица /предимно такива пръстени ще се разглеждат по-нататък/ нулевият идеал и самият пръстен са очевидно главни /породени от нулевия, респективно единичния елемент/.

Стандартен пример за пръстен на главни идеали е пръстенът Z от целите числа. Действително за идеал J № {0} в Z нека j е най-малкото положително число в J /такова има, тъй като J е подпръстен и от x О J следва -x О J/. Числото j поражда J, наистина за всяко k О J чрез деление на j с остатък се получава k = jq + r / 0 Ј r < j / и тогава от jq О J следва r = k - jq О J. Ако r > 0, това противоречи на избора на j като най-малък положителен елемент на J, следователно k е кратно на j и тогава J = ( j) = jZ.

Тъй като всеки двустранен идеал в един пръстен е по дефиниция подпръстен, а следователно и инвариантна подгрупа на адитивната група на пръстена (тъй като последната е Абелева!), всички резултати от теорията на групите относно съседните класове, разлагането по тях и възможността да се дефинира двучленна операция (в случая събиране) в множеството от съседните класове запазват своята валидност. Ако J е двустранен идеал в пръстена R и a, b О R, то съседните класове по идеала J, породени от a и b имат вида:

a + J = { a + j; j О J }, b + J = { b + j; j О J }

Сумата на съседните класове според глава 5 се дефинира като:

(a + J) + (b + J) ::= (a + b) + J,

дефинирайки сега и произведение на съседни класове по следния начин:

(a + J) * (b + J) ::= (ab) + J

/коректността на въведеното умножение се обуславя именно от факта, че J е двустранен идеал:

(a + j₁) * (b + j₂) = ab + aj₂ + j₁b + j₁j₂ = ab + (aj₂ + j₁b + j₁j₂) = ab + j

за някакви j₁,j₂, j О J поради aj₂, j₁b, j₁j₂ О J/, множеството от съседните класове на R по J се превръща в пръстен.

ДЕФИНИЦИЯ 6.8. Фактор-пръстен: ако R е пръстен и J - двустранен идеал в R, множеството от съседните класове на R по J с току-що описаните операции събиране и умножение се нарича фактор-пръстен на пръстена R по (относно) идеала J и се означава R/J.

Например за всяко m О Z, m > 0 кратните на m: { 0, ±m, ±2m, ±3m, ...} = [0] образуват идеал mZ и както лесно се вижда, съседните класове на Z по този идеал са всъщност всички класове от остатъци по модул m. Тогава фактор-пръстенът Z/[0] = Z/mZ = { [0], [1], [2], . . , [m-1] } = Z_m /който е поле при просто число m/.

За пръстени и полета ДЕФИНИЦИЯ 4.5 за морфизми приема следния вид:

ДЕФИНИЦИЯ 6.9. Хомоморфизъм и изоморфизъм:
нека j : R ® R' (R, R' - пръстени/полета) е съответствие на R в R' такова, че

j (-a) = -j (a), j (a + b) = j (a) + j (b) и j (ab) = j (a) j (b) за " a, b О R
/ако R и R' са полета още j (a^-1) = j (a)^-1 за " a № 0/.

Съответствието j се нарича хомоморфизъм на пръстени/полета.

Еднозначно обратим хомоморфизъм се нарича изоморфизъм (или автоморфизъм при R = R').

Следователно хомоморфизмът запазва резултатите от двете двучленни операции и индуцира хомоморфизъм на адитивната група на R в адитивната група на R' (ако R и R' са полета се индуцира и хомоморфизъм между мултипликативните им групи). Както в теорията на групите, така и при хомоморфизъм на пръстени или полета също се дефинира ядро на хомоморфизма /множество от всички елементи, изобразяващи се в нулевия/, установява се, че ядрото на всеки хомоморфизъм е двустранен идеал и е валидна теорема за хомоморфизмите, аналогична на ТВЪРДЕНИЕ 5.12 - хомоморфният образ на всеки пръстен е изоморфен с неговия фактор-пръстен по ядрото на хомоморфизма.

Следващото твърдение допълва ТВЪРДЕНИЕ.6.2 с още две важни свойства на полетата, в които става дума за въведените понятия идеал и подполе.

ТВЪРДЕНИЕ 6.3. Всяко поле съдържа само два идеала - тривиалните; всяко поле съдържа подполе, изоморфно или на Q, ако характеристиката му е 0, или на Z_p, ако характеристиката му е просто число p.

c Нека K е поле с единичен елемент e и J № { 0 } - идеал в K. Нека j О J, j № 0, тогава за "a О K произведението aj О J, следователно

(a j ) j^-1= a ( j j^-1) = ae = a О J,

тоест K Н J, но от друга страна J Н K, откъдето J = K.

За доказателството на второто свойство трябва да се забележи, че кратните 0, ±e, ±2e, ±3e, ... на единичния елемент /вижте забележката в ТВЪРДЕНИЕ 6.2.2) относно използуваните означения/ са всичките различни при Char(K) = 0, в противен случай /при Char(K) = p/ различни са само 0, e, 2e, 3e, . . , (p-1)e, а всяко друго кратно съвпада с някое от тях.

Нека Char(K) = 0. Ако се допусне, че me = ne за m, n О Z, m № n, тогава би следвало me - ne = (m - n)e = 0, което е невъзможно. Следователно при n № 0 също ne № 0 и съществува (ne)^-1 О K. По силата на затвореността на K относно събирането и умножението, K ще съдържа и всички елементи от вида (me).(ne)^-1 = (me)/(ne), които, както лесно се проверява, образуват подполе, изоморфно на Q при съответствието

(me).(ne)^-1 = (me)/(ne) « m/n О Q.

Нека Char(K) = p № 0. Тогава елементите 0, e, 2e, 3e, . . , (p-1)e образуват подполе, изоморфно на Z_p при съответствието

0 « [0], e « [1], 2e « [2], . . , (p - 1)e « [p - 1]. g

Доказаното означава, че познатото поле Q на рационалните числа е в определен смисъл "най-малкото" от всички полета с характеристика 0, а полетата от класове от остатъци по модул просто число - "най-малките" полета с положителна характеристика. От ТВЪРДЕНИЕ 6.3 непосредствено следва, че те са прости полета /това се предлага за доказателство в упражнение 6.6 по-долу/, затова всяко GF(p) @ Z_p при p - просто число, поради което за Z_p ще се употребява общото означение GF(p). От доказаното за кратните на единичния елемент лесно следва, че всички крайни полета имат проста характеристика, докато съществуват безкрайни полета както с проста характеристика, така и с характеристика 0.

Въпреки че полето Q не е разширение на друго поле, Q е разширение на пръстена Z и съдържа отношенията (частните) на целите числа, тоест Q е "най-малкото" множество, в което е възможно деление на цели числа /с познатото единствено изключение - делителят да не е 0/. Оказва се, че подобно разширение е възможно да се построи за всеки цялостен пръстен /Z е стандартен пример за цялостен пръстен/.

ТВЪРДЕНИЕ 6.4. За всеки цялостен пръстен R съществува поле, съдържащо R и решенията на всички уравнения от вида a = bx, с дадени a, b О R, b № 0.

c Нека a, b О R, b № 0. Наредената двойка (a, b) ще бъде означавана занапред с израза a/b и ще се нарича (формална) дроб с числител a и знаменател b. Символът "/ " (дробна черта, записвана наклонено или хоризонтално) ще служи като формален разделител между числителя и знаменателя, без да е асоцииран с някаква двучленна операция, тоест a/b е просто друг начин за означаване на наредената двойка (a, b). Нека F е множеството от всички формални дроби, тоест

F ::= { a/b; a, b О R, b № 0 } = { (a, b); a, b О R, b № 0 }.

Дробите a/b и a'/b' се считат равни (означение a/b = a'/b') ако в пръстена R е налице равенството ab' = a'b. Тривиално се проверява, че така дефинираното равенство на дроби е релация на еквивалентност и следователно осъществява разлагане на F на класове, всеки от които се състои от дробите, които са равни помежду си. Нека K е множеството от тези класове, тоест фактор-множеството на множеството от всички формални дроби относно въведената релация равенство. Сума на елементи от K с представители дробите a/b и c/d се дефинира по следния начин:

а произведение:

Лесно се вижда, че сумата и произведението са коректно дефинирани, тъй като не зависят от избраните представители от съответните класове и bd № 0 поради b № 0 и d № 0 /в цялостен пръстен няма делители на нулата/. Относно тези двучленни операции K е поле с нулев елемент 0/a и единичен елемент a/a (даже ако R е пръстен без единица). Противоположна на дробта a/b е (-a)/b, реципрочна е b/a (при ненулева дроб a/b). Съпоставяйки на " a О R дробта af/ f се вижда, че R е изоморфен с множеството от класовете { af/ f; a, f О R, f № 0 - фиксиран } Н K, тоест построеното поле K е разширение на R. Решение на уравнението a = bx при a, b О R, b № 0, както директно се проверява, е дробта a/b. g

ДЕФИНИЦИЯ 6.10. Поле от отношения: построеното в процеса на доказателството на ТВЪРДЕНИЕ 6.4 разширение K на цялостния пръстен R се нарича поле от отношения (поле от частни) за пръстена R.

Основания за въведената терминология и използуваните означения е фактът, че решението на уравнение от вида a = bx е известно като отношение (частно) на елементите a и b и се записва като x = ab^-1 или x = a/b.

Упражнения към глава 6:

6.1[!]. Да се установи кои от следващите множества са пръстени и полета /по-нататък a, b, c, d О Q/:

6.2[*]. Пръстен R се нарича Булев, ако x² = x за "x О R /тоест ако умножението е идемпотентна операция/. Да се докаже, че всеки Булев пръстен е комутативен и за "x О R е изпълнено x + x = 0.

6.3. Обратимите (относно умножението) елементи от Z_n са класовете [m] със свойството НОД(m, n) = 1.

6.4. За a, b О N нека m = НОК(a, b). За идеалите aZ и bZ да се докаже, че aZ З bZ = mZ.

6.5[*]. Всеки цялостен пръстен с краен брой елементи е поле.

6.6. Q и Z_p при p - просто число, са прости полета.

6.7[!]. Да се решат над GF(5) уравненията/системите:

2x² + 3x + 1 = 0; да се провери валидността на формулите на Виет за корените му;
x² + 1 = 0; полиномът x² + 1 да се разложи на линейни множители;

Oбратно към СЪДЪРЖАНИЕ

7. АЛГЕБРА НА ПОЛИНОМИТЕ НАД ДАДЕНО ПОЛЕ

В настоящата глава ще бъдат изложени основни резултати от алгебрата на полиномите над фиксирано основно поле K. Повечето резултати ще бъдат валидни за произволно поле; някои - за полета с характеристика 0; други - за конкретно поле, например за полето от комплексните числа. Редица твърдения допускат обобщение за полиноми над даден пръстен вместо поле.

ДЕФИНИЦИЯ 7.1. Полином на една променлива над дадено поле и свързани с него понятия: полином F(x) на една променлива над K се нарича сумата:

която съдържа краен брой събираеми (членове), където n = 0, 1, 2, ... ; a₀, a₁, a₂, . . , a_n О K и се наричат коефициенти: елементът x П K се нарича променлива (неизвестно) - това е формален служебен символ със свойството x⁰ ::= 1 /единицата на K/, който играе ролята на контейнер и може да бъде заместван с определени елементи. За краткост полиномът F(x) може да се означава и само с F, ако променливата се подразбира, също така членовете с нулеви коефициенти обикновено не се изписват, а член без явно изписан коефициент има по подразбиране коефициент 1. Полином, чиито всички коефициенти са равни на нулевия елемент на основното поле K, се нарича нулев полином - той ще бъде означаван занапред с 0, както и нулевият елемент на K, като смисълът на означението ще бъде ясен от контекста. Ненулев полином е полином с поне един ненулев коефициент. В ненулевия полином F(x) = a₀ + a₁x + a₂x² + ... + a_nxⁿ може да се счита, че a_n № 0, тогава коефициентът a₀ се нарича свободен (постоянен) член, а коефициентът a_n - старши (главен, водещ или доминиращ) коефициент. Полином със старши коефициент 1 се нарича нормиран полином. Показателят n на променливата x в члена със старшия коефициент се нарича степен на полинома и се означава с deg(F). Степента на всеки ненулев полином е неотрицателно цяло число, а за нулевия полином deg(0) ::= Ґ /смисълът на това приемане е, че степента на нулевия полином е по-ниска от степента на всеки ненулев полином/. Полином от нулева степен (който се свежда до единствен член - свободния) се нарича още константен полином (константа) и може да се отъждестви с елемента a₀ О K поради x⁰ = 1. Така всички константни полиноми над K се изчерпват с ненулевите елементи от K. Ако в полинома F(x) променливата x бъде заместена с произволен елемент a О K /или a О K', където K' е някакво разширение на K/ се получава еднозначно определен елемент

F(a) ::= a₀ + a₁a + a₂a² + a₃a³ + ... + a_naⁿ, F(a) О K /респективно F(a) О K'/,

който се нарича стойност на полинома F(x) за x = a.

Освен възприетата в горната дефиниция наредба на членовете на полинома по растящи степени се практикува и наредба по намаляващи степени, например:

F(x) = c₀x^m + c₁x^m-1 + c₂x^m-2 + ... + c_m-1 x + c_m

И двете наредби ще се използуват по-нататък в зависимост от съображения за удобство, а множеството от всички полиноми над основното поле K ще се означава с K[x].

Примери:

степен, като първите три са нормирани.

7.3. x - i, ix³ - (3 + 8i)x² - 4i О C[x].

7.4. Полиноми над крайни полета (нормирани):

x² + x + 1 О GF(2)[x] /елементът 1 О GF(2) интерпретира класа [1] по модул 2, тоест x² + x + 1 е кратко означение на [1] x² + [1] x + [1]/;
x^p - x, xⁿ - x О GF(p)[x] /n, p О N, n > 1, p - просто; ненулевите коефициенти 1 и -1 на тези полиноми интерпретират класовете [1] и [-1] = [p-1] по модул p поради -1 є p-1 (mod p).

В K[x] се дефинират релацията равенство и операциите събиране и умножение.

ДЕФИНИЦИЯ 7.2. Релации и операции в K[x]: нека

F(x) = a₀ + a₁x + a₂x² + a₃x³ + ... + a_mx^m О K[x],
G(x) = b₀ + b₁x + b₂x² + b₃x³ + ... + b_nxⁿ О K[x]

са полиноми над K /ако са от различни степени, например m < n, за сравняването и събирането полиномът от по-ниската степен може да се допълни с необходимия брой членове с нулеви коефициенти/.

Двата полинома се наричат равни /означение F = G/, ако

a₀ = b₀, a₁ = b₁, a₂ = b₂, . . , a_n = b_n.

Сума на полиномите F и G е полиномът:

Произведение на полиномите F и G е полиномът:

F(x)G(x) ::= a₀b₀ + (a₁b₀+ a₀b₁) x + (a₂b₀+ a₁b₁ + a₀b₂) x² + ...

... + (a_kb₀+ a_k-1 b₁ + ... + a₁b_k-1 + a₀b_k) x^k + ... + a_m b_nx^{m
+ n} =

Според дефиницията два ненулеви полинома са равни единствено ако са от една и съща степен и имат равни коефициенти пред еднаквите степени на променливата. Нулевият полином не е равен на никой ненулев полином. Събирането и умножението се извършват по добре познатите правила от елементарната алгебра. От тях следват полезните следствия за степените на сумата и произведението:

deg(F + G) Ј max(deg(F), deg(G)); deg(FG) = deg(F) + deg(G)

/с естествените уговорки за символа -Ґ: (-Ґ) + (-Ґ) ::= -Ґ, (-Ґ) + n ::= -Ґ за n О Z/.

ТВЪРДЕНИЕ 7.1. K[x] е цялостен пръстен с единица, който съдържа полето K.

c Съгласно ДЕФИНИЦИЯ 7.2 и затвореността на K относно събирането и умножението както F + G,така и FG О K[x], тъй като коефициентите им се получават само с тези две действия. Комутативният и асоциативният закони на събирането и умножението на полиноми следват от изпълнението на съответните закони в основното поле. Изпълнението на дистрибутивния закон в K[x] също се проверява непосредствено. По-нататък ако F(x) = a₀ + a₁x + a₂x² + ... + a_nxⁿ О K[x], нека -F(x) = -a₀ + (-a₁)x + (-a₂)x² + ... + (-a_n)xⁿ О K[x], тогава F + 0 = F; F + (-F) = 0, F.1 = F /0 - нулевият полином, 1 - константният полином, равен на единичния елемент на K/, което означава, че K[x] е комутативен и асоциативен пръстен с единица. Ако полиномите F № 0 и G № 0, то поради deg(FG) = deg(F) + deg(G) і 0 не може FG = 0, следователно в K[x] няма делители на нулата. Както беше отбелязано по-горе K[x] Й K защото всичките елементи на K изчерпват нулевия полином и константните полиноми от K[x], а очевидно #(K[x]) = Ґ дори при крайно поле K. g

Доказаният факт, че K[x] е цялостен пръстен означава, че K[x] в много отношения прилича на пръстена Z от целите числа и аналогията между аритметиката на целите числа и алгебрата на полиномите често ще личи от по-нататъшното изложение. Например подобно на Z и в K[x] се въвежда релацията делимост на полиноми.

ДЕФИНИЦИЯ 7.3. Делимост в K[x]: нека F(x), G(x) О K[x]; G(x) № 0. Полиномът F(x) се дели на G(x) (означение F | G) ако съществува полином H(x) О K[x], такъв, че F(x) = G(x)H(x).

Примери за делимост:

7.5. (x²- 1) | (x - 1) в R[x], тъй като x²- 1 = ( x - 1) ( x + 1).

7.6. (x²+ 1) | (x + i ) в C[x], тъй като x²+ 1 = ( x + i ) ( x - i ).

Следващото твърдение, чието елементарно доказателство се предоставя на читателя, дава някои очевидни свойства на въведената релация.

ТВЪРДЕНИЕ 7.2. Свойства на релацията делимост (по-надолу F(x), G(x), H(x), U(x), V(x) О K[x], c О K, c № 0, като всеки делител е ненулев полином):

F | F /рефлексивност/;
F | G и G | H Ю F | H /транзитивност/;
F | H и G | H Ю (FU + GV) | H;
F | G Ю FH | G;
F | c;
F | G Ю F | cG;
F | G и G | F Ю F = cG;
Всички делители на F от същата степен са от вида cF;
F | G и deg(F) < deg(G) Ю F = 0.

От свойствата личи, че при делимостта на полиноми константите /тоест полиномите от нулева степен/ са аналози на числата ±1 при делимостта на цели числа.

Също както при целите числа, така и при полиномите съществува деление с остатък:

ТВЪРДЕНИЕ 7.3. Теорема за деление с остатък: нека F(x), G(x) О K[x], G(x) № 0; тогава съществуват единствени полиноми Q(x) /частно/ и R(x) /остатък/, такива, че:

F(x) = G(x).Q(x) + R(x); deg(R) < deg(G).

c Съществуване: ако deg(F) < deg(G), то Q = 0 и R = F, иначе нека

F(x) = a₀x^m + a₁x^m-1 + ... + a_m-1 x + a_m и G(x) = b₀xⁿ + b₁xⁿ-1 + ... + b_n-1 x + b_n,

където a₀ № 0, b₀ № 0, deg(F) = m і n = deg(G). Разделяйки членовете с най-високите степени и съставяйки разликата:

(1) F(x) - (a₀/b₀) x^m-n.G(x) = F₁(x)

се вижда, че deg(F₁) = m' < m. Ако m' і n и a₀' е старшият коефициент на полинома F₁(x), постъпвайки по същия начин, за разликата

(2) F₁(x) - (a₀'/b₀) x^{m' -
n}.G(x) = F₂(x)

се вижда, че deg(F₂) = m" < m'. Ако все още m" і n, този процес продължава, като се получава редица от полиноми F, F₁, F₂, ..., чиито степени намаляват докато се получи полином R(x) от степен, по-ниска от n, с което се достига до вече разгледания в началото случай R = G.0 + R. Събирайки това равенство с (1), (2) и т.н. и означавайки сумата:

(a₀/b₀)x^{m -
n} + (a₀'/b₀)x^{m' - n} + ... = Q(x) се получава F = G.Q + R, deg(R) < n.

Единственост: ако освен F = G.Q + R има и друго представяне

F = G.Q₁ + R₁ като deg(R) < deg(G) и deg(R₁) < deg(G),

тогава G(Q - Q₁) = R₁ - R, тоест (R₁ - R) | G като deg(R₁ - R) < deg(G), но последното е възможно само при R = R₁ и Q = Q₁. g

От доказателството личи, че deg(Q) = deg(F) - deg(G) при deg(F) і deg(G).

Едно важно следствие от ТВЪРДЕНИЕ 7.3 е, че K[x], както и Z, е пръстен на главни идеали - аналогично на доказаното след ДЕФИНИЦИЯ 6.7 може да се установи /вижте упражнение 7.1/, че за всеки ненулев идеал J в K[x] съществува единствен пораждащ нормиран полином j(x), такъв, че

J = { j(x). f(x); f(x) О K[x]; f - произволен }.

Това обстоятелство дава възможност в K[x] също да се въведе релацията сравнимост (конгруентност или равноостатъчност) по модул за полиноми:

F(x) є G(x) (mod j (x)) Ы (F - G) | j , където F, G, j О K[x], j № 0.

Разбира се, сравнимите помежду си полиноми по модул j принадлежат на един и същи съседен клас по идеала, породен от j във фактор-пръстена K[x]/(j) и обратно. Аналогично на целите числа сравнимостта при полиномите е съдържателна когато модулът е неконстантен полином /всеки два полинома са сравними по константен модул/.

Примери за деление на полиноми:

7.7. При делението на x⁴+ x²+ 1 на x²+ 3x + 1 се получава:

x⁴+ x²+ 1 = (x²+ 3x + 1).(x² - 3x + 9) - 24x - 8, тоест x⁴+ x²+ 1 є - 24x - 8 (mod x²+ 3x + 1)

7.8. При делението на x³ - 7x+ 6 на x - 1 се получава:

x³- 7x + 6 = (x - 1).(x² + x - 6) + 0, тоест x³- 7x + 6 є 0 (mod x - 1)

В частния случай, когато deg(F) і 1 и делителят има вида x - a, където a О K /като пример 7.8/ се получава F(x) = (x - a).Q(x) + r, като коефициентите на частното Q(x) и остатъкът r О K се намират най-удобно с познатото правило /схема/ на Хорнер.

ТВЪРДЕНИЕ 7.4. Правило на Хорнер: нека

F(x) = a₀xⁿ + a₁xⁿ-1 + ... + a_n-1 x + a_n, където a₀ № 0, n = deg(F) і 1.

Коефициентите на частното Q(x) = b₀xⁿ-1 + b₁xⁿ-2 + ... + b_n-1 и остатъкът r при делението на полинома F на x - a могат да се намерят по схемата:

	a₀	a₁	a₂	...	a_n-1	a_n
a	b₀= a₀	b₁= a b₀+ a₁	b₂= a b₁+ a₂	...	b_n-1 = a b_n-2 + a_n-1	r = a b_n-1 + a_n

c Изразите за b₀, b₁, . . , b_n-1 и r се получават със сравняване на коефициентите в равенството:

a₀xⁿ + a₁xⁿ-1 + ... + a_n-1 x + a_n = (x - a).(b₀xⁿ-1 + b₁xⁿ-2 + ... + b_n-1) + r. g

От F(x) = (x - a).Q(x) + r при x = a следва полезният факт, че F(a) = r, тоест остатъкът от делението е равен на стойността на полинома за x = a. По тази причина правилото на Хорнер може да се използува ефективно за пресмятане на стойности на полиноми.

ДЕФИНИЦИЯ 7.4. Общ делител, най-голям общ делител, взаимно прости полиноми: нека F(x), G(x) О K[x]. Ненулевият полином H(x) О K[x] се нарича общ делител на F и G, ако F | H и G | H. Нормиран общ делител на F и G, който се дели на всеки друг техен общ делител, се нарича най-голям общ делител на F и G и се означава НОД(F, G).

Полиноми с най-голям общ делител, равен на 1, се наричат взаимно прости.

ТВЪРДЕНИЕ 7.5. Всеки два полинома, поне един от които е ненулев, имат единствен най-голям общ делител.

c Доказателството почти повтаря това на ТВЪРДЕНИЕ 1.3, като допълнителна подробност сега е само нормирането. Нека F(x), G(x) О K[x], G(x) № 0.

Единственост: ако H₁ = НОД(F, G) и H₂ = НОД(F, G), то поради H₁ | H₂ и H₂ | H₁ и съгласно ТВЪРДЕНИЕ 7.2 H₁ = H₂.

Съществуване: то може отново да се докаже конструктивно с алгоритъма на Евклид; предполагайки по-съдържателния случай, когато F не се дели на G /иначе очевидно НОД(F, G) = G/ след краен брой деления с остатък:

F(x) = G(x).Q₁(x) + R₁(x),	Q₁(x), R₁(x) О K[x],	0 Ј deg(R₁) < deg(G),
G(x) = R₁(x).Q₂(x) + R₂(x),	Q₂(x), R₂(x) О K[x],	0 Ј deg(R₂) < deg(R₁),
R₁(x) = R₂(x).Q₃(x) + R₃(x),	Q₃(x), R₃(x) О K[x],	0 Ј deg(R₃) < deg(R₂),
. . . . . . . . . . . . . . . . . . . . . .	. . . . . . . . . . . . . . . . . .	. . . . . . . . . . . . . . . . . . .
R_k-2(x) = R_k-1(x).Q_k + R_k(x),	Q_k(x), R_k(x) О K[x],	*0 Ј deg(R_k) < deg(R_k-1),*
R_k-1(x) = R_k(x).Q_k+1(x) + 0,	Q_k+1(x) О K[x]

веригата прекъсва, тъй като редицата от степените на последователните остатъци е строго намаляваща редица от неотрицателни цели числа, която не може да има безбройно много членове. За предпоследния остатък R_k(x) № 0 се установява, че е общ делител на F и G и че се дели на всеки друг техен общ делител. Тогава търсеният най-голям общ делител се получава нормирайки R_k(x). g

Примери:

7.9. НОД(x⁷ - 1, x⁵- 1):

x⁷ - 1 = (x⁵- 1) .x² + x² - 1;

x⁵- 1 = (x² -1).(x³+ x) + x - 1;

x² - 1 = (x - 1).(x + 1) + 0, следователно НОД(x⁷ - 1, x⁵- 1) = x - 1

7.10. НОД(x²+ 1, x²- 1):

x²+ 1 = (x²- 1).1 + 2 /възможно е остатъкът 2 да бъде нормиран и веднага/;

x²- 1 = 2.(1/2 x²- 1/2) + 0, следователно, след нормиране НОД(x²+ 1, x²- 1) = 1

Аналог на ТВЪРДЕНИЕ 1.4 при полиномите е

ТВЪРДЕНИЕ 7.6. Свойства на най-големия общ делител и взаимно простите полиноми:

НОД(F, G) = U.F + V.G за някои U(x), V(x) О K[x] /тъждество на Безу/;
F и G са взаимно прости Ы U.F + V.G = 1 за някои U(x), V(x) О K[x];
FG | H и НОД(F, H) = 1 Ю G | H.

ДЕФИНИЦИЯ 7.5. Разложими/неразложими неконстантни полиноми над дадено поле K: полиномът F(x) О K[x], deg(F) > 0, се нарича разложим над полето K, ако съществуват неконстантни полиноми F₁(x), F₂(x) О K[x], такива, че F(x) = F₁(x).F₂(x). В противен случай F се нарича неразложим над K.

Иначе казано, един полином от поне първа степен е неразложим, ако при всяко негово разлагане в произведение на два полинома над същото поле единият е обезателно от нулева степен (вижте предпоследното свойство от ТВЪРДЕНИЕ 7.2), тоест, ако допуска само тривиални разлагания на множители. Разложимите полиноми допускат нетривиални разлагания (тоест на множители от по-ниски степени) над основното поле.

Понятията разложимост/неразложимост се въвеждат само за неконстантни полиноми и са свързани съществено с определено поле, както личи от следващите примери.

Примери за разложими/неразложими полиноми:

7.11. x²- 1 = (x - 1) (x + 1) е разложим над Q.

7.12. x²- 2 = (x - )(x + ) е неразложим над Q, но е разложим над R.

7.13. x²+ 1 = (x - i) (x + i) е неразложим над Q и R, но е разложим над C.

Неразложимите/разложимите (неконстантни!) полиноми от K[x] са аналози на простите/съставните цели числа, а полиномите от нулева степен (константните полиноми) - на числата ±1.

ТВЪРДЕНИЕ 7.7.Свойства на неразложимите полиноми /F(x), G(x), P(x) О K[x]/:
1) всеки полином от първа степен е неразложим;
2) F и cF /c О K, c № 0/ са едновременно разложими/неразложими;
3) F - произволен, P - неразложим Ю или F | P, или НОД(F, P) = 1;
4) P - неразложим и FG | P Ю или F | P, или G | P;
5) всеки неконстантен полином се дели на поне един неразложим полином;
6) P - неразложим Ы фактор-пръстенът K[x]/(P) е поле.

c 1) Ако полином от първа степен се разлага в произведение на два полинома от по-ниски степени, то тези полиноми би трябвало да бъдат от нулева степен. Но произведение на такива полиноми е полином от нулева степен - противоречие.

Свойства 2) - 5) са очевидни и са аналогични на.някои от свойствата на простите числа, споменати в ТВЪРДЕНИЕ 1.8.

Свойство 6) е аналогично на твърдението, че Z_p= Z/pZ е поле точно тогава, когато p е просто число (пример 6.11). За доказателство трябва да се установи съществуването на реципрочен на всеки ненулев съседен клас по главния идеал (P) = { f(x).P(x); f(x) О K[x] } при P - неразложим, и обратно. Нека F(x) О K[x] поражда съседния клас F + (P) № 0 + (P), което означава, че F не се дели на P, но тогава според горното свойство 3) НОД(F, P) = 1 = F.U + P.V за някакви полиноми U, V О K[x]. От това представяне на най-големия общ делител следва

F.U + P.V є F.U є 1(mod P),

което в терминологията на съседните класове означава, че

(F + (P)).(U + (P)) = FU + (P) = 1 + (P), тоест (F + (P))^-1 = U + (P).

От друга страна от обратимостта на всеки ненулев съседен клас F + (P) следва, че F и P са взаимно прости щом F не се дели на P, което е възможно само ако P е неразложим. g

Пример 7.14. Конструкция на поле на Галоа с 4 елемента:

Полиномът P(x) = x² + x + 1 О GF(2)[x] е, както лесно се установява, неразложим над GF(2). Тъй като "F(x) О GF(2)[x] при деление на P(x) може да даде остатък най-много от първа степен /от вида ax + b; a, b О GF(2)/, всички възможни остатъци са следователно следните 4 полинома: 0, 1, x, x + 1, които изчерпват съседните класове по идеала (P). Според доказаното те образуват поле - GF(4), със следните таблици за събиране и умножение /по mod x² + x + 1; вижте коментара след ТВЪРДЕНИЕ 7.3, сравнете също с примери 4.11 и 6.8./:

+	0	1	x	x+1	противоположни:	*	1	x	x+1	реципрочни:
0	0	1	x	x+1	-0 = 0	0	0	0	0
1	1	0	x+1	x	-1 = 1	1	1	x	x+1	1^-1 = 1
x	x	x+1	0	1	-x = x	x	x	x+1	1	(x)^-1 = x+1
x+1	x+1	x	1	0	-(x+1) = x+1	x+1	x+1	1	x	(x+1)^-1 = x

Построеното поле GF(4) не е изоморфно на пръстена Z₄, разгледан в пример 6.8 /последният не е поле, тъй като 4 не е просто число/. От главния диагонал на таблицата за събиране, изцяло изпълнен с нулеви елементи, следва, че Char(GF(4)) = 2.

Аналог на основната теорема на аритметиката (ТВЪРДЕНИЕ 1.9) в K[x] е

ТВЪРДЕНИЕ 7.8. Разлагане на неразложими полиноми: всеки полином F(x)О K[x], deg(F) і 1, се разлага на произведение от старшия си коефициент и нормирани неразложими над K полиноми и това представяне е единствено с точност до реда на множителите.

c Принципна разлика между доказателствата на ТВЪРДЕНИЕ 1.9 и настоящото няма.

Съществуване: ако F(x) е неразложим над K, той очевидно се представя по описания начин, затова нека F(x) = F₁(x).F₂(x), където F₁(x), F₂(x)О K[x], deg(F₁) < deg(F), deg(F₂) < deg(F). Ако F₁(x) и F₂(x) са неразложими, търсеното представяне се получава с нормирането им, в противен случай този процес на отделяне на множители ще продължи краен брой пъти, тъй като степените на множителите строго намаляват - най-много до получаване на множители от първа степен, неразложими съгласно ТВЪРДЕНИЕ 7.7.1).

Единственост: ако се допусне съществуването на две разлагания:

F(x) = aF₁(x).F₂(x)...F_m(x) = bG₁(x).G₂(x)...G_n(x),

със сравнение на старшите коефициенти се получава a = b. По-нататък произведението от неразложимите полиноми F₁F₂...F_m | G₁, следователно някой от F₁, F₂, . . , F_m се дели на G₁, например нека F₁| G₁. Последното е възможно само ако те се различават с постоянен множител, но тъй като са нормирани остава F₁ = G₁. Прилагайки тези разсъждения отново към равенството F₂F₃...F_m = G₂G₃...G_n, в крайна сметка се получава съвпадение на всеки множител в едното представяне с множител от другото, което доказва единствеността. g

Обединявайки евентуални равни множители в горното представяне, се получава каноничното разлагане:

в което неразложимите нормирани множители j₁, j₂, j₃, . . , j_s са два по два различни.

Подобно на Z и в K[x] може да се дефинира понятието най-малко общо кратно на два полинома и да се изведат съотношения, аналогични на споменатите в ТВЪРДЕНИЯ 1.6 и 1.10, както и обобщенията на понятията най-голям общ делител, най-малко общо кратно и взаимно прости полиноми за повече от два полинома.

ДЕФИНИЦИЯ 7.6. Производна на полином и производни от по-висок ред:
производен полином (производна) на полинома

F(x) = a₀ + a₁x + a₂x² + ... + a_n-1 xⁿ-1 + a_nxⁿО K[x]

се нарича следният полином:

F'(x) ::= a₁ + 2a₂x + 3a₃x² + ... + (n-1)a_n-1 xⁿ-2 + na_nxⁿ-1

/както обикновено 2a₂::= a₂ + a₂; 3a₃ ::= a₃ + a₃ + a₃ и т.н./.

Производната на F'(x) се нарича втора производна на F(x) /означение F"(x)/ и аналогично се въвеждат производни от по-висок ред.

В алгебрата понятието производна се дефинира формално, тъй като познатата от математическия анализ дефиниция с граничен преход е неприложима за крайни полета /но например за C или R тези дефиниции са еквивалентни/. Така в K[x] освен двучленните операции събиране и умножение /ДЕФИНИЦИЯ 7.2/ се въвежда и едночленната операция диференциране /намиране на производна/. От дефиницията е ясно, че всеки полином има производни от всякакъв ред, като непосредствено се проверява верността на

ТВЪРДЕНИЕ 7.9. (F + G)' = F' + G'; (F.G)' = F'.G + G'.F; ако deg(F) = n, то F^{(n +
1)} = F^{(n + 2)} = ... = 0.

Забележка: не винаги deg(F' ) = deg(F) - 1; последното е вярно за полиноми над поле с характеристика 0, но например над GF(2):

(x⁴ + 1)' = 4x³ = 0x³ = 0 поради 4 є 0 (mod 2).

Следващата формула (с многобройни приложения и в математическия анализ) позволява полином с комплексни коефициенти да се разложи по степените на разликата x - a, тоест да се извърши линейна смяна на променливата.

ТВЪРДЕНИЕ 7.10. Формула на Тейлър за полиноми с комплексни коефициенти: нека F(x) О C[x], deg(F) = n и a О C, тогава

Пример 7.15. Разлагане на F(x) = x³- 7x + 6 О R[x] по степените на x + 1:

F(x) = x³- 7x + 6,	F(-1) = 12;
F'(x) = 3x² - 7,	F'(-1) = -4;
F"(x) = 6x,	F"(-1) = -6;
F'"(x) = 6,	F'"(-1) = 6.

Тогава x³- 7x + 6 = 12 - 4(x + 1) - 3(x + 1)² + (x + 1)³, но същият резултат може да се получи по-лесно и по-удобно с четирикратно деление на F(x) на x + 1 по правилото на Хорнер:

	1	0	-7	6
-1	1	-1	-6	12
-1	1	-2	-4
-1	1	-3
-1	1

Формулата на Тейлър се обобщава за поле с характеристика 0, ако знаменателите на участвуващите дроби се заменят съответно с 1!-, 2!-, . . , n!-кратните на единицата на полето /всички тези кратни са ненулеви елементи щом полето е с характеристика 0/.

ДЕФИНИЦИЯ 7.7. Корен (нула) на полином: нека F(x) О K[x]; елемент a О К със свойството F(a) = 0 се нарича корен (нула) на полинома F(x).

Както е известно на читателя, равенство от вида F(x) = 0, /символът 0 в дясната страна в случая е означение за нулевия елемент на полето, а не за нулевия полином!/, се нарича още алгебрично уравнение (с 1 неизвестно), а за всеки корен (нула) на F се говори, че удовлетворява уравнението. Обикновено терминът корен се използува във връзка с уравненията, а нула - във връзка с полиномите, но често двата термина се използуват взаимозаменяемо - по-нататък ще се използува първият от тях.

Следващото просто твърдение дава връзка между наличието на корени и делимостта:

ТВЪРДЕНИЕ 7.11. Теорема на Безу: нека F(x) О K[x]; елементът a О К е корен на полинома F(x) точно тогава, когато F(x) | (x - a).

c Действително от F(x) = (x - a).Q(x) + r следва F(a) = 0 едновременно с r = 0. g

Въпросът за връзката между наличието на корени и разложимостта/неразложимостта се решава по различен начин за полиномите от първа и за полиномите от по-високи степени.

ТВЪРДЕНИЕ 7.12. Всеки полином от първа степен има единствен корен в основното поле, над което е неразложим; ако F(x) е неразложим полином над K и deg(F) > 1, тогава F няма корени в K.

c Нека F(x) = a₀ + a₁x; a₁ № 0; F е неразложим според ТВЪРДЕНИЕ 7.7. Директно се проверява, че елементът a = -a₀a₁^-1 = -a₀/a₁ е корен на F. Ако освен a има и друг корен a' № a, то от a₀ + a₁a = 0 и a₀ + a₁a' = 0 с изваждане се получава a₁(a - a') = 0, откъдето a₁ = 0 - противоречие.
Ако за полином F(x) от по-висока от първа степен се допусне, че има корен a О K, то според теоремата на Безу F(x) = (x - a).Q(x), като deg(x - a) = 1, deg(Q) і 1, тоест F(x) би се оказал разложим над K - противоречие. g

От липсата на корени в основното поле неразложимостта следва само за полиноми от 2-ра и 3-та степен, но не задължително за полиноми от по-висока, например над R полиномите x⁴ + 1 и x⁶ + 1 нямат корени, но са разложими /вторият е разложим даже над Q/:

x⁴ + 1 = (x² - x + 1)(x² + x + 1); x⁶ + 1 = (x² + 1)(x⁴ - x² + 1).

Според теоремата на Безу щом a О К е корен на полинома F(x), то F(x) | (x - a), но понякога може F(x) да се дели и на по-високи степени на x - a. Това е основание за следващата

ДЕФИНИЦИЯ 7.8. Кратност на корен: неотрицателното цяло число k се нарича кратност на корена a на F(x), ако F(x) | (x - a)^k, но не се дели на (x - a)^k+ 1. Корени с кратност 1 се наричат още прости, а с по-висока - многократни (или накратко кратни).

С други думи кратността е най-високият показател k, за който разликата (x - a)^k дели F(x) и в такъв случай F(x) = (x - a)^k.G(x), където G(x) О K[x], G(a) № 0. Тогава елемент от основното поле, който въобще не е корен, може да се счита за 0-кратен корен. Следващото твърдение установява важна връзка между понятията производна и кратност за полета с характеристика 0:

ТВЪРДЕНИЕ 7.13. Ако Char(K) = 0, всеки k-кратен корен на F(x) е k-1-кратен корен на F' (x) /k О N/.

c Нека a О К е k-кратен корен на F(x), тогава F(x) = (x - a)^k.G(x), където G(a) № 0. Производната

F'(x) = k.(x - a)^k-1.G(x) + (x - a)^k.G'(x) = (x - a)^k-1.(k.G(x) + (x - a).G'(x))

се дели на (x - a)^k-1, и тъй като k.G(a) + (a - a).G'(x) = k.G(a) № 0 поради Char(K) = 0, F'(x) не се дели на (x - a)^k, което означава, че a е k-1-кратен корен на F'(x). g

Условието Char(K) = 0 може да се замени с по-слабото изискване кратността на корена да не се дели на характеристиката и доказателството остава в сила. Например простите корени на F(x) изобщо не са корени на F'(x) за произволно поле и така се получава полезното

ТВЪРДЕНИЕ 7.14. Необходимо и достатъчно условие полиномът F(x) да няма многократни корени е НОД(F, F' ) = 1, тоест той да бъде взаимно прост с производната си.

Въпросът за наличие на корени на полиномите (тоест за възможността за решаване на алгебрични уравнения) дълго време е бил от съществено значение в алгебрата. За полиномите от първа степен отговорът се дава от ТВЪРДЕНИЕ 7.12, но за полином от по-висока степен е възможно той да няма корени в основното поле. Може обаче да се докаже, че такъв полином винаги има корен в подходящо негово разширение. Например полиномът x²- 2 О Q[x], който очевидно няма рационални корени, има корени ± в споменатото в пример 6.9 разширение { a + b; a, b О Q }; полиномът x² + 1 О Q[x] има корени ± i в C.

ТВЪРДЕНИЕ 7.15. Теорема за съществуване на корен в подходящо разширение на полето: нека F(x) О K[x], deg(F) > 1 и F(x) няма корени в K. Тогава съществува разширение K' Й K, такова, че F(x) има корен в K'.

c Може е да се предположи, че F(x) е неразложим, в противен случай верността на твърдението ще следва от верността му за някой от неразложимите множители на F(x). Съгласно ТВЪРДЕНИЕ 7.7.6) фактор-пръстенът K[x]/(F) по главния идеал (F), породен от F, е поле и се състои от съседните класове от вида:

R(x) + (F) = {R(x) + Q(x).F(x) є R(x) (mod F(x)), Q(x) О K[x] - произволен},

където R(x) изчерпва всички възможни остатъци от делението на произволни полиноми от K[x] на F(x) /те са всички полиноми от степени, по-ниски от deg(F) и могат да се изберат за представители на съседните класове по mod F - вижте конструкцията на полето на Галоа от горния пример 7.14/.Тъй като за "a О K остатъкът от делението може да бъде равен на a, следва, че a О K[x]/(F), което означава, че K[x]/(F) е разширение на K /а елементът a поражда съседния клас a + (F) от всички полиноми, сравними с a по mod F /.За всеки представител от класа x + (F) О K[x]/(F), породен от полинома x:

x + (F) = { x + Q(x).F(x) є x (mod F(x)), Q(x) О K[x] - произволен},

състоящ се от всички полиноми, сравними с x по mod F, е изпълнено:

F(x + Q(x).F(x)) є F(x) є 0 (mod F(x)),

което в терминологията на класовете от фактор-пръстена K[x]/(F) означава, че F(x + (F)) = 0 /равенство във фактор-пръстена е еквивалентно на сравнение по модул в изходния пръстен/, тоест съседният клас x + (F) от разширението K' = K[x]/(F) е корен на F. g

ТВЪРДЕНИЕ 7.16. Броят на корените на всеки ненулев полином /броейки всеки корен толкова пъти, колкото е неговата кратност/ е равен на степента му. Всеки полином от поне първа степен може еднозначно да се разложи на линейни множители над подходящо разширение на основното поле, съдържащо всичките му корени, по следния начин:

F(x) = a(x - x₁) (x - x₂)...(x - x_n),

където a е старшият коефициент на F, n = deg (F), x₁, x₂, . . , x_n - корените на F.

c За полиномите от нулева степен /ненулевите константи от K/ твърдението за броя на корените е вярно, за полиномите от първа степен е доказано в ТВЪРДЕНИЕ 7.12, затова нека deg(F) = n і 2. Нека x₁ е корен на F /x₁ О K или някое негово разширение според ТВЪРДЕНИЕ 7.15/. Тогава над съответното поле според теоремата на Безу е в сила разлагането:

F(x) = (x - x₁).F₁(x), където deg(F₁) = n-1 і 1.

Нека x₂ е корен на F₁ /от евентуално ново разширение, като не е изключено x₂ = x₁/ и отново F₁(x) = (x - x₂).F₂(x), откъдето

F(x) = (x - x₁) (x - x₂).F₂(x).

Отделянето на корени по този начин /съпроводено с евентуално разширяване на полето/ очевидно може да продължава докато се достигне до полином от нулева степен, тоест точно n пъти. Полученият полином от нулева степен е равен, както лесно следва със сравняване на коефициентите, на старшия коефициент a на F.

Обединявайки евентуалните кратни множители /съответни на кратните корени/ в разлагането:

F(x) = a(x - x₁) (x - x₂) ... (x - x_n),

резултатът често се представя във вида;

където k₁, k₂, . . , k_s са кратностите на различните корени x₁', x₂', . . , x_s', и разбира се, k₁+ k₂ + ... + k_s = deg(F). Тъй като това е каноничното разлагане на F(x) на неразложими полиноми, то е единствено според ТВЪРДЕНИЕ 7.8. g

Съществуват обаче и полета със свойството, че съдържат корените на всички полиноми от положителна степен с коефициенти от същото поле (така наречените алгебрически затворени полета, за полиномите над които, образно казано, "каквито са коефициентите, такива са и корените") - такова е например полето от комплексните числа.

ТВЪРДЕНИЕ 7.17. Основна теорема на алгебрата (известна още като теорема на Даламбер или теорема на Гаус): всеки неконстантен полином с комплексни коефициенти има комплексен корен.

Исторически необходимостта от разширяване на полето на реалните числа до полето на комплексните числа се е появила именно с цел да се направи възможно решаването на произволни уравнения с реални коефициенти. Според основната теорема на алгебрата за уравнения с комплексни /а в частност и с реални/ коефициенти по-нататъшно разширяване вече не е необходимо. Въпреки името си обаче тази теорема по същество не е алгебрична - всички известни нейни доказателства /между впрочем сравнително дълги/ използуват средства от математическия анализ - и има второстепенно значение за алгебрата.

Според ТВЪРДЕНИЕ 7.16 и ТВЪРДЕНИЕ 7.17 ненулев полином с реални или комплексни коефициенти има точно толкова комплексни корени, колкото е степента му, докато броят на реалните корени на ненулев полином с реални коефициенти не надминава степента му /и в двата случая със забележката относно кратностите!/.

Друго следствие от ТВЪРДЕНИЕ 7.16 е, че единствените неразложими полиноми над едно алгебрически затворено поле (например C) са полиномите от първа степен.

За нулевия полином е очевидно, че всеки елемент от основното поле е негов корен. Тогава от доказаното следва, че ако полином притежава повече корени, отколкото е степента му, този полином е обезателно нулев, в частност при безкрайно основно поле единственият полином с безбройно много корени е нулевият. Полезно следствие от това е, че ако два полинома от степен, по-малка или равна на n приемат равни стойности за повече от n стойности на променливата, те са равни, тъй като разликата им е нулев полином (вижте и упражнение 7.9).

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

ТВЪРДЕНИЕ 7.18. Интерполационна формула на Лагранж: нека n О N; x₀, x₁, x₂, . . , x_n О K (всичките различни); y₀, y₁, y₂, . . , y_n О K (произволни). Тогава съществува единствен полином F(x) О K[x], deg(F) Ј n със свойството F(x_i) = y_i за i = 0, 1, 2, . . , n, който се дава с формулата:

c От израза за F(x) /сума от полиноми от n-та степен/ следва, че deg(F) Ј n. Директно се поверява, че F(x_i) = y_i за i = 0, 1, 2, . . , n, накрая единствеността следва от горната забележка. g

От теоремата за разлагане на линейни множители със сравняване на коефициентите в двете страни на равенството се получават следните връзки между корените и коефициентите:

ТВЪРДЕНИЕ 7.19. Формули на Виет: нека

F(x) = a₀xⁿ + a₁xⁿ-1 + a₂xⁿ-2 + ... + a_n-1 x + a_nО K[x], a₀ № 0

и F има корени x₁, x₂, x₃, . . , x_nО K' К K /тоест K' - евентуално разширение на K/. Тогава над K':

x₁ + x₂ + x₃ + ... + x_n = -a₁/a₀;
x₁x₂ + x₁x₃ + x₂x₃ + ... + x_n-1 x_n = a₂/a₀;
x₁x₂x₃ + x₁x₂x₄ + ... + x_n-2 x_n-1 x_n = -a₃/a₀;
. . . . . . . . . . . . . . . . .
x₁x₂x₃ ... x_n = (-1)ⁿ.a_n/a₀;

Следват някои твърдения за корени на полиноми с реални и цели коефициенти.

ТВЪРДЕНИЕ 7.20. Ако F(x) О R[x], наред с всеки комплексен корен w = a + bi, комплексно-спрегнатото число = a - bi е също корен на F (със същата кратност като w ).

c Нека F(x) = a₀xⁿ + a₁xⁿ-1 + a₂xⁿ-2 + ... + a_n-1 x + a_n, /a₀, a₁, a₂, . . , a_n О R, следователно = a_k за k = 0, 1, . . ,n/. От F(w) = 0 следва , тоест

което означава, че е също корен с очевидно същата кратност.g

От доказаното следва, че комплексните корени (които не са реални) на полином с реални коефициенти са четен брой, в частност, всеки полином от нечетна степен има реален корен.

ТВЪРДЕНИЕ 7.21. Разлагане на F(x) О R[x] на реални множители от 1-ва и 2-ра степен: всеки полином от поне втора степен с реални коефициенти се разлага по следния начин:

F(x) = a₀(x - a₁)(x - a₂)...(x - a_r)(x²+ p₁x + q₁)(x²+ p₂x + q₂)...(x²+ p_sx + q_s),

където a₀ е старшият коефициент на F, a₁, a₂, . . , a_r са реалните му корени, а всеки квадратен множител с реални коефициенти съответствува на двойка комплексно-спрегнати корени.

c Ако w = a + bi е комплексен корен на F, който не е реален, обединявайки множителите x - w и x - от разлагането на линейни множители, валидно над C, в едно произведение:

(x - w)(x - ) = x²- (w + ) x + w = x² - 2ax + a² + b²

се получава квадратен полином с реални коефициенти. g

ТВЪРДЕНИЕ 7.22. Цели и рационални корени на полиноми с цели коефициенти: нека F(x) = a₀xⁿ + a₁xⁿ-1 + a₂xⁿ-2 + ... + a_n-1 x + a_n /a₀ № 0/ е полином с цели коефициенти, тогава:
1) ако цялото число c № 0 е корен на F(x), то a_n | c;
2) ако несъкратимата рационална дроб p/q (p, q О Z; p, q № 0) е корен на F(x), то a_n | p и a₀ | q.

c 1) нека a₀cⁿ + a₁cⁿ-1 + a₂cⁿ-2 + ... + a_n-1 c + a_n = 0 за c О Z, тогава a_n = -c(a₀cⁿ-1 + a₁cⁿ-2 + a₂cⁿ-3 + ... + a_n-1), откъдето a_n | c;

2) ако a₀(p/q)ⁿ + a₁(p/q)ⁿ-1 + a₂(p/q)ⁿ-2 + ... + a_n-1(p/q) + a_n = 0, то a₀pⁿ + a₁pⁿ-1 q + a₂pⁿ-2q² + ... + a_n-1 pqⁿ-1 + a_nqⁿ = 0. Тогава a₀pⁿ = -q.(a₁pⁿ-1 + a₂pⁿ-2q + ... + a_n-1 pqⁿ-2 + a_nqⁿ-1), следователно a₀| q поради НОД(p, q) = 1.
Също a_nqⁿ = -p.(a₀pⁿ-1 + a₁pⁿ-2 q + ... + a_n-1 qⁿ-1), откъдето a_n| p. g

Пример 7.16. Решаване на уравнението 6x⁵ - 11x⁴ + 100x³ - 175x² + 64x + 16 = 0:

Евентуални цели корени трябва да се търсят между ±1, ±2, ±4, ±8, ±16 - делителите на свободния член 16. Проверката (най-удобно по правилото на Хорнер) показва, че 1 е двукратен корен, откъдето:

6x⁵ - 11x⁴ + 100x³ - 175x² + 64x + 16 = (x - 1)²(6x³ + x² + 96x +16)

Лесно се установява, че полиномът 6x³ + x² + 96x +16 няма цели корени. Евентуални рационални корени /очевидно само отрицателни/ следва да се търсят сред дроби със знаменатели 2, 3 и 6 /делителите на 6/. Проверката показва, че -1/6 е корен, след което

6x³ + x² + 96x +16 = (x + 1/6)(6x² + 96) = 6(x + 1/6)(x² + 16) = 6(x + 1/6)(x - 4i)(x + 4i),

откъдето корените на изходното уравнение са:

x₁ = x₂ = 1, x₃ = -1/6, x₄ = 4i, x₅ = -4i.

Тогава някои от горните резултати се илюстрират по следния начин:

канонично разлагане на линейни множители:

6x⁵ - 11x⁴ + 100x³ - 175x² + 64x + 16 = 6(x - 1)²(x + 1/6)(x - 4i)(x + 4i);

разлагане на реални множители от 1-ва и 2-ра степен:

6x⁵ - 11x⁴ + 100x³ - 175x² + 64x + 16 = 6(x - 1)²(x + 1/6)(x² + 16);

формули на Виет за сумата и произведението от корените:

x₁ + x₂ + x₃ + x₄ + x₅ = 1 + 1 - 1/6 + 4i - 4i = 11/6;
x₁x₂x₃x₄x₅ = 1* 1* (-1/6) * (4i) * (-4i) = -16/6.

* * * * * * *

Над K се въвеждат и полиноми на повече променливи (неизвестни). Нека n О N; x₁, x₂, . . , x_n П K са символи, с които са означени променливите (неизвестните), за които се предполага, че са комутативни и асоциативни помежду си, например x₁x₂x₃x₄ = x₄x₃x₂x₁.

Първо се образува по познатия от ДЕФИНИЦИЯ 7.1 начин пръстенът K[x₁], после K[x₁, x₂] ::= K[x₁][x₂] /елементите му са полиноми на x₂ с коефициенти - полиноми на x₁/, K[x₁, x₂, x₃] ::= K[x₁, x₂][x₃] и т.н. до K[x₁, x₂, . . , x_n] ::= K[x₁, x₂, . . , x_n-1][x_n], чиито елементи са полиноми на x_n с коефициенти - полиноми на x₁, x₂, . . , x_n-1. Може обаче да се предложи и директна конструкция.

ДЕФИНИЦИЯ 7.9. Полином на n променливи над дадено поле K и свързани с него понятия: нека n О N. Формалният израз

където a О K, k₁, k₂, . . , k_n = 0, 1, ..., се нарича едночлен с коефициент a от степен k₁+ k₂+ ... + k_n /приема се, че x_i⁰ ::= 1 за i = 1, 2, . . , n/.

Подобни едночлени са едночлени, отличаващи се само по коефициентите си /тоест съдържащи променливите съответно в еднакви степени/.

Полином F(x₁, x₂, . . , x_n) на n променливи се нарича сума от едночлени /членове на F/:

където сумирането се разпростира за краен брой комбинации на неотрицателните цели числа i₁, i₂, . . , i_n, тоест сума от краен брой членове.

Нулев полином е полином, чиито всички коефициенти /а следователно и членове/ са равни на нулевия елемент на K.

Степен на ненулев полином F /означение deg(F)/ е най-високата от степените на членовете му.

Хомогенен полином или форма е ненулев полином с членове от една и съща степен.

При полиноми на повече от една променлива вместо наредбите по растящи или намаляващи степени се използува обикновено лексикографска наредба на членовете му, например

x₁² + 3x₁x₂ - 5 x₂² ОQ[x₁, x₂]

е хомогенен полином от втора степен /квадратична форма/ на две променливи с лексикографска наредба на членовете.

Аналогично на случая n = 1 се дефинират релация равенство и операции събиране и умножение в множеството K[x₁, x₂, . . , x_n] от полиноми над K и се установява, че K[x₁, x₂, . . , x_n] е цялостен пръстен с единица, съдържащ полето K, но при n > 1 той вече не е пръстен на главни идеали.

ДЕФИНИЦИЯ 7.10. Симетричен полином: полином F(x₁, x₂, . . , x_n) на n променливи се нарича симетричен, ако той не се изменя при произволна пермутация на променливите, тоест ако

/i₁, i₂, . . , i_n - пермутация на номерата 1, 2, . . , n/

Примери за симетрични полиноми са сумата и произведението на променливите, по-общо формулите на Виет (ТВЪРДЕНИЕ 7.19) дават основание за следната

ДЕФИНИЦИЯ 7.11. Елементарни симетрични полиноми, степенни суми: полиномите

s ₁ ::= x₁ + x₂ + x₃ + ... + x_n;
s ₂ ::= x₁x₂ + x₁x₃ + x₂x₃ + ... + x_n-1 x_n;
s ₃ ::= x₁ x₂x₃ + x₁x₂x₄ + ... + x_n-2 x_n-1 x_n;
. . . . . . . . . . . . . . . . . . . . . . .
s _n ::= x₁x₂x₃...x_n

се наричат елементарни симетрични полиноми.

Полиномите s_k ::= x₁^k + x₂^k + x₃^k + ... + x_n^k /k = 0, 1, 2, ... / се наричат степенни суми.

ТВЪРДЕНИЕ 7.23. Основна теорема за симетричните полиноми: всеки симетричен полином F(x₁, x₂, . . , x_n) на n променливи може да се представи по единствен начин като полином от елементарните симетрични полиноми:

F(x₁, x₂, . . , x_n) = F (s ₁, s ₂, . . , s _n), където F (x₁, x₂, . . , x_n) О K[ x₁, x₂, . . , x_n]

Приложения на тази основна теорема са познати на читателя от елементарната алгебра като задачи за изразяване на симетрични функции от корените на квадратни уравнения.

Формули, изразяващи степенните суми чрез елементарните симетрични полиноми, са получени от Нютон.

ТВЪРДЕНИЕ 7.24. Формули на Нютон за степенните суми: в означенията от ДЕФИНИЦИЯ 7.11 при k = 1, 2, ... важи:

s_k - s_k-1 s₁ + s_k-2 s₂ - ... + (-1)^k-1s₁ s_k-1 + (-1)^k.ks_k = 0,

където при k > n се приема, че s_i ::= 0 за i = n+1, n+2, . . , k.

Тъй като s₀ ::= n, с тези формули могат последователно да се пресметнат s₁, . . , s_k.

За полиноми на повече променливи също може да се изгради теория на делимостта, разложимостта на множители и т.н., което няма да бъде предмет на следващото изложение, а ще бъдат засегнати накратко само така наречените рационални дроби. Тъй като K[x₁, x₂, . . , x_n] е цялостен пръстен, съгласно ТВЪРДЕНИЕ 6.4 той може да се вложи в поле от отношения.

ДЕФИНИЦИЯ 7.12. Рационални дроби и поле от рационални дроби: полето от отношения за K[ x₁, x₂, . . , x_n] се нарича поле от рационални дроби (на n променливи, n = 1, 2, ...), а елементите му (формални отношения от полиноми) - рационални дроби. Рационалната дроб на една променлива F(x)/G(x) се нарича несъкратима, ако НОД(F, G) = 1.

Рационалната дроб на една променлива F(x)/G(x) се нарича правилна, ако deg(F) < deg(G).

Според конструкцията на поле от отношения от ТВЪРДЕНИЕ 6.4 знаменателят на всяка рационална дроб е ненулев полином. Така от формално-алгебрична гледна точка например дробите

/първата е несъкратима/ са равни, докато ако се разглеждат като функции на една променлива (както е прието в математическия анализ) ще бъдат различни, тъй като имат различни дефиниционни множества.

Следват някои основни резултати за рационални дроби на една променлива.

ТВЪРДЕНИЕ 7.25. Всяка рационална дроб F(x)/G(x) се представя еднозначно като сума от полином и правилна дроб.

c Според ТВЪРДЕНИЕ 7.3 /теоремата за деление с остатък/:

F(x) = G(x)Q(x) + R(x), като deg(R) < deg(G);

следователно F(x)/G(x) = Q(x) + R(x)/G(x), като дробта R/G е правилна. g

ТВЪРДЕНИЕ 7.26. Всяка правилна дроб F/G, чийто знаменател е произведение от два по два взаимно прости полиноми, например G = G₁G₂...G_n, се представя по единствен начин като сума от правилни дроби със знаменатели G₁, G₂,. . , G_n:

c При n = 2 от НОД(G₁, G₂) = 1 следва, че 1 = F₁G₁ + F₂G₂ за някакви F₁, F₂ О K[x], тогава:

Разделяйки F_.F₁ на G₂ с остатък, се получава F_.F₁/G₂ = q + f/G₂, където q, f О K[x] и f/G₂е правилна дроб. Присъединявайки q към втората дроб, сумата q + F_.F₂/G₁ е правилна дроб като разлика от правилните дроби F/G и f /G₂. Ако съществуват две представяния:

с изваждането им се получава

(f₁ - h₁)/G₁ = (h₂ - f₂)/G₂, или (f₁ - h₁)G₂ = (h₂ - f₂)G₁.

Лявата страна на последното равенство (f₁ - h₁)G₂ | G₁, но поради НОД(G₁, G₂) = 1 следва, че (f₁ - h₁) | G₁. Тъй като deg(f₁ - h₁) < deg(G₁), това е възможно само при f₁ - h₁ = 0, тогава f₁ = h₁ и f₂ = h₂.

При n > 2 резултатът следва индуктивно. g

Според доказаното /сравнете и с упражнение 3.7/, ако знаменателят G на правилната дроб F/G има канонично разлагане

където j₁, j₂, j₃, . . , j_s са неразложими полиноми, а k₁, k₂, . . , k_s О N, F/G може да се представи еднозначно като сума от правилни дроби със знаменатели . Този резултат и едно следствие от него относно разлагането в сума от така наречените елементарни дроби имат обширни приложения в интегралното смятане при интегриране на рационални функции.

Упражнения към глава 7/по-нататък K означава произволно поле/:

7.1. K[x] е пръстен на главни идеали.

7.2[!]. Да се намерят остатъците от делението на полином F(x) на (x - a)(x - b) или на (x - a)² без да се извършва самото деление /a, b О K, a № b/

7.3. Кога НОД(ax² + bx + c, 2ax + b) = 1; НОД(x³ + px + q, 3x² + p) = 1 /a, b, c, p, q О C, a № 0/?

7.4. Използувайки идеята на Евклидовото доказателство за съществуване на безбройно много прости числа /ТВЪРДЕНИЕ 1.8.4)/ да се докаже, че над K съществуват безбройно много неразложими полиноми.

7.5. Полином от 2-ра или от 3-та степен без корени в K е неразложим над K.

7.6[!]. Да се намерят всички неразложими полиноми от 2-ра и 3-та степен над GF(2); по аналогия с пример 7.14 да се построи GF(8).

7.8. Полином над C се дели на производната си точно тогава, когато има вида a(x - w)ⁿ, където a, w О C, a № 0, n О N.

7.9[!]. За полиноми над C да се докаже еквивалентността на дефинициите за равенство на полиноми: формално-алгебричната (ДЕФИНИЦИЯ 7.2) и функционалната (познатото от математическия анализ равенство на две функции на една променлива). Разглеждайки полиномите x + 1 и x²+ 1 О GF(2)[x] или x^p - x и 0 О GF(p)[x] да се докаже, че за крайно поле двете дефиниции не са еквивалентни.

7.10. С интерполационната формула на Лагранж да се конструират полиноми по дадени стойности:

F(x) О R[x]; F(0) = 0, F(-1) = F(1) = 1;
F(x) О GF(5)[x]; F(1) = 2, F(2) = 3, F(3) = 4.

7.11[!]. Всеки рационален корен на нормиран целочислен полином е цял.

7.12[!]. Да се намерят всички комплексни корени на уравненията:

4x⁴- 8x³+ x²+ 3x - 1 = 0;
x⁴- 10x³+ 35x²- 50x + 24 = 0;
24x⁴- 50x³+ 35x²- 10x + 1 = 0;

с формулите на Виет и Нютон да се пресметнат сумите от степените на корените им до третата включително.

7.13[!]. Да се намерят коефициентите на нормиран полином над C от възможно най-ниска степен с корени:

±1 и ±i;
1 /двукратен/ и 1±2i;
1, 1/2, 1/3 и 1/4.

7.14. Ако корените на полинома x³ + px² + qx + r О C[x] образуват:

аритметична прогресия, то единият от тях е равен на -p/3;
геометрична прогресия, то единият от тях е равен на

7.15. За полиномите a₁x² + b₁x + c₁ и a₂x² + b₂x + c₂ / a₁, b₁, c₁, a₂, b₂, c₂ О K, a₁ № 0, a₂ № 0/ да се изведе необходимо и достатъчно условие да имат общ корен като се разгледа произведението (x₁'- x₂') (x₁'- x₂") (x₁"- x₂') (x₁"- x₂"),където x₁' , x₁" са корени на първия, x₂', x₂" - на втория полином.

Oбратно към СЪДЪРЖАНИЕ

8. ВЕКТОРНИ ПРОСТРАНСТВА

Тези алгебрични системи са предмет на обстойно изучаване в линейната алгебра, затова в тази глава ще бъдат споменати само най-важните понятия и резултати. Нека по-нататък с K е означено произволно поле, чиито елементи във връзка с разглежданите въпроси често се цитират като скалари.

ДЕФИНИЦИЯ 8.1. Векторно (линейно) пространство над поле K: адитивна Абелева група V от елементи, наречени вектори (с двучленна операция събиране), като на "a О K и "a О V е съпоставен вектор aa О V /произведение на вектор със скалар - знакът за тази операция обикновено се пропуска/, така, че да бъдат изпълнени аксиомите:

a(a + b) = aa + ab /a О K; a, b О V/;
(a + b)a = aa + ba /a, b О K; a О V/;
a(ba) = (ab)a /a, b О K; a О V/;
1.a = a /1 - единица на K, a О V/;

се нарича векторно (линейно) пространство над K.

Неутралният елемент на V се нарича нулев вектор /означение 0/.

ТВЪРДЕНИЕ 8.1. Основни свойства на нулевия вектор:
1) 0.a = 0 за "a О V;
2) a.0 = 0 за "a О K;

c 0.а = (0 + 0)a = 0.a + 0.a, откъдето 0.a = 0; a.0 = a.(0 + 0) = a.0 + a.0, откъдето a.0 = 0. g

Примери за векторни пространства:

8.1. Множеството от свободните вектори в равнината или в пространството с известните от геометрията събиране на вектори и умножение на вектор с число е векторно пространство над полето R /този пример обяснява произхода на термина векторно пространство/.

8.2. Множеството от матрици с фиксирани размери над произволно поле относно събирането на матрици и умножение на матрица със скалар.

8.3. Множеството (пръстенът) K[x] от полиноми над произволно поле K относно събирането на полиноми и умножение на полином с елемент от K.

8.4. Множеството от полиноми от най-много n-та степен /n О N/ над произволно поле относно операциите от пример 8.3.

8.5. Полето C е векторно пространство над полето R относно събирането на комплексни числа и умножението на комплексно число с реално.

8.6. Полето GF(4) от пример 7.14 е векторно пространство над GF(2).

ДЕФИНИЦИЯ 8.2. Линейни комбинации, линейна зависимост, линейна независимост: ако a₁, a₂, . . , a_n О K и a₁, a₂, . . , a_n О V, векторът a = a₁a₁ + a₂a₂ + ... + a_n a_n се нарича линейна комбинация на векторите a₁, a₂, . . , a_n(с коефициенти a₁, a₂, . . , a_n).

Векторите a₁, a₂, . . , a_s се наричат линейно зависими, ако съществува линейна комбинация
a₁a₁ + a₂ a₂ + ... + a_s a_s = 0 с поне един ненулев коефициент a_i /i = 1, 2, . . , s/.

Векторите a₁, a₂, . . , a_s се наричат линейно независими, ако a₁a₁ + a₂a₂ + ... + a_sa_s = 0 единствено при a₁ = a₂ = ... = a_s = 0 /тривиална линейна комбинация/.

От ДЕФИНИЦИЯ 8.2 следва, че всяко от понятията линейна зависимост и линейна независимост е логическо отрицание на другото. Лесно се съобразява, че при безкрайно поле K ако съществува една нетривиална линейна комбинация на векторите a₁, a₂, . . , a_s, равна на 0, съществуват и безбройно много такива. Затова векторите от един комплект са линейно зависими, ако нулевият вектор може да се представи като тяхна линейна комбинация по повече от един начин (следователно по безбройно много начини при безкрайно поле), и са линейно независими в противен случай (ако нулевият вектор се представя само по тривиалния начин).

ТВЪРДЕНИЕ 8.2. Свойства на линейно зависимите и линейно независимите вектори /във всяко от следващите свойства става дума за вектори от едно и също пространство/:

1) ако към комплект от линейно зависими вектори се добавят нови (произволни), векторите от разширения комплект са също линейно зависими;

2) ако от комплект от линейно независими вектори се отстранят няколко (като остане поне един), останалите вектори са също линейно независими;

3) ако векторите от един комплект са линейно зависими, поне един от тях може да се представи като линейна комбинация на останалите и обратно;

4) ако векторите от един комплект са линейно независими, никой от тях не може да се представи като линейна комбинация на останалите и обратно;

5) ако a₁, a₂, . . , a_m и b₁, b₂, . . , b_n /m, n О N/ са 2 комплекта линейно независими вектори и всеки вектор от втория комплект е линейна комбинация на векторите от първия, то m і n.

ДЕФИНИЦИЯ 8.3. Размерност и базис на векторно пространство: ако за векторното пространство V съществува множество B от краен брой линейно независими вектори със свойството, че всеки вектор от V се представя като линейна комбинация на векторите от B, то V се нарича крайномерно векторно пространство, B се нарича базис на V, а броят на векторите в базиса се нарича размерност на V /означение dim(V)/. В противен случай V се нарича безкрайномерно.

Коректността на дефиницията за понятието размерност следва от лесно доказуемия с помощта на ТВЪРДЕНИЕ 8.2.5) факт, че всеки два базиса на V имат равен брой вектори. Освен това никой базис не може да съдържа нулевия вектор /вектори, сред които участвува нулевият, са линейно зависими/.

В примери 8.1 - 8.6 само K[x] е безкрайномерно, тъй като степените 1 = x⁰, x, x², x³, ... са линейно независими. Множеството от свободните вектори в пространството е тримерно с базис, образуван от всеки три некомпланарни ненулеви вектори. Множеството от матрици-редове с n компоненти /n О N/ е n-мерно с базис например (1, 0, . . , 0), (0, 1, . . , 0),.., (0, 0, . . , 1). Базис на пространството от полиномите от степен, не по-висока от n, образуват 1, x, x², . . , xⁿ. Полето C е двумерно векторно пространство над R с базис, образуван от 1 и i /имагинерната единица/. Полето GF(4) от пример 7.14 е двумерно векторно пространство над полето GF(2) с базис, образуван от 1 и x.

ТВЪРДЕНИЕ 8.3. Теорема за еднозначно разлагане на вектор по базис: ако e₁, e₂, . . , e_n образуват базис на V, то за "a О V представянето на a като линейна комбинация на базисните вектори е единствено.

c Нека а = a₁'.e₁ + a₂'.e₂+ ... + a_n'.e_n, и а = a₁".e₁ + a₂".e₂+ ... + a_n".e_n са две представяния. С изваждането им се получава:

0 = (a₁' - a₁")e₁ + (a₂' - a₂")e₂+ ... + (a_n' - a_n")e_n,

и поради линейната независимост на базисните вектори следва, че

a₁' - a₁" = 0, a₂' - a₂" = 0, . . , a_n' - a_n" = 0,

тоест двете представяния са идентични. g

Упражнения към глава 8:

8.1. Да се докаже ТВЪРДЕНИЕ 8.2.

8.2. Ако dim(V) = n, максималният брой линейно независими вектори от V е равен на n.

8.3. Числата 1 и i са линейно независими над R.

8.4. Подмножество V' на векторното пространство V се нарича подпространство, ако V' е също векторно пространство относно операциите, дефинирани в V. Очевидно всяко векторно пространство има тривиалните подпространства - { 0 } и самото V. Освен това ако dim(V) = n, да се докаже, че съществуват и подпространства от всички междинни размерности 1, 2, . . , n-1.

Oбратно към СЪДЪРЖАНИЕ

9. ПРОСТИ РАЗШИРЕНИЯ НА АЛГЕБРИЧНИ ПОЛЕТА.
ПОЛЕ НА РАЗЛАГАНЕ. ПОЛЕТА НА ГАЛОА.

В настоящата глава ще бъде описана една техника за получаване на разширения на алгебрични полета, известна като присъединяване към дадено поле на корен на полином над това поле, който корен не принадлежи на полето. С помощта на тази процедура, започвайки от добре известните полета на Галоа GF(p) при p - просто число, могат да се конструират всички крайни полета.

Нека по-нататък K е произволно поле, F(x) = j₀ + j₁ x + j₂x² + ... + j_nxⁿ О K[x] е неразложим над K, deg(F) = n > 1 с корен w П K, който, както лесно се проверява, при наложените изисквания /съществено използувани по-нататък!/ за F(x) не може да бъде корен на друг полином от по-ниска степен.

ТВЪРДЕНИЕ 9.1. Множеството

K(w) ::= { g₀ + g₁ w + g₂w²+ ... + g_n-1 w^n-1; g ₀, g ₁, . . , g_n-1 О K }

от линейни комбинации на степените 1 = w⁰, w, w², . . , wⁿ-1 на корена w, е поле.

c Всеки елемент a₀ + a₁w + a₂w² + ... + a_n-1wⁿ-1 О K(w) има единствено представяне от посочения вид, действително иначе ако

b₀ + b₁w + b₂w² + ... + b_n-1 wⁿ-1

е друго представяне, то с изваждане на двете представяния се получава:

0 = (a₀ - b₀) + (a₁ - b₁)w + (a₂ - b₂)w²+ ... + (a_n-1 - b_n-1)wⁿ-1,

тоест w би бил корен на полином от степен, по-ниска от n = deg(F) - противоречие. Това означава от една страна, че степените 1, w, w², . . , wⁿ-1 са линейно независими; а от друга - че елементите

a = a₀ + a₁w + a₂w² + ... + a_n-1 wⁿ-1 и b = b₀ + b₁w + b₂w² + ... + b_n-1wⁿ-1

са равни точно тогава, когато a₀ = b₀, a₁ = b₁, a₂ = b₃, . . , a_n-1 = b_n-1.Лесно се вижда, че сумата:

a + b ::= (a₀ + b₀) + (a₁ + b₁)w + (a₂ + b₂)w²+ ... + (a_n-1 + b_n-1)wⁿ-1,

и произведението:

ab ::= (a₀b₀) + (a₀b₁ + a₁b₀) w + (a₀b₂ + a₁b₁ + a₂b₀) w²+ ... + (a_n-1 b_n-1) w^2n-2

са елементи от същия вид, тъй като всички степени на w от n нататък могат да се изразят чрез 1, w, w², . . , wⁿ-1 като следствие на факта, че w е корен на полинома F(x).

Наистина от F(w) = j₀ + j₁ w + j₂w² + ... + j_nwⁿ = 0 и j_n № 0 следва, че

wⁿ = - (j₀ + j₁ w + j₂w² + ... + j_n-1 wⁿ-1) j_n^-1

И така K(w) е алгебрична система, затворена относно събирането и умножението. Комутативните и асоциативните закони за събирането и умножението, както и дистрибутивният закон са изпълнени като следствие от тяхното изпълнение в K. По-нататък директно се вижда, че елементите

0 = 0 + 0w + 0w² + ... + 0wⁿ-1 и 1 = 1 + 0w + 0w² + ... + 0wⁿ-1

са съответно нулев и единичен и -a = -a₀ - a₁ w - a₂w² - ... - a_n-1wⁿ-1 е противоположен за a.

Остава да се докаже съществуването на реципрочен за всеки ненулев елемент. Нека за елемента a № 0 с горното представяне A(x) е полиномът a₀ + a₁ x + a₂x² + ... + a_n-1 x^n-1, тоест a = A(w). Щом F(x) е неразложим, то съгласно ТВЪРДЕНИЕ 7.7 или A | F, или A и F са взаимно прости, но поради deg(A) < deg(F) и А № 0 не може A | F, затова НОД(F, A) = 1. Тогава според ТВЪРДЕНИЕ 7.6 съществуват полиноми P(x), Q(x) О K[x] такива, че F(x).P(x) + A(x).Q(x) = 1 и преминавайки към стойностите при x = w се получава F(w)P(w) + A(w)Q(w) = 1, тоест A(w).Q(w) = 1 тъй като w е корен на F и F(w) = 0, или a.Q(w) = 1, откъдето a^-1 = Q(w), като в това представяне за a^-1 могат да участвуват, както беше отбелязано по-горе, степените на w най-много до n-1. g

.Забележка: изразяването на реципрочния елемент a^-1 = 1/а като стойност на подходящ полином в по-елементарни случаи е известно на читателя като рационализация на знаменателя на ирационална алгебрична дроб (с числител 1).

Построеното поле K(w), чиито елементи са полиноми на w от най-много n-1-ва степен, се нарича просто разширение на K, и е "най-малкото" поле, съдържащо K и w в следния смисъл: може да се докаже, че K(w) е сечение на всички полета, съдържащи K и w. Освен това при направените предположения за F(x) е налице изоморфизъм

K(w) @ K[x]/(F)

/илюстриращ пример е посочен в упражнение 9.1/.

ТВЪРДЕНИЕ 9.2. Полето K(w) е векторно пространство над K с базис 1 = w⁰, w, w², . . , wⁿ-1 и размерност deg(F).

c Изискванията на ДЕФИНИЦИЯ 8.1 за K(w) се проверяват непосредствено. Максималността на системата от степените 1, w, w², . . , wⁿ-1 и линейната им независимост (което означава, че образуват базис), както и единствеността на разлагането по базиса за всеки елемент от K(w) са доказани в ТВЪРДЕНИЕ 9.1. g

От получените резултати се вижда например, че известното поле C от комплексните числа е просто разширение на полето R от реалните числа, получено от R чрез присъединяване към R на корена i на неразложимия полином от втора степен x²+ 1 и по тази причина е, както беше споменато в предишната глава, двумерно векторно пространство над R с базис 1 и i. Последният факт обуславя и познатата геометрична интерпретация на C с Гаусовата равнина на комплексните числа, а всяко комплексно число може да се счита за полином на i от най-много първа степен с реални коефициенти /реалната и имагинерната части на числото/.

Съгласно резултатите от глава 7 за всеки неконстантен полином съществува поле, съдържащо всичките му корени и над това поле полиномът може да се разложи на линейни множители. Същото е очевидно вярно и за произволно разширение на въпросното поле, затова представлява интерес "най-малкото" от всички полета с такова свойство.

ДЕФИНИЦИЯ 9.1. Поле на разлагане за полином F(x) О K[x], deg(F) > 0: поле K_F, над което F(x) се разлага на линейни множители, като F(x) не се разлага на линейни множители в никое собствено подполе на K_F, се нарича поле на разлагане за F(x).

Може да се докаже следното

ТВЪРДЕНИЕ 9.3. За всеки полином от положителна степен съществува поле на разлагане, което е единствено с точност до изоморфизъм.

Доказателството на съществуването е основано на описаната процедура на последователното присъединяване към основното поле на всички корени, които не му принадлежат, а частта за единственост означава по-подробно, че всеки две полета на разлагане са изоморфни, като изоморфизмът между тях оставя неизменни елементите на основното поле, а осъществява някаква пермутация на непринадлежащите на основното поле корени на полинома.

Например полиномът x²- 2 О Q[x] има за свое поле на разлагане Q() = { a + b; a, b О Q }, получено с присъединяване на към Q; над Q() е в сила разлагането

x²- 2 = (x -) (x + ).

За x^p - x О GF(p)[x] при p - просто /вижте пример 7.4 относно означенията за коефициентите/, полето на разлагане е самото GF(p) /което няма собствени подполета!/, действително според ТВЪРДЕНИЕ 6.2.4) за "x О GF(p) = { [0], [1], [2], . . , [p-1]} е изпълнено x^p = x, тоест [0], [1], [2], . . , [p-1]са всичките p на брой (различни) корени на полинома x^p - x и разлагането му е:

x^p - x = x( x - [1]) ( x - [2]) ...( x - [p-1]).

До края на тази глава ще бъдат резюмирани накратко основните резултати за крайните полета, като ще се използува обичайното означение GF(q) за поле на Галоа с q елемента. Освен това по-нататък p ще означава просто число.

ТВЪРДЕНИЕ 9.4. Характеристиката на всяко поле на Галоа е просто число.

c Следва от ТВЪРДЕНИЕ 6.2 и доказания в ТВЪРДЕНИЕ 6.3 факт, че поле с характеристика 0 не може да има краен брой елементи, тъй като кратните на единичния му елемент са всичките различни. g

ТВЪРДЕНИЕ 9.5. Всяко поле на Галоа с характеристика p съдържа подполе, изоморфно на GF(p).

c Следва от ТВЪРДЕНИЕ 6.3. и ТВЪРДЕНИЕ 9.4. g

ТВЪРДЕНИЕ 9.6. Броят на елементите на едно крайно поле е равен на цяла положителна степен на характеристиката му.

c Нека Char (GF(q)) = p. Тогава GF(q) съдържа подполе, изоморфно с GF(p) и GF(q) може да се разглежда като крайномерно векторно пространство над GF(p), тъй като самото GF(q) е крайно. Нека базисът на GF(q) над GF(p) се състои от елементите w₁, w_2, . . , w_m, тогава всеки елемент от GF(q) се представя еднозначно като линейна комбинация l₁w₁+ l₂w₂ + ... + l_m w_m , в която всеки коефициент l_i /i = 1, 2, . . , m/ е от полето GF(p), следователно може да бъде избран по p на брой начина. Това означава, че броят на всичките линейни комбинации е p^m, тоест #(GF(q)) = p^m. g

Според ТВЪРДЕНИЕ 6.2.4) за " x О GF(q) е изпълнено x^q = x, което означава, че " x О GF(q) е корен на полинома x^q - x.

ТВЪРДЕНИЕ 9.7. Съществуване и единственост на полетата на Галоа: за всяко просто число p и за всяко естествено число m нека q = p^m. Тогава съществува единствено с точност до изоморфизъм поле на Галоа GF(q), по-точно всяко такова поле е изоморфно на полето на разлагане на полинома x^q - x О GF(p)[x].

c Полиномът x^q - x има производна (x^q - x)' = q.x^q-1 - 1 = p^m x^q-1 - 1 = -1 № 0 /p^m t = 0 за "t О GF(p) поради Char(GF(p)) = p/ и тогава НОД(x^q - x, -1) = 1, откъдето, съгласно ТВЪРДЕНИЕ 7.14 следва, че всичките му q на брой корени x₁, x₂, . . , x_q / deg(x^q - x) = q / са различни. Директно се проверява, че те образуват поле GF(q), над което е в сила разлагането:

x^q - x = ( x - x₁) ( x - x₂) ...( x - x_q ),

каквото не може да има в никое друго "по-малко" поле, защото последното не би съдържало всичките q корени на x^q - x. Следователно GF(q) е неговото поле на разлагане. Ако K е друго поле с q елемента, за всеки негов елемент важи x^q = x, тоест K е също поле на разлагане на x^q - x и поради единствеността на полето на разлагане с точност до изоморфизъм (ТВЪРДЕНИЕ 9.3) следва K @ GF(q). g

Според коментара в началото на тази глава, започвайки от GF(p), може да се конструира GF(p^m) с присъединяване на корен на неразложим над GF(p) полином от степен m. Може да се докаже съществуване на такива полиноми, но конструкцията от ТВЪРДЕНИЕ 9.7 има предимството, че използува друг подход, който не се позовава на това недоказано твърдение.

В заключение следва описание на мултипликативната група на поле на Галоа. За GF(p) както адитивната група Z_p, така и мултипликативната Z_p \ [0] = { [1], [2], . . , [p-1] }, са очевидно циклични. В общия случай за адитивната това вече не е вярно /вижте упражнение 9.5/, но е в сила

ТВЪРДЕНИЕ 9.8. Мултипликативната група на всяко поле на Галоа е циклична.

Упражнения към глава 9:

9.1[!]. Да се конструира GF(4) с присъединяване към GF(2) на корен w П GF(2) на полинома x²+ x + 1 О GF(2)[x]. Да се сравнят конструкциите на GF(4) с двете процедури: присъединяване на корен и факторизация /описана в пример 7.14/.

9.2[!]. Да се провери, че уравненията x² = 2 и x²= 3 нямат корени в GF(5). Ако w е корен на някое от тези уравнения, да се конструира полето на Галоа GF(25) от GF(5) с присъединяване на w.

9.3. Да се рационализират знаменателите на дробите

9.4. Да се изведе теоремата на Уилсън (упражнение 2.4) като следствие от посоченото в коментара след ТВЪРДЕНИЕ 9.3 разлагане на полинома x^p - x О GF(p)[x] при p - просто.

9.5. Използувайки таблиците за събиране и умножение за полето на Галоа GF(4) /пример 7.14/ директно да се провери, че адитивната му група е изоморфна на диедралната група D₂ /групата на Клайн/ и не е циклична, а мултипликативната е циклична от трети ред. Да се изследва адитивната група на GF(8).

9.6. Всеки елемент от полето GF(2^m) /m О N/ е точен квадрат /за полета на Галоа с нечетен брой елементи това не е вярно, например според горното упражнение 9.2 в GF(5) 2 и 3 не са точни квадрати/.

Oбратно към СЪДЪРЖАНИЕ

АЗБУЧЕН УКАЗАТЕЛ

< A >

Абелева (комутативна) група
Автоморфизъм

на групи
на пръстени/полета

Адитивна група

на пръстен/поле

Азбука
Алгебрически затворени полета
Алгебрична операция

асоциативна
двучленна (бинарна)
дистрибутивна
едночленна (унарна)
идемпотентна
комутативна
тричленна (тернарна)

Алгебрична система (структура)
Алгебрично уравнение
Алгоритъм на Евклид за намиране на най-голям общ делител:

на числа
на полиноми

Асоциативен закон
Асоциативен пръстен
Асоциативна операция

Oбратно към АЗБУЧЕН УКАЗАТЕЛ

< Б >

Базис (на векторно пространство)
Безкрайномерно векторно пространство
Безу

теорема на
тъждество на

Бинарна операция
Булев пръстен

Oбратно към АЗБУЧЕН УКАЗАТЕЛ

< В >

Вектор

нулев

Векторно (линейно) пространство

безкрайномерно
крайномерно

Взаимно прости числа
Взаимно прости полиноми
Виет, формули на

Oбратно към АЗБУЧЕН УКАЗАТЕЛ

< Г >

Галоа, поле на
Гаус, теорема на
Главен идеал
Група

Абелева (комутативна)
адитивна
диедрална
мултипликативна
на Клайн
от симетриите на фигура
симетрична
циклична

Oбратно към АЗБУЧЕН УКАЗАТЕЛ

< Д >

Даламбер, теорема на
Двоично-рационални (дуално-рационални) числа
Двустранен идеал
Двучленна операция
Деление
Делимост

на цели числа
на полиноми

Делител (дивизор)

собствен
тривиален

Делители на нулата
Десен идеал
Десен неутрален елемент
Диедрална група
Диофантови уравнения
Дистрибутивен закон
Дистрибутивна операция
Дробна част (на реално число)

Oбратно към АЗБУЧЕН УКАЗАТЕЛ

< Е >

Евклид, алгоритъм на ® Алгоритъм на Евклид
Единичен елемент

на (мултипликативна) група
на пръстен/поле

Едночлен
Едночленна операция
Елементарни симетрични полиноми
Ендоморфизъм
Епиморфизъм
Естествен (каноничен) хомоморфизъм

Oбратно към АЗБУЧЕН УКАЗАТЕЛ

< З >

Затвореност

Oбратно към АЗБУЧЕН УКАЗАТЕЛ

< И >

Идеал

главен
двустранен
десен
ляв

Идемпотентна операция
Идентично преобразувание (идентитет)
Изваждане
Изоморфизъм
Израз
Инвариантна подгрупа
Инверсен (обратен) елемент
Индекс на подгрупа
Инфиксни означения

Oбратно към АЗБУЧЕН УКАЗАТЕЛ

< К >

Каноничен хомоморфизъм
Канонично разлагане

на прости множители
на неразложими полиноми

Кейли, таблица на
Китайска теорема за остатъците
Клайн, група на
Класове от остатъци
Коефициенти

на полином
на линейна комбинация

Комутативен закон
Комутативен пръстен
Комутативна група
Комутативна операция
Композиция на преобразувания
Конкатенация (на стрингове)
Константен полином (константа)
Конгруентност ® Сравнимост
Корен (нула) на полином
Крайномерно векторно пространство
Кратни (многократни) корени
Кратни (на елемент)
Кратно
Кратност (на корен)

Oбратно към АЗБУЧЕН УКАЗАТЕЛ

< Л >

Лагранж

теорема (за крайните групи) на
формула (интерполационна) на

Латински квадрат
Линейна зависимост/независимост (на вектори)
Линейна комбинация (на вектори)
Линейно пространство
Ляв идеал
Ляв неутрален елемент

Oбратно към АЗБУЧЕН УКАЗАТЕЛ

< М >

Малка теорема на Ферма
Мерсен, прости числа на
Моноид
Мономорфизъм
Морфизми
Мултипликативна група

на поле

Oбратно към АЗБУЧЕН УКАЗАТЕЛ

< Н >

Най-голям общ делител (НОД, GCD)

на полиноми
на цели числа

Най-малко общо кратно (НОК, LCM)
Ненулев полином
Неразложим полином
Несъкратима рационална дроб
Неутрален елемент

десен
ляв

Нормален делител
Нормиран полином
Носител (на алгебрична система)
Нула (на полином)
Нулев вектор
Нулев елемент
Нулев полином
Нютон, формули на

Oбратно към АЗБУЧЕН УКАЗАТЕЛ

< О >

Образуващ елемент
Обратен елемент
Общ делител
Общо кратно
Операнд
Основна теорема

за симетричните полиноми
на алгебрата (теорема на Даламбер, теорема на Гаус)
на аритметиката

Остатък

при деление на цели числа
при деление на полиноми

Отношение (частно)

Oбратно към АЗБУЧЕН УКАЗАТЕЛ

< П >

Период (на систематична дроб)
Питагоров триъгълник

Подгрупа

инвариантна (нормален делител)
тривиална

Подобни едночлени
Подполе

собствено

Подпространство (на векторно пространство)

тривиално

Подпръстен

тривиален

Поле

алгебрически затворено
на Галоа (крайно поле)
на разлагане
от отношения (частни)
от рационални дроби
просто

Полином (над дадено поле)

елементарен симетричен
константен
ненулев
неразложим
нормиран
нулев
разложим
симетричен
хомогенен (форма)

Полугрупа
Постфиксни означения
Правилна рационална дроб
Правило (схема) на Хорнер
Префиксни означения
Признаци за делимост
Приоритет (на операции)
Присъединяване на корени
Производна (производен полином)
Просто поле
Просто разширение (на поле)
Просто число

на Мерсен
на Ферма

Противоположен елемент
Пръстен

асоциативен
Булев
комутативен
на главни идеали
нулев
от полиноми на една променлива (над дадено поле)
от полиноми на повече променливи (над дадено поле)
с единица
цялостен

Пълна система от остатъци

Oбратно към АЗБУЧЕН УКАЗАТЕЛ

< Р >

Равенство

на полиноми
на формални дроби

Равноостатъчност ® Сравнимост
Разлагане по съседни класове
Разложим полином, разложимост
Размерност (на векторно пространство)
Разширение (на пръстен/поле)

просто

Рационални дроби
Ред

на група
на елемент

Релация на еквивалентност
Резултат (от алгебрична операция)
Реципрочен елемент

Oбратно към АЗБУЧЕН УКАЗАТЕЛ

< С >

С точност до изоморфизъм
Свободен член
Сигнатура (на алгебрична система)
Симетричен полином
Симетрична група
Скалар
Смесена периодична дроб
Собствено подполе
Сравнимост (конгруентност, равноостатъчност)

на полиноми
на цели числа

Сравнения с едно неизвестно
Старши (главен, водещ) коефициент
Степен (на полином)

на една променлива
на повече променливи

Степени (на елемент)
Степенни суми
Стойност (на полином)
Стринг
Субституция
Събиране

в (адитивна) група
в пръстен

Съкращаване
Съседен клас
Съставно число

Oбратно към АЗБУЧЕН УКАЗАТЕЛ

< Т >

Таблица на Кейли
Тейлър, формула на
Теорема

за деление с остатък (на полиноми)
за деление с остатък (на цели числа)
за еднозначно разлагане на вектор по базис
за еднозначно разлагане на полином на линейни множители
за остатъците на линейната функция
за съществуване на корен в подходящо разширение на полето
за хомоморфизмите
на Безу
на Лагранж за крайните групи
на Уилсън

Тривиални подгрупи
Тривиални подпространства
Тривиални подпръстени
Тричленна (тернарна) операция
Тъждество на Безу
Тяло (пръстен с деление)

Oбратно към АЗБУЧЕН УКАЗАТЕЛ

< У >

Уилсън, теорема на
Умножение

в (мултипликативна) група
в пръстен

Унарна операция
Универсална алгебра

Oбратно към АЗБУЧЕН УКАЗАТЕЛ

< Ф >

Фактор-група
Фактор-множество
Фактор-пръстен
Ферма, Малка теорема на
Ферма, прости числа на
Фибоначи, числа на
Форма (хомогенен полином)
Формални дроби
Формула

(интерполационна) на Лагранж
на Тейлър

Формули

на Виет
на Нютон (за степенните суми)

Oбратно към АЗБУЧЕН УКАЗАТЕЛ

< Х >

Характеристика (на поле)
Хомоморфизъм

естествен (каноничен)
на групи
на пръстени/полета

Хомогенен полином (форма)
Хорнер, правило на

Oбратно към АЗБУЧЕН УКАЗАТЕЛ

< Ц >

Цели Гаусови числа
Целочислено деление (Pascal)
Целочислен модул (Pascal)
Център (на група)
Циклична група
Цяла част (на реално число)
Цялостен пръстен

Oбратно към АЗБУЧЕН УКАЗАТЕЛ

< Ч >

Частно (отношение)

непълно

Числа на Фибоначи
Чиста периодична дроб

Oбратно към АЗБУЧЕН УКАЗАТЕЛ

< Я >

Ядро (на хомоморфизъм)

Oбратно към СЪДЪРЖАНИЕ

ЛИТЕРАТУРА

1. Н. Обрешков - Висша алгебра, Наука и изкуство, София, 1966
2. К. Дочев, Д. Димитров, В.Чуканов - Ръководство за упражнения по висша алгебра: пръстени и полета, полиноми и групи, Наука и изкуство, София, 1976
3. Г. Генов, С. Миховски, Т. Моллов - Алгебра с теория на числата, Наука и изкуство, София, 1991
4. Д. К.Фаддеев - Лекции по алгебре, Москва, "Наука", 1984
5. Р. Лидл, Г. Нийдеррайтер - Конечные поля, т.1, Москва, "Мир", 1988
6. Jean-Marie Monier - Algebre I, Cours et 600 exercices corriges