Sonlarning umumiy bo‘luvchisi va karralisi

34.3-teorema. (qoldiqli bo‘lish) Xar qanday a va b
a = bq r (34.1) tenglikni qanoatlantiruvchi q va r(0r b< ) butun sonlari mavjud va ular yagona ravishda aniqlanadi.
Isbot. Mavjudligi. bq son a dan katta bo‘lmagan, b ga
bo‘linuvchi eng katta natural son bo‘lsin, u holda bq  a < b q( 1).
Bu tenglikning ikkala qismiga bq ni qo‘shsak,
0  a bq < b
hosil bo‘ladi. Agar
r  a bq
deb olsak, a = bq r ni hosil qilamiz. Yagonaligi. Faraz qilaylik,
a bq r= ₁  ₁, 0 r b₁ < , a bq= ₂ r₂, 0 r₂ < b
munosabatlar o‘rinli bo‘lsin. U holda bu tengliklarning ayirmasidan
0 = (b q q₁   ₂) (r r_{1 2})
kelib chiqadi.
Bundan, r r₁  ₂ = b q( ₂ q₁) hosil bo‘ladi, demak, b r r| ( ₁  ₂) kelib chiqadi. Lekin | r r₁  ₂ |< b bo‘lgani uchun b r r| ( ₁  ₂) shart faqatgina r r₁  ₂ = 0, ya’ni r₂ = r₁ bo‘lgandagina bajariladi. Bundan esa q₂ = q₁ ekanligi kelib chiqadi. 
Teoremadagi tenglikka sonlarni qoldiqli bo‘lish va undagi q songa bo‘linma, r songa esa qoldiq deyiladi.
Misol 34.1. –197 ni 11 ga qoldiqli bo‘lsak, 197 =11 ( 18)  1, bu yerda q=18, r =1.
Qoldiqli bo‘lish haqidagi teoremaga asosan quyidagi tengliklari yozish mumkin.

1. 
   bq= ₁ r₁, 0 < r₁ < b,
   
2. 
   rq= _{1 2} r₂, 0 < r₂ < r₁,
   

.......................... ................ (34.2)
rn2 = r qn1 n1 rn, 0 < rn < rn1, rn1 = rqn n.
Bu tengliklarning o‘ng tomonidagi tengsizliklarga e’tibor bersak, quyidagi tengsizliklar bog‘lanishi ko‘zga tashlanadi: b r> ₂ > r₃ > r₄ >...> r_n > 0,

bu yerda barcha r_i (2,n) lar natural sonlardir. Natural sonlar quyidan chegaranganligi tufayli biror-bir n nomerdan boshlab r_n1 = 0 bo‘ladi.
(34.2) tengliklar sistemasiga Yevklid algoritmi deb yuritiladi.
Misol 34.2. 2576 va 154 sonlar uchun Yevklid algoritmini tuzamiz:
2576 =154 16 112,
154 =112 1 42,
112 = 42 2 21,
42 = 28 1 14  ,
28=14 2.
34.4-ta’rif. a b,  butun sonlarning har birini bo‘ladigan songa shu sonlarning umumiy bo‘luvchisi deyiladi.
34.5-ta’rif. Kamida biri noldan farqli bo‘lgan a va b butun sonlarning umumiy bo‘luvchilari ichida eng kattasi ularning eng katta umumiy bo‘luvchisi deyiladi va EKUB( , )a b yoki qisqacha (a b, ) kabi belgilanadi.
34.6-ta’rif. Agar (a b, ) =1 bo‘lsa, a va b sonlar o‘zaro tub sonlar deyiladi.
34.7-tasdiq. a va b butun sonlarning EKUBi Yevklid algoritmidagi oxirgi r_n qoldiqqa tengdir, ya’ni (a b, ) = r_n.
Isbot. a va b butun sonlar uchun Yevklid algoritmini tuzamiz. U holda tengliklarning birinchisiga asosan a va b butun sonlarning ixtiyoriy umumiy bo‘luvchi r₁ ni bo‘ladi, va aksincha a r bq= ₁  ₁ ga asosan r₁ va b larning xar qanday umumiy bo‘luvchisi a sonni bo‘ladi. Demak, (a b, ) = ( ,b r₁).
Bu mulohazalarni Yevklid algoritmiga ikkinchi, uchinchi va undan keyin keladigan tengliklarga qo‘ysak,
(b r, ₁) = (r r_{1 2}, ),
(r r_{1 2}, ) = ( , )r r_{2 3} ,