1.Modul arifmetikasi
Natural sonlar to‘plamini N ={1, 2,3, … } va butun sonlar to‘plamini Z={0,
1, 2, 3, … } ko‘rinishda belgilaymiz.
Noldan farqli bo‘lgan a soni va v sonlar Z –to‘plamga tegishli, ya’ni a,b Z bo‘lib, a
0 bo‘lsin., agarda shunday s soni mavjud bo‘lib, v=as tenglik bajarilsa, u holda, a
soni v sonini bo‘ladi deyiladi.
Berilgan a va v sonlarni bo‘luvchi butun son, ularning umumiy bo‘luvchisi deyiladi.
Umumiy bo‘luvchilar ichida eng kattasi eng katta umumiy bo‘luvchi (EKUB)
deyiladi va (a, v) ko‘rinishda belgilanadi. Agarda a va v sonlarning eng katta
umumiy bo‘luchisi 1, (a, v)=1 bo‘lsa, a va v sonlar o‘zaro tub deyiladi.
Berilgan natural son p>1 tub deyiladi, agarda bu son o‘zi p va 1 dan boshqa natural
songa bo‘linmasa.
Misol uchun: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, tub sonlar, ular sanoqli va
cheksiz quvvatli to‘plamni tashkil etadi. Kelgusida, barcha butun sonlarni modul
(xarakteristika) deb ataluvchi biror fiksirlangan natural n soniga bo‘lganda
qoladigan qoldiqlar bilan bog‘liq holda qaraymiz. Bunda cheksiz quvvatli
(elementlari soni cheksiz) bo‘lgan barcha butun sonlar to‘plamiga, 0 dan n-1 gacha
bo‘lgan butun sonlarni o‘z ichiga oladigan chekli, quvvati n ga teng bo‘lgan {0; 1;
2; 3;…;n-1} to‘plam mos qo‘yiladi.
Bu quyidagicha amalga oshiriladi: a va n –natural sonlar bo‘lsa, “a sonini n
soniga qoldiq bilan bo‘lish”, deganda ushbu a=qn+r, bu yerda 0<r <n, shartni
qanoatlantiruvchi natural q va r sonlarini topish tushuniladi. Bu oxirgi tenglikda
qoldiq deb ataluvchi r soni nolga teng bo‘lsa r=0, natural a soni n soniga bo‘linadi
yoki n soni a sonining bo‘luvchisi deyiladi.
Butun a va b sonlari modul n bo‘ycha taqqoslanadigan deyiladi, agarda ularni n ga
bo‘lganda qoladigan qoldiqlari teng bo‘lsa, hamda, a
b(mod n) deb yoziladi.
Bundan esa a va b sonlar ayirmasining n ga qoldiqsiz bo‘linishi kelib chiqadi.
Qoldiqni ifodalash uchun ushbu
b=a mod n tenglikdan foydalaniladi, hamda
b=a mod n tenglikni qanoatlantiruvchi b sonini topish a sonini modul n bo‘yicha
keltirish deyiladi.
Biror n modul bo‘yicha qo‘shish, ayirish va ko‘paytirish amallariga nisbatan
quyidagi kommutativlik, assotsiativlik va distributivlik munosabatlari o‘rinli:
(a+b)mod n=((a mod n)+(b mod n))mod n,
(a-b)mod n=((a mod n)-(b mod n))mod n,
(a·b)mod n=((a mod n) · (b mod n))mod n,
(a(b+c)mod n=(((a·b) mod n)+(a·c) mod n))mod n.
Quyida modul amallari bilan bog‘liq bir nechta misollar keltirib o‘tilgan:
b=a mod n tenglikda a>n>0 bo‘lgan holda, natijani hisoblash uchun a ni n
ga bo‘lib, qoldig‘i olinadi. Masalan, 12mod5=2; 15mod6=3;
b=a mod n tenglikda n>0 va a<0 bo‘lgan holda, a ga toki yig‘inda noldan
katta bo‘lgunga qadar n qo‘shiladi. Masalan, -5mod6=1; -12mod5=3;
b=a mod n tenglikda a kasr son bo‘lgan holda, tenglik quyidagi
(b*c)modn=1 tenglikka keltiriladi. a=1/c ga teng bo‘lsa, c butun son bo‘ladi.
Olingan tenglikdan b ning o‘rniga qiymat berish orqali tenglik bajaralishi
tekshiriladi. Tenglik bajarilsa, unda b ga o‘zlashtiriladi. Bu usul ko‘p vaqt talab
etadi. Shuning uchun amalda Evklidning kengaytirilgan algoritmining xususiy
holidan foydalaniladi. Ushbu algoritmning ketma-ketligi quyidagicha:
(e*d)modn=1 tenglikda e va n ma’lum bo‘lib, d ni topish talab etilsin.
Buning uchun quyidagi belgilanishlar kiritiladi a=n va b=e. Uchta elementdan
iborat bo‘lgan, uchta to‘plam quyidagicha tuziladi:
U={a, 1, 0}, V={b, 0, 1}, T={U[1]modV[1], U[2]-[U[1]/V[1]]*V[2], U[3]-
[U[1]/V[1]]*V[3]}. Bu yerda dastlabki qiymatlardan U va V to‘plamlar hosil
qilinadi va ular asosida T to‘plam hisoblanadi. Agar T to‘plamning birinchi
elementi T[1]=1 ga teng bo‘lganda hisoblanishlar to‘xtatiladi va d=T[3] ga teng
bo‘ladi. Aks holda, V to‘plamning qiymatlari U to‘plamga, T to‘plamning
qiymatlari V to‘plamga o‘zlashtiriladi (U=V, V=T) va ular asosida yangidan T
to‘plam hisoblanadi va yana T[1]=1 tengiligi tekshiriladi. Ushbu ketma-ketlik
T[1]=1 tenglik bajarrilgunga qadar amalga oshiriladi va teng bo‘lgan holda d=T[3]
deb olinadi va hisoblashlar to‘xtatiladi.
Masalan, (d*8)mod23=1; a=23, b=8; U holda to‘plamlar: U={23, 1, 0},
V={8, 0, 1} va T={23mod8, 1-[23/8]*0, 0-[23/8]*1}={7, 1, -2} Demak, T[1]=1
shart bajarilmadi. U=V={8, 0, 1}, V=T={7, 1, -2}, T={8mod7, 0-[8/7]*1, 1-
[8/7]*(-2)}={1, -1, 3}. Demak T[1]=1 ga teng va d=T[3]=3. Natijani:
(3*8)mod23=1 tengligi bilan isbotlash mumkin.
|
