|
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 • Z 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 taqqoslamalarni 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 - k = b - k(modm - k) bo‘ladi.
Isbot. a = b(mod m) ekanligidan a = b + m -1 tenglikni hosil qilamiz. Bu tenglikni ikkala tomonini k ga ko‘paytirsak, a - k = b - k + m - k -1 kelib chiqadi, ya’ni a - k = b - k(modm - k).
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 -1 tenglikdan a - d=b - d+m - d -1, a = b + m -1
hosil bo‘ladi, ya’ni a = b (mod m).
xossa. Agar a va b sonlari m, m2,..., mk 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 • Z ekanligidan m = щ • q shartni qanoatlantiruvchi m soni uchun a = b + щ • (q • Z) 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 • Z bo‘lib, a = a • d, m = щ • d bo‘lsin. U holda b = a • d — щ • d • Z 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 • Z 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-bemL 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:
Do'stlaringiz bilan baham: |
