Berilgan sonlarning eng katta umumiy bo’luvchisi va eng kichik umumiy karralisini topish algoritmi. Reja

Xossalar.

1. 
   p tub son bo’lsa, ixtiyoriy natural mson uchun ( pm p, )  yoki ( pm, ) 1 bo’ladi;
   
2. 
   d mn m dm n dn ( , ),  ',  ' bo’lsa , u holda (m n', ') 1 bo’ladi;
   
3. 
   d mn m d m n d n ( , ),  ' ',  ' ' va (m n', ') 1bo’lsa , u holda d  d'bo’ladi;
   
4. 
   agar m p p ₁^{ 1} ₂ ²...p^_k ^k va n p p ₁^{ 1} ₂ ²...p_k^k bo’lsa ( bu yerda p p p₁ , ₂... _k – tub sonlar, _i, _i  0), u holda
   

(mn p, ) ^ ₁min(_{1 1}, ) ^p₂min(_{2 2}, )...^p_kmin(_k , _k ) tenglik o’rinli.

5. 
   a va b sonlarining eng katta umumiy bo’luvchisi shu sonlarning barcha umumiy bo’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  r< b) bo’lsa, u holda D(a, b) , D(b, r) to’plamlar ustma–ust tushadi. Bundan ularning eng katta 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 uchun qoldiqli bo’lish haqida teoremaga ko’ra:
a = bq₁ + r₁.
Agar r₁ = 0 bo’lsa, u holda (a, b) = b.
Agar r₁  0 bo’lsa, u holda b = r₁q₂ + r₂.
Agar r₂ = 0 bo’lsa, u holda jarayonni to’xtatamiz, aks holda (ya’ni r₂  0) davom ettiramiz : r₁ = r₂q₃ + r₃. b > r₁ > r₂ > r₃ > . . . >0 tengsizliklardan jarayon qoldiq nolga aylanganda tugashi kelib chiqadi.
Demak, quyidagi tengliklarga ega bo’lamiz : a = bq₁ + r₁ , b = r₁ q₂ + r₂ , r₁ = r₂ q₃ + r₃ ,
. . . . . . . . . . . . .,
rn–2 = rn–1 qn–1 + rn , rn–1 = rn qn .
Bunda (a, b) = (b, r₁) = (r₁, r₂) = . . . = (r_n–1, r_n) = r_n.
Shunday qilib, (a, b) ni topish uchun qoldiqli bo’lish jarayoni 0 ga teng qoldiq hosil bo’lguncha davom ettiriladi, 0 dan farqli eng kichik qoldiq a, b sonlarining eng katta bo’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 shu sonlarning eng kichik umumiy karralisi deyiladi va u [ a, b] orqali belgilanadi.
Xossalar.

1. 
   m ab m aa bb[ , ],  ' ' bo’lsa , u holda (a b', ') 1 bo’ladi;
   
2. 
   Agar m' son ab, sonlarning umumiy bo’luvchisi bo’lib, m aa bb a b'  ' ', ( ', ') 1 tengliklar bajarilsa, u holda m'  m bo’ladi;
   
3. 
   A gar ac va bc bo’lsa, u holda [ab c, ] bo’ladi;
   
4. 
   agar m p p ₁^{ 1} ₂ ²...p^_k ^k va n p p ₁^{ 1} ₂ ²...p_k^k bo’lsa ( bu yerda p p p₁ , ₂... _k – tub sonlar, _i, _i  0), u holda
   

[mn p, ]^ ₁max(_{1 1}, ) ^p₂max(_{2 2}, )...^p_kmax(_k , _k ) tenglik o’rinli.
Teorema. Barcha m va n butun sonlar uchun
[ m, n] · (m, n) = mn tenglikni isbotlang.
Isboti. [a,b]= [|a|,|b|] bo’lgani uchun faqat natural m va n sonlar holini qarash yetarli.
m p p 1 1 2 2...pk k va n p p 1 1 2 2...pkk bo’lsin ( bu yerda p p p₁ , ₂... _k – tub sonlar, _i, _i  0), u holda
(mn p, ) ^ ₁min(_{1 1}, ) ^p₂min(_{2 2}, )...^p_kmin(_k , _k ) va [mn p, ]^ ₁max(_{1 1}, ) ^p₂max(_{2 2}, )...^p_kmax(_k , _k ) tengliklar o’rinli. Bundan
(m,n) [m,n] _^p₁min(^{1 1}, ) ^p₁max(^{1 1}, ) pmin(₂ ^{2 2}, ) pmax(₂ ^{2 2}, ) ...^p_kmin( ^{k k}, ) ^p_kmax( ^{k k}, ) 
_^p₁min(1 1, )max(1 1, ) ^p₂min(2 2, )max(2 2, )...^p_kmin( _{k k}, )max( _{k k}, ) _^p₁   1 1 ^p₂ 2 2...p^{ }_kk k _mn kelib chiqadi.
^𝑎 ratsional son berilgan bo’lsin. 𝑎 va 𝑏 sonlariga Yevklid algoritmini tatbiq qilamiz.
0 ≤ 𝑟₁ < 𝑏
0 ≤ 𝑟₂ < 𝑟₁
0 ≤ 𝑟₃ < 𝑟₂
………………………………………………………

