Қазақстан республикасы білім және ғылым министрлігі алматы облыстық білім департаменті қапшағай қалалық білім, дене тәрбиесі және спорт бөлімі қапшағай қаласы «№12 орта мектеп мектепке дейінгі шағын орталығымен»

Евклид алгоритмі – екі бүтін санның ең үлкен ортақ бөлгішін және өзара өлшенетін кесінділердің ең үлкен ортақ өлшемін табу тәсілі.

Алгоритмнің «бір-бірінен азайту» және «бір-біріне бөлу» әдістері бар. Өзара өлшенетін кесінділердің ең үлкен ортақ өлшемін табу үшін азайту әдісі қолданылса, екі бүтін санның ең үлкен ортақ бөлгішін табу үшін бөлу әдісі тиімді.

Қазіргі кездегі әріпті өрнектермен Евклид алгоритмі былай жазылады, a > b; a, b Z:

ЕҮОБ(а;в) = as + вt,

мұндағы s және t – бүтін сандар. Ең үлкен ортақ бөлгішті осындый түрде жазуды Безу қатынасы, s және t – Безу коэффициенттері деп аталады. Осы Безу қатынасы өрнегін қарасақ, екі айнымалысы бар теңдеуді еске түсіреді: s және t сандары х және у айнымалылардың мәндері. Бұдан Евклид алгоритмін Диофант теңдеулерін шешуге де қолдануға болады деуге болады.

Кез-келген екі натурал санның кем дегенде бір ортақ бөлгіші болады (d=1). Сондықтан да Евклид алгоритмі шексіз жалғаса алмайды. Егер (a,b)=1 болса, a және b сандары өзара жай сандар деп аталады. Олар жай сандар немесе құрама сандар да болуы мүмкін. Мысалы, (33,35) =1.

Егер a санын b санына бөлгенде r қалдық қалатын болса, онда a және b сандарының ең үлкен ортақ бөлгіші b және r сандарының ең үлкен ортақ бөлгішіне тең болатынын дәлелдейік: (a,b) = (b,r).

a және b сандарының барлық ортақ бөлгіштері b және r сандарының барлық ортақ бөлгіштері де болып табылатынын дәлелдесек, онда олардың ең үлкен ортақ бөлгіштері де тең болатыны дәлелденеді.

d саны a және b сандарының қандай да бір ортақ бөлгіші болсын. Онда a = qb+r болғандықтан r=a – qb саны да d-ға бөлінеді (a саны да, qb саны да d-ға еселі). Сондықтан d саны b және r сандарының да бір ортақ бөлгіші болады. Сол сияқты b және r сандарының бір ортақ бөлгіші d болса, онда ол a және b сандарының да бір ортақ бөлгіші болады.

Егер r =0 болса, a және b сандарының ең үлкен ортақ бөлгіші b санының өзі болады.

Мысалы: (36, 20) = (20, 16) = (16, 4) =4.

Мысал. а = 525, b = 231 болсын. Евклид алгоритмін пайдаланайық:

Немесе мынадай кестемен жазу да ыңғайлы:

525 = 231 · 2 + 63

Сонымен, (525, 231) = 21, яғни ең үлкен ортақ бөлгіштің Безу қатынасы арқылы жазылуы:

21 = 63 - 42 · 1 = 63 - (231 - 63 · 3) · 1 =
= 525 - 231 · 2 - (231 - (525 - 231 · 2) · 3) =
= 525 · 4 - 231 · 9.

Евклид алгоритмі ең үлкен ортақ бөлгішті табу үшін ғана емес, оның бар болуын дәлелдеу үшін де қолданылады. Көпмүшелер және кесінділер үшін де алгоритм дәл осылай пайдаланылады. Өзара өлшенбейтін кесінділер үшін алгоритм шексіз жалғасады.