Viii bob. Taqqoslamalar §. Taqqoslamalar va ularning xossalari

VIII BOB. TAQQOSLAMALAR

37. 
    - §. Taqqoslamalar va ularning xossalari
    

Bizga a va b butun sonlar va qandaydir m natural son berilgan bo‘lsin.

1. 
   tarif. Agar a va b sonlarini m ga bo‘lgandagi qoldiqlari teng bo‘lsa, a va b sonlar m modul bo‘yicha taqqoslanuvchi deyiladi va a = b(mod m) shaklda yoziladi.
   

Masalan, a = 22 va b = 27 sonlari m = 5 modul bo‘yicha taqqoslanadi, ya’ni 22 = 27(mod5).

2. 
   xossa. a va b sonlari m modul bo‘yicha taqqoslanuvchi bo‘lishi uchun a — b soni m ga bo‘linishi zarur va yetarli.
   

Isbot. Haqiqatdan, a va b sonlarni m ga qoldiqli bo‘lsak, a = m • q + r, b = mq₂ + r, 0 < r < m — 1 munosabatlarni hosil qilamiz. Bu yerdan a — b = m(q — q) ekanligi kelib chiqadi, ya’ni a — b soni m ga bo‘linadi.
Demak, a va b sonlarining m modul bo‘yicha taqqoslanuv- chanligi a = b + m • t ekanligiga teng kuchlidir. Bundan esa quyidagi xossaning o‘rinli ekanligi bevosita kelib chiqadi.

3. 
   xossa. Agar a = b(mod m) va b = c(mod m) bo‘lsa, u holda a = c(mod m).
   

Endi taqqoslamaning asosiy xossalarini keltiramiz.

4. 
   xossa. Bir hil modulli taqqoslamalarni hadma-had qo‘shish mumkin, ya’ni a = b(mod m) va c = d (mod m) bo‘lsa,
   

a + c = b + d (mod m).
Isbot. Aytaylik, a = b(modm) va c = d(modm) bo‘lsin. U holda a — b va c — d sonlari m ga bo‘linadi.
(a + c) — (b + d) = (a — b) + (c — d) ekanligidan (a + c) — (b + d) sonining m ga bo‘linishi kelib chiqadi, demak, a + c = b + d (mod m).

5. 
   xossa. Bir xil modulli taqqoslamalami hadma-had ko‘paytirish mumkin, ya’ni a = b(modm) va c = d(modm) bo‘lsa,
   

a ■ c = b ■ d(modm).
Isbot. Haqiqatdan, a - b va c - d sonlari m ga bo‘linishidan, ac -bd = (a - b)c + b(c - d) sonining ham m ga bo‘linishi kelib chiqadi. Demak, a ■ c = b ■ d(modm).

6. 
   xossa. Taqqoslamaning xar bir hadini va modulini bir hil songa ko‘paytirish mumkin, ya’ni a = b(mod m) bo‘lsa, a ■ к = b ■ к (mod m ■ к) bo‘ladi.
   

Isbot. a = b(mod m) ekanligidan a = b + m ■ t tenglikni hosil qilamiz. Bu tenglikni ikkala tomonini к ga ko‘paytirsak, a ■ к = b ■ к + m ■ к ■ t kelib chiqadi, ya’ni a ■ к = b ■ к (mod m ■ к).

7. 
   xossa. Taqqoslamaning har bir hadini va modulini bir hil songa bo‘lish mumkin.
   

Isbot. Aytaylik, a = b(modm) bo‘lib, a = a ■ d, b = b ■ d va m = m ■ d bo‘lsin. U holda a = b + m ■ t tenglikdan a ■ d=b ■ d+m ■ d ■ t,
a = b + m ■ t
hosil bo‘ladi, ya’ni a = b (mod m).

8. 
   xossa. Agar a va b sonlari m, m, . ., m modullar bo‘yicha taqqoslanivchi bo‘lsa, u holda a va b bu sonlarning eng kichik umumiy karralisi bo‘yicha taqqoslanuvchi bo‘ladi.
   

Isbot. a = b(modщ), a = b(modm₂), ._, a = b(modm_k) ekanli­gidan a - b sonining щ , щ,..., щ larning barchasiga bo‘linishi kelib chiqadi. Demak, ularning eng kichik umumiy karralisiga ham bo‘linadi. □

9. 
   xossa. Agar a va b sonlari m modul bo‘yicha taqqosla­nuvchi bo‘lsa, u holda ular m ning ixtiyoriy bo‘luvchisi bo‘yicha taqqoslanuvchi bo‘ladi.
   

257

Isbot. a = b + m • t ekanligidan m = щ • q shartni qanoatlanti- ruvchi m soni uchun a = b + щ • (q • t) kelib chiqadi, demak a = b(mod щ ).

10. 
    xossa. Agar taqqoslamaning bitta hadi va moduli biror songa bo‘linsa, u holda taqqoslamaning ikkinchi hadi ham shu songa bo‘linadi.
    

Isbot. Aytaylik a = b + m • t bo‘lib, a = a • d, m = щ • d bo‘lsin. U holda b = a • d — щ • d • t ekanligidan b sonining ham d ga bo‘linishini hosil qilamiz.

11. 
    xossa. Agar a = b(modm) bo‘lsa, u holda (a,m) = (b,m) bo‘ladi.
    

