Reja Taqqoslamalar va ularning xossalari

10-Misol. Agar har bir butun a soni uchun aⁿ  a (mod n) taqqoslama o’rinli bo’lsa, n murakkab soni absolyut psevdotub son deyiladi. 561 ning absolyut psevdotub son ekanligini ko’rsating.
Yechilishi. Berilgan sonni tub ko’paytuvchilarga ajratamiz 561 = 31117. Ferma teoremasiga asosan 561 bilan o’zaro tub bo’lgan har bir butun a soni uchun a²  1 (mod 3), a¹⁰  11 (mod 11), a¹⁶  17 (mod 17) taqqoslamalar o’rinli bo’ladi. 3, 11, 17 tub sonlardan iborat bo’lganligi uchun va [2, 10, 16] = 80 bo’lganligidan bu taqqoslamalardan quyidagi taqqoslamalar kelib chiqadi: a⁸⁰  1 (mod 561), a⁵⁶⁰  1 (mod 561). Demak, 561 absolyut psevdotub sondan iborat . ■


Bir noma’lumli algebraik taqqoslamalar.
Birinchi darajali taqqoslamalar.
n-darajali bir noma’lumli taqqoslama deb quyidagi ko’rinishdagi taqqoslamaga aytiladi:
a₀xⁿ + a₁x^n-1 + ... + a_n-1x + a_n  0 (mod m),
bu yerda a₀  0 (mod m), a_i  Z, i = , n – manfiy bo’lmagan butun son.
Taqqoslamani yechish – uni qanoatlantiradigan x ning barcha qiymatlarini topish demakdir.
Agar berilgan taqqoslamani biror x =  qiymat qanoatlantirsa, u holda bu taqqoslamani  bilan m modjul bo’yicha taqqoslanaidgan barcha sonlar ham qanoatlantiradi: x   (mod m), yoki, x = mk + , ya’ni, m modul bo’yicha  tegishli bo’lgan chegirmalar sinfining barcha chegirmalari qanoatlantiradi. Har bir sinf bitta yechimni tashkil etadi. Demak, taqqoslamani yechish – uni qanoatlantiradigan chegirmalarning barcha sinflarini topishdan iborat.
Har bir sinfdan bittadan olingan chegirmalar to’la sistemani tashkil etganligi uchun taqqoaslamani qanoatlantiradigan sonlar sinfini topish chegirmalarning to’la sistemasidan ularga mos keladigan chegirmalarni topishdan iborat ekan. Odatda  sifatida berilgan modul bo’yicha manfiy bo’lmagan eng kichik yoki absolyut qiymati jihatidan eng kichik chegirmalar olinadi. Shunday qilib, to’la sistemaning nechta chegirmasi berilgan taqqoslamani qanoatlantirsa, taqqoslama shuncha yechimga ega bo’ladi.
Agar bir xil x noma’lumli va bir xil modulli ikkita taqqoslamani x noma’lumninng bir xil qiymatlari qanoatlantirsa, bunday taqqoslamalar teng kuchli deyiladi.
Berilgan taqqoslamaga teng kuchli taqqoslamalar quyidagi almashtirishlar natijasida hosil bo’ladi:
a) berilgan taqqoslamaning ikkala tomoniga ham bir xil sonni qo’shish natijasida;
b) berilgan taqqoslamaning ixtiyoriy bir qismiga modulga karrali bo’lgan sonni qo’shish natijasida;
c) berilgan taqqoslamaning ikkala tomonini modul bilan o’zaro tub bo’lgan songa ko’paytirish (bo’lish) natijasida;
d) taqqoslamaning ikkala tomonini va modulini bir xil songa bo’lish natijasida.
1-Misol. Quyidagi taqqoslamalarni yeching:
a) x³ - 2x + 6  0 (mod 11);
b) x⁴ + 2x³ + 6  0 (mod 8);
c) x⁴ - x³ – x² + 5x - 2  0 (mod 6).
Yechilishi. a) 11 modul bo’yicha absolyut qiymati jihatidan eng kichik chegirmalarning to’la sistemasidan iborat
-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5
sonlarni bevosita taqqoslamaga qo’yib tekshirish natijasida 5 soni taqqoslamani qanoatlantirishini hosil qilamiz. Yechimni x  5 (mod 11) ko’rinishda yozamiz.
b) 8 modul bo’yicha chegirmalarning to’la sistemasi -3, -2, -1, 0, 1, 2, 3, 4 da birorta ham chegirma taqqoslamani qanoatlantirmaydi, shuning uchun berilgan taqqoslama yechimga ega emas.
c) 6 modul bo’yicha chegirmalarning to’la sistemasi -2, -1, 0, 1, 2, 3 da faqat ikkita son taqqoslamani qanoatlantiradi: -1 va 2. Berilgan taqqoslama ikkita yechimga ega: x  -1 (mod 6) va x  2 (mod 6).
Modulning bo’luvchisi bo’yicha olingan taqqoslama berilgan modul bo’yicha taqqoslamaning natijasidan iborat bo’ladi. ■
2-Misol. x² - 5x + 6  0 (mod 9) taqqoslamani yeching.
Yechilishi. Modulning bo’luvchisi bo’yicha olingan taqqoslamani qaraymiz: x² - 5x + 6  0 (mod 3), bu yerdan x² +x  0 (mod 3) yoki x (x + 1)  0 (mod 3), ko’paytuvchilarning har birini alohida yechib x  0, 2 (mod 3) ni hosil qilamiz. Yechimlarni chegirmalar sinfi orqali x = 3q; 3q + 2 shaklda yozamiz.
Endi x = 3q ni berilgan taqqoslamaga qo’yamiz:
9q² – 15q + 6  0 (mod 9), bu yerdan 3q  3 (mod 9), ya’ni. q  1 (mod 3) yoki q = 1 + 3t. Bu yerdan x = 3 + 9t yoki x  3 (mod 9) yechimni hosil qilamiz.
x = 3q + 2 da berilgan taqqoslama quyidagi ko’rinishda bo’ladi:
9q² +12q + 4 – 15q – 10 + 6  0 (mod 9). Bu taqqoslamani soddalashtirishlardan so’ng 3q  0 (mod 9) yoki q  0 (mod 3) ni hosil qilamiz. q = 3t bo’lganda berildgan taqqoslamaning ikkinchi yechimi x = 9t + 2 yoki x  2 (mod 9) ni hosil qilamiz.
Shunday qilib, berilgan taqqoslama ikkita yechimga ega ekan: x  2; 3 (mod 9). ■
3-Misol. Teng kuchli taqqoslamaga o’tish bilan quyidagi taqqoslamani yeching: 13x  5 (mod 47).
Yechilishi. Taqqoslamaning o’ng tomoniga 47 ni qo’shamiz:
13x  52 (mod 47). Endi taqqoslamaning ikkala tomonini 13 ga qisqartirib, uning yechimini hosil qilamiz: x  4 (mod 47). ■
Birinchi darajali taqqoslamaning umumiy ko’rinishi quyidagicha yoziladi:
ax  b (mod m).
Bu taqqoslamani yechishda quyidagi hollar bo’lishi mumkin:
a) Agar (a, m) = 1 bo’lsa, u holda taqqoslama faqat yagona yechimga ega.
b) Agar (a, m) = d > 1 bo’lib, b ozod had d ga bo’linmasa, u holda taqqoslama yechimga ega emas.
s) Agar (a, m) = d > 1 bo’lib, b ozod had d ga bo’linsa, u holda taqqoslama d ta yechimga ega bo’ladi va bu yechimlar quyidagi formulalar bilan topiladi:
x_k   + (mod m), k=1, 2, …., d
bu yerda  - quyidagi taqqoslamaning yechimidan iborat:
x  (mod ).

ax  b (mod m) taqqoslamani yechish usullarini faqat (a, m) = 1 bo’lganda qarab chiqamiz, uchinchi holda taqqoslama d ga qisqartirilgandan so’ng birinchi holga keltiriladi.
Birinchi darajali taqqoslamalarni yechishda quyidagi uchta usul qo’llaniladi:
a) yechim m modul bo’yicha eng kichik manfiy bo’lmagan yoki absolyut qiymati jihatidan eng kichik chegirmalarning to’la sistemasidagi sonlarni bevosita sinash usuli bilan topiladi.
b) Eyler usuli. Yechim quyidagi formula bilan topiladi:
x  ba^(m)-1 (mod m),
bu yerda (m) –Eyler funksiyasi;
s) chekli uzluksiz kasrlar yordamida quyidagi formula bilan yechim topiladi:
x  (-1)ⁿ b P_n-1 (mod m),
bu yerda P_n-1 – kasrni uzluksiz kasrga yoyganda hosil bo’ladigan oxirgisidan bitta oldingi munosib kasrning suratidan iborat.
Ba’zi hollarda taqqoslamalarning xossalariga asoslangan almashtirishlar orqali berilgan taqqoslama oson yechiladi (3-misolga qarang).