Arifmetikaning Asosiy Teormasi Eng Katta Umumiy Bo'luvchi Eng Kichik Umumiy Karrali Reja

Arifmetikaning Asosiy Teormasi Eng Katta Umumiy Bo'luvchi Eng Kichik Umumiy Karrali


Reja:


1.Eng katta umumiy bo’luvchining ta’rifi.
2.Eng kichik umumiy karrali element tushunchasi.
3.Bo’linish alomati.
K— butunlik sohasi bo`lsin . a,b elеmеntlarni eng katta umumiy bo`luvchisi dеb shunday dK elеmеntni tushinamizki u quyidagi xossaga ega bo`ladi:
(i) d/a ; d/b
(i i) c/a; c/b=> c/d
va u d = ЭКУК(ab) yoki d = (ab) deb belgilaymiz. Ravshanki har bir ushbu d elеmеnt bilan assosiativlanadigan c elеmеnt ham (i) va (i i) xossaga ega bo`ladi. Aksincha , agar c va d , a va b elеmеntlarni EKUB bo`lsa, u holda c/d d/c bo`ladi ya'ni a va b assosiativlanadigan elеmеntlarni EKUB ni farqlamaymiz (a,b) va dеb olamiz .
Yuqoridagi ta'rifdan (i ) ( (i i) xossalarga quyidagi xossalarni ham qo`shish mumkin .
(i i i) (a b) = a  a /b
(i v) (a0) = a
(v) (ta , tb) = t( a b)
(v i) (( a b)c) = (a(b c))
Ushbu xossalarni tеkshirish hеch qanday qiyinchilik tug`dirmaydi. (vi) xossa EKUB tushinchasini chеkli sondagi elеmеntlar uchun ham qo`llash imkonini bеradi.
Elеmеitlеntlarni eng kichik umumiy bo`linuvchisi m = ЭКУК(аb) yoki m = ab dеb assosiativ aniqligida ya'ni quyidagi xossaga ega bo`lgan elеmеntga aytiladi:
a / m ; b / m (1)
a/c ; b / c  m /c (2)
Хususan с = аb deb olsak m / ab bo`ladi.
Teorema. К butunlik sohasini ab elementi uchun (аb) ab mavjud bo`lsin. U holda
а). аb = 0  a = 0 yoki b = 0.
b). ab 0 m=ab  ab = dm=> d = (ab) bo`ladi.
Isboti. а). аb ni ya`ni а va b elеmеntlarni EKUK ta'rifidan kеlib chiqadi.
b) xossani o`rinli ekanligini isbotlash uchun ab = dm tеnglikni qanoatlantiruvchi d ( i) va (ii) shartni qanoatlantirishini ko`rsatish kеrak.
Haqiqatan ham, (1) dan m = aa<sub>1</sub> m = bb<sub>1</sub> bo`ladi, demak ab = dm = daa₁ buni a ga qisqartirib b = dа₁ tenglikka , ya`ni d \ b kelamiz, xuddi shunday ab = md = dbb<sub>1</sub>a = db<sub>1</sub> ya`ni d / a ga kelamiz.
а = fa₂ b = fb₂ bo`lsin. c = fa<sub>2</sub>b<sub>2</sub> deb olaylik. U holda,c = ab<sub>2</sub> = ba<sub>2</sub> a va b elеmеntlarni bo`linuvchisi bo`ladi. (2) xossaga ko`ra с = с₁m bunda с₁К biror element, bu erdan
fc₁m = fc = f²a₂b₂ = ab = dm ya`ni d = fс<sub>1</sub> va f \ d bo`ladi. Demak,
( ii) tenglikka keldik.
K-faktorial halqa bo`lsin. P-(pa) orqali K dagi barcha tub elеmеntlar to`plamini bеlgilaymiz. a,bК elementlarni Р ni elеmеntlari orqali yoyilmasini ko`raylik:
 (3)
u / 1v / 1 k<sub>i</sub>  0, l<sub>i</sub>  0 p<sub>i</sub>P
bu erda ba`zi k_i yoki l_i lar nolga teng bo`lishi mumkin.
Bo`linish alomati. аbК elеmеntlar K faktorial halqada (3) ko`rinishda yozilgan bo`lsin. U holda quyidagi faktlar o`rinli.