𝑟_𝑛−1 = 𝑟_𝑛𝑞_𝑛
Bu yerdan

Qisqacha,
Ta’rif. Ratsional sonni (1) ko’rinishdagi ifodasi chekli zanjir kasr yoki uzluksiz kasr deyiladi.
Teorema. Har qanday ratsional sonni chekli zanjir kasr ko’rinishida yozish mumkin.
Isboti. I. Agar ^𝑎 musbat bo’lsa;
𝑏
1 )
2)

2. 
   ^𝑎 manfiy bo’lsa, uni ko’rinishda ifodalash mumkin. U holda
   

𝑏

2. 
   Agar ^𝑎 butun son bo’lsa, u holda
   

Ta’rif.
, , , …
𝑛 kasrlar chekli zanjir (1) ning munosib kasrlari deyiladi.
Har bir munosib kasr ratsional sondir.
𝛿_𝑠 – munosib kasr berilgan almashtirish orqali hosil qilinadi.
Demak,
;

va h.k.

Demak, 𝑃₀ = 𝑞₀, 𝑃₁ = 𝑞₀𝑞₁ + 1, … , 𝑃_𝑘 = 𝑃_𝑘−1𝑞_𝑘 + 𝑃_𝑘−2
𝑄₀ = 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) ⋮ 3 ekanligini ko’rsatish lozim. Qoldiqli bo’lish haqidagi teoremaga ko’ra har qanday natural sonni n = 3k yoki n = 3k + 1 yoki n = 3k + 2 ko’rinishda ifodalash mumkin. Bundan

1. 
   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 toppish uchun ularni tub ko’paytuvchilaridan yoki Yevklid algoritmidan foydalanish mumkin.
1-usul. Berilgan sonlarni tub ko’paytuvchilarga kanonik yoyilmasini topamiz:
123 = 3 ∙ 41 = 3¹ ∙ 41¹ ∙ 107⁰;
321 = 3 ∙ 107 = 3¹ ∙ 41⁰ ∙ 107¹;
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 Yevklid algoritmini 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∙3
6=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∙18321∙5-75∙10+48∙3=123∙18-321∙5-(321-123∙2) ∙10+(123-75∙1) ∙3=123∙41-321∙1575∙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 .
3-misol. 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. Quyidagi holatlar bo’lishi mumkin:
𝑘 𝑙 𝑘 ∙ 𝑙
1 12 12

3. 
   4 12
   
4. 
   3 12
   

12 1 12
Bundan,
𝑎 𝑏 𝑎 ∙ 𝑏
8 96 768
24 32 768
32 24 768
96 8 768
Demak, (𝑎, 𝑏): (8; 96), (24; 32), (32; 24), (96; 8) 4-misol. Berilgan ¹⁰⁴ kasrni chekli zanjir kasr ko’rinishida ifodalang va uning
23 munosib kasrlarini toping. Yechish. ¹⁰⁴ kasrni chekli zanjir kasr ko’rinishida ifodalash uchun 104 va 53
23 sonlari 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:
;
;
;
.
Hosil bo’lgan tengliklarning o’ng tomonidagi kasr sonni uning teskarisi bilan almashtirish natijasida

chekli zanjirni hosil qilamiz. Uni qisqacha ¹⁰⁴ ko’rinishida ifodalaymiz.
Agar berilgan kasr manfiy bo’lsa, birinchi qoldiqni musbat qilib olamiz. Masalan, va kasr qismi chekli zanjir ko’rinishida ifodalanadi.

Berilgan ning munosib kasrlarini topish uchun quyidagi jadvalni tuzamiz:
𝑘 -1 0 1 2 3
𝑞_𝑘 - 4 1 1 11
𝑃_𝑘 1 4 5 9 104
𝑄_𝑘 0 1 1 2 23
Demak, .
5-misol. Berilgan sonni zanjir kasr ko’rinishida ifodalang:
Yechish.
;
;
;
;
;

𝛼₅ = 𝛼₁ bo’lganligi uchun, yana yuqoridagi jarayon hosil bo’ladi. Demak, √14 = [3; (1, 2, 1,6)].