Yevklid algoritmi

Yevklid algoritmi.

Butun sonlar uchun ma`lum bo`lgan Yevklid algoritmi va uning natijalarini ko`pxadga ham tadbiq etishini ko`rib o`taylik . f(x) 0 bo`lib f(x) ko`pxadning darajasi (x) 0 ko`pxadning darajasidan kichik emas deb faraz qilamiz va f(x) ni (x) ga bo`lamiz . Hosil bo`lgan bo`linma va qoldiqni mos ravishda g<sub>1</sub>(x) va r<sub>1</sub>(x) bilan belgilaymiz . Ma`lumki r₁(x) ning darajasi (x) ning darajasidan kichikdir . Endi (x) ni r₁(x) ga bo`lib , bo`linma va qoldiqni g₂(x) va r₂(x) orqali belgilaymiz . Yana r₂(x) ning darajasi r₁(x) ning darajasidan kichikligini etiborga olib , r₁(x) ni r₂(x) ga bo`lamiz va hosil bo`lgan bo`linma va qoldiqni g<sub>3</sub>(x) va r<sub>3</sub>(x) bilan belgilaymiz va h.k. Har bir qoldiqni bundan keyingi qoldiqqa bo`lamiz . Natijada darajalari kamayib boruvchi r₁(x) , r₂(x) , r₃(x), … ko`phadlar ( qoldiqlar) hosil bo`ladi . Bu qoldiqlarni soni albatta cheklidir , chunki ularni darajalari kamayib boruvchi (lekin manfiy emas) butun sonlar ketma ketligini hosil qiladi , bunday qator esa cheksiz bo`la olmasligi ravshan . Shu sababli yuqoridagi bo`lish jarayoni chekli bo`lib , biz shunday r<sub>k</sub>(x) qoldiqqa kelamizki , unga oldingi r<sub>k-1</sub>(x) qoldiq bo`linadigan bo`ladi . Natijada ushbu tengliklar sistemasini hosil qilamiz :

f(x)= (x) g₁(x)+ r₁(x) ,
(x)= r₁(x) g₂(x) +r₂(x) ,
r₁(x) =r₂(x) g₃(x)+ r₃(x),
…………………………..
r_k-2(x)= r_k-1(x) g_k(x)+ r_k(x) ,
r_k-1(x) = r_k(x) g_k+1(x).
Bu ketma –ket bo`lish jarayoni odatda Yevklid algoritmi deyiladi . Endi ko`phadning umumiy bo`luvchilari tushunchasini qaraylik .