Urganch davlat universiteti fizika-matematika fakulteti amaliy matematika va informatika

2.2. EKUB VA EKUK HISOBLASH ALGORITMI. 

   Matematika  fanidan  ma‟lumki,  ikki  va  undan  ortiq  sonni  EKUB  va  EKUK  ini 

hisoblash  uchun  tub  ko‟paytuvchilarga  ajratishdan  foydalanar  edik.  Lekin, 

keyinchalik  sonni  EKUB  va  EKUK  ini  hisoblash  uchun  ularning  tub 

ko‟paytuvchilarga ajratish ham talab etilmay qoldi. Buing sababi shundaki, Evklid 

algoritmi  yaratilganidadir.  Evklid  algoritmi  yordamida  ikkita  ixtiyoriy  butun 

musbat sonlarni EKUB ini hisoblash mumkin. Quyida Evklid algoritmi keltirilgan: 

 

 

 

 

 

 

 

- 

 

 

+ 

 

 

 

 

 

 

 

 

 

b 

A, b 

b≠0 

C=a; 

A=b; 

B=c%b; 

a 

t 

---

 

 

   Ushbu algoritmning ishlash prinsipi haqida qisqacha tushuncha bersam, ikkita a 

va b sonlari kiritladi. Keyin B sonini 0 ga teng emas deb shart qo‟yamiz, agar 

rostan b soni nolga teng bo‟lmasa  

;

;

% ;

C

A

A

B

B

C

B







 

   Qiymatlarini  o‟zlashtiramiz.  Ko‟rnib  turibdiki,  buning  uchun  qo‟shimcha  C 

o‟zgaruvchisi  ham  olingan.  C  ga  A  ning  qiymati  yuklangan,  A  ga  esa  B  ning 

qiymati,  B  ga  bo‟lsa  C  ning  B  ga  bo‟lgandagi  qoldiqi  yuklangan.  Bu  jarayon  B 

nolga  teng  bo‟lgunicha  davom  ettirilgan.  B  nolga  teng  bo‟lganda  biz  A  va  B 

sonlarining  EKUB  ini  hisoblab  topgan  bo‟lamiz  va  shu  EKUB  A  o‟zgaruvchiga 

yuklangan  bo‟ladi.  Algoritm  so‟ngida  EKUB  ni  chiqarish  uchun  A  ni  chiqarish 

yetarlidir.  shu  bilan  algoritm  tugaydi.  EKUB  ni  toppish  uchun  ushbu  Evklid 

algoritmining  ananaviy  algoritmdan  farqi  shundaki,  bu  Evklid  algoritmida  tub 

ko‟paytuvchilarga  ajratish  talab  qilinmaydi.  Faqatgina  qoldiq  qismin  hisoblab 

bilish kifoya.  

   Xuddi  shu  kabi  EKUK  ni  ham  Evklid  algoritmidan  foydalanib  hisoblash 

mumkin.  Buning  uchun  matematikada  keng  qo‟llaniladigan  formuladan 

foydalanamiz: 

*

( , ) *

( , )

A B

EKUB A B

EKUK A B



 

Ya‟ni,  ikkita  sonning  ko‟paytmasi  ularning  EKUB  va  EKUK  lari  ko‟paytmasiga 

teng.  Ushbu  formulaga  asosan,  biz  EKUK  ni  topib  olamiz  va  uning  algoritmini 

tuzamiz.