Taqqoslamalar va ularning xossalari

Taqqoslamalar va ularning xossalari

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

37.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).}
37.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.

37.3-xossa. Agar
a  c(mod m).
a  b(mod m)
va b  c(mod m)
bo‘lsa, u holda

Endi taqqoslamaning asosiy xossalarini keltiramiz.
37.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(mod m) va
c  d (mod m)
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). 

37.5-xossa. Bir xil modulli taqqoslamalarni hadma-had

ko‘paytirish mumkin, ya’ni
a  b(mod m) va
c  d (mod m)
bo‘lsa,

a  c  b  d (mod m) .

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 (mod m) . 

37.6-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(mod m  k)
bo‘ladi.

Isbot.

a  b(mod m)
ekanligidan a  b  m  t
tenglikni hosil

qilamiz. Bu tenglikni ikkala tomonini k ga ko‘paytirsak,

a  k  b  k  m  k  t
kelib chiqadi, ya’ni
a  k  b  k(mod m  k). 

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

Isbot. Aytaylik,
a  b(mod m)
bo‘lib,
a  a₁  d,
b  b₁  d va

m  m₁  d
bo‘lsin. U holda a  b  m  t
tenglikdan

hosil bo‘ladi, ya’ni

a₁  d  b₁  d  m₁  d  t, a₁  b₁  m₁  t
a₁  b₁ (mod m₁ ). 

37.8-xossa. Agar a va b sonlari
m₁, m₂ , ..., m_k
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 m₁),
a  b(mod m₂ ), …,
a  b(mod m_k )
ekanli-

gidan a  b
sonining
m₁, m₂ , ..., m_k
larning barchasiga bo‘linishi kelib

chiqadi. Demak, ularning eng kichik umumiy karralisiga ham bo‘linadi.


37.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.

Isbot. a  b  m  t
ekanligidan
m  m₁  q
shartni qanoatlanti-

ruvchi
m₁ soni uchun
a  b  m₁  (q  t)
kelib chiqadi, demak

a  b(mod m₁). 
37.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  m₁  d
bo‘lsin.

U holda
b  a₁  d  m₁  d  t
ekanligidan b sonining ham d ga

bo‘linishini hosil qilamiz. 

37.11-xossa. Agar
bo‘ladi.
a = b(mod m)
bo‘lsa, u holda (a, m) = (b, m)

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 m
orqali belgilaymiz, ya’ni
m = {...,  2m,  m, 0, m, 2m, ...}.

Butun sonlar to‘plamida quyidagicha R binar munosabat

aniqlaymiz. Agar a va b sonlari uchun a  b  m bo‘lsa, (a,b)  R
deb qabul qilamiz. Boshqacha aytganda, m modul bo‘yicha taqqoslanivchi sonlar jufti binar munosabatga tegishli bo‘ladi.

37.12-teorema. to‘plamda m modul bo‘yicha kiritilgan binar munosabat ekvivalentlik munosabati bo‘ladi.
Isbot. Teoremani isbotlash uchun ekvivalentlikning uchta shartini o‘rinli bo‘lishini ko‘rsatamiz:

1. 
   a  a(mod m),
   

chunki
a  a = 0
soni m ga bo‘linadi, demak

(a, a)  R.

2. 
   agar
   

a  b(mod m)

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(mod m)
ekanligi kelib chiqadi. Demak, agar (a,b)  R
dan

(b, a)  R
kelib chiqadi.

3. 
   agar
   

a  b(mod m)
va b  c(mod m)
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(mod m)
kelib chiqadi. Demak, (a,b)  R va

(b,c)  R
ekanligidan (a,c)  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.

37.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, ...},

m 1 ={...,  2m 1, 1, m 1, 2m 1, ...}.

Ta’kidlash joizki, m modul bo‘yicha chegirmalar sinflari-ning

ta’rifidan
a = b(mod m)
munosabat



^{a = b} munosabatga teng kuchlidir.

37.3-teoremaga asosan, to‘plamnining m modul bo‘yicha turli chegirmalar sinfi faktor to‘plamning elementlari bo‘ladi, ushbu faktor
to‘plam kabi belgilanadi, ya’ni
_m = _0, 1, ..., m 1_.


Yuqorida keltirilgan xossalar faktor to‘plamda qo‘shish va

ko‘paytirish amalarini kiritishga imkon beradi, ya’ni a, b 

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}
bog‘liq emas.
ko‘paytmalar a va b elementlarning tanlanishiga

+	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

Quyidagi jadvalda ₆ = {0, 1, 2, 3, 4, 5} to‘plamda qo‘shish va ko‘paytirish amallari jadvallarini keltiramiz:
Ravshanki, to‘plamda aniqlangan qo‘shish va ko‘paytirish




amallari kommutativlik, assotsiativlik va distributivlik qonunlariga bo‘ysunadi, ya’ni

1. 
   a  b = b  a;
   

2. 
   
   
   
   
   
   
   a  b = b  a;
   

c) a  (b  c) = (a  b)  c;








d) a  (b  c) = (a  b)  c;
e) a  (b  c) = a  b  a  c.
Hosil qilingan chegirmalar sinflari uchun quyidagi xossalar o‘rinli.
37.13-xossa. a) agar sinfdagi biror son m bilan o‘zaro tub bo‘lsa, u holda bu sinfdagi barcha sonlar bilan ham o‘zaro tub bo‘ladi;
b) juft-jufti bilan m mo‘dul bo‘yicha taqqoslanmaydigan ixtiyoriy
m ta y₁, y₂ , ..., y_m sonlari uchun _m  _y₁, y₂ ,..., y_{m };
c) agar (a, m)  1 bo‘lsa, _1 a, 2  a,..., m  a_ 