4. mavzu bo`linish alomatlari. Ekub va ekuk. Qoldiqli bo`lish. Taqqoslamalar

EKUB va EKUK.
a, bN sonlarning har biri bo‘linadigan sonshusonlarningumumiybo‘luvchisideyiladi.Masalan,a=12;b=14 bo‘lsin. Bu sonlarning umumiy bo‘luvchilari 1; 2 bo‘ladi.Agar a va b sonlarning umumiybo‘luvchisi faqat 1bo‘lsa, u holda avabsonlaro‘zarotubsonlardeyiladi.a,b  Nsonlarumumiybo‘luvchilariningengkattasishusonlarningengkattaumumiybo‘luvchisideyiladivaB(a;b)orqalibelgilanadi.Masalan,B(12;14)=2.O‘zaro tub sonlar uchun B(a;b)=1.
a,b  Nsonlarningumumiykarralisideb,agaham,bgahambo‘linuvchinaturalsongaaytiladi.avabsonlarningumumiykarralisiichidaengkichigimavjudbo‘lib,uavabsonlariningengkichikumumiykarralisideyiladivaK(a;b)orqalibelgilanadi.Masalan,K(6;8)=24.
Naturalsonlarningkanonikyoyilmalaribirnechtasonningeng kattaumumiy bo‘luvchi va eng kichikumumiy karralilarinitopishdahamqo‘llaniladi.a, b va csonlari uchun quyidagicha bo‘lsin: , , .t_k=min{_k, _k, _k}vas_k=max{_k, _k, _k} deb olamiz.U holda: bo‘ladi.
1-misol. 126=2∙3²∙7,540=2²∙3³∙5va630=2∙3²∙5∙7bo‘lganiuchun:B(126;540;630)=2∙32=18,K(126; 540; 630)=2²∙3³∙5∙7=3780 bo‘ladi.
a,b  Nva a ≥ bbo‘lsin.Uholdaavabsonlariuchun a = b∙q + r(0  r < b)tengliko‘rinlibo‘ladiganqN,rNsonlarimavjud va q, r sonlaribir qiymatli aniqlanadi.
1-teorema. Agar a ≥ bbo‘lib, a =b∙q + r (0  r < b) bo‘lsin.avabsonlariningbarchaumumiybo‘luvchilaribva r sonlarining ham umumiy bo‘luvchilari bo‘ladi va, aksincha,bvarsonlariningbarchaumumiy bo‘luvchilariavabsonlarininghamumumiybo‘luvchilaribo‘ladi.
Natija-1: a = b ∙ q + r bo‘lsa, B(a;b) = B(b;r) bo‘ladi.
Natija-2:AgarB(p,q) = 1bo‘lib,asonihampga,hamqgabo‘linsa,up∙q gabo‘linadi
T eoremavauningnatijasiasosida,B(a; b)nitopishning Evklid algoritmi deb ataluvchi quyidagiusuliga egabo‘lamiz.a,b N,a > bbo‘lsin.anibgaqoldiqlibo‘lamiz:a = b ∙ q₁ + r₂, 0 r₂2= 0 bo‘lsa, B(a;b)=b bo‘ladi.r₂ 0 bo‘lsa, natijagako‘raB(a;b)=B(b;r₂)bo‘ladi.bnir₂gaqoldiqlibo‘lamiz:b=r₂ ∙ q₂+ r₃,0 r₃< r₂.Agar r₃=0 bo‘lsa,B(a;b)=B(b;r₂)= r₂bo‘ladi.r₃ 0 bo‘lsa,natijaga ko‘ra B(a;b)=B(b;r₂)=B(r₂;r₃)bo‘ladi.r₂nir₃gaqoldiqlibo‘lamiz:r₂=r₃ ∙ q₃+ r₄,0r₄3.Agar r₄= 0bo‘lsa,B(a;b)=B(b;r₂)=B(r₂;r₃)= r₃bo‘ladi.r₄ 0 bo‘lsa, natijaga ko‘ra B(a; b)=B(b; r₂)=B(r₂; r₃)=B(r₃; r₄)bo‘ladi vayuqoridagi jarayonni davomettiramiz.Bujarayondaqoldiqlarnaturalsonlarbo‘lib,kichiklashibboradi:r₂> r₃> r₄>....Shusababli,birorqadamdanso‘ngqoldiq0 gatengbo‘ladi,ya’nibiror nnaturalson uchun r_n+1= 0 bo‘ladi va r_n-1= r_n∙ q_n+ 0 == r_n∙q_ntenglikbajariladi.BuholdaB(r_n-1;r_n)var_n 0,r_n-10,r_n-2 0,...,r₂ 0munosabatlargaegabo‘lamiz.Yuqoridagimulohazalardan,B(a; b)=B(b; r₂)=B(r₂;r₃)=B(r₃; r₄)=...=B(r_{n -1};r_n) = r_nbo‘lishikelibchiqadi.
Shundayqilib,B(a;b)nitopishuchunqoldiqlibo‘lishjarayoni 0 gateng qoldiq hosil bo‘lguncha davom ettiriladi, 0 danfarqliengoxirgiqoldiq,avabsonlariningengkattaumumiybo‘luvchisibo‘ladi.
2-misol.B(1515;600)nitopish uchun qoldiqlarni hiosblaymiz (o‘ngdagi rasm).Demak, B(1515;600)=15
Ikkitadanortiqa₁, a₂,...,a_nsonlariningengkattaumumiybo‘luvchisivaengkichikumumiykarralisinitopishquyidagichaamalgaoshiriladi.B(a₁,a₂) = d₂;B(d₂,a₃) = d₃, ... ,B(d_n-1,a_n) = d_n.Bundan:d_n= B(a₁, a₂,...,a_n) bo‘ladi. Xuddi shunday K(a₁,a₂) = k₂; K(k₂,a₃) = k₃, ... , K(k_n-1,a_n) = k_n.Bundan: k_n= K(a₁, a₂,...,a_n) bo‘ladi.
Endi B (a;b) va K (a;b) orasidagi bog‘lanishni ko‘ramiz.