Еkub va ekukni topish. Evklid algoritmi

Еkub va ekukni topish. Evklid algoritmi

Reja:

1. 
   Eng katta umumiy bo‘luvchi
   
2. 
   Eng kichik umumiy karrali
   
3. 
   EKUKlarini toppish
   
4. 
   Evklid algoritmi
   

Eng katta umumiy bo‘luvchi (EKUB) va eng kichik umumiy karrali (EKUK),xossalari.

Evklid algoritmi.Chekli zanjir kasrlar, munosib kasrlar, xossalari. Ta’rif. 𝑎 va 𝑏 butun
sonlarning ikkalasiga ham bo’linadigan son shu sonlarningumumiy bo’luvchisi deyiladi.
Ta’rif. 𝑎 va 𝑏 natural sonlar umumiy bo’luvchilarining eng kattasi shu sonlarningeng kata
umumiy bo’luvchisi (EKUB) deyiladi, uni (𝑎, 𝑏) ko’rinishda belgilanadi. Ta’rif. Agar (𝑎, 𝑏)
= 1 bo’lsa, u holda 𝑎 va 𝑏 natural sonlar o’zaro tub sonlardeyiladi. Teorema(qoldiqli bo’lish
haqidagi). Har qanday 𝑎 ∈ 𝑍, 𝑏 ∈ 𝑁 uchun shundayyagona 𝑞 ∈ 𝑍 va yagona manfiymas 𝑟
butun son topiladiki, ular uchun ushbu𝑎 = 𝑏𝑝 + 𝑟 0 ≤ 𝑟 < 1. q ,q1 sonlar butun bo’lgani
uchunq= q1 , r1 = r ga ega bo’lamiz. Izoh. Yuqoridagi q son to’liqsiz bo’linma, r son esa a ni
b ga bo’lganda hosilbo’lgan qoldiq deb yuritiladi. Natija. a sonining biror bo’luvchisiga mos
bo’lgan bo’linma yagonadir.a va b sonlarning ikkalasini ham bo’ladigan son shu sonlarning
umumiy bo’luvchisideyiladi. D(a, b) orqali a va b sonlarning umumiy bo’luvchilari
to’plamini belgilaymiz.Ravshanki, barcha a va b uchun D(a, b) to’plam yuqoridan
chegaralangan. Shuninguchun a va b sonlarining umumiy bo’luvchilari ichida eng kattasi
mavjud bo’lib, shusonlarning eng katta umumiy bo’luvchisi deyiladi va (a, b) orqali
belgilanadi. Xossalar.a)ptub son bo’lsa, ixtiyoriy naturalmson uchun( , ) p m p yoki( , ) 1
p m bo’ladi;b)d m n m dm n dn    ( , ), ', 'bo’lsa , u holda( ', ') 1 m n bo’ladi;c)d m
n m d m n d n    ( , ), ' ', ' 'va( ', ') 1 m n bo’lsa , u holdad d 'bo’ladi;d) agar1 21
2 ...k m p p pk  va1 21 2 ...kk n p p p  bo’lsa ( bu yerda1 2 , ... k p p p –
tub sonlar,, 0  i i ), u holdamin( , ) min( , ) 1 1 2 2 min( , )1 2 ( , ) ... k k m n p p pk
    tenglik o’rinli.e) a va b sonlarining eng katta umumiy bo’luvchisi shu
