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


Download 51.12 Kb.
bet1/2
Sana17.02.2023
Hajmi51.12 Kb.
#1207251
  1   2
Bog'liq
ekub va ekuk

Eng katta umumiy bo‘luvchi (EKUB) va eng kichik umumiy karrali (EKUK), xossalari.


𝑎 va 𝑏 butun sonlarning ikkalasiga ham bo’linadigan son shu sonlarning umumiy bo’luvchisi deyiladi.
𝑎 va 𝑏 natural sonlar umumiy bo’luvchilarining eng kattasi shu sonlarning eng kata umumiy bo’luvchisi (EKUB) deyiladi, uni (𝑎, 𝑏) ko’rinishda belgilanadi.
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 xR sonining butun qismini, ya’ni x dan katta bo’lmagan eng katta butun sonini belgilaymiz.
{x} =x – [x] tenglik bilan xR 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=bq1+ r1 tenglik bajarilsa ( 0 r1< b ), u holda
b(q –q1)= r1 r
bo’ladi. 0 r, r1< b tengsizliklardan
bq –q1= r1–r<b
tengsizlik kelib chiqadi, bundan q –q1< 1. q ,q1 sonlar butun bo’lgani uchun

q= q1 , r1 = 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;




  1. d  (m,n),

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


  1. d  (m,n),

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


  1. agar m p1 p2 ...pk

va n p1 p2 ...pk
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) pmin( 1, 1) pmin(2 ,2 )...pmin(k ,k )
1 2 k

tenglik o’rinli.





  1. 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 = bq1 + r1.
Agar r1 = 0 bo’lsa, u holda (a, b) = b.

Agar r1  0 bo’lsa, u holda b = r1q2 + r2.
Agar r2 = 0 bo’lsa, u holda jarayonni to’xtatamiz, aks holda (ya’ni r2  0) davom ettiramiz : r1 = r2q3 + r3.
b > r1 > r2 > r3 > . . . >0
tengsizliklardan 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 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;




  1. 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;




  1. Agar a c va b c bo’lsa, u holda [a,b] c bo’ladi;




  1. agar m p1 p2 ...pk

va n p1 p2 ...pk
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] pmax( 1, 1) pmax(2 ,2 )...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 p1 p2 ...pk va n p1 p2 ...pk
1 2 k 1 2 k

bo’lsin ( bu yerda
p1 , p2 ...pk
– tub sonlar, i , i  0 ), u holda



(m, n) pmin( 1, 1) pmin(2 ,2 )...pmin(k ,k ) va [m, n] pmax( 1, 1) pmax(2 ,2 )...pmax(k ,k )

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

(m,n) [m,n]
pmin( 1,  1) pmax(  1,  1) pmin( 2, 2) pmax( 2, 2) ...pmin(k , k ) pmax( k, k)

1 1 2 2 k k

pmin( 1, 1)max( 1, 1) pmin(2 ,2 ) max(2 ,2 )...pmin(k ,k )max(k ,k ) p1 1 p2 2 ...pk k
mn

1 2 k
kelib chiqadi.
1 2 k



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

𝑏

𝑟
𝑏 = 𝑟1𝑞1 + 𝑟2𝑏
1
𝑏

1
= 𝑞 + 𝑟2
𝑟1
0 ≤ 𝑟2 < 𝑟1

𝑟1 = 𝑟2𝑞2 + 𝑟3𝑟1 = 𝑞2 + 𝑟3
0 ≤ 𝑟3 < 𝑟2

𝑟2 𝑟2
………………………………………………………
𝑟𝑛−2 = 𝑟𝑛−1𝑞𝑛−1 + 𝑟𝑛 𝑟𝑛−2 = 𝑞𝑛−1 + 𝑟𝑛


𝑟
𝑟𝑛−1 = 𝑟𝑛𝑞𝑛 𝑟𝑛−1 = 𝑞𝑛
𝑛
𝑟𝑛−1
𝑟𝑛−1

Bu yerdan
𝑎 = 𝑞



+ 𝑟1 = 𝑞





+ 1 = 𝑞 + 1





= ⋯ = 𝑞 + 1






𝑏 0 𝑏
0 𝑏
0 𝑞 + 𝑟2



+ ⋯

0 𝑞 + 1

𝑟1



𝑏
Qisqacha, 𝑎 = [𝑞0, 𝑞1, 𝑞2, … , 𝑞𝑛] (1).
1 𝑟1
1
𝑞2
1
𝑞𝑛




Download 51.12 Kb.

Do'stlaringiz bilan baham:
  1   2




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling