..........................,
(rn2,rn1) = (r rn1, n),
(r rn1, n) = rn
tengliklarni hosil qilamiz, demak, (a b, ) = rn.
Endi sonlarning EKUBi haqidagi muhim xossalarni keltiramiz.
34.8-xossa. Agar berilgan sonlarni biror songa ko‘paytirsak, u holda ularning EKUBi ham shuncha marta ortadi.
Isbot. Yevklid algoritmini ak va bk sonlarga tadbiq etsak, tengliklarni xar bir hadi k marta ortadi. Shuning uchun,
(ak bk, ) = ( , ) .a b k
34.9-xossa. Agar a va b sonlarning har biri biror d songa bo‘linsa, ularning EKUBi ham shu songa bo‘linadi, ya’ni
a b (a b, )
d d, = d
tenglik o‘rinli bo‘ladi.
Isbot. 34.8-xossaga asosan (ab, ) = d da bd d, = d da b, d.
Bundan
a b (ab, ) d d, = d
ekanligi kelib chiqadi.
Xususiy holda d = (a b, ) bo‘lsa,
a b (ab, )
(ab ab, ) ( ,, ) = (ab, ) =1
kelib chiqadi, ya’ni agar a da= 1 va b db= 1 bo‘lib, d = (a b, ) bo‘lsa,
(a b1 1, ) =1 bo‘ladi.
34.10-teorema. Agar ( , ) =1a c va c ab| bo‘lsa c b| bo‘ladi, ya’ni a va c sonlar o‘zaro tub bo‘lib, ab ko‘paytma c ga bo‘linsa, u holda b son c songa bo‘linadi.
Isbot. ( , ) =1a c tenglikning ikkala tomonini b ga ko‘paytiramiz:
(ab cb, ) = b.
Teorema shartiga asosan, c ab| va cb son c ga karrali bo‘lganligi uchun, yuqoridagi xossalarga asosan c | (ab cb, ), bundan
esa c b| ekanligi kelib chiqadi.
34.11-teorema. ab, uchun u v, topiladiki,
au bv d =
bo‘ladi, bu yerda d = (a b, ).
Isbot. Quyidagi f : f x y( , ) = axby 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, a = dqr, 0 r < d ni hosil qilamiz. Bu yerdan
r a dq a= = (au bv q a ) = (1uq) b qv( ) = au bv1 1
ekanligidan rE f( ) 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:
rn = rn2 r qn1 n1 = rn2 (rn3 r qn2 n2)qn1 =
rn2 r qn3 n1 r q qn2 n2 n1 =
rn2(1q qn2 n1)rn3(qn1) =... au bv.
Tabiiyki, a va b sonlar o‘zaro tub bo‘lishi uchun au bv =1 shartni qanoatlantiruvchi u v, sonlarning mavjud bo‘lishi zarur va yetarlidir.
Do'stlaringiz bilan baham: |