Eng katta umumiy bo‘luvchi (ekub) va eng kichik umumiy karrali (ekuk), xossalari. 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 sonlarning umumiy bo’luvchisi deyiladi.
Ta’rif. 𝑎 va 𝑏 natural sonlar umumiy bo’luvchilarining eng kattasi shu sonlarning eng kata umumiy bo’luvchisi (EKUB) deyiladi, uni (𝑎, 𝑏) ko’rinishda belgilanadi.
Ta’rif. Agar ⁽𝑎, 𝑏⁾ = 1 bo’lsa, u holda 𝑎 va 𝑏 natural sonlar o’zaro tub sonlar deyiladi.
Teorema(qoldiqli bo’lish haqidagi). Har qanday 𝑎 ∈ 𝑍, 𝑏 ∈ 𝑁 uchun shunday yagona 𝑞 ∈ 𝑍 va yagona manfiymas 𝑟 butun son topiladiki, ular uchun ushbu
𝑎 = 𝑏𝑝 + 𝑟 0 ≤ 𝑟 < 𝑏
munosabatlar o’rinli bo’ladi.
Isboti. [x] orqali xR sonining butun qismini, ya’ni x dan katta bo’lmagan eng katta butun sonini belgilaymiz.
{x} =x – [x] tenglik bilan xR sonining kasr qismi aniqlanadi. Butun qism va kasr qism ta’riflaridan bevosita
a _  a  _  a 
| b | ^| b |^{ }| b |^
   

tenglik kelib chiqadi. Demak,

^{a   a  | b |  a  | b |} =bq+r,
^| b |^{ }| b |^
   

bu yerda

^{q   a sgn b} , r=a–bq = ^{ a  | b |} .
^| b |^{ }| b |^
   
Bundan a=bq+r va 0  r< b.
Agar a=bq₁+ r₁ tenglik bajarilsa ( 0  r₁< b ), u holda
b(q –q₁)= r₁ – r
bo’ladi. 0  r, r₁< b tengsizliklardan
bq –q₁= r₁–r<b
tengsizlik kelib chiqadi, bundan q –q₁< 1. q ,q₁ sonlar butun bo’lgani uchun

q= q₁ , r₁ = r ga ega bo’lamiz.
Izoh. Yuqoridagi q son to’liqsiz bo’linma, r son esa a ni b ga bo’lganda hosil bo’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’luvchisi deyiladi. 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. Shuning uchun a va b sonlarining umumiy bo’luvchilari ichida eng kattasi mavjud bo’lib, shu sonlarning eng katta umumiy bo’luvchisi deyiladi va (a, b) orqali belgilanadi.

Xossalar.

1. 
   ^{p tub son bo’lsa, ixtiyoriy natural m son uchun} ( p, m)  p ^yoki ( p, m) 1 ^bo’ladi;
   

2. 
   d  (m,n),
   

m  dm',
n  dn'
^{bo’lsa , u holda} (m', n') 1 ^bo’ladi;

3. 
   d  (m,n),
   

m  d 'm',
n  d 'n' ^va (m', n') 1^{bo’lsa , u holda}
d  d ' bo’ladi;

4. 
   agar m  p^1 p^2 ...p^k
   

va n  p^1 p^2 ...p^k
bo’lsa ( bu yerda
p , p ...p – tub sonlar,

1 2 k
_i , _i  0 ), u holda
1 2 k
1 2 k

_{(m, n)  p}min( ₁, ₁) _pmin(₂ ,₂ )_...pmin(_k ,_k )
1 2 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 ^{= r}n–1 ^qn–1 ^{+ r}n ^,
r_n–1 = r_n q_n .
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 [a,b], m  aa '  bb' ^{bo’lsa , u holda} (a ',b') 1 ^bo’ladi;
   

2. 
   Agar
   

m ' son
a,b sonlarning umumiy bo’luvchisi bo’lib,
m'  aa'  bb', (a',b') 1

tengliklar bajarilsa, u holda
m'  m bo’ladi;

3. 
   Agar a c va b c bo’lsa, u holda ^{[a,b] c} bo’ladi;
   

4. 
   agar m  p^1 p^2 ...p^k
   

va n  p^1 p^2 ...p^k
bo’lsa ( bu yerda
p , p ...p – tub sonlar,

1 2 k
_i , _i  0 ), u holda
1 2 k
1 2 k

_{[m, n]  p}max( ₁, ₁) _pmax(₂ ,₂ )_...pmax(_k ,_k )
1 2 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^1 p^2 ...p^k va n  p^1 p^2 ...p^k
1 2 k 1 2 k

bo’lsin ( bu yerda
p₁ , p₂ ...p_k
– tub sonlar, _i , _i  0 ), u holda

_{(m, n)  p}min( ₁, ₁) _pmin(₂ ,₂ )_...pmin(_k ,_k ) _{va [m, n]  p}max( ₁, ₁) _pmax(₂ ,₂ )_...pmax(_k ,_k )

1 2 k
tengliklar o’rinli. Bundan
1 2 k

(m,n) [m,n]
_{ p}min( ₁,  ₁) _pmax(  ₁,  ₁) _pmin( ₂, ₂) _pmax( ₂, ₂) _...pmin(_k , _k ) _pmax( _k, _k) _

1 1 2 2 k k

_{ p}min( ₁, ₁)max( ₁, ₁) _pmin(₂ ,₂ ) max(₂ ,₂ )_...pmin(_k ,_k )max(_k ,_k ) _{ p} ₁ _{1 p}₂ _{2 ...p}_k _k
 mn

1 2 k
kelib chiqadi.
1 2 k

^𝑎, 𝑏 > 0 ratsional son berilgan bo’lsin. 𝑎 va 𝑏 sonlariga Yevklid algoritmini tatbiq
𝑏
qilamiz.
𝑎 = 𝑏𝑞₀ + 𝑟₁ ⇒ ^𝑎 = 𝑞₀ + ^𝑟1 0 ≤ 𝑟₁ < 𝑏

𝑏

𝑟
𝑏 = 𝑟₁𝑞₁ + 𝑟₂ ⇒ ^𝑏
1
𝑏

1
= 𝑞 + ^𝑟2
𝑟₁
0 ≤ 𝑟₂ < 𝑟₁

𝑟₁ = 𝑟₂𝑞₂ + 𝑟₃ ⇒ ^𝑟1 = 𝑞₂ + ^𝑟3
0 ≤ 𝑟₃ < 𝑟₂

𝑟₂ 𝑟₂
………………………………………………………
^𝑟𝑛−2 ^{= 𝑟}𝑛−1^𝑞𝑛−1 ^{+ 𝑟}𝑛 ^⇒ 𝑟𝑛−2 ^{= 𝑞}𝑛−1 ⁺ 𝑟𝑛

𝑟
𝑟_𝑛−1 = 𝑟_𝑛𝑞_𝑛 ^𝑟𝑛−1 = 𝑞_𝑛
𝑛
^𝑟𝑛−1
^𝑟𝑛−1

Bu yerdan
^𝑎 = 𝑞

+ ^𝑟1 = 𝑞

+ ¹ = 𝑞 + ¹

= ⋯ = 𝑞 + ¹

𝑏 ⁰ 𝑏
⁰ 𝑏
⁰ 𝑞 + ^𝑟2



+ ⋯

⁰ _{𝑞 +} 1

𝑟₁



𝑏
Qisqacha, ^𝑎 = [𝑞₀, 𝑞₁, 𝑞₂, … , 𝑞_𝑛] (1).
1 _𝑟1
1
𝑞₂
1
𝑞_𝑛