Isbot. a = b + m • t ekanligidan a ning (b,m) ga bo‘linishi kelib chiqadi. a va m sonlarining EKUBini ularning chiziqli ifodasi orqali ifodalasak,
au + mv = (a, m)
tenglikdan, hamda a va m sonlari (b,m) ga bo‘linishidan (a,m) ning (b,m) ga bo‘linishi kelib chiqadi, ya’ni (b,m) | (a,m). Shunga o‘xshab, (a,m) | (b,m) munosabat ham ko‘rsatiladi, demak (a,m) = (b, m).
Berilgan m soniga karrali bo‘lgan butun sonlar to‘plamini тЪ orqali belgilaymiz, ya’ni
rriL = -2m, —m, 0, m, 2m,
Butun sonlar to‘plamida quyidagicha R binar munosabat aniqlaymiz. Agar a va b sonlari uchun a-b^mL bo‘lsa, (a,b)eR deb qabul qilamiz. Boshqacha aytganda, m modul bo‘yicha taqqoslanuvchi sonlar jufti binar munosabatga tegishli bo‘ladi.

12. 
    teorema. Z to‘plamda m modul bo‘yidia kiritilgan binar munosabat ekvivalentlik munosabati bo‘ladi.
    

Isbot. Teoremani isbotlash uchun ekvivalentlikning uchta shartini o‘rinli bo‘lishini ko‘rsatamiz:

1. 
   a = a(modm), chunki a - a = 0 soni m ga bo‘linadi, demak (a, a) e R.
   
2. 
   agar a = b(modm) bo‘lsa, u holda a -b son m ga bo‘linadi. Bundan esa, b - a = -(a - b) soni ham m ga bo‘linishi, ya’ni b = a(modm) ekanligi kelib chiqadi. Demak, agar (a,b) e R dan (b,a) e R kelib chiqadi.
   
3. 
   agar a = b(modm) va b = c(modm) bo‘lsa, u holda a - b va b - c sonlar m ga bo‘linadi, a - c = (a -b) + (b - c) son ham m ga bo‘lingani uchun a = c(modm) kelib chiqadi. Demak, (a,b) e R va (b,c) e R ekanligidan (a,c) e R kelib chiqadi.
   

Ma’lumki, xar qanday ekvivalentlik munosabati berilgan to‘plamni kesishmaydigan sinflarga ajratadi. Yuqorida aniqlangan ekvivalentlik munosabati bo‘yicha hosil qilingan sinflarga chegirmalar sinflari deyiladi.

2. 
   teoremaga asosan, a - b ayirma m ga bo‘linsa, a va b sonlarni m ga bo‘lgandagi qoldiqlari teng bo‘ladi, demak, m modul bo‘yicha aniqlangan chegirmalar sinfi m ga bo‘linganda bir hil qoldiq qoladigan butun sonlardan iborat bo‘ladi. Butun sonni m ga bo‘lgandagi qoldiqlar 0,1,..., m -1 sonlaridan biriga teng bo‘lishini hisobga olsak, m modul bo‘yicha aniqlangan chegirmalar m ta sinfdan tashkil topadi. Demak, biz quyidagi sinflarga ega bo‘lamiz:
   

0. 
   = {..., -2m, -m, 0, m, 2m,...},
   

1 = {..., -m +1,1, m +1,...},
9
m -1 = {..., -2m -1, -1, m-1,2m-1,...}.
Ta’kidlash joizki, m modul bo‘yicha chegirmalar sinflarining ta’rifidan a = b(moAm) munosabat a = b munosabatga teng kuchlidir.

2. 
   teoremaga asosan, Ъ to‘plamnining m modul bo‘yicha turli chegirmalar sinfi faktor to‘plamning elementlari bo‘ladi, ushbu faktor to‘plam Z_ra kabi belgilanadi, ya’ni
   

259



Z_m={o, 1}.
Yuqorida keltirilgan xossalar Z_ra faktor to‘plamda qo‘shish va ko‘paytirish amalarini kiritishga imkon beradi, ya’ni a. b e 71,_m elementlarning yig‘indisi va ko‘paytmasini quyidagicha aniqlaymiz:
a + b := a + b, a ■ b : = a ■ b.
Bu aniqlangan qo‘shish va ko‘paytirish amallari binar algebraik amallar bo‘ladi. Haqiqatdan ham, 37.4 va 37.5-xossalarga asosan, a + b yig‘indi va a ■ b ko‘paytmalar a va b elementlarning tanlanishiga bog‘liq emas.
Quyidagi jadvalda Z₆ = {0,1, 2, 3, 4, 5} to‘plamda qo‘shish va ko‘paytirish amallari jadvallarini keltiramiz:

+	0	1	2	3	4	5
0	0	1	2	3	4	5
1	1	2	3	4	5	0
2	2	3	4	5	0	1
3	3	4	5	0	1	2
4	4	5	0	1	2	3
5	5	0	1	2	3	4

	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	1	2	3	4	5
2	0	2	4	0	2	4
3	0	3	0	3	0	3
4	0	4	2	0	4	2
5	0	5	4	3	2	1

Ravshanki, Z_ra to‘plamda aniqlangan qo‘shish va ko‘paytirish amallari kommutativlik, assotsiativlik va distributivlik qonunlariga bo‘ysunadi, ya’ni

1.