b'\n_START_ARTICLE_\nI\xc5\xa1pl\xc4\x97stinis Euklido algoritmas\n_START_PARAGRAPH_\nI\xc5\xa1pl\xc4\x97stinis Euklido algoritmas - Euklido algoritmo t\xc4\x99sinys, skirtas rasti dviej\xc5\xb3 nat\xc5\xabrali\xc5\xb3j\xc5\xb3 skai\xc4\x8di\xc5\xb3 a\\,,b\\, did\xc5\xbeiausi\xc4\x85 bendr\xc4\x85 dalikl\xc4\xaf, bei rasti sveikuosius x\\,, y\\,, tenkinan\xc4\x8dius ax + by = dbd(a, b).\\,\n_START_SECTION_\nAlgoritmas\n_START_PARAGRAPH_\nNema\xc5\xbeindami bendrumo tarkime, kad  a > b  Tuomet a u\xc5\xbesira\xc5\xa1o kaip_NEWLINE_a= bq + r, kur dalybos liekana tenkina 0< r < b . Analogi\xc5\xa1kai_NEWLINE_b= rq_1 + r_1, kur  0<r_1<r _NEWLINE_r= r_1q_2 + r_2, kur  0<r_2<r_1 _NEWLINE_\xe2\x80\xa6_NEWLINE_r_{k}= r_{k+1} q_{k+2} + r_{k+2}, kur  0<r_{k+2}<r_{k+1} _NEWLINE_r_{k+1}= r_{k+2}q_{k+3}_NEWLINE_I\xc5\xa1 r>r_{1}> ... > r_{k+2} seka, kad ka\xc5\xbekada gausime dalybos liekan\xc4\x85 lygi\xc4\x85 0. Tuomet paskutinioji nenulin\xc4\x97 liekana r_{k+2} ir bus did\xc5\xbeiausias bendrasis daliklis._NEWLINE_I\xc5\xa1 prie\xc5\xa1 paskutin\xc4\x97s lygyb\xc4\x97s galime i\xc5\xa1reik\xc5\xa1ti r_{k+2} per r_{k+1} ir r_{k}. I\xc5\xa1 dar ankstesn\xc4\x97s galima i\xc5\xa1reik\xc5\xa1ti r_{k+1} per r_{k} ir r_{k-1}. \xc4\xaestat\xc4\x99 \xc4\xaf pirm\xc4\x85j\xc4\x85 i\xc5\xa1rai\xc5\xa1k\xc4\x85 gausime r_{k+2} i\xc5\xa1rai\xc5\xa1k\xc4\x85 per r_{k} ir r_{k-1}. Taip toliau vis t\xc4\x99sdami gausime r_{k+2} i\xc5\xa1rai\xc5\xa1k\xc4\x85 per a, b, t. y. rasime x, y, tenkinan\xc4\x8dius ax + by = dbd(a, b)\n_START_SECTION_\nPavyzdys\n_START_PARAGRAPH_\nImkime a  = 46, b  = 32. Nuosekliai atlikdami veiksmus gauname:_NEWLINE_46 = 32 \xc3\x97 1 + 14;_NEWLINE_32 = 14 \xc3\x97 2 + 4;_NEWLINE_14 = 4 \xc3\x97 3 + 2;_NEWLINE_4 = 2 \xc3\x97 2;_NEWLINE_Gavome, kad dbd(46,32) = 2._NEWLINE_2 = 14 + 4 \xc3\x97 (-3) = 14 + (32 + 14\xc3\x97 (-2)) \xc3\x97 (-3) = 32 \xc3\x97 (-3) + 14 \xc3\x97 7 = 32 \xc3\x97 (-3) + (46 \xe2\x80\x93 32) \xc3\x97 7 = 32 \xc3\x97 (-10) + 46 \xc3\x97 7.'