Mavzu: Butun sonlarda bolinish nazaryasi Reja: Kirish. Asosiy qism

3-teorema. topiladiki,
au + bv = d
bo‘ladi, bu yerda d = (a, b).
Isbot. Quyidagi funksiyani
qaraymiz. Agar a va b sonlar bir vaqtda nolga teng bo‘lmasa, bu funksiya musbat qiymatlarni ham, manfiy qiymatlarni ham qabul qiladi. Bundan tashqari a va b sonlari bu funksiyaning qiymatlar sohasi E(f ) ga tegishli bo‘ladi. Bu funksiya musbat qiymatlarining eng kichigini d bilan belgilaymiz, ya’ni d = au + bv son noldan katta eng kichik musbat son bo‘lsin.
U holda a sonini d ga qoldiqli bo‘lib, ni
hosil qilamiz. Bu yerdan
r = a — dq = a — (au + bv)q = a(1 — uq) + b(—qv) = au + bv_x ekanligidan
kelib chiqadi. d soni E(f) ga tegishli bo‘lgan
eng kichik musbat son bo‘lganligi uchun r = 0 kelib chiqadi, ya’ni a soni d ga bo‘linadi.
Shunga o‘xshash, b sonining ham d ga bo‘linishi ko‘rsatiladi. Ikkinchi tomondan a va b sonlarning xar qanday bo‘luvchisi d = au + bv sonni ham bo‘ladi va shunga ko‘ra d dan katta bo‘lmaydi, demak d = (a,b). □
Shuni ta’kidlaymizki, d = au + bv chiziqli ifodani amalda topish uchun Yevklid algoritmidagi tengliklarda pastdan yuqoriga qarab harakat qilinadi:

Tabiiyki, a va b sonlar o‘zaro tub bo‘lishi uchun au + bv = 1 shartni qanoatlantiruvchi u,v eZ sonlarning mavjud bo‘lishi zarur va yetarlidir.
Misol 3. 2576 va 154 sonlarining EKUBini ularning chiziqli kombinatsiyasi orqali ifodalang.
2-misolda biz (2576,154) = 14 ekanligini ko‘rsatgan edik. Unda keltirilgan Yevklid algoritmidan foydalanib, pastdan yuqoriga qarab yozsak:
14 = 42 - 28-1 = 42 - (112 - 42 - 2)-1 = 42-112-1 + 42 - 21 =42(1 + 2-1) +112(—1) = 42 - 3 +112(—1) = (154-112-1) - 3 +112(-1) = 154 - 3-112 - 3-112 = 154 - 3 -112 - 4 = 154 - 3 - (2576 -154-16) - 4 = 154 - 3 + 2576 - (-4) +154 - 64 = 2576 - (-4) +154 - 67 hosil bo‘ladi. Demak, u = -4, v = 67.
Ikkita sonning EKUBini topish tushunchasini bir nechta sonlarning EKUBini topishga ham tadbiq etish mumkin. Faraz qilaylik, n ta a,a,...,a sonlar ketma-ketligi berilgan bo‘lsin. Bu sonlarning EKUBini topish uchun birinchi bo‘lib (a,a₂) = d, so‘ngra (d₂, a₃ ) = d₃, (d₃, a ) = d₄, ..., (d_n_j, a ) = d_n EKUBlarni topamiz. Hosil bo‘lgan d_n soni berilgan sonlar ketma-ketligining EKUBi bo‘ladi, ya’ni
(aj, a₂,..., a_n ) = d_n.