Algebra va sonlar nazariyasi

x = x + p • tj = x+p% = x+p²t2+p³t₃ = x+p³^.
Bu jarayonni p“ gacha davom ettirib, (40.4) taqqoslamaning f'(x) soni p ga bo‘linmaydigan x yechimi orqali (40.3) taqqoslamaning x = x_a + p^at_a yechimini hosil qilamiz.
Misol 40.1. x⁴ + 7 x + 4 - 0(mod27) taqqoslamani yeching. p = 3³ bo‘lganligi uchun, dastlab x⁴ + 7x + 4 - 0(mod3) taqqoslamani qaraymiz. Ma’lumki, bu tenglama yagona yechimga ega bo‘lib, uning yechimi x - 1(mod3). Bundan tashqari, f '(1) = 11 bo‘lib u son 3 ga bo‘linmaydi. Demak, berilgan taqqoslama ham yagona yechimga ega. Bu yechimni topish uchun dastlab, x = 1 + 3t_: ekanligidan foydalanib, quyidagi taqqoslamani qaraymiz:
f (1) + 3t;f '(1) - 0(mod9),
12 + 3t -11 - 0(mod9),

4. 
   + 6tj - 0(mod9),
   

1. 
   + 2tj - 0(mod3).
   

Bu taqqoslamadan t - 1(mod3), ya’ni t = 1 + 3t₂ kelib chiqadi. Bundan esa, x = 1 + 3t_: = 4 + 9t₂ ekanligini hosil qilamiz. Endi quyidagi taqqoslamani qaraymiz:
f (4) + 9tf '(4) - 0(mod27),
288 + 9t₂ • 263 - 0(mod27),

17. 
    + 9t₂ • 20 - 0(mod27),
    

2. 
   + 20t₂ - 0(mod3),
   

2. 
   + 2t₂ - 0(mod3),
   

t₂ - 2(mod3).

Demak, t₂ = 2 + 3t₃ ya’ni x = 1 + 3t_: = 4 + 9t₂ = 22 + 27t₃. Shunday qilib, berilgan taqqoslamaning yechimi x = 22 + 27t₃ ekanligini hosil qildik.
Endi f (x) - 0(modm), taqqoslamani yechishning umumiy holini qaraymiz. Ya’ni m ixtiyoriy natural son bo‘lsin.

