Evklid algoritmi

Misol. EKUK(462,252) ni toping.
462 = 252⋅1 + 210,
252 = 210⋅1 + 42,
210 = 42⋅5.
demak, EKUB(462,252) =42

Javob: EKUK(462,252)=2772


Mashqlar.
Quyidagi sonlarning EKUK ini toping.
1) 645 и 381; 2) 846 и 246; 3) 5338 и 11618.
Javob: 1) 81915; 2) 34686; 3) 197506.


4. Natural sonlarni tub ko`paytuvchilarga ajratish.
Istalgan natural sonni tub ko`paytuvchlar ko`paytmasi shaklida tasvirlash mumkin, bunda bir xil ko`paytuvchilar ko`paytmasi daraja shaklida yozildi. Agar zarur bo`lsa, bu ko`paytmada tub sonlarning nol ko`rsakichli darajasini ham qo`llash mumkin. Shunday qilinganda chekli sondagi istalgan tub sonlarni bir xil tub sonlar nomanfiy butun ko`rsatkichli darajalarining ko`paytmasi shaklida tasvirlash mumkin.
Misol. a=2<sup>5</sup>513<sup>3</sup>, b=3<sup>2</sup>7<sup>4</sup>, c=5<sup>3</sup>17<sup>2</sup> sonlarni bir tub sonlar darajalarining o`paytmasi shaklida yozing.
Yechilishi.
a=2⁵513³=2⁵3⁰5¹7⁰13³17⁰,
b= b=3²7⁴=2⁰3²5⁰7⁴13⁰17⁰,
c=5³17²=2⁰3⁰5³7⁰13⁰17².
Teorema. Ikkita va natural sonlar berilgan bo`lsin, bunda p<sub>1</sub>, p<sub>2</sub>, …, p<sub>s</sub> — turli tub sonlar, k<sub>i</sub> va l<sub>i</sub> — daraja ko`rsatkichlar esa nomanfiy butub sonlar. M soni n soniga bo`linidhi uchun barcha i =1, 2, … , s uchun k<sub>i</sub>  l<sub>i</sub> tengsizlik bajarilishi zarur va yetarli.
Isboti:
 Agar m=nx, bunda xN, bo`lsa, x ning istalgan tub bo`luvchisi p<sub>1</sub>, p<sub>2</sub>, … , p<sub>s</sub> sonlardan biriga teng bo`ladi. Shuning uchun kabi yozish mumkin,bu yerda t_i0.
Bundan .
Natural sonning tub ko`paytuvchilarga yoyilmasining yagonaligidan k<sub>i</sub>=l<sub>i</sub>+t<sub>i</sub>, bundan esa barcha i=1, 2, 3, … , s uchun k<sub>i</sub>l<sub>i</sub> ekani kelib chiqadi.
 Agar barcha i=1, 2, 3, … , s uchun k<sub>i</sub>l<sub>i</sub> bo`lsa, u holda bo`ladi. Bundan m=nx ekani kelib chiqadi.
Bu teoremadan berilgan sonlarning eng katta umumiy bo`luvchisini va eng kichik umumiy karralisini topishning yangi uslini beradi.
1. EKUB(m₁,m₂,…,m_r) = , bu yerda barcha i=1,2,…,s lar uchun u_i=min{k_1i,k_2i,…,k_ri}.
Ya`ni, berilgan sonlarning eng katta umumiy bo`luvchisini topish uchun ularning tub ko`paytuvchilarga yoyilmasidagi bir xil tub ko`paytuvchilarni eng kichik darajalari bilan olib, ularni o`zaro ko`paytirish kerak.
2. EKUK(m₁,m₂,…,m_r) = , bu yerda barcha i=1,2,…,s lar uchun v_i=max{k_1i,k_2i,…,k_ri}.
Ya`ni, berilgan sonlarning eng kichik umumiy karralisini topish uchun ularning tub ko`paytuvchilarga yoyilmasidagi bir xil tub ko`paytuvchilarni eng katta darajalari bilan olib, ularni o`zaro ko`paytirish kerak.
Misol. 91476, 3960 va 3360 sonlarining eng katta umumiy bo`luvchisini toping.

91476	2	3960	2	3360	2
45738	2	1980	2	1680	2
22869	3	990	2	840	2
7623	3	495	3	420	2
2541	3	165	3	210	2
847	7	55	5	105	3
121	11	11	11	35	5
11	11	1	7	7
1	1
91476=2^23^3711^2		3960=2^33^2511		3360=2^5357

