Algebra va sonlar nazariyasi

Ae' = 0
shartni qanoatlantiruvchi vektorni hosil qiamiz. Bu vektorni mavjud bazis vektorlar tarkibiga qo‘shib, n + 1 o‘lchamli V fazoda ^e\ e^{, e}2^,...^{, e}p;^f, U...^{, f}_q; ;^h, h2^,...^, hs


239

bazisni hosil qilamiz. Bu bazisda chiziqli almashtirish kanonik ko‘rinishga kelib, e' xos vektorga mos keluvchi xos qiymat nolga teng bo‘ladi. Biz yuqorida T = 0 deb olish uchun A almashtirish o‘rniga A -tE almashtirishni qaragan edik. Agar to‘g‘ridan to‘gri t Ф- 0 holni qaralsa, xuddi shunga o‘xshab e' xos vektorni hosil qilish mumkin, lekin bu xos vektorga mos keluvchi xos qiymat t ga teng bo‘ladi.

Endi ikkinchi holni ya’ni xos sonlarning ba’zilari nolga teng bo‘lgan holni qaraymiz. Bu holda (33.6) tenglikning o‘ng tomonidagi ifodaning xos qiymati nolga teng va xos qiymatlari noldan farqli vektorlar jamlanmasiga ajratish orqali ikki hil qo‘shiluvchilar ko‘rinishida yozib olamiz.
Xos qiymatlari noldan farqli bo‘lgan vektorlarga mos keluvchi qo‘shiluvchilarni birinchi holdagi kabi, koeffitsientlarni tanlash hisobiga nolga aylantirib yuborish mumkin. U holda (33.6) tenglikning o‘ng tomonida faqat xos qiymatlari nolga teng bo‘lgan vektorlardan iborat qo‘shiluvchilar qoladi.
Aytaylik, X=X =... = X= 0, (t < к) bo‘lib, bu xos sonlarga
^{mos keluvchi vektorlar e}l^{, e}2^,...^{, e}p; X ^/2^,...^, /; ; g^ g2^,...^, gr
bo‘lsin. Bu holda (33.6) tenglik quyidagi ko‘rinishga keladi:
^Ae' = ^c1^e1 + ... + ^cp^ep + ^fl/ + ... + p_q^/_q + ... + + ... + Yrg_r -
^A(X1^e1 + ... +Xp^ep ^{) - A(}M1^/1 + ... + M q^/q ^{) -} ... ^{- A(}Y1g1 + ... + Vrgr ⁾. .
Ammo X=X = .. = X = 0 bo‘lgani uchun
Ae = 0, Ae = e , ... , Ae = e ,
1 ⁵ 2 1 ^{5 5} p p-1⁵
A/1 = 0, A/2 = /1,..., Afq = /q-1,
9
^Ag1 = ^ ^Ag2 = ^Ag_r = g_r-1.
Demak e, e,. ., ^ vektorlarning (33.7) tenglik o‘ng tomonida
qatnashayotgan chiziqli kombinatsiyasi ushbu ko‘rinishda bo‘ladi:
^c1^e1 + ^c2^e2 + ... + ^Cp^ep ^- J2^e1 ^- ^3^e2 ^- ... ^- Xp^ep-1.

Bu ifodada X₂=«, Хз=а₂,-., X_p=a_p faraz qilib, biz a e_p haddan boshqa hamma hadlarni yo‘qotib yuborishimiz mumkin. Shu

operatsiyani qolgan fl, f,,..., f_q; ; g, g2,..., g_r vektorlar
jamlanmasi uchun ham qo‘llasak,
^Ae'= ^ap^ep +^pJ_q +... + r_rg_r
tenglikni qanoatlantiruvchi vektorni hosil qilamiz.
Agar a_p = p =... = r = 0 bo‘lib qolsa, u holda
Ae ' = 0
tenglik hosil bo‘lib,
^e ^ ^el^{, e}2^,...^{, e}p; ^{f f}2^,...^{, f}_q; ; К К...^, К
bazisda chiziqli almashtirish normal shaklga keladi.
Agar a_p, P_q,..., r_r koeffitsientlardan kamida bittasi noldan farqli
bo‘lsa, chiziqli almashtirishni normal shaklga keltirish uchun V' qism fazodagi bazisni o‘zgartirishga tog‘ri keladi. Umumiylikka ziyon yetkazmagan holda, p > q >... > r deb olaylik. Bu holda
ep+l = e', ep = Aep+, ep—1 = Aep,..., e( = Ae2
deb olsak,
^ep+1 = ^e ' = ^ap^ep + ^Pq^fq + ... + Гг§г ^{, e}'p = ^Aep+1 = ^ap^ep—1 + ^Pq^fq—1 + ... + Гг,?г— 1 <sup>,


e</sup>p—r+2 = ^Aep—r+3 = ^ap^ep—r+1 + ^Pq^fq—r+1 + ... + ^Гг§1,
9
A = Ae' = a e
hosil bo‘ladi.
Tanlangan e[, e₁, e₂,..., e_p vektorlarni el , e2,..., e'_p, e'_p+₁ vektorlar
bilan almashtirib qolgan vektorlarni o‘zgarishsiz qoldirsak, berilgan chiziqli almashtirish ushbu bazisda normal shaklga keladi.


241

VII BOB. BO‘LINISH NAZARIYASI

34. 
    - §. Bo‘linish belgilari.
    

Sonlarning umumiy bo‘luvchisi va karralisi

1. 
   ta’rif. Agar noldan farqli a va b butun sonlar uchun a = bq tenglikni qanoatlantiruvchi q butun son mavjud bo‘lsa, u holda a son b songa qoldiqsiz bo‘linadi (qisqacha bo‘ladi) yoki b son a sonni bo‘ladi deyiladi, hamda b | a kabi belgilanadi.
   

a = bq tenglikdagi a son bo‘linuvchi, b son a sonining bo‘luvchisi, q son esa bo‘linma deb ataladi.
Ravshanki, ikkita son umumiy bo‘luvchiga ega bo‘lsa, ularning yig‘indisi va ayirmasi ham shu bo‘luvchiga ega.
x, y va z butun sonlar bo‘lsa, u holda quyidagi sodda xossalar o‘rinli:

1. 
   x | x (refleksivlik hossasi);
   
2. 
   agar x | y va y | z bo‘lsa, u holda x | z (tranzitivlik hossasi);
   
3. 
   agar x | y va y | x bo‘lsa, u holda y = ±x;
   
4. 
   agar x | y va y ф 0 bo‘lsa, u holda | x | <| y |;
   
5. 
   agar x | y va x | z bo‘lsa, u holda barcha butun a,fl sonlar uchun x | (ay + flz);
   
6. 
   x | y bo‘lishi uchun | x 111 y | bo‘lishi zarur va yetarli.
   

Izoh. Shuni aytish joizki, ohirgi f) hossa bo‘linish bilan bog‘liq mulohazalarni butun sonlar uchun emas, balki natural sonlar uchun yuritishga imkon yaratadi.

2. 
   teorema. Agar a Ф 0 va b ф 0 uchun a = bq tenglikni qanoatlantiruvchi q son mavjud bo‘lsa, u yagonadir.
   

Isbot. Teskarisini faraz qilamiz, ya’ni a = bq tenglikni qanoatlantiruvchi kamida ikkita xar hil q va q₂ sonlar mavjud bo‘lsin:
a = bq, a = bq₂.

U holda bu tengliklardan

^b(q_l ^— q₂^{) = 0}
kelib chiqadi. b ф 0 ekanligi q — q₂ = 0, ya’ni q_x = q₂ bo‘ladi.
□

3. 
   teorema. (qoldiqli bo‘lish) Xar qanday a e Z va b e N
   

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,

1. 
   < 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 < , < b munosabatlar o‘rinli bo‘lsin. U holda bu tengliklarning ayirmasidan 0 = b(ql — ^2) + (rl — r;)
kelib chiqadi.
Bundan, r - r = b(q - q) hosil bo‘ladi, demak, b | (r — r₂) kelib chiqadi. Lekin | r — r l< b bo‘lgani uchun b | (r — r₂) shart faqatgina r — ^ = 0, ya’ni r₂ = rj bo‘lgandagina bajariladi. Bundan esa ^ = q_x 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.


243

Qoldiqli bo‘lish haqidagi teoremaga asosan quyidagi tengliklari yozish mumkin.

a = bq + r, 0 < r < b, b = r_xq₂ + r, 0 < r₂ < r, (34.2) ^r„-2 = ^r„-1q„-1 + ^r_n^{, 0}< ^r„ < r^ ^r„-1 = ^r„q„.
Bu tengliklarning o‘ng tomonidagi tengsizliklarga e’tibor bersak, quyidagi tengsizliklar bog‘lanishi ko‘zga tashlanadi:
b > r > r > r >... > r >0,
bu yerda barcha r (2, „) lar natural sonlardir. Natural sonlar quyidan chegaranganligi tufayli biror-bir „ nomerdan boshlab r_n+1 = 0 bo‘ladi.

2. 
   tengliklar sistemasiga Yevklidalgoritmi 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.

4. 
   ta’rif. a,b eZ butun sonlaming har birini bo‘ladigan songa shu sonlaming umumiy bo‘luvchisi deyiladi.
   
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.
   
6. 
   ta’rif. Agar (a,b) = 1 bo‘lsa, a va b sonlar o‘zaro tub sonlar deyiladi.
   

7. 
   tasdiq. a va b butun sonlaming EKUBi Yevklid algoritmidagi oxirgi r_B qoldiqqa tengdir, ya’ni (a, b) = г_и.
   

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,


tengliklarni hosil qilamiz, demak, (a,b) = r .
Endi sonlarning EKUBi haqidagi muhim xossalarni keltiramiz.

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,

9. 
   xossa. Agar a va b sonlarning har biri biror d songa bo‘linsa, ularning EKUBi ham shu songa bo‘linadi, ya’ni
   

(b, r ) = (r, r,),
Ob ^r2⁾ = ^(r2^{, r}3^),


O^ ^rn-1⁾ = ^(rn-1^{, r}n X O^ ^rn ⁾ = ^rn


(ak, bk) = (a, b)k.





tenglik o‘rinli bo‘ladi.
Isbot. 34.8-xossaga asosan





Bundan





ekanligi kelib chiqadi.


245

Xususiy holda d = (a, b) bo‘lsa,

^ a b (a, b) v (a, b) ’ (a, b) J (a, b) kelib chiqadi, ya’ni agar a = da va b = db_x bo‘lib, d = (a,b) bo‘lsa, (a, b) = 1 bo‘ladi.

10. 
    teorema. Agar (a,c) = 1 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. (a,c) = 1 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 с | b ekanligi kelib chiqadi. □

11. 
    teorema. \/a,b eZ uchun 3w,veZ topiladiki,
    

au + bv = d
bo‘ladi, bu yerda d = (a, b).
Isbot. Quyidagi f: Z² ->Z, f (x, y) = ax + by 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 = dq + r, 0 < r < d ni hosil qilamiz. Bu yerdan
r = a — dq = a — (au + bv)q = a(1 — uq) + b(—qv) = au + bv ekanligidan r eE(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 = ^rn-2 ^{- r}n-l4n-1 = ^rn-2 ^{- (r}n-3 ^{- r}n-24n-2⁾4n-1 =
= ^rn-2 ^{- r}n-34n-1 + ^rn-24n-24n-1 =
= ^rn-2 ⁽¹ + 4n-24n-1 ⁾ + ^rn-3 ^(-4n-1 ⁾ = ... = ^aU + ^bv
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 34.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
a a₂,..., a_n ) = d_n.


247

12. 
    ta’rif. Agar a,a,...,a sonlar ketma-ketligida (a_t,a.) = 1,
    

bo‘lsa, bu sonlar ketma-ketligi juft-jufti bilan o‘zaro tub deyiladi.

14. 
    ta’rif. a va b sonlaming xar biriga bo‘linadigan son shu
    sonlaming umumiy karralisi deyiladi.
    

Masalan, 12 va 18 sonlaming umumiy karralisi 36, 72, 108, ...
bo‘ladi.

14. 
    ta’rif. a va b sonlaming umumiy karralilari ichida eng
    kichigiga bu sonlaming eng kichik umumiy karralisi (EKUK) deyiladi
    va [a, b] orqali belgilanadi.
    

Ikkita sonning EKUKi quyidagi oddiy xossalarga ega.

14. 
    xossa.
    

1. 
   ikkita sonning EKUKi shu sonlar ko‘paytmasini ularning
   

a • b
EKUBiga bo‘lgan nisbatiga teng, ya’ni [a, b] =


(a, b)
₁₄[a,b] [a,b] _e . , .([a,b] [a,b]^

2. 
   ) va sonlar o zaro tubdir, ya ni I , I = 1;
   

a b ^ a b J

100. 
     a va b sonlaming umumiy karralisi, ularning EKUKiga
     karralidir;
     

4. 
   agar k >0 bo‘lsa, [ka,kb] = k[a,b] bo‘ladi.
   

a b
к ’ к


e) agar к | a va к | b bo‘lsa, u holda


^[a’^b] bo‘ladi.


к
Isbot. Ushbu xossalardan faqat birinchisini ko‘rsatish bilan chegaralanamiz. Aytaylik, M soni a va b sonlaming biror umumiy karralisi bo‘lsin. U holda a | M va b | M, ya’ni
M = ak, M = bs.
Bundan ak soni b ga bo‘linishi kelib chiqadi.
Agar (a,b) = d bo‘lsa, u holda a = qd, b = bd va (a,b) = 1 deb olib, b | ak ekanligidan b_x | afc munosabatni, (a ,b_x ) = 1 bo‘lganligi uchun b_x | k bo‘lishini hosil qilamiz. Demak, k soni b_x ga bo‘linadi, ya’ni