sonlarning barcha umumiybo’luvchilariga bo’linadi. Teorema. Agar a soni b sonidan kichik
bo’lmasdan, a = bq + r (0  r< b) bo’lsa,u holda (a, b)= (b, r) bo’ladi.Isboti. D(a, b) orqali a
va b sonlarning umumiy bo’luvchilari to’plamini belgilaymiz. a= bq + r (0  r< b) va c 
D(a, b) bo’lsin. Demak, r= a – bq soni c soniga bo’linadi,ya’ni c  D(b, r). Aksincha, c 
D(b, r) bo’lsa, u holda a = bq + r soni c ga bo’linadi,ya’ni c  D(a, b ). Demak, agar a soni
b sonidan katta bo’lmasdan, a = bq + r (0  rustma–ust tushadi. Bundan ularning engkatta elementlari o’zaro teng bo’lishi kelib chiqadi,

ya’ni (a, b)= (b, r). Izoh. Barcha a va b nolga teng bo’lmagan sonlar uchun a,b(a>b>0)

sonlar uchunqoldiqli bo’lish haqida teoremaga ko’ra:a = bq1 + r1.Agar r1 = 0 bo’lsa, u
holda (a, b) = b.Agar r1  0 bo’lsa, u holda b = r1q2 + r2.Agar r2 = 0 bo’lsa, u holda
jarayonni to’xtatamiz, aks holda (ya’ni r2  0) davomettiramiz : r1 = r2q3 + r3.b > r1 > r2
> r3 > . . . >0tengsizliklardan jarayon qoldiq nolga aylanganda tugashi kelib chiqadi.Demak,
quyidagi tengliklarga ega bo’lamiz :a = bq1 + r1 ,b = r1 q2 + r2 ,r1 = r2 q3 + r3 ,. . . . . . . . . . . . .,rn–2 = rn–1 qn–1 + rn ,rn–1 = rn qn .Bunda (a, b) = (b, r1) = (r1, r2) = . . .
= (rn–1,rn) = rn.Shunday qilib, (a, b) ni topish uchun qoldiqli bo’lish jarayoni 0 ga teng
qoldiq hosilbo’lguncha davom ettiriladi, 0 dan farqli eng kichik qoldiq a, b sonlarining eng
kattabo’luvchisi bilan ustma–ust tushadi.Mazkur jarayon Evklid algoritmi deyiladi. Izoh.
Agar a soni b sonidan kichik bo’lmasa, u holda(a, b)= (b, a–b)bo’ladi. Ta’rif. a va b
sonlarining musbat umumiy karralilari ichida eng kichigi shusonlarning eng kichik umumiy
karralisi deyiladi va u [ a, b] orqali belgilanadi. Xossalar.a)m a b m aa bb    [ , ], '
'bo’lsa , u holda( ', ') 1 a b bo’ladi;b) Agarm'sonab,sonlarning umumiy bo’luvchisi
bo’lib,m aa bb a b ' ' ', ( ', ') 1   tengliklar bajarilsa, u holdam m 'bo’ladi;c)
Agar ac va bc bo’lsa, u holda[ , ] a b cbo’ladi;d) agar1 21 2 ...k m p p pk  
va1 21 2 ...kk n p p p  bo’lsa ( bu yerda1 2 , ... k p p p – tub sonlar,, 0  i i ), u holdamax( , ) max( , ) 1 1 2 2 max( , )1 2 [ , ] ... k k m n p p pk  tenglik
o’rinli. Teorema. Barcha m va n butun sonlar uchun[m, n] · (m, n) =mntenglikni
isbotlang.Isboti. [a,b]= [|a|,|b|] bo’lgani uchun faqat natural m va n sonlar holini qarash
yetarli.1 21 2 ...k m p p pk  va1 21 2 ...kk n p p p  bo’lsin ( bu yerda1
2 , ... k p p p – tub sonlar,, 0  i i ), u holdamin( , ) min( , ) 1 1 2 2 min( , )1 2 ( , ) ... k
k m n p p pk     vamax( , ) max( , ) 1 1 2 2 max( , )1 2 [ , ] ... k k m n p p
pk     tengliklar o’rinli. Bundan(m,n) [m,n]min( , ) max( , ) min( , ) max( , )
1 1 1 1 2 2 2 2 min( , ) max( , )1 1 2 2 ...k k k k p p p p p p k k        
   min( , ) max( , ) min( , ) max( , ) 1 1 1 1 2 2 2 2 1 1 2 2 min( , ) max( , )1 2 1
2 ... ...k k k k k k p p p p p p mn k k                
        kelib chiqadi.𝑎𝑏, 𝑏 > 0 ratsional son berilgan bo’lsin. 𝑎 va 𝑏
