Evklid algoritmı

Evklid algoritmı

Evklid algoritmı — eki pútkil sandıń eń úlken ulıwma bóliwshisin tabıw, sonıń menen birge eki ólshewles kespeniń ulıwma ólshewin tabıw usılı. Eki oń pútkil sandıń eń úlken ulıwma bóliwshisin tabıw ushın áwele úlken sandı kishi sanǵa bolıw, keyininen kishi sandı úlken sandıń qaldıǵına, keyin bolsa birinshi qaldıqtı ekinshi qaldıqqa hám taǵı basqa bolıw kerek. Bul processdagi nólden ayrıqsha aqırǵı qaldıq berilgen sanlardıń eń úlken ulıwma bóliwshisi boladı.

Eki kespeniń eń úlken ulıwma ólshewin tabıw ushın da áne sonday jol tutıladı. Bunda qaldıqlı bolıw ámeli onıń geometriyalıq analogi menen almastırıladı : kishi kespe úlken kespege neshe ret jaylassa, sonsha ret qoyıladı, úlken kespeniń qalǵan bólegi (“bólıwden qalǵan qaldıq” retinde qabıl etiletuǵın ) kishi kespege qóyıladı hám t.b. Eger a hám b kespelar ólshewles bolsa, ol halda aqırǵı nólden ayrıqsha qaldıq bul kespelardiń eń úlken ulıwma ólshewin beredi. Kespelar ulıwma ólshewge iye bolmaǵan halda nólden ayrıqsha qaldıqlar izbe-izligi sheksiz dawam etedi.
Evklid algoritmı áyyemgiden málim. Onıń jası 2 mıń jıldan artıq. Ol Evklidtiń «Negizler» ida tariyplengen. Evklid bul algoritmnen paydalanıp apiwayı sanlar, eń kishi ulıwma bóliniwshi hám basqa ózgesheliklerdi keltirip shıǵarǵan. Evklid algoritmı eki kespeniń eń úlken ulıwma ólshewin tabıw usılı retinde (geyde ol gezekpe-gezek ayırıw dep ataladı ) pifagorshılarǵa da málim edi. XVI ásir ortalarında Evklid algoritmı bir ózgeriwshili kóp aǵzalılarǵa da qollanıw etildi. Keyinirek Evklid algoritmın birpara basqa algebrik obiektler ushın da anıqlawǵa muwapıq boldı.
Evklid algoritmı kóp qollanıwlarǵa iye. Onı anıqlawshı teńlikler a hám b sanlardıń eń úlken ulıwma bóliwshisi bolǵan d sanın d=ax+by kórinisinde ańlatıw imkaniyatın beredi (x; y — pútkil sanlar ), bul formula bolsa eki belgisizli birinshi dárejeli Diofant teńlemeleri sheshimlerin tabıwǵa tiykar boladı. Evklid algoritmı ratsional sandı úzliksiz bólshek retinde súwretlew quralı bolıp tabıladı. Ol kóbinese elektron esaplaw mashinaları programmalarında qollanıladı, sanlar teoriyasında da áhmiyeti úlken bolıp tabıladı.