Matematikadan

esa 30 ta tish bor. Ulardan biri (tishi kami)
ikkinchisi bo'ylab aylanadi. Aylantirishdan
avval glldiraklardagi ikkita bir-biriga tegib
turgan tishlarning holati belgilandi. 1) Necha
marta aylangandan so'ng g'ildiraklar belgilangan
holatga qaytadi? 2 ) Bu masalani tishlar
soni 13 ta va 19 ta bolgan hoi uchun ham hal
qiling. Nega bu holda tishlar soni kam bolsada,
tishlarning belgilangan holatga kelishlari
kechroq (g'ildiraklar ko'proq aylangach) ro‘y
beradi?
Sonlarning EKUB ni topishning darslikda
bayon qilingan usulidan farqli yana bir usuli
bor. Bu usulni Evklid algoritmi deyishadi.
Uni bir misolda tushuntiraylik.
14
Misol. 3996 va 288 sonlarining EKUBi topilsin.
1-qadam. Sonlarning kattasini kichigiga
bo‘lamiz. 3996:288=13(252 qoldiq). 2 5 2 - birinchi
qoldiq, r1=252.
2-qadam. 288 ni birinchi qoldiq 252 ga
bo‘lamiz. 288:252=1(36 qoldiq). 36 - ikkinchi
qoldiq, r2=36.
3-qadam. Birinchi qoldiq 252 ni ikkinchi
qoldiq 36 ga bo'lamiz: 252:36=7 (0 qoldiq).
Dastlab olingan ikkita son qanchalik katta
bolmasin, ketma-ket bolishning bu jarayoni
qoldiqlar kichiklashib borayotgani uchun
chekli qadamdan so‘ng albatta tugaydi - 0
qoldiq chiqadi. Bunday ketma-ket bo‘lish
jarayoni qaysi qoldiqqa bo‘lganimizda tugasa
(qoldiq 0 bo‘lsa), o‘sha qoldiq berilgan
ikki sonning EKUBi bo‘ladi. Demak,
EKUB (3996, 288)=36.