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

BERILGAN SONLARNING ENG KATTA UMUMIY BO’LUVCHISI VA ENG KICHIK UMUMIY KARRALISINI TOPISH ALGORITMI.

Reja:

1. 
   Sonlarning eng kichik umumiy karralisi va eng katta umumiybo‘luvchisini topish, ularning asosiy xossalari.
   
2. 
   Murakkab songa bo‘linish alomati. Arifmetikaning asosiy teoremasi.
   
3. 
   Berilgan sonlarning eng katta umumiy bo’luvchisi va eng kichik umumiy karralisini topish algoritmi
   

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 
a   _ | b |   | 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.