=0 tenglamaning barcha ildizlari to`plami , 1, -1, -1, -1 elementlardan iborat bo`lmasdan, balki va -1 elementlardan iborat

2.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=2³311 360=2³3²5

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: 2³,3. Bu tub ko`paytuvchilarning ko`paytmasi 264 va 360 sonlarini EKUB I bo`ladi. Ya`ni B(264,360)= 2³3=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:2<sup>3</sup>,3<sup>2</sup>,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)= 2³3²11∙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