Evklid algoritmı

Teorema. Eki hám natural sanlar berilgen bolsın, bunda p₁, p₂, …, p_s — turli apiwayı sanlar, k_i va l_i — dáreje kórsetkishler bolsa nomanfiy apiwayı sanlar. M sanı n sanına bolınidhi ushın barlıq i =1, 2, …, s ushın k_i  l_i Teńsizlik atqarılıwı zárúr hám jetkilikli.
Tastıyıqı :
• Eger m=nx, bunda xN, bolsa, x nıń qalegen apiwayı bóliwshisip₁, p₂, … , p_s sanlardan birine teń boladı. Sonıń ushin sıyaqlı jazıw múmkin, bul jerde t_i0.
Bunnan .
Natural sandıń apiwayı kóbeytiwshilerge jayılmasinan birden-birliginen k_i=l_i+t_i, bunnan bolsa hámme i=1, 2, 3, … , s ushin k_il_i ekeni kelip shıǵadı.
 Agar bárshe i=1, 2, 3, … , s uchun k_il_i bolsa, ol halda boladı. Bundan m=nx ekani kelib shıǵadı.
Bul teoremadan berilgen sanlardıń eń úlken ulıwma bóliwshisin hám eń kishi ulıwma eseligin tabıwdıń jańa uslın beredi.
1. EKUB(m₁,m₂,…,m_r) = , bul jerde bárshe i=1,2,…,s lar ushın u_i=min{k_1i,k_2i,…,k_ri}.
Yaǵnıy, berilgen sanlardıń eń úlken ulıwma bóliwshisin tabıw ushın olardıń apiwayı kóbeytiwshilerge jayılmasındaǵı birdey apiwayı kóbeytiwshilerdi eń kishi dárejeleri menen alıp, olardı óz-ara kóbeytiw kerek.
2. EKUK(m₁,m₂,…,m_r) = , bu yerda bárshe i=1,2,…,s lar uchun v_i=max{k_1i,k_2i,…,k_ri}.
Yaǵnıy, berilgen sanlardıń eń úlken ulıwma bóliwshisin tabıw ushın olardıń apiwayı kóbeytiwshilerge jayılmasındaǵı birdey apiwayı kóbeytiwshilerdi eń kishi dárejeleri menen alıp, olardı óz-ara kóbeytiw kerek.
Misol. 91476, 3960 va 3360 sanlarınıń eń úlken uliwma bóliwshisin tabıń.

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
Juwap: 12
Misol: 462, 252, 90 sanlarınıń eń kishi ulıwma eseligi tabıń.

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
Juwap: 36036.
5. Berilgen sandıń bóliwshileri sanın anıqlaw.
Teorema. sanınıń bárshe natural bóliwshileri sanı (₁+1) (₂+1)… (_k+1) ga teń.
Tastıyıq. n sanınıń hár bir natural bóliwshisin birden-bir usılda kóriniste jazıw múmkin, bunda bárshe i=1,2,3, …, k lar ushun _i≤_i. sonıń ushın n sanınıń bárshe bóliwshileri sanı (₁,₂,₃, …,_k) komplekstiń múmkin bolǵan bárshe jaǵdayları sanına teń._i son 0 dan _i ǵa shekem _i+1 qıylı baha qabıl etedi, usınıń sebepinen múmkin bolǵan jaǵdaylar sanı (₁+1) (₂+1)… (_k+1) ǵa teń.
Mısal. 180 sanınıń bárshe natural bóliwshileri sanın tabıń.
Sheshiliwi. 180=2²3²5. (180)=(2+1)(2+1)(1+1)=18
Juwap: 18 ta.
6. Birpara ájayıp sanlar
6. 1. Jetilisken sanlar.
Evklid óziniń “Negizler”ida jetilisken sanlar menen shuǵıllanǵan. Ol jetilisken san dep óziniń tán bóliwshileri (sol sandıń ózinden basqa bóliwshileri) qosındısina teń bolǵan sanlardı ataǵan. Eger n sanınıń tán bóliwshileri qosındısi (n) menen belgilensa, jetilisken san ushın (n)=n boladı.
Mısalı, 6=1+2+3; 28=1+2+4+7+14.
Áyyemgi greklarga (eki mıń jıl aldın ) tek 4 jetilisken san málim bolǵan : 6, 28, 496, 8128.
Jetilisken sanlardı payda etiw usılı tómendegi Yevklid-Eyler teoremasida aytılǵan.
Teorema (Yevklid-Eyler teoremasi). Eger n=2^k-1(2^k-1) (k>1 natural san) bolıp, 2^k-1 apiwayı san bolsa, n jetilisken san baladı.
6. 2. Baxıtlı sanlar.
1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33,... (1)
taq sanlar izbe-izliginen tómendegishe jańa izbe-izlik dúzemiz.
u₁=1 va u₁ Den úlken bolǵan eń kishi toq san 3 ni u2 dep alamız. Endi (1) izbe-ızlıqten hár bir úshinshi elementin óshiremiz. Nátiyjede odaǵı 5, 11, 17,... nomerler óshirilip, 1, 3, 7, 9, 13, 15, 21, 25, 27, 31, 37, ... (2)
izbe-izlik hosil boladı. (2) izbe-izliktiń u₂=3 den keyingi óshirilmesten qalǵan elementa 7 ni u₃ dep alamız : u3=7. Endi (2) izbe-ızlıqtıń hár bir jetinshi elementin óshiremiz. Nátiyjede
1, 3, 7, 9, 13, 15, 25, 27, 31, 37,... (3)
izbe-ızlıq dosil baladı. (3) de u3=7 den keyin óshirilmagan hadni u4=9 dep alamız. Endi (3) izbe-ızlıq -dıń hár bir 9 -hadini óshiremiz hám taǵı basqa. Sol jol menen sonday izbe-ızlıqtı payda etamiz, onıń 100 den kishi bolǵan hadlari tómendegilerden ibarat baladı:
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)
Sol jol menen dúzilgen sheksiz izbe-ızlıqtıń hadlari baxıtlı sanlar dep ataladı. Baxıtlı san dep at beriliwine sebep, olardıń óshirilmesten qrlganligi bolsa kerek. (4) izbe-ızlıqta sheksiz kóp apiwayı sanlar bar, degen gipoteza ámeldegi bolsa -de, lekin bul másele házirge shekem tastıyıq etilmegen. 98600 ge shekem bolǵan baxıtlı sanlar arasında 715 apiwayı baxıtlı san bar ekenligi esaplanǵan.
6. 3. Qolay sanlar.
Tómendegi teorema orınlı bolıp tabıladı:Agar natural san ushin (*) munásebetler o`rinli bo`lsa, (bunda A, B—natural, , ₁, , ₁ — nólden parqlı pútún sanlar ), ol halda n quramalı san baladı (A=B bolǵanda yoyilma  va  larnıń belgileri menen parq qilsalar, olar birdey jayılmalar dep qabıl etiledi).
Eger natural n sanı ushın (*) dıń birinshisi orınlı bolsa, ol halda n apiwayı san bolmawi múmkin.
Bul teorema úlken áhmiyetke iye, sebebi onıń járdeminde berilgen sandıń (*) kórinistegi eki yoyilmasini tabıw nátiyjesinde, ol sandıń quramalılıǵın anıqlaw múmkin baladı. AB kóbeytpeniń ayırım bahaları ushın joqarıda keltirilgen teoremanıń kerisi orınlı boladı, yaǵnıy ol kóbeytpe ushın hár qanday quramalı san A²+B² formasında eki qıylı ajırasıwǵa iye baladı.
Eyler tómendegi sorawdı qoyǵan edi: AB kóbeytpeniń qanday bahalarında apiwayı san A²+B² formada ańlatpalanadı?
Bul sorawǵa Eyler tolıq juwap bere almaǵan bolsa -da, lekin 1 den 10000 ge shekem bolǵan natural sanlar ishinde bunday kóbeytpelerdiń tek 65 si bar ekenligin kórsetdi hám olardı qolay sanlar dep atadi.
14 k-1, 14 k+9, 14 k+11 kórinistegi taq sanlardıń apiwayı san bolıwı ushın. olardıń x²+7y² formasında tek bir qıylı jol menen ańlatılıwları tastıyıqlanǵan, bunda (x, y) =1, 7 bolsa qolay san.
Mısallar.1) 29=142+1=1²+72²,
37=142+9=3²+72²,
67=144+11=2²+73²;
2) 11=x²+7y² (bunda AB=7), bul hal tek x=2, y=1 bolǵanda boladı.
41=x²+37y². AB=37, x=2, y=1;
18518809=197²+1848100² apiwayı san. AB= 11848=1848.
Eyler taqan qolay sanlar tómendegishe: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 16, 18, 21, 22, 24, 25, 28, 30, 33, 37, 40, 42, 45, 48, 57, 58, 60, 70, 72, 78, 85, 88, 93, 102, 105, 112, 120, 130, 133, 165, 168, 177, 190, 210, 232, 240, 253, 273, 280, 312, 330, 345, 357, 385, 408, 462, 520, 760, 840, 1320, 1365, 1848. Eyler shıdam menen esaplawdı 100000 ge shekem dawam ettirgen bolsa -de, kórsetilgen 65 qolay sandan basqa qolay sanlar tabılǵanı joq. Búgingi kúnde de tek sol 65 qolay san bar.
Qolay sanlar sanınıń shekliligini matematikalıq Choula tastıyıq etken. Lekin olardıń qansha ekenligine anıq juwap bere almaymız.