Reja Taqqoslamalar va ularning xossalari

Z/mZ bilan m modul bo’yicha barcha chegirmalar sinflari to’plamini belgilaymiz:
Z/mZ = {0 mod m, 1 mod m,..., (m-1) mod m}.
Bu to’plamda qo’shish va ko’paytirish amallarini quyidagi tengliklar orqali kiritiladi:
a mod m + b mod m = (a + b) mod m,
(a mod m)  (b mod m) = ab mod m.
(Z/mZ, +) – abel gruppasidan, hamda Z gruppaning mZ qism gruppa bo’yicha faktor gruppasidan iborat bo’lib, m modul bo’yicha chegirmalar sinfining additiv gruppasi deyiladi.
(Z/mZ, +, ) – birlik elementli kommutativ xalqadan iborat bo’lib, m modul bo’yicha chegirmalar sinfinig xalqasi deyiladi.

Agar (a, m) = 1 bo’lsa, a mod m sinf m modul bilan o’zaro tub bo’lgan chegirmalar sinfi deyiladi.

m modul bilan o’zaro tub bo’lgan chegirmalar sinflari to’plami ko’paytirishga nisbatan abel gruppasi tashkil etadi va u m modul bilan o’zaro tub bo’lgan chegirmalar sinflarining multiplikativ gruppasi deyiladi.
Agar ab  1 (mod m) bo’lsa, a chegirma b chegirmaga m modul bo’yicha teskari deyiladi.
1-Misol. 10 modul bo’yicha chegirmalar to’la sistemasining uchta turini yozing.
Yechilishi. 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 – 10 modul bo’yicha eng kichik manfiy bo’lmagan chegirmalarning to’la sistemasi.
-9, -8, -7, -6, -5, -4, -3, -2, -1, 0 – 10 modul bo’yicha absolyut qiymati jihatidan eng kichik manfiy chegirmalarning to’la sistemasi.
-4, -3, -2, -1, 0, 1, 2, 3, 4, 5 yoki –5, -4, -3, -2, -1, 0, 1, 2, 3, 4 – 10 modul bo’yicha absolyut qiymati jihatidan eng kichik chegirmalarning to’la sistemasi. ■
2-Misol. 10 modul bo’yicha chegirmalarning keltirilgan sistemasining uchta turini yozing.
Yechilishi. 1, 3, 7, 9 – 10 modul bo’yicha eng kichik manfiy bo’lmagan chegirmalarning keltirilgan sistemasi.
-9, -7, -3, -1 – 10 modul bo’yicha absolyut qiymati jihatidan eng kichik manfiy chegirmalarning keltirilgan sistemasi.
-3, -1, 1, 3 chegirmalar 10 modul bo’yicha absolyut qiymati jihatidan eng kichik chegirmalarning keltirilgan sistemasi. ■
3-Misol. 20, -4, 22, 18, -1 sonlar qanday modul bo’yicha chegirmalarning to’la sistemasini tashkil etadi?
Yechilishi. 5 modul bo’yicha berilgan sonlar mos ravishda 0, 1, 2, 3, 4 sonlar bilan taqqoslanadi, shuning uchun izlanayotgan modul 5 ga teng. ■
4-Misol. 3¹, 3², 3³, 3⁴, 3⁵, 3⁶ sonlar sistemasi 7 modul bo’yicha chegirmalarning keltirilgan sistemasini tashkil eitishini ko’rsating.
Yechilishi. Berilgan sonlardan eng kichik musbat chegirmalarni tuzamiz:
3, 2, 6, 4, 5, 1, chunki 3²  2 (mod 7), 3³  6 (mod 7), 3⁴  4 (mod7), 3⁵  5 (mod 7), 3⁶  1 (mod 7). ■
5-Misol. 383¹⁷⁵ ni 45 ga bo’lganda hosil bo’ladigan qoldiqni toping.
Yechilishi. 383  23 (mod 45) bo’lganligi uchun 383¹⁷⁵  23¹⁷⁵ (mod 45). Endi (45) = 24 va (23, 45) = 1 dan Eyler teoremasiga ko’ra:
23²⁴  1 (mod 45) ni hosil qilamiz. Demak,
23¹⁷⁵ = 23^{247 + 7} = (23²⁴)⁷  23⁷  1⁷ 23⁷ (mod 45).
Shu taxlitda davom etib, 23⁷ = (23²)³ 23  34³  23 = 34²  34  23  1156  782  31 17 = 527  32 (mod 45) ni hosil qilamiz.
Shunday qilib, 383¹⁷⁵  32 (mod 45). Izlanayotgan qoldiq 32 dan iborat. ■
6-Misol. x ning har qanday butun qiymatida x⁷  x (mod 42) taqqoslamani to’g’riligini ko’rsating.
Yechilishi. Ferma teoremasiga ko’ra, x⁷  x (mod 7). Endi x⁷  x (mod 2 va 3) ekanligini isbot qilamiz, buning uchun 2 va 3 modullar bo’yicha chegirmalarning to’la sistemasini, y’ani 0, 1, 2 sonlarni sinash yetarli.
7-Misol. Butun sonning 100-darajasini 125 ga bo’lganda hosil bo’ladigan qoldiqni toping.
Yechilishi. Agar (a, 5) = 1 bo’lsa, u holda Eyler teoremasiga ko’ra:
a^{ (125)} = a¹⁰⁰  1 (mod 125).
Agarda (a, 5) = 5 bo’lsa, u holda a¹⁰⁰  0 (mod 125).
Demak, agar (a, 5) = 1 bo’lsa, u holda izlanayotgan qoldiq 1 ga teng. Agarda (a, 5) = 5 bo’lsa, u holda a¹²⁵ soni 125 ga bo’linadi. ■
8-Misol. 2^{ (m) – 1} ni toq m soniga bo’linganida hosil bo’ladigan qoldiqni toping.
Yechilishi. 2^{ (m) – 1}  r (mod m), 0  r < m bo’lsin. U holda 2^{ (m)}  2r  1 (mod m) yoki r = , bu yerda q  Z. 0  r < m shartni q = 1 da yagona qiymat qanoatlantiradi, bu yerdan r = ni hosil qilamiz. ■
9-Misol. 341 soni uchun 2³⁴¹  2 (mod 341) taqqoslamaning o’rinli ekanligini ko’rsating.
Yechilishi. 341 – murakkab son, 341 = 11 31. 2⁵  1 (mod 31) va 2¹⁰  1 (mod 31) taqqoslamalar o’rinli ekanligini osongina tekshirish mumkin.
Ferma teoremasiga asosan 2¹⁰  1 (mod 11). 11 va 13 sonlar o’zaro tub bo’lganligi uchun bu yerdan 2¹⁰  1 (mod 1131) kelib chiqadi, ya’ni 2¹⁰  1 (mod 341). Demak, 2³⁴⁰  1 (mod 341) va 2³⁴¹  2 (mod 341) taqqoslamalar o’rinli. ■