Evklid algoritmı

6. 4. Dos sanlar.
Pifagordan dos ne dep soraǵanlarında, «do'stim — meniń ózim. Bul 220 hám 284 larning dosligi» dep juwap bergen eken.
Bul sanlardıń «do'st» ligi neden ibarat, degen sorawǵa juwap beraylik.
Arab matematigi Turaqlı ibn Korra (826 -901 jıllar ) dos sanlardı payda etiw qaǵıydasın bergen edi. Keyinshelik bul qaǵıydanı Ferma qaytaldan tákirarlap, Dekart 1638 jılda baspa etken edi.
Eger m hám n sanlar ushın birewiniń bárshe tán bóliwshileri qosındısi ekinshisine teń bolsa, yaǵnıy (m)= (n) bolsa, olar dost sanlar deb ataladı. Bunda sandıń ózi bo`luvchi sıpatında qabıl qılınbaydı.
Mısalı,
220=1+2+4+71+142 (1, 2, 4, 71 va 142 lar 284 tiń xos bóliwshileri).
284=1+2+4+5+10+11+20+22+44+55+100, oń tárepdegi qosılıwshı -lar 220 dıń tán bóliwshileri bolıp tabıladı.
Demek, 220 hám 284 lar — dos sanlar.
Eger m hám n dos sanlar bolsa, ol halda m=2^p; n=2^ql Bolıwı kerekligin tastıyıqlanǵan. Bunda  — natural san, p, q, l — apiwayı sanlar bolıp, p=(2k+1)²2^2-k-1; q=2^-1+2^+k larǵa teń bolıwı kerekligi de tastıyıqlanǵan. Bul formulanı Turaqlı ibn Korra islep shıqqan.
Eger k=1 dep alınsa, p, q, l apiwayı sanlar ushın p=3²2^2-1-1, q=32^-1-1, l=32^-1 lardı payda etemiz.  ǵa hár túrlı bahalar berip, k=1 ushın tómendegi kesteni dúziw múmkin:

	p	q	l	m	n
2	71	5	11	284	220
4	1151	23	47	18416	17296
7	73727	191	383	4437056	9363584

Álbette hár qanday  ushın p, q, l lar apiwayı san bola bermeydi. Sonıń ushın  ni sonday tańlaw kerek, payda bolǵan p, q, l lar apiwayı sanlar bolsın. Dıń ma`nisi ósiwi menen p, q, l dıń bahaları, atap aytqanda p tez ósedi hám sonıń ushın p apiwayı yamasa quramalı ekenligin anıqlaw ayırım jaǵdaylarda qıyın bolıp qaladı.
Ayırım k=5, 7, 9,... lar ushın joqarıda keltirilgen kesteni dúziw júdá qıyın.
Kórip ótilgenlerden tısqarı dos sanlardıń taǵı bir neshe jupin keltiremiz:
2620 hám 2924;
5020 hám 5564;
6232 hám 6368;
10744 hám 10856 ;
17296 hám 18416 ;
66928 hám 66992.
63020 hám 76084;
Dos sanlardı payda etiwde tiykarǵı qıyınshılıq  Dıń qanday bahalarında p, q, l lar apiwayı san bolıwlıǵın anıqlawda bolıp tabıladı. Sonıń ushın da bárshe dos sanlar kompleksin oyda sawlelendire almaymız.
Házirgi kúnde 900 ǵa jaqın dos sanlar jupi málim bolıp tabıladı. Olar arasında óz-ara apiwayı bolǵan dos sanlar joq.
Eyler dos sanlardıń 60 jupin tapqan edi. Olar arasında hár ekewi de jup san bolǵanları 34 hám hár ekewi toq sanlardan ibarat bolǵanları 26. Biri jup, ekinshisi toq bolǵan dos sanlar jupi barma?
Bul sorawǵa juwap tabılǵanı joq. Eger bunday dos sanlar ámeldegi bolsa, olardıń hár biri 10²³ Den úlken bolıp, mn sanı 20 dan artıq apiwayı bóliwshine ıyelewi kerakligi tastıyıqlanǵan.