От курса по програмиране е известно, че едно цяло число може да бъде представено в компютърната памет по различни начини, по-специално това представяне зависи от това как е описано: като стойност от тип integer, или real, или string. В същото време в повечето езици за програмиране целите числа се разбират като числа от много ограничен диапазон: типичен случай е от -2 15 = -32768 до 2 15 - 1 = 32767 . Системи компютърна алгебрасе справят с големи цели числа, по-специално, всяка такава система може да изчислява и показва числа като 1000 в десетичен знак! (повече от хиляда знака).
В този курс ще разгледаме представянето на цели числа в символна форма и няма да навлизаме в подробности за това колко памет е отделена за запис на един символ (бит, байт или друг). Най-често срещаното е представянето на цели числа в позиционни бройни системи. Такава система се определя от избора на основата на числото, например 10. Наборът от цели десетични числа обикновено се описва по следния начин:
Писмената дефиниция на цели числа дава уникалността на представянето на всяко такова число и подобно определение (само, може би с различна основа) се използва в повечето системи. компютърна алгебра. Използвайки това представяне, е удобно да се реализират аритметични операции върху цели числа. В същото време събирането и изваждането са относително "евтини" операции, докато умножението и делението са "скъпи". Когато се оценява сложността на аритметичните операции, трябва да се вземе предвид както цената на елементарна операция (еднобитова), така и броят на еднобитовите операции за извършване на всяка операция с многоцифрени числа. Сложността на умножението и делението се дължи преди всичко на факта, че с увеличаване на дължината на число (записването му във всяка числова система) броят на елементарните операции се увеличава по квадратичен закон, за разлика от линейната за събиране и изваждане. Освен това това, което обикновено наричаме алгоритъм за многоцифрено деление, всъщност се основава на изброяване (често много значимо) на възможната следваща цифра на частното и не е достатъчно само да се използват правилата за разделяне на едноцифрени числа. При голяма база на бройната система (често тя може да бъде от порядъка на 2 30 ), този метод е неефективен.
Нека е естествено число (записано в десетична система). За да вземе рекорда му 
в -арна бройна система можете да използвате следния алгоритъм (означава цялата част от числото):
Дадено: A-естествено число в десетичната бройна система k > 1-естествено число Необходимост: A-запис на число A в k-арна бройна система Стартиране на i:= 0 цикъл, докато A > 0 bi:= A (mod k) A: = i:= i + 1 край на цикъл dA:= i - 1 край
Следният алгоритъм се използва за възстановяване на десетично число от последователността на неговата k-арна нотация:
Дадено: k > 1-естествено число поредица от цифри, представляващи числото A в k-арната система Нужда от: A-запис на числото A в десетичен запис Старт A:= 0 цикъл до края на последователността b:= следващ елемент от последователността A:= A * k + b крайна линия Край
1.2. УПРАЖНЕНИЕТО. Обяснете защо деленето се използва за преобразуване на число от десетичната система в k-число, а умножението се използва за преобразуване от k-число в десетично.
Умножавайки по "колона" две двуцифрени числа в десетичната бройна система, ние извършваме следните операции:
(10a + b)(10c + d) = 100ac + 10(ad + bc) + bd,
т.е. 4 операции на умножение на едноцифрени числа, 3 операции на събиране и 2 операции на умножение по силата на числовата основа, които се свеждат до изместване. При оценката на сложността може да се вземат предвид всички елементарни операции, без да се разделят по тегла (в този пример имаме 9 елементарни операции). Задачата за оптимизиране на алгоритъма при този подход се свежда до минимизиране на общия брой елементарни операции. Може обаче да се смята, че умножението е по-"скъпа" операция от събирането, което от своя страна е "по-скъпо" от смяната. Имайки предвид само най-скъпите операции, получаваме това мултипликативнасложността на умножаването на двуцифрени числа по "колона" е 4.
Раздел 5 разглежда алгоритмите за изчисляване на най-големите общи делители и оценява тяхната сложност.
Разглежданото представяне не е единственото канонично представяне на цели числа. Както вече беше отбелязано, за да се избере канонично представяне, може да се използва уникалността на факторизацията на естествено число в прости фактори. Такова представяне на цяло число може да се използва в онези задачи, където се използват само операции за умножение и деление, тъй като те стават много "евтини", но цената на операциите за събиране и изваждане се увеличава непропорционално, което предотвратява използването на такова представяне. При някои проблеми отхвърлянето на каноничното представяне дава значителна печалба в скоростта, по-специално може да се използва частична факторизация на число. Подобен метод е особено полезен при работа не с числа, а с полиноми.
Ако е известно, че по време на работа на програмата всички цели числа, срещани при изчисленията, са ограничени по абсолютна стойност от дадена константа, тогава за да се зададат такива числа, тяхната система от остатъци по модул на някои взаимно прости числа, чийто продукт надвишава споменатата константа, може да се използва. Изчисленията с класове остатъци обикновено са по-бързи от аритметиката с множествена точност. И с този подход аритметика с множествена точност трябва да се използва само при въвеждане или извеждане на информация.
Имайте предвид, че заедно с каноничните представяния в системите компютърна алгебрасе използват и други представяния. По-специално, желателно е наличието или отсъствието на знак "+" пред цяло число да не влияе на възприемането на компютъра за него. Така за положителните числа се получава нееднозначно представяне, въпреки че формата на отрицателните числа е еднозначно определена.
Друго изискване е възприятието на число да не се влияе от наличието на нули преди първата значима цифра.
1.3. УПРАЖНЕНИЯ.
- Изчислете броя на едноцифрените умножения, използвани при умножаване на m-цифрено число по n-цифрено число по колона.
- Покажете, че две двуцифрени числа могат да бъдат умножени, като се използват само 3 едноцифрени умножения и се увеличава броят на събиранията.
- Намерете алгоритъм за разделяне на дълги числа, който не изисква много изброяване, за да намерите първата цифра на частното.
- Опишете алгоритъма за преобразуване на естествени числа от m-арната бройна система в n-арната.
- V Римска номерацияследните символи се използват за запис на числа: I - едно, V - пет, X - десет, L - петдесет, C - сто, D - петстотин, M - хиляда. Символът се счита за отрицателен, ако има символ с по-голямо число вдясно от него, и положителен в противен случай. Например числото 1948 в тази система ще бъде записано така: MCMXLVIII. Формулирайте алгоритъм за преобразуване на число от римско в десетично и обратно. Реализирайте получения алгоритъм на един от алгоритмичните езици (например C). Ограничения за първоначалните данни: 1<= N < 3700 , в записи результата ни один символ не должен появляться больше 3 раз.
- Формулирайте алгоритъм и напишете програма за събиране на естествени числа в римско число.
- Ще кажем, че имаме работа с числова система смесени или векторни, ако ни е даден вектор от n естествени числа M = (m 1 , . . .,m n) (база) и обозначението K = (k 0 , k 1 , . . , k n) означава числото k = k 0 +m 1 (k 1 +m 2 (k 2 + · · +m n ·k n) . . .)). Напишете програма, която според данните (ден от седмицата, часове, минути, секунди) определя колко секунди са минали от началото на седмицата (понеделник, 0, 0, 0) = 0, и извършва обратната трансформация.
Примери
a + b i (\displaystyle a+bi)където а (\displaystyle a)и b (\displaystyle b)рационални числа, i (\displaystyle i)е въображаемата единица. Такива изрази могат да се добавят и умножават според обичайните правила за операции с комплексни числа, като всеки ненулев елемент има обратен, както се вижда от равенството (a + bi) (aa 2 + b 2 − ba 2 + b 2 i) = (a + bi) (a − bi) a 2 + b 2 = 1. (\displaystyle (a+bi)\left(( \frac (a)(a^(2)+b^(2)))-(\frac (b)(a^(2)+b^(2)))i\right)=(\frac (( a+bi)(a-bi))(a^(2)+b^(2)))=1.)От това следва, че рационалните числа на Гаус образуват поле, което е двумерно пространство над (тоест квадратично поле).- По-общо, за всяко цяло число без квадрат d (\displaystyle d) Q (d) (\displaystyle \mathbb (Q) ((\sqrt (d))))ще бъде квадратично разширение на полето Q (\displaystyle \mathbb (Q) ).
- кръгло поле Q (ζ n) (\displaystyle \mathbb (Q) (\zeta _(n)))получени чрез добавяне Q (\displaystyle \mathbb (Q) )примитивен корен нсилата на единството. Полето също трябва да съдържа всички свои сили (тоест всички корени нта сила на единството), неговото измерение над Q (\displaystyle \mathbb (Q) )е равно на функцията на Ойлер φ (n) (\displaystyle \varphi (n)).
- Реалните и комплексните числа имат безкрайна власт над рационалните числа, така че те не са числови полета. Това следва от неизброимост: всяко числово поле е изброимо.
- Поле за всички алгебрични числа A (\displaystyle \mathbb (A) )не е числова. Въпреки че разширението A ⊃ Q (\displaystyle \mathbb (A) \supset \mathbb (Q) )алгебрично, той не е краен.
Пръстен от цели числа, числово поле
Тъй като числовото поле е алгебрично разширение на полето Q (\displaystyle \mathbb (Q) ), всеки негов елемент е корен от някакъв полином с рационални коефициенти (т.е. той е алгебричен). Освен това всеки елемент е корен от полином с цели коефициенти, тъй като е възможно да се умножат всички рационални коефициенти по произведението на знаменателите. Ако даденият елемент е корен на някакъв унитарен полином с цели коефициенти, той се нарича целочислен елемент (или алгебрично цяло число). Не всички елементи на числово поле са цели числа: например, лесно е да се покаже, че единствените целочислени елементи Q (\displaystyle \mathbb (Q) )са редовни цели числа.
Може да се докаже, че сумата и произведението на две алгебрични числа отново е цяло алгебрично число, така че целите елементи образуват подпръстен на числовото поле K (\displaystyle K)Наречен цял пръстенполета K (\displaystyle K)и се означава с . Полето не съдържа делители на нула и това свойство се наследява при преминаване към подпръстен, така че пръстенът от цели числа е интегрален; частна кутия за пръстени O K (\displaystyle (\mathcal (O))_(K))е самото поле K (\displaystyle K). Пръстенът от цели числа на произволно числово поле има следните три свойства: той е интегрално затворен, ноетеров и едномерен. Комутативен пръстен с тези свойства се нарича Дедекинд, на името на Ричард Дедекинд.
Разлагане на прости числа и група от класове
В произволен пръстен на Дедекинд има уникално разлагане на ненулеви идеали в продукт на прости. Въпреки това, не всеки пръстен от цели числа удовлетворява факторното свойство: вече за пръстена от цели числа, квадратично поле OQ (− 5) = Z [ − 5 ] (\displaystyle (\mathcal (O))_(\mathbb (Q) ((\sqrt (-5))))=\mathbb (Z) [(\sqrt ( -5)))разлагането не е уникално:
6 = 2 ⋅ 3 = (1 + − 5) (1 − − 5) (\displaystyle 6=2\cdot 3=(1+(\sqrt (-5)))(1-(\sqrt (-5)) )))Чрез въвеждането на норма върху този пръстен можем да покажем, че тези разширения наистина са различни, тоест едното не може да бъде получено от другото чрез умножение с обратим елемент.
Степента на нарушение на факторното свойство се измерва с помощта на идеалната група класове, тази група за пръстена от цели числа винаги е крайна и нейният ред се нарича брой на класовете.
Бази на числови полета
цяла основа
цяла основачислово поле Фградуси н- това е комплект
Б = {б 1 , …, b n}от нелементи от пръстена от целочислени полета Ф, така че всеки елемент от пръстена от цели числа НАполета Фможе да се запише само като З-линейна комбинация от елементи Б; тоест за всеки хот НАима уникално разлагане
х = м 1 б 1 + … + m n b n,където м иса редовни цели числа. В този случай всеки елемент Фможе да се запише като
м 1 б 1 + … + m n b n,където м иса рационални числа. След това всички елементи Фсе отличават със свойството, че това са точно онези елементи, за които всички м ицяла.
Използвайки инструменти като локализация и ендоморфизма на Фробениус, може да се конструира такава основа за произволно числово поле. Конструкцията му е вградена функция в много системи за компютърна алгебра.
Силова основа
Позволявам Ф- поле с числови степени н. Сред всички възможни бази Ф(как В-векторно пространство), има силови бази, тоест бази на формата
Б х = {1, х, х 2 , …, х н−1 }за някои х ∈ Ф. Според теоремата за примитивните елементи, такива хвинаги съществува, така се нарича примитивен елементтова разширение.
Норма и следа
Алгебрично числово поле е крайномерно векторно пространство над Q (\displaystyle \mathbb (Q) )(означаваме нейното измерение като n (\displaystyle n)), а умножението с произволен елемент от полето е линейна трансформация на това пространство. Позволявам e 1 , e 2 , … e n (\displaystyle e_(1),e_(2),\ldots e_(n))- всякаква основа Ф, след това трансформацията x ↦ α x (\displaystyle x\mapsto \alpha x)съответства матрица A = (a i j) (\displaystyle A=(a_(ij))), определено от условието
α e i = ∑ j = 1 n a i j e j , a i j ∈ Q . (\displaystyle \alpha e_(i)=\sum _(j=1)^(n)a_(ij)e_(j),\quad a_(ij)\in \mathbf (Q) .)
Елементите на тази матрица зависят от избора на база, но всички инварианти на матрицата, като детерминанта и следа, не зависят от нея. В контекста на алгебричните разширения, детерминантата на матрицата за умножение на елемент се нарича нормататози елемент (означен N (x) (\displaystyle N(x))); матрична следа - елемент за проследяване(означено Tr (x) (\displaystyle (\text(Tr))(x))).
Следа на елемент е линеен функционал на Ф:
Tr (x + y) = Tr (x) + Tr (y) (\displaystyle (\text(Tr))(x+y)=(\text(Tr))(x)+(\text(Tr)) (y))и Tr (λ x) = λ Tr (x) , λ ∈ Q (\displaystyle (\text(Tr))(\lambda x)=\lambda (\text(Tr))(x),\lambda \in \mathbb (Q)).Нормата е мултипликативна и хомогенна функция:
N (x y) = N (x) ⋅ N (y) (\displaystyle N(xy)=N(x)\cdot N(y))и N (λ x) = λ n N (x) , λ ∈ Q (\displaystyle N(\lambda x)=\lambda ^(n)N(x),\lambda \in \mathbb (Q)).Като начална база можете да изберете целочислена основа, умножаването с целочислено алгебрично число (тоест с елемент от пръстена от цели числа) в тази основа ще съответства на матрица с целочислени елементи. Следователно, следата и нормата на всеки елемент от пръстена от цели числа са цели числа.
Пример за използване на норма
Позволявам d (\displaystyle d)- - целочислен елемент, тъй като е коренът на редуцирания полином x 2 − d (\displaystyle x^(2)-d)). В тази основа, умножение по a + b d (\displaystyle a+b(\sqrt (d)))съответства матрица
(a d b b a) (\displaystyle (\begin(pmatrix)a&db\\b&a\end(pmatrix)))следователно, N (a + b d) = a 2 − d b 2 (\displaystyle N(a+b(\sqrt (d)))=a^(2)-db^(2)). На елементите на пръстена тази норма приема цели числа. Нормата е хомоморфизъм на мултипликативната група Z [ d ] (\displaystyle \mathbb (Z) [(\sqrt (d))])на мултипликативна група Z (\displaystyle \mathbb (Z) ), така че нормата на обратимите елементи на пръстена може да бъде равна само на 1 (\displaystyle 1)или − 1 (\displaystyle -1). За решаване на уравнението на Пел a 2 − d b 2 = 1 (\displaystyle a^(2)-db^(2)=1), достатъчно е да се намерят всички обратими елементи на пръстена от цели числа (наричани още пръстеновидни единици) и изберете сред тях тези с норма 1 (\displaystyle 1). Според теоремата на Дирихле за единици всички обратими елементи на даден пръстен са степени на един елемент (до умножение по − 1 (\displaystyle -1)), следователно, за да се намерят всички решения на уравнението на Пел, е достатъчно да се намери едно фундаментално решение.
Вижте също
литература
- H. Koch.Алгебрична теория на числата. - М.: ВИНИТИ, 1990. - Т. 62. - 301 с. - (Резултати от науката и техниката. Серия "Съвременни проблеми на математиката. Фундаментални направления".).
- Чеботарев Н.Г.Основи на теорията на Галоа. Част 2. - М.: Редакция URSS, 2004.
- Вейл Г.Алгебрична теория на числата. Пер. от английски - М. : Редакция URSS, 2011.
- Серж Ланг, Алгебрична теория на числата, второ издание, Springer, 2000 г
Видяхме, че операциите върху полиноми се свеждат до операции върху техните коефициенти. В същото време за събиране, изваждане и умножение на полиноми са достатъчни три аритметични операции - не се изисква деление на числата. Тъй като сборът, разликата и произведението на две реални числа са отново реални числа, събирането, изваждането и умножаването на полиноми с реални коефициенти води до полиноми с реални коефициенти.
Въпреки това, не винаги трябва да се работи с полиноми, които имат някакви реални коефициенти. Има случаи, когато по самата същност на въпроса коефициентите трябва да имат само цели числа или само рационални стойности. В зависимост от това кои стойности на коефициентите се считат за допустими, свойствата на полиномите се променят. Например, ако разгледаме полиноми с всякакви реални коефициенти, тогава можем да разложим на множители:
Ако се ограничим до полиноми с цели коефициенти, тогава разширяването (1) няма смисъл и трябва да считаме полинома за неразложим на фактори.
Това показва, че теорията на полиномите по същество зависи от това кои коефициенти се считат за допустими. Далеч от всеки набор от коефициенти може да се приеме като приемлив. Например, разгледайте всички полиноми, чиито коефициенти са нечетни цели числа. Ясно е, че сборът от два такива полинома вече няма да бъде полином от същия тип: в края на краищата сборът от нечетни числа е четно число.
Нека си зададем въпроса: какви са „добрите“ набори от коефициенти? Кога сборът, разликата, произведението на полиноми с коефициенти от даден тип има коефициенти от същия тип? За да отговорим на този въпрос, въвеждаме понятието числов пръстен.
Определение. Непразен набор от числа се нарича числов пръстен, ако заедно с произволни две числа a и , съдържа тяхната сума, разлика и продукт. Това също се изразява по-накратко, като се казва, че пръстенът с числата е затворен при операциите събиране, изваждане и умножение.
1) Множеството от цели числа е числов пръстен: сумата, разликата и произведението на цели числа са цели числа. Множеството от естествени числа не е числов пръстен, тъй като разликата на естествените числа може да бъде отрицателна.
2) Множеството от всички рационални числа е числов пръстен, тъй като сборът, разликата и произведението на рационалните числа са рационални.
3) Образува числов пръстен и множество от всички реални числа.
4) Числа от вида a, където a и цели числа образуват числов пръстен. Това следва от отношенията:
5) Множеството от нечетни числа не е числов пръстен, тъй като сборът от нечетни числа е четен. Наборът от четни числа е числов пръстен.
Пръстенът, в който е въведено отношението "да бъде по-голямо от нула" (означено с a > 0), се нарича разположен пръстен, ако за всеки елемент от този пръстен са изпълнени две условия:
1) едно и само едно от условията е вярно
a > 0 \/ –a >0 \/ a = 0
2) a > 0 /\ b > 0 => a + b > 0 /\ ab > 0.
Множество, в което се въвежда определено отношение на ред - нестрога (рефлексивно, антисиметрично и транзитивно) или строга (антирефлексивно и транзитивно) се нарича подредени. Ако законът за трихотомията е изпълнен, тогава множеството се нарича линейноподредени. Ако разгледаме не произволно множество, а някаква алгебрична система, например пръстен или поле, тогава за подреждането на такава система се въвеждат и изисквания за монотонност по отношение на операциите, въведени в тази система (алгебрична структура). Така поръчан ринг/полее ненулев пръстен/поле, в който е въведена линейна връзка (a > b), която удовлетворява две условия:
1) a > b => a + c > b + c;
2) a > b, c > 0 => a c > b c;
Теорема 1.Всеки разположен пръстен е подредена система (пръстен).
Всъщност, ако в пръстена се въведе отношението „да бъде по-голямо от 0“, тогава е възможно също така да се въведе отношение, по-голямо от за два произволни елемента, ако приемем, че
a > b a - b > 0.
Такава връзка е отношение на строг, линеен ред.
Тази връзка „по-голямо от“ е антирефлексивна, тъй като условието a > a е еквивалентно на условието a - a > 0, последното противоречи на факта, че a - a = 0 (според първото условие на разположения пръстен, елемент не може да бъде едновременно по-голям от 0 и равен на 0) . Следователно твърдението a > a е невярно за всеки елемент a, така че връзката е антирефлексивна.
Нека докажем транзитивност: ако a > b и b > c, тогава a > c. По дефиниция от условията на теоремата следва, че a - b > 0 и b - c > 0. Събирайки тези два елемента, по-големи от нула, отново получаваме елемент, по-голям от нула (според второто условие на разположения пръстен ):
a - b + b - c \u003d a - c\u003e 0.
Последното означава, че a > c. Така въведената релация е отношение на строг ред. Освен това, тази връзка е релация от линеен ред, тоест за множеството от естествени числа, теорема за трихотомията:
За всякакви две естествени числа е вярно едно и само едно от следните три твърдения:
Наистина (поради първото условие на разположения пръстен) за числото a - b е вярно едно и само едно от условията:
1) a - b > 0 => a > b
2) - (a - b) = b - a > 0 => b > a
3) a - b = 0 => a = b.
Свойствата за монотонност са валидни и за всеки разположен пръстен. Наистина ли
1) a > b => a - b > 0 => a + c - c - b > 0 => a + c > b + c;
2) a > b / \ c > 0 => a - b > 0 => (според второто условие на разположения пръстен) (a - b) c > 0 => ac - bc > 0 => ac > bc .
Така доказахме, че всеки разположен пръстен е подреден пръстен (подредена система).
За всеки разположен пръстен следните свойства също ще бъдат верни:
а) a + c > b + c => a > b;
б) a > b /\ c > d => a + c > b + d;
в) a > b / \ c< 0=>ac< bc;
Същите свойства важат и за други знаци.<, , .
Нека докажем, например, свойство (c). По дефиниция от условието a > b следва, че a - b > 0, а от условието c< 0 (0 >в) следва, че 0 - c > 0, а оттам и числото - c > 0, умножаваме две положителни числа (a - b) (-c). Резултатът ще бъде положителен и при второто условие на разположения пръстен, т.е.
(a - b) (-c) > 0 => -ac + bc > 0 => bc - ac > 0 => bc > ac => ac< bc,
Q.E.D.
г) aa = a 2 0;
Доказателство: Според първото условие на разположения пръстен, или a > 0, или –a > 0, или a = 0. Разгледайте тези случаи поотделно:
1) a > 0 => aa > 0 (според второто условие на разположения пръстен) => a 2 > 0.
2) –a > 0 => (–a)(–a) > 0, но по свойството на пръстена (–a)(–a) = aa = a 2 > 0.
3) a \u003d 0 => aa \u003d a 2 \u003d 0.
По този начин и в трите случая a 2 е или по-голямо от нула, или равно на 0, което просто означава, че a 2 ≥ 0 и свойството е доказано (обърнете внимание, че ние също доказахме, че квадратът на елемент от разположен пръстен е 0, ако и само ако самият елемент е 0).
д) ab = 0 a = 0 \/ b = 0.
Доказателство: Да приемем обратното (ab =0, но нито a, нито b са равни на нула). Тогава са възможни само две опции за a, или a > 0, или – a > 0 (опцията a = 0 е изключена от нашето предположение). Всеки от тези два случая се разделя на още два случая в зависимост от b (или b > 0, или – b > 0). Тогава са възможни 4 опции:
a > 0, b > 0 => ab > 0;
– a > 0, b > 0 => ab< 0;
a > 0, – b > 0 => ab< 0;
– a > 0 – b > 0 => ab > 0.
Както виждаме, всеки от тези случаи противоречи на условието ab = 0. Свойството е доказано.
Последното свойство означава, че разположеният пръстен е зона на цялост, което също е задължително свойство на подредените системи.
Теорема 1 показва, че всеки разположен пръстен е подредена система. Обратното също е вярно - всеки поръчан пръстен се намира. Всъщност, ако има връзка a > b в пръстена и всеки два елемента от пръстена са сравними един с друг, тогава 0 също е сравнимо с всеки елемент a, тоест или a > 0, или a< 0, либо а = 0, что почти точно совпадает с первым условием расположенного кольца, требуется только доказать, что условие а < 0 равносильно в упорядоченном кольце условию –a >0. За да докажем последното, прилагаме свойството монотонност на подредените системи: към дясната и лявата част на неравенството a< 0 прибавим –а, в результате чего получим требуемое.
Второто условие на разположения пръстен следва от свойствата на монотонност и транзитивност:
a > 0, b > 0 => a + b > 0 + b = b > 0 => a + b > 0,
a > 0, b > 0 => ab > 0b = 0 => ab > 0.
Теорема 2.Пръстенът от цели числа е подреден пръстен (подредена система).
доказателство:Нека използваме дефиниция 2 на пръстена от цели числа (виж 2.1). Според тази дефиниция всяко цяло число е или естествено число (числото n се дава като [
a > 0 a N
Тогава първото условие на разположения пръстен автоматично се изпълнява за цели числа: ако a е естествено, то е по-голямо от 0, ако a е обратното на естественото, тогава –a е естествено, тоест също е по-голямо от 0, възможен е и вариантът a = 0, който също прави истинска дизюнкция в първото условие на разположения пръстен. Валидността на второто условие на разположения пръстен следва от факта, че сборът и произведението на две естествени числа (цели числа по-големи от нула) отново е естествено число и следователно по-голямо от нула.
По този начин всички свойства на подредените пръстени автоматично се прехвърлят към всички цели числа. Освен това, за цели числа (но не и за произволно подредени пръстени) е валидна теоремата за дискретността:
Теорема за дискретността.Не може да се вмъкне цяло число между две съседни цели числа:
( a, x З) .
Доказателство: разгледайте всички възможни случаи за a и приемете обратното, тоест, че има x такова, че
а< x < a +1.
1) ако a е естествено число, тогава a + 1 също е естествено число. Тогава, според теоремата за дискретността за естествени числа, не може да се вмъкне естествено число x между a и a / = a + 1, тоест x във всеки случай не може да бъде естествено. Ако приемем, че x = 0, тогава нашето предположение е, че
а< x < a +1
ще ни доведе до условието а< 0 < a + 1 (здесь мы просто подставили х = 0), откуда видим, что а < 0, что противоречит тому, что а – натуральное. Если х не натуральное и не 0, но х – целое, значит –х – натуральное, тогда х < 0. При этом, согласно нашему предположению, а < x, что по свойству транзитивности опять приводит к тому, что а < 0, что невозможно, так как а – натуральное. Таким образом, для натуральных а утверждение а < x < a +1 всегда ложно, и теорема справедлива.
2) a = 0. Тогава a + 1 = 1. Ако условие а< x < a + 1, то мы получим 0 < x < 1, то есть с одной стороны х – натуральное (целое, большее нуля), а с другой стороны х меньше 1, что невозможно для натуральных чисел. Таким образом, для нуля наша теорема справедлива.
3) a е отрицателно (–a > 0), тогава a + 1 0. Ако a + 1< 0, то умножая условие а < x < a + 1 на –1 получим:
–а–1< – x < –a,
тоест стигаме до ситуацията, разгледана в първия случай (тъй като и -a-1, и -a са естествени), откъдето - x не може да бъде цяло число и следователно x не може да бъде цяло число. Ситуацията, когато a + 1 = 0 означава, че a = -1, т.е.
–1 < x < 0.
Умножавайки това неравенство по (–1), стигаме до случай 2. Така теоремата е валидна във всички ситуации.
Терем на Архимед.За всяко цяло число a и цяло число b > 0 съществува положително цяло число n, такова че a< bn.
За естествен а теоремата вече е доказана, тъй като условието b > 0 означава, че числото b е естествено. За a 0 теоремата също е очевидна, тъй като дясната страна на bn е естествено число, тоест също е по-голяма от нула.
В пръстена от цели числа (както във всеки разположен пръстен) можем да въведем концепцията за модул:
|a| = 
.
Валидни свойства на модула:
1) |a + b| |a| + |b|;
2) |a – b| |a| – |b|;
3) |a b| = |a| |b|.
доказателство: 1) Забележете, че от дефиницията е очевидно, че |a| е стойност, която винаги е неотрицателна (в първия случай |a| = a ≥ 0, във втория случай |a| = –a, но a< 0, откуда –а >0). Неравенствата |a| ≥ a, |a| ≥ –a (модулът е равен на съответния израз, ако е неотрицателен, и по-голям от него, ако е отрицателен). Подобни неравенства са валидни за b: |b| ≥ b, |b| ≥ -b. Събирайки съответните неравенства и прилагайки свойството (b) на подредените пръстени, получаваме
|a| + |b| ≥ a + b |a| + |b| ≥ – a – b.
Според дефиницията на модула
|a+b| = 
,
но и двата израза от дясната страна на равенството, както е показано по-горе, не надвишават |a| + |b|, което доказва първото свойство на модулите.
2) Нека заменим в първото свойство a с a - b. Получаваме:
|a – b + b| ≤ |a – b| + |b|
|a| ≤ |a – b| + |b|
Преместване |b| от дясната страна наляво с противоположен знак
|a| – | b| ≤ |a – b| =>|a-b| |a| – |b|.
Доказателството за свойство 3 е оставено на читателя.
задача:Решете уравнението в цели числа
2y 2 + 3xy - 2x 2 + x - 2y \u003d 5.
Решение: Факторизиране на лявата страна. За да направите това, ние представяме термина 3xy = – xy + 4xy
2y 2 + 3xy - 2x 2 + x - 2y \u003d 2y 2 - xy + 4xy - 2x 2 + x - 2y \u003d
Y (2y - x) + 2x (2y - x) - (2y - x) \u003d (y + 2x - 1) (2y - x).
По този начин нашето уравнение може да бъде пренаписано като
(y + 2x - 1) (2y - x) = 5.
Тъй като трябва да го решим в цели числа, x и y трябва да са цели числа, което означава, че факторите от лявата страна на нашето уравнение също са цели числа. Числото 5 от дясната страна на нашето уравнение може да бъде представено като продукт на цели фактори само по 4 начина:
5 = 51 = 15 = –5(–1) = –1(–5). Следователно са възможни следните опции:
1)
2)
3)
4)
Сред изброените системи само (4) има целочислено решение:
x = 1, y = -2.
Задачи за самостоятелно решаване
№ 2.4. За елементи a, b, c, d от произволно разположен пръстен, докажете свойствата:
а) a + c > b + c => a > b; б) a > b / \ c > d => a + c > b + d.
№ 2.5. Решете уравненията в цели числа:
|
а) y 2 - 2xy - 2x = 6; б) 2x 2 - 11xy + 12y 2 = 17; в) 35xy + 5x - 7y = 1; г) x 2 - 3xy + 2y 2 = 3; д) |
е) xy + 3x - 5y + 3 = 0; ж) 2xy - 3y 2 - 4y + 2x \u003d 2; з) xy 2 + x = 48; и) 1! +2! + 3! + … + n! = y 2 ; j) x 3 - 2y 3 - 4z 3 \u003d 0 |
;№ 2.6. Намерете четирицифрено число, което е точен квадрат и такова, че първите му две цифри са равни една на друга, а последните две цифри са равни една на друга.
№ 2.7. Намерете двуцифрено число, равно на сбора от неговите десетки и квадрата от неговите единици.
№ 2.8. Намерете двуцифрено число, което е равно на двойното произведение на неговите цифри.
№ 2.9. Докажете, че разликата между трицифрено число и число, записано със същите цифри в обратен ред, не може да бъде квадрат на естествено число.
№ 2.10. Намерете всички естествени числа, завършващи на 91, които след изтриване на тези цифри намаляват с цял брой пъти.
№ 2.11. Намерете двуцифрено число, равно на квадрата на неговите единици плюс куба на неговите десетки.
№ 2.12. Намерете шестцифрено число, започващо с числото 2, което се увеличава 3 пъти, като пренаредите това число до края на числото.
№ 2.13. Повече от 40, но по-малко от 48 цели числа са записани на дъската. Средноаритметичната стойност на всички тези числа е 3, средната аритметична на положителните е 4, а средната аритметична на отрицателните е 8. Колко числа са записани на черната дъска? Кое число е по-голямо, положително или отрицателно? Какъв е максималният възможен брой положителни числа?
№ 2.14. Може ли частното от трицифрено число и сбора от цифрите му да бъде 89? Може ли това коефициент да е равно на 86? Каква е максималната възможна стойност на това коефициент?
Федерална агенция за образование
Държавно образователно заведение за висше професионално образование
Вятски държавен университет за хуманитарни науки
Факултет по математика
Катедра Математически анализи и методи
преподаване на математика
Финална квалификационна работа
на тема: Гаусов пръстен от цели числа.
Завършено:
студент 5-та година
Факултет по математика
Гнусов В.В.
___________________________
Научен съветник:
старши преподавател на катедрата
алгебра и геометрия
Семенов A.N.
___________________________
Рецензент:
Кандидат по физика и математика наук, доцент
Катедра по алгебра и геометрия
Ковязина Е.М.
___________________________
Допуснат до защита във ВАС
Глава Отдел ________________ Вечтомов Е.М.
« »________________
Декан на факултета ___________________ Варанкина В.И.
Въведение.
Пръстен от цели комплексни числа
е открит от Карл Гаус и наречен Гаусиан на негово име.К. Гаус стигна до идеята за възможността и необходимостта от разширяване на концепцията за цяло число във връзка с търсенето на алгоритми за решаване на сравнения от втора степен. Той прехвърли концепцията за цяло число върху числа от формата
, където са произволни цели числа и е коренът на уравнението. На това множество К. Гаус е първият, който конструира теория за делимост, подобна на теорията за делимост на цели числа. Той обоснова валидността на основните свойства на делимостта; показа, че има само четири обратими елемента в пръстена от комплексни числа: ; доказа валидността на теоремата за деление с остатък, теоремата за единствеността на разлагането на прости множители; показа кои прости естествени числа ще останат прости в пръстена; открил естеството на простите цели комплексни числа.Теорията, разработена от К. Гаус, описана в неговия труд "Аритметични изследвания", е фундаментално откритие за теорията на числата и алгебрата.
За дипломната работа бяха поставени следните цели:
1. Развийте теорията за делимост в пръстена от числа на Гаус.
2. Открийте естеството на простите числа на Гаус.
3. Покажете приложението на гаусовите числа при решаване на обикновени диофантови задачи.
ГЛАВА 1. ДЕЛИМОСТ В ПРЪЩЕНА НА ГАУСОВИТЕ ЧИСЛА.
Помислете за набора от комплексни числа. По аналогия с множеството от реални числа в него може да се различи подмножество от цели числа. Наборът от числа на формата
, където ще се наричат комплексни цели числа или числа на Гаус. Лесно е да се провери дали аксиомите на пръстена са валидни за това множество. По този начин този набор от комплексни числа е пръстен и се нарича пръстен от гаусови цели числа . Нека го означим като , тъй като е продължение на пръстена от елемента: .Тъй като пръстенът от гаусови числа е подмножество от комплексни числа, тогава някои дефиниции и свойства на комплексните числа са валидни за него. Например за всяко число на Гаус
съответства на вектор, започващ в точка и завършващ в . следователно, модул Гаусовите числа са. Обърнете внимание, че в разглеждания набор изразът на подмодула винаги е неотрицателно цяло число. Следователно в някои случаи е по-удобно за използване нормата , тоест квадратът на модула. По този начин . Можем да различим следните свойства на нормата. За всякакви гаусови числа е вярно следното: (1) (2) (3) (4) (5) - множеството от естествени числа, тоест положителни цели числа.Валидността на тези свойства се проверява тривиално с помощта на модула. Мимоходом отбелязваме, че (2), (3), (5) са валидни и за всякакви комплексни числа.
Пръстенът на гаусовите числа е комутативен пръстен без делители 0, тъй като е подпръстен на полето на комплексните числа. Това предполага мултипликативната свиваемост на пръстена
, т.е. (6)1.1 ОБРАТНИ И ЛЕГИ ЕЛЕМЕНТИ.
Нека видим кои числа на Гаус ще бъдат обратими. Умножението е неутрално
. Ако е число на Гаус обратимо , тогава по дефиниция съществува такова, че . Преминавайки към нормите, съгласно свойство 3, получаваме . Но следователно тези норми са естествени. Следователно, чрез свойство 4, . Обратно, всички елементи от това множество са обратими, тъй като . Следователно числата с норма, равна на единица, ще бъдат обратими, тоест , .Както можете да видите, не всички числа на Гаус ще бъдат обратими. Ето защо е интересно да се разгледа въпросът за делимост. Както обикновено, ние казваме това
е разделен на, ако съществува такова, че За всякакви гаусови числа, както и обратими, свойствата са верни. (7) (8) (9) (10) , където (11) (12)(8), (9), (11), (12) се проверяват лесно. Валидността (7) следва от (2), а (10) следва от (6). Поради свойството (9), елементите на множеството
