Кіріспе
Коммутативті сақина Евклидтік бөлініспен
In mathematics, more specifically in ring theory, a Euclidean domain (also called a Euclidean ring) is an integral domain that can be endowed with a Euclidean function which allows a suitable generalization of the Euclidean division of integers. This generalized Euclidean algorithm can be put to many of the same uses as Euclid's original algorithm in the ring of integers: in any Euclidean domain, one can apply the Euclidean algorithm to compute the greatest common divisor of any two elements. In particular, the greatest common divisor of any two elements exists and can be written as a linear combination
of them (Bézout's identity). Also every ideal in a Euclidean domain is principal, which implies a suitable generalization of the fundamental theorem of arithmetic: every Euclidean domain is a unique factorization domain. It is important to compare the class of Euclidean domains with the larger class of principal ideal domains (PIDs). An arbitrary PID has much the same "structural properties" of a Euclidean domain (or, indeed, even of the ring of integers), but when an explicit algorithm for Euclidean division is known, one may use the Euclidean algorithm and extended Euclidean algorithm to compute greatest common divisors and Bézout's identity. In particular, the existence of efficient algorithms for Euclidean division of integers and of polynomials in one variable over a field is of basic importance in computer algebra. So, given an integral domain R, it is often very useful to know that R has a Euclidean function: in particular, this implies that R is a PID. However, if there is no "obvious" Euclidean function, then determining whether R is a PID is generally a much easier problem than determining whether it is a Euclidean domain. Euclidean domains appear in the following chain of class inclusions:
Математикада, әсіресе сақиналар теориясында, Евклидтік домен (сонымен қатар Евклидтік сақина деп аталады) – бүтін сандардың Евклидтік бөлінісін жалпылауға мүмкіндік беретін Евклидтік функциямен жабдықталған интегралдық домен. Бұл жалпыланған Евклидтік алгоритмді бүтін сандар сақинасындағы Евклидтің бастапқы алгоритмі сияқты көптеген мақсаттарда қолдануға болады: кез келген Евклидтік доменде, кез келген екі элементтің ең үлкен ортақ бөлгішін есептеу үшін Евклидтік алгоритмді қолдануға болады. Атап айтқанда, кез келген екі элементтің ең үлкен ортақ бөлгіші болады және оларды сызықтық комбинация түрінде жазуға болады (Безоу тождестігі). Сондай-ақ, Евклидтік домендегі әрбір идеал негізгі болады, бұл арифметиканың негізгі теоремасының тиімді жалпылануын білдіреді: әрбір Евклидтік домен – бірегей факторлау домені. Евклидтік домендер класын негізгі идеалдық домендер (PID) класымен салыстыру маңызды. Кез келген PID, Евклидтік доменнің (немесе тіпті бүтін сандар сақинасының) ұқсас «құрылымдық қасиеттеріне» ие, бірақ Евклидтік бөлу үшін нақты алгоритм белгілі болған жағдайда, ең үлкен ортақ бөлгіштерді және Безоу тождестігін есептеу үшін Евклидтік алгоритмді және кеңейтілген Евклидтік алгоритмді қолдануға болады. Атап айтқанда, бүтін сандарды және бір айнымалыдағы полиномдарды Евклидтік бөлудің тиімді алгоритмдерінің болуы компьютерлік алгебрада маңызды рөл атқарады. Сондықтан, R интегралды домен болған жағдайда, R-дің Евклидтік функциясы бар екенін білу өте пайдалы: атап айтқанда, бұл R-дің PID екенін білдіреді. Дегенмен, егер «көзге көрінетін» Евклидтік функция болмаса, R-дің PID екенін анықтау, әдетте, Евклидтік домен екенін анықтаудан гөрі әлдеқайда оңай мәселе. Евклидтік домендер келесі кластық кіріктірулер тізбегінде кездеседі:
In mathematics, more specifically in ring theory, a Euclidean domain (also called a Euclidean ring) is an integral domain that can be endowed with a Euclidean function which allows a suitable generalization of the Euclidean division of integers. This generalized Euclidean algorithm can be put to many of the same uses as Euclid's original algorithm in the ring of integers: in any Euclidean domain, one can apply the Euclidean algorithm to compute the greatest common divisor of any two elements. In particular, the greatest common divisor of any two elements exists and can be written as a linear combination
of them (Bézout's identity). Also every ideal in a Euclidean domain is principal, which implies a suitable generalization of the fundamental theorem of arithmetic: every Euclidean domain is a unique factorization domain. It is important to compare the class of Euclidean domains with the larger class of principal ideal domains (PIDs). An arbitrary PID has much the same "structural properties" of a Euclidean domain (or, indeed, even of the ring of integers), but when an explicit algorithm for Euclidean division is known, one may use the Euclidean algorithm and extended Euclidean algorithm to compute greatest common divisors and Bézout's identity. In particular, the existence of efficient algorithms for Euclidean division of integers and of polynomials in one variable over a field is of basic importance in computer algebra. So, given an integral domain R, it is often very useful to know that R has a Euclidean function: in particular, this implies that R is a PID. However, if there is no "obvious" Euclidean function, then determining whether R is a PID is generally a much easier problem than determining whether it is a Euclidean domain. Euclidean domains appear in the following chain of class inclusions:
Қасиеттері
R домен және R-де f Евклид функциясы болсын: R – негізгі идеалдық домен (PID). Шындығында, егер I – R-дің нөлдік емес идеалы болса, онда I \ {0} жиынындағы f(a)-ның ең кіші мәніне ие кез келген a элементе I-нің генераторы болады. Осыған сәйкес, R сондай-ақ бірегей факторлау домені және Нотер сақинасы болып табылады. Жалпы негізгі идеалдық домендерге қатысты, факторлаудың болуы (яғни R атомдық домен) Евклид домендерінде дәлелдеу өте оңай: егер Евклид функциясы f (EF2) шартын орындаса, онда x-ті f(x)-тан артық бірлік емес факторларға жіктеу мүмкін емес, сондықтан x-тен бастап, қайта-қайта жіктелетін факторларды ыдырату, әрине, өзіндік элементтерге жіктеуге әкеледі. Егер f (EF2) шартын орындаса, онда керісі де дұрыс, және f өзінің ең кіші мәнін дәл R-дің өзіндік элементтерінде алады. Егер Евклидтік бөлу алгоритмдік болса, яғни, бөліндіні және қалдықты есептеуге алгоритм болса, онда кеңейтілген Евклид алгоритмі бүтін сандардағыдай анықталады. Егер Евклид домені өріс болмаса, онда оның келесі қасиетке ие a элементе бар: кез келген x элементі a-ға бөлінбесе, онда x = ay + u түрінде жазылады, мұнда u – бірлік, ал y – элемент. Бұл a-ны f(a) мүмкіндігінше кішірек бірлік емес деп таңдау арқылы жүзеге асырылады. Бұл ерекше қасиет кейбір негізгі идеалдық домендердің Евклид домендері еместігін көрсету үшін қолданылуы мүмкін, өйткені барлық PID-лерде бұл қасиет жоқ. Мысалы, d = −19, −43, −67, −163 үшін, сақинасы бүтін сандар Евклид емес PID болып табылады, бірақ d = −1, −2, −3, −7, −11 жағдайлары Евклид. Алайда, Q-ның көптеген шекті кеңейтулерінде тривиальды сынып тобы бар бүтін сандар сақинасы Евклидтік болады (ол міндетті түрде өріс нормасының абсолюттік мәніне қатысты емес; төмендегіге қараңыз). Егер кеңейтілген Риман гипотезасы орындалса, егер K – Q-ның шекті кеңейтімі болса және K-ның бүтін сандар сақинасы шексіз көп бірліктері бар PID болса, онда бүтін сандар сақинасы Евклидтік болады. Атап айтқанда, бұл тривиальды сынып тобы бар толық нақты квадраттық сандар өрістеріне қатысты. Сонымен қатар (ERH болмай тұрып), егер K өрісі Q-ның Галуа кеңейтімі болса, тривиальды сынып тобы және бірлік ранкі үштен үлкен болса, онда бүтін сандар сақинасы Евклидтік болады. Бұл сандар өрісі Q-ға қатысты Галуа болса, оның сынып тобы тривиальды болса және кеңейту 8-ден жоғары дәрежелі болса, онда бүтін сандар сақинасы міндетті түрде Евклидтік болады.
R is a principal ideal domain (PID). In fact, if I is a nonzero ideal of R then any element a of I \ {0} with minimal value (on that set) of f(a) is a generator of I. As a consequence R is also a unique factorization domain and a Noetherian ring. With respect to general principal ideal domains, the existence of factorizations (i. e., that R is an atomic domain) is particularly easy to prove in Euclidean domains: choosing a Euclidean function f satisfying (EF2), x cannot have any decomposition into more than f(x) nonunit factors, so starting with x and repeatedly decomposing reducible factors is bound to produce a factorization into irreducible elements. Any element of R at which f takes its globally minimal value is invertible in R. If an f satisfying (EF2) is chosen, then the converse also holds, and f takes its minimal value exactly at the invertible elements of R.
If Euclidean division is algorithmic, that is, if there is an algorithm for computing the quotient and the remainder, then an extended Euclidean algorithm can be defined exactly as in the case of integers. If a Euclidean domain is not a field then it has an element a with the following property: any element x not divisible by a can be written as x = ay + u for some unit u and some element y. This follows by taking a to be a non unit with f(a) as small as possible. This strange property can be used to show that some principal ideal domains are not Euclidean domains, as not all PIDs have this property. For example, for d = −19, −43, −67, −163, the ring of integers of is a PID which is not Euclidean, but the cases d = −1, −2, −3, −7, −11 are Euclidean. However, in many finite extensions of Q with trivial class group, the ring of integers is Euclidean (not necessarily with respect to the absolute value of the field norm; see below). Assuming the extended Riemann hypothesis, if K is a finite extension of Q and the ring of integers of K is a PID with an infinite number of units, then the ring of integers is Euclidean. In particular this applies to the case of totally real quadratic number fields with trivial class group. In addition (and without assuming ERH), if the field K is a Galois extension of Q, has trivial class group and unit rank strictly greater than three, then the ring of integers is Euclidean. An immediate corollary of this is that if the number field is Galois over Q, its class group is trivial and the extension has degree greater than 8 then the ring of integers is necessarily Euclidean.