4. 
   tasdiq. Agar m = щ • m₂ •... • m_k bo‘lib, (щ,щk = 1 bo‘lsa,
   

f(x) - 0(modm) taqqoslama quyidagi sistemaga teng kuchli bo‘ladi:
f (x) - 0(mod щ k, f (x) - 0(mod m),


f (x) - 0(mod m_k).
Bundan tashqari, agar T_x, T₂,..., T sonlari sistemaning har bir taqqoslamasi yechimlari soni bo‘lsa, u holda f (x) - 0(modm) taqqoslama yechimlari soni T • T •... T ga teng bo‘ladi.
Isbot. Tasdiq birinchi qismining isboti 37.8 va 37.9-xossalardan to‘g‘ridan-to‘g‘ri kelib chiqadi.
Ikkinchi qismining isbotini esa quyidagi mulohaza orqali hosil qilamiz. Aytaylik, xar bir
f (x) - 0(mod m_s) taqqoslama T ta yechimga ega bo‘lib, ularning yechimlari
x - ^(mod m_s), x - b_s2(mod m_s), ..., x - b_s^ (mod m_s) ko‘rinishida bo‘lsin. Bundan ko‘rinadiki,
x - b (mod щ ), x - b (mod m ),


x - b (mod m )
ko‘rinishidagi kombinatsiyalar soni aynan T • T • .. •T ta bo‘lib, ular m modul bo‘yicha turli sinflarni beradi.


277

Bu tasdiqdan ko‘rinadiki, f (x) - 0(mod m),

m = pf • pf² • .. • pt^k ko‘rinishidagi taqqoslamani yechish masalasi f (x) - 0(mod pf) taqqoslamalarni yechish masalasiga keltirildi.
Misol 40.2. x⁴ + 2x³ + 8x + 9 - 0(mod35) taqqoslamani yeching. Yuqoridagi tasdiqqa ko‘ra ushbu taqqoslama quyidagi sistemaga teng kuchli
Jx⁴ + 2x³ + 8x + 9 - 0(mod5),
[x⁴ + 2x³ + 8x + 9 - 0(mod 7).
Bu sistemaning birinchi taqqoslamasi ikkita x -1; 4(mod5), ikkinchi taqqoslamasi esa uchta x - 3; 5; 6(mod7) yechimlarga ega. Demak, berilgan taqqoslama oltita yechimga ega bo‘ladi. Bu yechimlarni topish uchun esa, quyidagi 6 ta sistemani yechish kerak bo‘ladi:
Jx - b (mod5),
J (40.5)
[x - b₂ (mod 7),
bu yerda b e {1; 4}, b₂ e {3; 5; 6}.

1. 
   teoremadan foydalanib, bu sistemani yechsak, m*= 5, m = 7 ekanligidan M_x = 7 va M₂ = 5 kelib chiqadi. 7 • 3 - 1(mod5) va 5 • 3 -1 (mod7) bo‘lganligi uchun M[ = 3 va M₂ = 3 hosil bo‘ladi. Demak, (40.5) sistemalarning yechimlari
   

x - 21b + 15b₂ (mod35)
ko‘rinishida bo‘ladi.
b e {1; 4}, b₂ e {3; 5; 6} ekanligidan esa, berilgan taqqoslamaning quyidagi yechimlarini hosil qilamiz: x - 6; 19; 24; 26; 31; 34(mod35).

37. 
    - §. Lejandr va Yakobi simvollari
    

Ushbu mavzuda yuqori darajali taqqoslamalarni qaraymiz, ya’ni
bizga

xⁿ - a (mod m)

(41.1)


taqqoslama berilgan bo‘lib, (a, m) = 1 bo‘lsin.

1. 
   ta’rif. Agar xⁿ - a(modm) taqqoslama yechimga ega bo‘lsa, u holda a soniga n -darajali chegirma deyiladi, aks holda a soni n -darajali chegirma emas deyiladi.
   

Shuningdek, n = 2, n = 3 va n = 4 bo‘lganda chegirmalar mos ravishda kvadratik, kubik va bikvadratik deyiladi.
Dastlab, kvadratik bo‘lgan holga batafsil to‘xtalamiz. Aytaylik,
bizga


kvadratik taqqoslama berilgan bo‘lsin, bu yerda p(p > 2) — tub son.

2. 
   tasdiq. Agar a soni p modul bo‘yicha kvadratik chegirma
   

Isbot. Haqiqatdan, agar a soni p modul bo‘yicha kvadratik chegirma bo‘lsa, u holda (41.2) chegirma kamida bitta yechimga ega. Aytaylik, x - x (mod p) yechim bo‘lsin, u holda (—x )² = xf ekanligidan ushbu x - — x (mod p) ham yechim ekanligi kelib chiqadi.
Bu ikki yechim o‘zaro teng emas, chunki x -—x(modp) bo‘lsa, bundan 2x - 0(modp) kelib chiqadi, ammo bu (2, p) = (x, p) = 1 ekanligiga zid.
Kvadratik chegirmaning ikkitadan ko‘p yechimi mavjud bo‘lmaganligi uchun bu yechimlar uning barcha yechimlarini beradi.


tasi kvadratik chegirma bo‘lib, ular quyidagi sonlardan biriga teng:


x² - a(mod p)


(41.2)


bo‘lsa, u holda x² - a(modp) chegirma ikkita yechimga ega.


□


p—1

3. 
   tasdiq. p modul bo‘yicha keltirilgan sistemalardan
   

279

Isbot. Haqiqatdan ham, p modul bo‘yicha keltirilgan

sistemaning chegirmalari orasida kvadratik chegirma bo‘ladiganlari
faqat quyidagi sonlarning kvadratlari bo‘ladi:
^{p -1} - 2 -112 ^{p -1}

3. 
   2 Bu sonlar p ta bo‘lib, ular juft-jufti bilan p modul bo‘yicha
   

taqqoslanmaydigan sonlardir. Bu sonlarning kvadratlari esa aynan


^l2,²²,..., [£—^Г2
sonlarni beradi. Bundan tashqari, ushbu kvadratlar ham juft-jufti bilan p modul bo‘yicha taqqoslanmaydigan sonlardir. Chunki,
k² -1²(modp), 0 < k < l <
bo‘lsa, u holda x² -1²(modp) tenglama to‘rtta x = -l,-k,k,l yechimga ega. Bu esa kvadratik tenglamaning yechimi aynan ikkita bo‘lishiga zid.

4. 
   tasdiq. Agar a soni p modul bo‘yicha kvadratik chegirma bo‘lsa, u holda
   

p^-1
a ² - 1(modp), (41.3)
aks holda, ya’ni a soni p modul bo‘yicha kvadratik chegirma bo‘lmasa,
p^-1
a ² --1(mod p). (41.4)
Isbot. Ferma teoremasiga ko‘ra, a^p-i - 1(modp). Bundan esa,
f p-* ^ f p-* ^
a ² -1 • a ² +1- 0(mod p)
V у V у
kelib chiqadi.
Bu ko‘paytmalardan faqat bittasi p ga bo‘linadi. Chunki, ikkalasi ham p ga bo‘linsa, u holda 2 ham p ga bo‘linishiga to‘g‘ri




keladi. Shu sababli (41.3) va (41.4) taqqoslamalarning aynan bittasi o‘rinli bo‘ladi.
Agar a kvadratik chegirma bo‘lsa, u holda qandaydir x uchun a - x² (mod p)
p — 1
o‘rinli bo‘ladi. Bu tenglikning ikkala tomonini darajaga
ko‘tarib,
p^—1
a ² - x^p—1 (mod p) - 1(mod p) tenglikni hosil qilamiz. Ya’ni, a kvadratik chegirma uchun (41.3) munosabat o‘rinli.
p — 1
Bundan tashqari, kvadratik chegirmalar soni ta bo‘lganligi
^p—⁽ p — 1 va x ² - 1(modp) tenglama tadan ko‘p yechimga ega
bo‘lmaganligi uchun kvadratik chegirma bo‘lmagan sonlar uchun

4. 
   shart o‘rinli ekanligi kelib chiqadi.
   

Lejandr simvoli. p ga bo‘linmaydigan a soni berilgan bo‘lsin.

5. 
   ta’rif. p ga bo‘linmaydigan barcha a lar uchun quyidagi­cha aniqlangan songa Lejandr simvoli deyiladi:
   

(