No`kis Innovatciyaliq Inistituti qa`nigeligi topar student O`z betinshe jumisi

No`kis Innovatciyaliq Inistituti
________qa`nigeligi _-topar student
O`z betinshe jumisi




Pan:________________________
Tema:_______________________
Qabilladi:______________________
EKUK va EKUB topish alogitmi


Reja:


1.Eng katta umumiy bo‘luvchi


2.Eng kichik umumiy karrali


3.EKUKlarini topish

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
yoki( , ) 1belgilanadi. Xossalar.a)ptub son bo’lsa, ixtiyoriy naturalmson uchun( , ) p m p
bo’ladi;c)d m ( , ), ', 'bo’lsa , u holda( ', ') 1 m n   bo’ladi;b)d m n m dm n dn p m
'bo’ladi;d) agar1 21bo’lsa , u holdad d  ( , ), ' ',


''va( ', ') 1 m n   n m d m n d n
bo’lsa ( bu yerda1 2 , ... k p p p –  va1 21 2...kk n p p p  2 ...k m p p pk
), u holdamin( , ) min( , ) 1 1 2 2 min( , )1 2 ( , ) ... k k m n p p pki i  tub sonlar,, 0
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
rbo’lmasdan, a = bq + r (0 < b) bo’lsa,u holda (a, b)= (b, r) bo’ladi.Isboti. D(a, b) orqali a
rva b sonlarning umumiy bo’luvchilari to’plamini belgilaymiz. a= bq + r (0 < b) va c
D(b, r).D(a, b) bo’lsin. Demak, r= a – bq soni c soniga bo’linadi,ya’ni c Aksincha, c
D(a, b ). Demak, agar a soniD(b, r) bo’lsa, u holda a = bq + r soni c ga bo’linadi,ya’ni c
rb sonidan katta bo’lmasdan, a = bq + r (0
ustma–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
0 bo’lsa, u holda b = r1q2 + r2.Agar r2 = 0 bo’lsa, u

holdaholda (a, b) = b.Agar r1

0) davomettiramiz : r1 = r2q3 + r3.bjarayonni to’xtatamiz, aks holda (ya’ni r2 > 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’ladi;b) Agarm'sonab,sonlarning umumiy bo’luvchisi'bo’lsa , u holda( ', ') 1 a b
bo’ladi;c)tengliklar bajarilsa, u holdam m '  bo’lib,m aa bb a b ' ' ', ( ', ') 1
  Agar ac va bc bo’lsa, u holda[ , ] a b cbo’ladi;d) agar1 21 2 ...k m p p pk
tenglik  ), u holdamax( , ) max( , ) 1 1 2 2 max( , )1 2 [ , ] ... k k m n p p pki i  bo’lsa ( bu yerda1 2 , ... k p p p – tub sonlar,,

0   va1 21 2 ...kk n p p p

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
bo’lsin ( bu yerda1  va1 21 2 ...kk n p p p  yetarli.1 21 2 ...k m p p pk
), u holdamin( , ) min( , ) 1 1 2 2 min( , )1 2 ( , ) ... ki i  2 , ... k p p p – tub sonlar,, 0
vamax( , ) max( , ) 1 1 2 2 max( , )1 2 [ , ] ... k k m n p p     k m n p p pk
tengliklar o’rinli. Bundan(m,n) [m,n]min( , ) max( , ) min( , ) max( , )     pk
        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;

Paydalanilg`an a`debiyatlar

Google

Linkedin.com

Teachingenglish.com