Bulardan, EKUB(1476, 3960, 3360)=2²3²5⁰7⁰11⁰=12
Javob: 12
Misol: 462, 252, 90 sonlarining eng kichik umumiy karralisini toping.

462	2	252	2	91	7
231	3	126	2	13	13
77	7	63	3	1
11	11	21	3
1	7	7
1
462=23711		252=2^23^27		91=713

Bulardan, EKUK(462, 252, 91)=2²3²7¹11¹13¹=36036
Javob: 36036.
5. Berilgan sonning bo`luvchilari sonini aniqlash.
Teorema. sonining barcha natural bo`luvchilari soni (₁+1) (₂+1)… (_k+1) ga teng.
Isbot. n sonining har bir natural bo`luvchisini yagona usulda ko`rinishda yozish mumkin, bunda barcha i=1,2,3, …, k lar uchun _i≤_i. shuning uchun n sonining barcha bo`luvchilari soni (<sub>1</sub>,<sub>2</sub>,<sub>3</sub>, …,<sub>k</sub>) majmuaning mumkin bo`lgan barcha holatlari soniga teng. _i son 0 dan _i gacha _i+1 xil qiymat qabul qiladi, shu sababli mumkin bo`lgan holatlar soni (<sub>1</sub>+1) (<sub>2</sub>+1)… (<sub>k</sub>+1) ga teng.
Misol. 180 sonining barcha natural bo`luvchilari sonini toping.
Yechilishi. 180=2²3²5. (180)=(2+1)(2+1)(1+1)=18
Javob: 18 ta.
6. Ba`zi ajoyib sonlar
6.1. Mukammal sonlar.
Evklid o`zining “Negizlar”ida mukammal sonlar bilan shug`ullangan. U mukammal son deb o`zining xos bo`luvchilari (shu sonning o`zidan boshqa bo`luvchilari) yig`indisiga teng bo`lgan sonlarni atagan. Agar n sonining xos bo`luvchilari yig`indisi (n) bilan belgilansa, mukammal son uchun (n)=n bo`ladi.
Masalan, 6=1+2+3; 28=1+2+4+7+14.
Qadimiy greklarga (ikki ming yil oldin) faqat 4 ta mukammal son ma`lum bo`lgan: 6, 28, 496, 8128.
Mukammal sonlarni hosil qilish usuli quyidagi Yevklid-Eyler teoremasida bayon etilgan.
Teorema(Yevklid-Eyler teoremasi). Agar n=2^k-1(2^k-1) (k>1 natural son) bo`lib, 2<sup>k</sup>-1 tub son bo`lsa, n mukammal son bo`ladi.
6.2. Baxtli sonlar.
1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, ... (1)
toq sonlar ketma- ketligidan quyidagicha yangi ketma-ketlik tuzamiz.
u<sub>1</sub>=1 va u<sub>1</sub> dan katta bo`lgan eng kichik toq son 3 ni u₂ deb olamiz. Endi (1) ketma-ketlikning har bir uchinchi elementini o`chiramiz. Natijada undagi 5, 11, 17, ... raqamlar o`chirilib,
1, 3, 7, 9, 13, 15, 21, 25, 27, 31, 37, ... (2)
ketma-ketlik hosil bo`ladi. (2) ketma-ketlikning u<sub>2</sub>=3 dan keyingi o`chirilmasdan qolgan elementa 7 ni u₃ deb olamiz: u₃=7. Endi (2) ketma-ketlikning har bir yettinchi elementini o`chiramiz. Natijada
1, 3, 7, 9, 13, 15, 25, 27, 31, 37, ... (3)
ketma-ketlik dosil bo`ladi. (3) da u₃=7 dan keyin o`chirilmagan hadni u<sub>4</sub>=9 deb olamiz. Endi (3) ketma-ketlik­ning har bir 9-hadini o`chiramiz va hokazo. Shu yo`l bilan shunday ketma-ketlikni hosil qilamizki, uning 100 dan kichik bo`lgan hadlari quyidagilardan iborat bo`ladi:
1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 53, 63,
67, 69, 73, 75, 79, 87, 93, 99 (4)
Shu yo`l bilan tuzilgan cheksiz ketma-ketlikning hadlari baxtli sonlar deb ataladi. Baxtli son deb nom be­rilishiga sabab, ularning o`chirilmasdan qrlganligi bo`lsa kerak. (4) ketma-ketlikda cheksiz ko`p tub sonlar bor, degan gipoteza mavjud bo`lsa-da, lekin bu masala hozirgacha isbot qilinmagan. 98600 gacha bo`lgan baxtli sonlar orasida 715 ta tub baxtli son mavjudligi hisoblangan.