|
Sonlarning tub ko`paytuvchilarga yoyish usuli bilan ularning EKUB va EKUK ini topish
|
| bet | 45/61 | | Sana | 24.05.2024 | | Hajmi | 1,62 Mb. | | #252315 |
Bog'liq =0 tenglamaning barcha ildizlari to`plami , 1, -1, -1, -1 elemen2.6.Sonlarning tub ko`paytuvchilarga yoyish usuli bilan ularning EKUB va EKUK ini topish
Sonni tub sonlar ko`paytmasi ko`rinishida yozish uni tub ko`paytuvchilarga ajratish deyiladi.
Masalan, 78=2∙3∙13. Istalgan murakkab son tub ko`paytuvchilarga ajraydi va bu yoyilma yagona ekanligi Tub va murakkab sonlar mavzusida aytib o`tildi. Sonlarni tub ko`paytuvchilarga yoyish yoki sonning kanonik ko`rinishda yozish uning EKUK va EKUB ini topishda qo`llaniladi. Masalan 264 va 360 sonlarini EKUK va EKUB ini topaylik. Buning uchun ularning kanonik yoyilmasini yozib olamiz:
264=23311 360=23325
264
|
2
|
|
360
|
2
|
132
|
2
|
180
|
2
|
66
|
2
|
90
|
2
|
33
|
3
|
45
|
3
|
11
|
11
|
15
|
3
|
1
|
|
5
|
5
|
|
|
1
|
|
64 va 360 sonlarining kanonik yoyilmasiga kiruvchi umumiy tub ko`paytuvchilarning eng kichik darajadagilarini ajratamiz. Bu tub ko`paytuvchilar: 23,3. Bu tub ko`paytuvchilarning ko`paytmasi 264 va 360 sonlarini EKUB I bo`ladi. Ya`ni B(264,360)= 233=24.
Umuman, berilgan a va b sonning EKUB ini topish uchun:
- ularning kanonik yoyilmasini topamiz;
- kanonik yoyilmadagi umumiy tub sonlar ko`paytmasini eng kichik dardjalarini ajratamiz;
- bu kichik darajali tub sonlarning ko`paytmasi berilgan a va b sonining EKUBi bo`ladi.
Endi, EKUKni kanonik yoyilma yordamda topish usulini qaraymiz. 264 va 360 sonlarining kanonik yoyilmasidan barcha tub ko`paytuvchilarning eng yuqori darajadagilarini ajratamiz:23,32,5,11. 264 sonida 5 sonini 0-darajada qatnashyayti deb olish mumkin. Bu tub ko`paytuvchilarning ko`paytmasi 264 va 360 sonini EKUKi bo`ladi.Ya`ni, K(264,360)= 233211∙5=3960.
Berilgan sonning kanonik yoyilmasini topish uchun:
- sonlarning kanonik yoyilmasini tuzamiz;
- kanonik yoyilmalardagi barcha sonlarning eng katta darajalilarini ajratamiz;
- bu katta darajali tub sonlarning ko`paytmasi berilgan sonlarning EKUKi bo`ladi.
Evklid algoritmi. Kanonik yoyilma usulida EKUK va EKUBni topish ba`zan noqulay va uzoq hisob-kitoblarni talab qiladi. Berilgan sonning EKUB va EKUKini topishning soddaroq usuli Evklid algoritmi hisoblanadi va u u quyidagi mulohazalarga asoslanadi.
1. Agar a soni b ga bo‘linsa, B(a,b)=b bo‘ladi, chunki b ning o‘zidan katta bo‘luvchisi yo‘q.
2. Agar a soni b ga bo‘linmasa, a=bq+r va ,UB(a,b)=UB(b,r) bo‘ladi (UB- umumiy bo`luvchilar), ya’ni a soni b ga qoldiqli bo‘linadi, a va b ning umumiy bo‘luvchilari to‘plami b va a ni b ga bo‘lishdagi qoldiq r ning umuiy bo‘luvchilari to‘plami bilan ustma-ust tushadi. d= UB(a,b) bo‘lsin. (a:d b:d)->(r=a–bq):d (ayirmaning bo‘linishi haqidagi teoremaga ko‘ra) d= UB(b,r). Aksincha d= UB(b,r) bo‘lsin, u holda a=bq+r ham d ga bo‘linadi, (yigindini bo‘linishi haqidagi teoremaga ko‘ra), bundan d= UB(a,b) degan xulosa kelib chiqadi.
3. bo`lsa B(a,b)=B(b,r) bo‘ladi. 2–mulohazaga ko‘ra a,b va b, r sonlarining umumiy bo‘luvchilari to‘plamlari bir xil, demak bu to‘plamlarning eng katta elementlari ham bir xil bo‘ladi.
Ana shu 3 ta mulohazaga tayanib a, b sonlarining EKUB ini topishni b, r sonlari EKUBini topish bilan almashtirish mumkin bo‘ladi. Agar b r ga karrali bo‘lsa, va hokazo. Bu jarayon biror qoldiq o‘zidan keyingi qoldiqqa qoldiqsiz bo‘linguncha davom etadi va shu oxirgi 0 dan farqli qoldiq B(a, b) bo‘ladi.
Masalan: B(728,455) ni topish kerak bo‘lsin. Ketma -ket bo‘lishni ixcham ko‘rinishida quyidagicha yozish mumkin: B(728,455)=91
|
|
|
728
|
455
|
|
|
|
455
|
1
|
|
|
455
|
273
|
|
|
|
273
|
1
|
|
|
273
|
182
|
|
|
|
182
|
1
|
|
|
182
|
91
|
=B(a,b)
|
|
|
182
|
2
|
|
|
|
0
|
|
|
|
|
|
| |
