Eng katta umumiy bo'luvchi va eng kichik umumiy bo'linuvchi. O'zaro tub sonlar. Yevklid algoritmi

Eng katta umumiy bo'luvchi va eng kichik umumiy bo'linuvchi. o'zaro tub sonlar. Yevklid algoritmi Reja: Eng katta umumiy bo'luvchi (EKUB). Eng kichik umumiy bo'linuvchi (karrali) (EKUK). o'zaro tub sonlar va ularning xossalari. Yevklid algoritmi. ta'rif. a va b butun sonlarning ikkisini xam buladigan son shu sonlarning umumiy bo'luvchisi deyiladi. Biz fakat natural bo'luvchilar bilan shu²ullanamiz. Misol. 12 va 18 sonlarining umumiy bo'luvchilari 1, 2, 3, 6. bo'ladi. Bu misoldan kurinadiki, a va b sonlarning bir nechta umumiy bo'luvchilari mavjud bo'lishi. Bu umumiy bo'luvchilar to'plamini Da, b orqali belgilaylik. Demak, D12, 18 =1, 2, 3, ,6 bo'ladi. ta'rif. a va b natural sonlar umumiy bo'luvchilarining eng kattasiga shu sonlarning eng katta umumiy bo'luvchisi (EKUB) deyiladi va uni (a; b) ko'rinishda belgilanadi. Misol. (12;18)=6. ta'rif. Agar (a; b)=1 bulsa, u holda a va b natural sonlar o'zaro tub sonlar deyiladi. Misol. (7;11)=1 bo'lgani uchun 7 va 11 sonlari o'zaro tub sonlar, lekin (12;18)=6 bo'lgani uchun 12 va 18 sonlari o'zaro tub sonlar bulmaydi. Agar A to'plam. aN sonning bo'luvchilari to'plami, V to'plam bN sonning bo'luvchilari to'plami bulsa, u holda Da,b=AV bo'ladi. Teorema. (a:b)= (a;b)= b. Isboti. a:b va b:b. Demak, b son a ning xam, uzining xam umumiy bo'luvchisi ekan. Lekin bu sonlar uchun b dan katta umumiy bo'luvchi yuk. Chunki, b son uzidan katta songa bulinmaydi. Shu sababli b son a va b sonlar uchun EKUB bo'ladi. Demak, Da,b=Db bo'ladi. Misol. 12:6 = (12; 6)=6. Natija. (a; b) = d bulsa, u holda shunday u va v butun sonlar topiladiki, ular uchun au+bv=d tenglik bajariladi. Bu natijaning isboti [1] da keltirilgan. ta'rif. a1, a2, , an butun sonlarning barchasini buladigan son shu sonlarning umumiy bo'luvchisi deyiladi. a1, a2, , an butun sonlarning umumiy bo'luvchilari bir nechta bo'lishi mumkin. Ularning eng kattasiga a1,a2,,an sonlarning EKUB deyiladi va uni (a1, a2, , an) ko'rinishida belgilanadi. ta'rif. Agar (a1, a2, , an)=1 bulsa, u holda a1, a2, , an natural sonlarni o'zaro tub sonlar deyiladi. Uzapo tub sonlar quyidagi xossalarga ega: 1.((a; c)=1 (b;c)=1=((ab;c)=1); 2. ((ab:c)(a:c)=1)=(b:c)(c0): 3. ((a;b)=1)=((an;bn)=1) (nN); 4. ((a;b)=d)=(()=1); 5. ((a:b)(a:c)((b;c)=1)=(a:bc) (b0, c0) Bu xossalarning isboti [ 1,2] da keltirilgan. ta'rif. Agar a1, a2, , an sonlarning ixtiyoriy ikkitasi o'zaro tub bulsa, u holda ular juftlama o'zaro tub sonlar deyiladi. Misol. (7; 9; 16)=1 va (7,9)=1, (7,16)=1,(9,16)=1 bo'lgani uchun 7, 9, 16 sonlari juftlama o'zaro tub sonlar deyiladi. Teorema. a=bq+r = (a;b)=(b;r). Isboti. d son a va b sonlarning ixtiyoriy umumiy bo'luvchisi ...