1) а / b faqat va faqat, agarda k_i  l_i i = 1 2 ...., r

2) (ab) = p_i^s₁p₂^s₂......p_r^s_r bunda s_i = min{k_il_i} i = 1 2, ...,r
3) [ab] = p₁^t₁p₂^t₂...p_r^t_r bunda t_i = max{k_il_i} i =1 2,.....,r
Shunday qilib, s_i sifatida k_i va l_i darajalaridan eng kichigini olish kerak, t_i sifatida esa eng kattasini. Xususan аbК elementlar o`zaro tub ya`ni (аb) =1 agarda faqat va faqat ularni tub ko`paytuvchilari har xil bo`lsa. Bu bo`linish bеlgisini amaliyotda qo`llash (3) ko`rinishda yoyilmani topish qiyinchiligi bilan bog`liq.
K= Z holda ham ko`p qiyinchiliklar tugiladi. Masalan bеrilgan n sondan kichik tub sonlarni aniqlash.
Quyida biz ko`ramizki faktorial halqada аb va аb] larni topishni soda usullaru mavjud.
Yilda matematika, eng katta umumiy bo'luvchi (gcd) ikki yoki undan ko'p butun sonlarnolga teng bo'lmagan eng katta musbat butun son ajratadi butun sonlarning har biri. Ikki butun son uchun x, y, ning eng katta umumiy bo'luvchisi x va y bilan belgilanadi  . Masalan, 8 va 12 gcd 4 ga teng, ya'ni  .^[1][2][3]
"Eng katta umumiy bo'luvchi" nomida "eng katta" sifatdoshi "eng yuqori" bilan, "bo'luvchi" so'zi "omil" bilan almashtirilishi mumkin, shunda boshqa ismlar ham kiradi eng katta umumiy omil (gcf), va boshqalar.^[4][5][6][7] Tarixiy jihatdan, xuddi shu kontseptsiyaning boshqa nomlari ham kiritilgan eng katta umumiy o'lchov.^[8]
Ushbu tushunchani polinomlarga kengaytirish mumkin (qarang Polinomning eng katta umumiy bo'luvchisi) va boshqalar komutativ halqalar (qarang § komutativ halqalarda quyida).
Aslida, eng katta umumiy bo'linuvchilarni aniqlash orqali hisoblash mumkin asosiy faktorizatsiya Ikkala raqam va taqqoslash omillari, quyidagi misolda bo'lgani kabi: gcd (18, 84) ni hisoblash uchun biz 18 = 2 · 3 ning asosiy faktorizatsiyasini topamiz.² va 84 = 2² · 3 · 7, va ikkita ifodaning "qoplanishi" 2 · 3 ga teng bo'lganligi sababli, gcd (18, 84) = 6. Amalda bu usul faqat kichik sonlar uchun amal qiladi; umuman asosiy faktorizatsiyani hisoblash juda uzoq davom etadi. Bu erda tasvirlangan yana bir aniq misol Venn diagrammasi. Aytaylik, 48 va 180 ning eng katta umumiy bo'luvchisini topish kerak edi. Birinchidan, ikkita sonning asosiy omillarini toping:
48 = 2 × 2 × 2 × 2 × 3,
180 = 2 × 2 × 3 × 3 × 5.
Ularning ikkala umumiy "2" va "3":
^[12]
Eng kam umumiy ko'paytma = 2 × 2 × (2 × 2 × 3) × 3 × 5 = 720
Eng katta umumiy bo'luvchi = 2 × 2 × 3 = 12.
Juda samarali usul bu Evklid algoritmi, ishlatadigan a bo'linish algoritmi kabi uzoq bo'linish ikki raqamning gcd ham ularning farqini bo'lishini kuzatish bilan birgalikda.
Masalan, gcd (48,18) ni hisoblash uchun 48 ni 18 ga bo'ling, natijada 2 va qolgan 12 ga ega bo'ling. Keyin 18 ga 12 ga bo'ling va 1 ga va 6 ga qoldiq oling. Keyin 12 ni 6 ga bo'ling. 0 ning qoldig'ini olish uchun, bu 6 gcd ekanligini anglatadi. Bu erda, biz har bir qadamda keltirilgan ko'rsatkichni e'tiborsiz qoldirdik, faqat qolgan qismi 0 ga etganida, biz javobga kelganligimizni bildirdik. Rasmiy ravishda algoritm quyidagicha tavsiflanishi mumkin:

,
qayerda
.
Agar argumentlar ikkalasi ham noldan katta bo'lsa, u holda algoritmni oddiy elementlarda quyidagicha yozish mumkin:
,
agar a > b
agar b > a

Lehmerning GCD algoritmi

Asosiy maqola: Lehmerning GCD algoritmi
Lexmer algoritmi Evklid algoritmi tomonidan ishlab chiqarilgan dastlabki kvotentlarni faqat dastlabki bir necha raqamlar asosida aniqlash mumkin degan kuzatuvga asoslanadi; bu a dan katta bo'lgan raqamlar uchun foydalidir kompyuter so'zi. Aslida, bir kishi boshlang'ich raqamlarni ajratib oladi, odatda bitta yoki ikkita kompyuter so'zini hosil qiladi va Evklid algoritmlarini ushbu kichik sonlar ustida ishlaydi, chunki bu kvotalar asl sonlar bilan olinadiganlar bilan bir xil bo'lishi kafolatlanadi. Ushbu takliflar asl sonlarni kamaytirish uchun bir vaqtning o'zida ishlatish uchun 2 dan 2 gacha bo'lgan kichik matritsaga (ya'ni bitta so'zli tamsayılar matritsasiga) yig'iladi. Ushbu jarayon raqamlar ikkilik algoritm (quyida ko'rib chiqing) samaraliroq bo'lgan hajmga ega bo'lguncha takrorlanadi.
Ushbu algoritm tezlikni yaxshilaydi, chunki u juda katta sonlarda bajariladigan operatsiyalar sonini kamaytiradi va aksariyat amallar uchun apparat arifmetikasi tezligidan foydalanishi mumkin. Darhaqiqat, kvotentsiyalarning aksariyati juda kichik, shuning uchun Evklid algoritmining adolatli sonli bosqichlari bitta so'zli butun sonlarning 2-dan 2 gacha matritsasida to'planishi mumkin. Lemmer algoritmi juda katta miqdordagi qismga duch kelganda, u evklid algoritmining bitta takrorlanishiga qaytishi kerak. Evklid bo'linishi katta raqamlar.
Gcd sifatida (a,b) = gcd (b,a), agar a < b keyin almashinish a va b. Raqam v = a − b ijobiy va kichikroq a. Bo'linadigan har qanday raqam a va b ham bo'linishi kerak v shuning uchun har bir umumiy bo'luvchi a va b ning umumiy bo'luvchisi hamdir b va v. Xuddi shunday, a = b + v ning har bir umumiy bo'luvchisi b va v ning umumiy bo'luvchisi hamdir a va b. Shunday qilib, ikki juft (a, b) va (b, v) bir xil umumiy bo'luvchilarga ega va shuning uchun gcd (a,b) = gcd (b,v). Bundan tashqari, kabi a va b ikkalasi ham g'alati, v teng, jarayon juftlik bilan davom etishi mumkin (a, b) kichikroq raqamlar bilan almashtirildi (v/2, b) gcd-ni o'zgartirmasdan.
Yuqoridagi bosqichlarning har biri kamida bittasini kamaytiradi a va b ularni manfiy bo'lmagan holda qoldirish va shunga o'xshashlarni faqat sonli marta takrorlash mumkin. Shunday qilib, jarayon oxir-oqibat tugaydi a = b, to'xtatish ishi. Keyin gcd bo'ladi a × 2^d.
Misol: (a, b, d) = (48, 18, 0) → (24, 9, 1) → (12, 9, 1) → (6, 9, 1) → (3, 9, 1) → (3, 3, 1); asl gcd, shuning uchun 2 ning 6 mahsulotidir^d = 2¹ va a= b= 3.
Ikkilik GCD algoritmini ikkilik kompyuterlarda amalga oshirish ayniqsa oson. Uning hisoblash murakkabligi bu

Hisoblash murakkabligi odatda uzunlik bo'yicha beriladi n kirish. Mana, bu uzunlik  va murakkablik shundaydir
.

Boshqa usullar

yoki Tomae funktsiyasi. Tugatish pastki qismida ko'rsatiladi ellipslar (ya'ni juda yuqori zichlik tufayli nuqta tashlab qo'yilgan).
Agar a va b ikkalasi ham nolga teng, eng katta umumiy bo'luvchi a va b yordamida hisoblash mumkin eng kichik umumiy ko'plik (lcm) ning a vab:,
lekin odatda lcm gcd dan hisoblanadi.
Foydalanish Toma vazifasi f,
uchun umumlashtiradigan a va b ratsional sonlar yoki mutanosib haqiqiy raqamlar.
Keyt Slavin buni g'alati deb ko'rsatdi a ≥ 1:
bu kompleks uchun baholanishi mumkin bo'lgan funktsiya b.^[13] Volfgang Shramm buni ko'rsatdi

bu butun funktsiya o'zgaruvchida b barcha musbat sonlar uchun a qayerda v_d(k) Ramanujan summasi.^[14]

Murakkablik

The hisoblash murakkabligi eng katta umumiy bo'luvchilarni hisoblash keng o'rganilgan.^[15] Agar kimdir Evklid algoritmi ko'paytirish va bo'lishning elementar algoritmlari, ko'pi bilan ikkita butun sonning eng katta umumiy bo'luvchisini hisoblash. n bitlar bu  Bu shuni anglatadiki, eng katta umumiy bo'luvchini hisoblash doimiy koeffitsientga qadar ko'paytma bilan bir xil murakkablikka ega.
Ammo, agar ro'za bo'lsa ko'paytirish algoritmi ishlatilsa, murakkablikni yaxshilash uchun evklid algoritmini o'zgartirish mumkin, lekin eng katta umumiy bo'luvchini hisoblash ko'paytmaga nisbatan sekinroq bo'ladi. Aniqrog'i, ning ikkita butun sonini ko'paytirish bo'lsa n bitlar vaqtni oladi T(n), keyin eng katta umumiy bo'luvchi uchun eng tez ma'lum bo'lgan algoritm murakkablikka ega  Bu shuni anglatadiki, eng tez ma'lum bo'lgan algoritmning murakkabligi bor 
Avvalgi murakkabliklar odatdagidek amal qiladi hisoblash modellari, xususan multitassali Turing mashinalari va tasodifiy kirish mashinalari.
Eng katta umumiy bo'linuvchilarning hisob-kitobi shu bilan echilishi mumkin bo'lgan muammolar sinfiga tegishli kvazilinear vaqt. Fortiori, mos keladigan qaror muammosi sinfga tegishli P polinom vaqtida echiladigan masalalar. GCD muammosi ma'lum emas Bosimining ko'tarilishiva shuning uchun ma'lum bir yo'l yo'q parallellashtirmoq bu samarali; ham emasligi ma'lum emas P tugallangan, bu GCD hisobini samarali ravishda parallel qilish mumkin emasligini anglatadi. Shallkross va boshq. bog'liq muammo (Evklid algoritmi paytida paydo bo'lgan qolgan ketma-ketlikni aniqlaydigan EUGCD) NC muammosiga teng bo'lganligini ko'rsatdi. butun sonli chiziqli dasturlash ikkita o'zgaruvchiga ega; agar har qanday muammo bo'lsa Bosimining ko'tarilishi yoki shunday P tugallangan, ikkinchisi ham.^[16] Beri Bosimining ko'tarilishi o'z ichiga oladi NL, GCD-ni hisoblash uchun kosmik tejamkor algoritm, hattoki nondeterministik Turing mashinalari uchun ham mavjudmi, noma'lum.
Adabiyotlar


1.Кострикин А.И. Введение в алгебру.Учебник.М.Наука,1977г.
2.Ҳожиев Ж., Файнлейб.Ф.С. Алгебра ва сонлар назарияси курси. Т. 2001 й.
3.Курош Ф.Г. Олий алгебра курси. Т.Укитувчи . 1976 й..
4.Фадеев Д.К.,Соминский И.С.Сборник задач по высшей алгебре. М.Наука .1976 г.
5. Гелфанд И.М. Лекции по линейной алгебре. http://www.mcmee.ru, http://lib.mexmat. ru.
6. Курош А.Г. Курс высшей алгебре http://www.mcmee.ru, http://lib.mexmat. ru.