sonlariga Yevklid algoritmini tatbiqqilamiz.𝑎 = 𝑏𝑞0 + 𝑟1 ⇒𝑎𝑏= 𝑞0 +𝑟1𝑏 0 ≤ 𝑟1 < 𝑏𝑏 =
𝑟1𝑞1 + 𝑟2 ⇒𝑏𝑟1= 𝑞1 +𝑟2𝑟1 0 ≤ 𝑟2 < 𝑟1𝑟1 = 𝑟2𝑞2 + 𝑟3 ⇒𝑟1𝑟2= 𝑞2 +𝑟3𝑟2 0
≤ 𝑟3 < 𝑟2………………………………………………………𝑟𝑛−2 = 𝑟𝑛−1𝑞𝑛−1 + 𝑟𝑛
⇒𝑟𝑛−2𝑟𝑛−1= 𝑞𝑛−1 +𝑟𝑛𝑟𝑛−1𝑟𝑛−1 = 𝑟𝑛𝑞𝑛𝑟𝑛−1𝑟𝑛= 𝑞𝑛Bu yerdan𝑎𝑏= 𝑞0 +𝑟1𝑏= 𝑞0
+1𝑏𝑟1= 𝑞0 +1𝑞1 +𝑟2𝑟1= ⋯ = 𝑞0 +1𝑞1 +1𝑞2 + ⋯1𝑞𝑛Qisqacha, 𝑎𝑏= [𝑞0, 𝑞1, 𝑞2,
… , 𝑞𝑛] (1). Ta’rif. Ratsional sonni (1) ko’rinishdagi ifodasi chekli zanjir kasr yoki
uzluksizkasr deyiladi. Teorema. Har qanday ratsional sonni chekli zanjir kasr ko’rinishida
yozishmumkin. Isboti. I. Agar 𝑎𝑏 musbat bo’lsa;1) 𝑎 > 𝑏 ⇒𝑎𝑏= [𝑞0, 𝑞1, 𝑞2, … , 𝑞𝑛]2) 𝑎 <
𝑏 ⇒𝑎𝑏= [0, 𝑞1, 𝑞2, … , 𝑞𝑛]II. 𝑎𝑏 manfiy bo’lsa, uni 𝑎𝑏= −𝑡 +𝑎1𝑏1 ko’rinishda ifodalash
mumkin. U holda𝑎𝑏= −𝑡 +𝑎1𝑏1= [−𝑡, 𝑞1, 𝑞2, … , 𝑞𝑛]III. Agar 𝑎𝑏= 𝑐 butun son bo’lsa, u
holda 𝑎𝑏= 𝑐 = [𝑐] Ta’rif.𝛿0 =𝑃0𝑄0=𝑞01, 𝛿1 =𝑃1𝑄1= 𝑞0 +1𝑞1, 𝛿2 =𝑃2𝑄2= 𝑞0
+1𝑞1+1𝑞2, … 𝛿𝑛 =𝑎𝑏=𝑃𝑛𝑄𝑛kasrlar chekli zanjir (1) ning munosib kasrlari deyiladi. Har
bir munosib kasr ratsional sondir.𝛿𝑠 – munosib kasr 𝑞𝑠−1 ni 𝑞𝑠−1 +1𝑞𝑠 berilgan
almashtirish orqali hosil qilinadi.Demak,𝛿0 =𝑞01=𝑃0𝑄0; 𝛿1 = 𝑞0
+1𝑞1=𝑞0𝑞1+1𝑞1=𝑃1𝑄1𝛿2 = 𝑞0 +1𝑞1 +1𝑞2= 𝑞0 +𝑞2𝑞1𝑞2 + 1=𝑞0𝑞1𝑞2 +
𝑞0 + 𝑞2𝑞1𝑞2 + 1=𝑞2(𝑞0𝑞1 + 1) + 𝑞0𝑞1𝑞2 + 1=𝑃1𝑞2 + 𝑃0𝑄1𝑞2 + 𝑄0va
h.k.𝛿𝑘 =𝑃𝑘−1𝑞𝑘 + 𝑃𝑘−2𝑄𝑘−1𝑞𝑘 + 𝑄𝑘−2Demak, 𝑃0 = 𝑞0, 𝑃1 = 𝑞0𝑞1 + 1, … , 𝑃𝑘 =
𝑃𝑘−1𝑞𝑘 + 𝑃𝑘−2 𝑄0 = 1, 𝑄1 = 𝑞1, … , 𝑄𝑘 = 𝑄𝑘−1𝑞𝑘 + 𝑄𝑘−2 Misollardan namunalar: 1-
misol. ∀𝑛 ∈ 𝑁 uchun 𝑛(𝑛 + 1)(2𝑛 + 1) ning 6 ga bo’linishini isbotlang.Isboti. Natural
sonlar qatorida 2 ta ketma-ket kelgan sonlar 𝑛(𝑛 + 1) ⋮ 2 bo’lganligidan𝑛(𝑛 + 1)(2𝑛 + 1)
⋮ 2 va 6=2∙3 bo’lib, (2, 3)=1 ekanligidan 𝑛(𝑛 + 1)(2𝑛 + 1) ⋮ 3ekanligini ko’rsatish lozim.
Qoldiqli bo’lish haqidagi teoremaga ko’ra har qandaynatural sonni n = 3k yoki n = 3k + 1
yoki n = 3k + 2 ko’rinishda ifodalashmumkin. Bundan1) Agar 𝑛 = 3𝑘 bo’lsa, u holda 𝑛(𝑛 +
1)(2𝑛 + 1) ⋮ 3 ;2) Agar 𝑛 = 3𝑘 + 1 ko’rinishda bo’lsa, u holda 2𝑛 + 1 = 6𝑘 + 3 va 𝑛(𝑛 +
1)(2𝑛 +1) ⋮ 3 ;3) Agar 𝑛 = 3𝑘 + 2 ko’rinishda bo’lsa, u holda 𝑛 + 1 = 3𝑘 + 3 va 𝑛(𝑛 +
1)(2𝑛 +1) ⋮ 3 ;Demak, (𝑛 + 1)(2𝑛 + 1) ⋮ 6 . 2- misol. Berilgan 123 va 321 sonlarning
EKUB va EKUKlarini ikki usulda toping. Yechish. Berilgan natural sonlarning EKUB va
EKUKlarini topish uchun ular nitub ko’paytuvchilaridan yoki Yevklid algoritmidan
foydalanish mumkin. 1-usul. Berilgan sonlarni tub ko’paytuvchilarga kanonik yoyilmasini
topamiz:123 = 3 ∙ 41 = 31∙ 411∙ 1070;321 = 3 ∙ 107 = 31∙ 410∙ 1071; Demak, EKUB va
EKUKning ta’rifiga ko’ra (123; 321)=3 va[123; 321]=3∙41∙107=13161. 2-usul. Berilgan
sonlar uchun qoldiqli bo’lish teoremasi yordamida Yevklidalgoritmini
tuzamiz:321=123∙2+75; 75=321-123∙2;123=75∙1+48; 48=123-75∙1;75=48∙1+27; 27=75-
48∙1;48=27∙1+21; 21=48-27∙1;27=21∙1+6; 6=27-21∙1;21=6∙3+3; 3=21-6∙36=3∙2+0
Demak,3=21-6∙3=(48-27∙1)-(27-21∙1) ∙3=48-27∙4+21∙3=123-75∙1-(75-48∙1) ∙4+(48-27∙1)
∙3=123-75∙5+48∙7-27∙3=123-(321-123∙2) ∙5+(123-75∙1) ∙7-(75-48∙1) ∙3=123∙18-321∙5-
75∙10+48∙3=123∙18-321∙5-(321-123∙2) ∙10+(123-75∙1) ∙3=123∙41-321∙15-75∙3=123∙41-
321∙15-(321-123∙2) ∙3=123∙47-321∙18=123∙47+321∙(-18).Bundan, 3=123∙47+321∙(-18)
kelib chiqadi. Yevklid algoritmidagi oxirgi noldan farqli qoldiq EKUB ni beradi.
Demak,(123, 321)=3. Bundan [123,321] =321∙123(321,123)= 13161. 3-misol. {𝑎 ∙ 𝑏 =
768(𝑎, 𝑏) = 8 sistemani qanoatlantiruvchi 𝑎 va 𝑏 sonlarni toping. Yechish. Berilgan 𝑎 va 𝑏
sonlarning eng katta umumiy bo’luvchisi 8 ekanligidan,bu sonlarni 𝑎 = 8𝑘 va 𝑏 = 8𝑙
ko’rinishda yozib olamiz. Bu yerda (𝑙, 𝑘) = 1. Bundan𝑎 ∙ 𝑏 = 8𝑘 ∙ 8𝑙 = 64 ∙ 𝑘 ∙ 𝑙 = 768 ni,
bundan esa 𝑘 ∙ 𝑙 = 12 ni hosil qilamiz. Demak,12 o’zaro tub 𝑘 va 𝑙 sonlarning ko’paytmasi
ko’rinishida ifodalanadi. Quyidagiholatlar bo’lishi mumkin: 𝑘 𝑙 𝑘 ∙ 𝑙 1 12 12 3 4 12 4 3 12
12 1 12Bundan, 𝑎 𝑏 𝑎 ∙ 𝑏 8 96 768 24 32 768 32 24 768 96 8 768Demak, (𝑎, 𝑏): (8; 96), (24;
32), (32; 24), (96; 8) 4-misol. Berilgan 10423 kasrni chekli zanjir kasr ko’rinishida
ifodalang va uningmunosib kasrlarini toping. Yechish. 10423 kasrni chekli zanjir kasr
ko’rinishida ifodalash uchun 104 va 53sonlari uchun Yevklid algoritmi tuzamiz. 104 = 23 ∙ 4
+ 12; 23 = 12 ∙ 1 + 11; 12 = 11 ∙ 1 + 1; 11 = 1 ∙ 11 + 0. Yevklid algoritmidagi tengliklarning har ikkala tomonini bo’luvchilarga bo’lamiz:10423= 4 +1223;2312= 1 +1112;1211= 1 +111;111= 11. Hosil bo’lgan tengliklarning o’ng tomonidagi kasr sonni uning teskarisi
bilanalmashtirish natijasida10423 = 4 +1223 = 4 +12312= 4 +11 +1112= 4 +11 +11211= 4
+11 +11 +111chekli zanjirni hosil qilamiz. Uni qisqacha 10423= [4; 1, 1, 11] ko’rinishida
ifodalaymiz.Agar berilgan kasr manfiy bo’lsa, birinchi qoldiqni musbat qilib olamiz.
Masalan,−2313= −2 +313 va kasr qismi chekli zanjir ko’rinishida ifodalanadi.−2313 = −2
+313 = −2 +1133= −2 +14 +13= [−2; 4, 3] Berilgan 10423= [4; 1, 1, 11] ning munosib
kasrlarini topish uchun quyidagijadvalni tuzamiz: 𝑘 -1 0 1 2 3𝑞𝑘 - 4 1 1 11𝑃𝑘 1 4 5 9
104𝑄𝑘 0 1 1 2 23Demak, 𝑃0𝑄0= 4;𝑃1𝑄1= 5;𝑃2𝑄2=92;𝑃3𝑄3=10423. 5-misol.
Berilgan √14 sonni zanjir kasr ko’rinishida ifodalang: Yechish.√14 = 3 +1𝛼1;𝛼1
=1√14−3=√14+35= 1 +1𝛼2;𝛼2 =1√14+35−1=5√14−2=√14+22= 2 +1𝛼3;𝛼3
=1√14+22−2=2√14−2=√14+25= 1 +1𝛼1;𝛼4 =1√14+25−1=5√14−3= √14 + 3 = 6
+1𝛼5;𝛼5 =1√14+3−6=1√14−3.𝛼5 = 𝛼1 bo’lganligi uchun, yana yuqoridagi jarayon hosil
bo’ladi. Demak, √14 =[3; (1, 2, 1, 6)].
*Sana : 2015-yil 17-Noyabr
Maqsad : Evklid algoritmi bo'yicha EKUB
topish dasturini tuzish
Muallif : Mo'minjon Abduraimov
*/
#include

using namespace std;

int main()
{
int a, b;

cout << "A = "; cin >> a;

cout << "B = "; cin >> b;

while (a != b)

{
if (a > b) a %= b;
else b %= a;

if (a == 0) a = b;

if (b == 0) b = a;
}

cout << a << endl;

return 0;
}