VIII BOB. TAQQOSLAMALAR
- §. Taqqoslamalar va ularning xossalari
Bizga a va b butun sonlar va qandaydir m natural son berilgan bo‘lsin.
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).
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 = mq2 + 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.
xossa. Agar a = b(mod m) va b = c(mod m) bo‘lsa, u holda a = c(mod m).
Endi taqqoslamaning asosiy xossalarini keltiramiz.
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).
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).
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 ■ к).
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).
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(modm2), ._, a = b(modmk) ekanligidan a - b sonining щ , щ,..., щ larning barchasiga bo‘linishi kelib chiqadi. Demak, ularning eng kichik umumiy karralisiga ham bo‘linadi. □
xossa. Agar a va b sonlari m modul bo‘yicha taqqoslanuvchi 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 щ ).
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.
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.
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:
a = a(modm), chunki a - a = 0 soni m ga bo‘linadi, demak (a, a) e R.
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.
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.
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:
= {..., -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.
teoremaga asosan, Ъ to‘plamnining m modul bo‘yicha turli chegirmalar sinfi faktor to‘plamning elementlari bo‘ladi, ushbu faktor to‘plam Zra kabi belgilanadi, ya’ni
259
Zm={o, 1}.
Yuqorida keltirilgan xossalar Zra 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 Z6 = {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, Zra to‘plamda aniqlangan qo‘shish va ko‘paytirish amallari kommutativlik, assotsiativlik va distributivlik qonunlariga bo‘ysunadi, ya’ni
Do'stlaringiz bilan baham: |