Eng katta umumiy bo‘luvchi (ekub) va eng kichik umumiy karrali (ekuk), xossalari. Evklid algoritmi

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) 𝑎 < 𝑏 ⇒ ^𝑎 = [0, 𝑞₁, 𝑞₂, … , 𝑞_𝑛]

2. 
   ^𝑎 manfiy bo’lsa, uni ^𝑎 = −𝑡 + ^𝑎1
   

ko’rinishda ifodalash mumkin. U holda

𝑏 𝑏
𝑏₁

^𝑎 = −𝑡 + ^𝑎1 = [−𝑡, 𝑞



, 𝑞
, … , 𝑞 ]

𝑏 𝑏₁
1 2 𝑛

2. 
   Agar ^𝑎 = 𝑐 butun son bo’lsa, u holda ^𝑎 = 𝑐 = [𝑐]
   

𝑏

Ta’rif.

𝛿 = ^𝑃0 = ^𝑞0, 𝛿
= ^𝑃1 = 𝑞
𝑏

+ ¹ , 𝛿

1
= ^𝑃2 = 𝑞 + ¹
, … 𝛿
₌ 𝑎 ₌ 𝑃_𝑛

⁰ 𝑄₀ 1
1 _𝑄1
0 _𝑞1
2 _𝑄2
0 _{𝑞 +} ¹
𝑞₂
𝑛 _𝑏
𝑄_𝑛

kasrlar chekli zanjir (1) ning munosib kasrlari deyiladi.
Har bir munosib kasr ratsional sondir.

𝑞
𝛿_𝑠 – munosib kasr 𝑞_𝑠−1 ni 𝑞_𝑠−1 + ¹
𝑠

berilgan almashtirish orqali hosil qilinadi.

Demak,


𝛿₀ = ^𝑞0 = ^𝑃0; 𝛿₁ = 𝑞₀ + ¹


₌ 𝑞₀𝑞₁+1 ₌ 𝑃₁

1 𝑄₀
𝑞₁
𝑞₁
𝑄₁

𝛿 = 𝑞 + ¹

= 𝑞

₊ 𝑞_2
= 𝑞₀𝑞₁𝑞₂ + 𝑞₀ + 𝑞_{2 =} 𝑞₂⁽𝑞₀𝑞₁ + 1⁾ + 𝑞₀

+
2 0
𝑞₁
1
𝑞₂
⁰ 𝑞₁𝑞₂ + 1
𝑞₁𝑞₂ + 1
𝑞₁𝑞₂ + 1

va h.k.
₌ 𝑃₁𝑞₂ + 𝑃₀
𝑄₁𝑞₂ + 𝑄₀
𝛿_𝑘
= ^𝑃𝑘−1^𝑞𝑘 ^{+ 𝑃}𝑘−2
^𝑄𝑘−1^𝑞𝑘 ^{+ 𝑄}𝑘−2

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∙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. 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 ¹⁰⁴
   

23

kasrni chekli zanjir kasr ko’rinishida ifodalang va uning

munosib kasrlarini toping.

Yechish. ¹⁰⁴
23

kasrni chekli zanjir kasr ko’rinishida ifodalash uchun 104 va 53

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:
104 _{= 4 +} 12_;
23 23
23 _{= 1 +} 11_;
12 12
¹² = 1 + ¹ ;
11 11


¹¹ = 11.
1
Hosil bo’lgan tengliklarning o’ng tomonidagi kasr sonni uning teskarisi bilan almashtirish natijasida

104 _{= 4 +} 12 _{= 4 +} 1



= 4 + ¹
= 4 + ¹ = 4 + ¹

1 +
23 23 ²³
12
11 1 1

1 +
12 ^{12 1}
11 11

1 +

1 +
chekli zanjirni hosil qilamiz. Uni qisqacha ¹⁰⁴ = [4; 1, 1, 11] ko’rinishida ifodalaymiz.
23
Agar berilgan kasr manfiy bo’lsa, birinchi qoldiqni musbat qilib olamiz. Masalan,
− ²³ = −2 + ³ va kasr qismi chekli zanjir ko’rinishida ifodalanadi.

13 13
− ²³ = −2 + ³



= −2 + ¹ = −2 + ¹

= [−2; 4, 3]

3

3
13 13
13 _{4 +} 1

Berilgan ¹⁰⁴ = [4; 1, 1, 11] ning munosib kasrlarini topish uchun quyidagi
23
jadvalni tuzamiz:
𝑘 -1 0 1 2 3
𝑞_𝑘 - 4 1 1 11
𝑃_𝑘 1 4 5 9 104
𝑄_𝑘 0 1 1 2 23
Demak, ^𝑃0 = 4; ^𝑃1 = 5; ^𝑃2 = ⁹; ^𝑃3 = ¹⁰⁴.

𝑄₀
𝑄₁
𝑄₂
2 𝑄₃ 23

5. 
   
   ^{misol. Berilgan} √^{14 sonni zanjir kasr ko’rinishida ifodalang:} Yechish.
   

√^{14 = 3 + 1 ;}
𝛼₁

𝛼₁ = ¹


₌ √¹⁴⁺³ _{= 1 +} ¹ _;

√^{14−3 5}


𝛼₂ = ¹ = ⁵
𝛼<sub>2


=</sub> √¹⁴⁺² _{= 2 +} ¹ _;

5
√¹⁴⁺³₋₁
√^{14−2 2}
𝛼₃

𝛼₃ = ¹


₌ ² ₌ √¹⁴⁺² _{= 1 +} ¹ _;

2
√¹⁴⁺²₋₂
√^{14−2 5}
𝛼₁

√¹⁴⁺²₋₁
𝛼₄ = ¹
5


𝛼₅ = ¹
₌ 5
√¹⁴⁻³


₌ 1


⁼ √^{14 + 3 = 6 + 1 ;}
𝛼₅

.

√¹⁴⁺³⁻⁶ √<sup>14−3



𝛼5 = 𝛼1 bo’lganligi uchun, yana yuqoridagi jarayon hosil bo’ladi. Demak,</sup> √^{14 =} [3; ⁽1, 2, 1, 6⁾].