Urganch davlat universiteti axborot texnologiyalari kafedrasi

1.2.4. Yevklid algoritmi va uning zamonaviy versiyasi 

Ikkita  butun  sonlarning  eng  katta  umumiy  bo‘luvchisi  n  ikki  sonni  qoldiqsiz  bo‘luvchi 

eng  katta  natural  sondir,  a  va  b  sonlarning  eng  katta  umumiy  bo‘luvchisini  EKUB(a,b)  orqali 

belgilaymiz.  EKUB(a,b)  ni  hisoblash  uchun  a  va  b  larni  oddiy  ko‘paytuvchilarga  yoyishni  va 

ulardan zarur miqdorda umumiy sonlarni tanlab olishga harakat qilamiz. Masalan, 40=2*2*2*5; 

60=2*2*3*5; va EKUB(40,60)=2*2*5. Biroq , bundan yaxshiroq usullar ham mavjud. 

Yevklid algoritmi quyidagilarga asoslangan, ya`ni 

EKUB(a,b)=a, agar b=0, 

EKUB(a,b)=a, agar a=b, 

EKUB(a,b)=EKUB(b,a), agar a

EKUB(a,b)=EKUB(a*b,b), agar b

. 

Masalan: 

EKUB(21,15)=EKUB(6,15)=EKUB(15,6)=EKUB(9,6)=EKUB(3,6)=EKUB(6,3)=EKUB(3,3)=3 

Biroq,  katta  a  va  kichik  b  da  EKUB(a,b)=EKUB(a-b,b)  qoidasini  qo‘llash  a  bilan 

taqqoslagudek  bo‘ladi,  ya’ni  (log  a  ga  nisbatan)  murakkabligi  eksponentsial  bo‘lib  qoladi. 

Yevklid algoritmining zamonaviy versiyasi, agar b b

 (a mod b-a ning b ga bo‘lishdagi qoldiq) 

bo‘lsa, EKUB(a,b)= EKUB(b,a mod b) ekanligiga asoslangan: