Viii bob. Taqqoslamalar §. Taqqoslamalar va ularning xossalari

265

ar = s (mod m), ar. = s. (mod m)

ekanligidan
ar - ar = (s - S )(mod m) = 0(mod m) kelib chiqadi. (a,m) = 1 bo‘lganligi uchun r - Г = 0(modm), ya’ni
Г = r. Bu esa r sonlarining turli ekanligiga zid.
Shuningdek, s, s₂,..., s sonlarning barchasi m bilan o‘zaro tub ekanligini ko‘rish qiyin emas. Bundan esa r ■ r₂ ■... ■ r = s ■ s₂ ■ ...■ S tenglik kelib chiqadi.
ar = s (mod m) taqqoslamalarni hadma-had ko‘paytirsak,
a°r ■ r₂ ■... ■ r ^ s ■ s₂ ■ . ■ s(modm) munosabatga ega bo‘lamiz. Demak, a° = 1(mod m).
Agar Eyler teoremasida m soni o‘rniga biror p tub olinsa, u holda (38.2) tenglik quyidagi ko‘rinishga keladi:
a^p1 = 1(mod p).
Ushbu tegnlikning ikkala tomonini a ga ko‘paytirsak, a^p = a(mod p)
tenglikka ega bo‘lamiz. Bu tenglik Fermaning kichik teoremasi deyiladi.

37. 
    - §. Birinchi darajali taqqoslamalar.
    

Qoldiqlar haqidagi Xitoy teoremasi
Biz 37-mavzuda 7L_m = |(). 1..... m - l| to‘plamni aniqlab, bu
to‘plamda qo‘shish va ko‘paytirish amallarini kiritgan edik.
Ushbu mavzuda 7L_m to‘plamdaberilgan
a ■ x = b
bir noma’lumli birinchi darajali tenglamani yechish masalasi bilan shug‘ullanamiz.
Ma’lumki, 7L_m da keltirilgan bir noma’lumli tenglama ax = b(mod m)
bir noma’lumli birinchi darajali taqqoslamaga teng kuchlidir, bu yerda flieZ, x -noma’lum butun son.

Demak, Ъ_т dagi bir noma’lumli birinchi darajali tenglamani yechish masalasi bir noma’lumli birinchi darajali taqqoslamani yechish masalasiga ekvivalent.

Bir noma’lumli birinchi darajali taqqoslamalarni quyidagi uchta holatga ajratish mumkin:

1. 
   (a, m) = 1;
   
2. 
   (a,m) = d >0 bo‘lib, b soni d ga bo‘linmaydi;
   
3. 
   (a,m) = d >0 bo‘lib, b soni d ga bo‘linadi.
   

1. 
   tasdiq. ax = b(modm) bir noma’lumli birinchi darajali taqqoslama tenglama uchun quyidagilar o‘rinli:
   

1. 
   (a,m) = 1 bo‘lsa, taqqoslamaning yechimi mavjud va yagonadir;
   
2. 
   (a,m) = d >0 bo‘lib, b soni d ga bo‘linmasa, yechim mavjud emas;
   
3. 
   (a,m) = d >0 bo‘lib, b soni d ga bo‘linsa, taqqoslama d ta yechimga ega.
   

Isbot. Dastlab, (a,m) = 1 bo‘lgan holni qaraymiz. 37.13-xossaga asosan a-x ko‘rinishidagi elementlardan tashkil topgan to‘plam Ъ_т bilan ustma-ust tushib, x ning turli qiymatlarida a-x ham turli qiymatlami qabul qiladi. Demak, ixtiyoriy Z)eZ_m uchun yagona x topiladi, ya’ni taqqoslama yagona yechimga ega.
Aytaylik, (a,m) = d bo‘lsin, ya’ni a = a_xd, m = md. 37.10- xossaga asosan ax = b(modm) yechimga ega bo‘lishi uchun b sonining ham d ga bo‘linishi zarur va yetarli, ya’ni b = b_xd.
Taqqoslamaning xar bir hadi va modulini d ga bo‘lib, ax = b (mod m )
tenglamani hosil qilamiz. (a, m) = 1 bo‘lganligi uchun bu tenglama yagona yechimga ega.
Aytaylik, x soni tenglama yechimining eng kichik nomanfiy elementi bo‘lsin. U holda

267

x = x + щ , x + 2щ , ..., x + (d - 1)m
sonlari ham berilgan tenglamaning yechimi bo‘ladi. Ya’ni, ushbu holda tenglama d ta yechimga ega. □
Bir noma’lumli tenglamalarni yechishning bir qancha usullari mavjud.
Tanlash usuli. Z_ra to‘plam chekli bo‘lganligi uchun a-x = b tenglamaga Z_ra dagi elementlarini birma-bir olib kelish qo‘yish mumkin. Agar ularning birortasida tenglama ayniyatga aylansa, demak bu element tenglamaning yechimi bo‘ladi.
Masalan, Z₆ to‘plamda 5-x = 4 tenglamani qaraymiz. Noma’lumning o‘miga Z₆ ning elementlarini olib borib qo‘ysak, quyidagilarni hosil qilamiz:
5 ■1 = 5, 5 ■ 2 = 4, 5 ■ 3 = 3, 5 ■ 4 = 2, 5 ■ 5 = 1.
Demak, 5 ■ x = 4 tenglamaning yechimi x₀ = 2 bo‘ladi.
Sonlarning EKUBi orqali yechish usuli. Aytaylik, a-x = b tenglamada (a,m) = 1 bo‘lsin. U holda 3w, v e Z sonlari topilib,
au + mv = 1
bo‘ladi. Bu tenglikdan a ■ u = 1 ekanligini hosil qilamiz.
a ■ x = b tenglamaning ikkala tomonini u ga ko‘paytirsak, u ■ a ■ x = u ■ b,
(u ■ a)^x = u ■ b,
1- x = u ■ b, x = u ■ b.
Demak, x = u-b berilgan tenglamaning yechimi bo‘ladi.
Misol 39.1. 7-x = 9 tenglamani Z₁₀ da yeching. Bu yerda a = 7, b = 9 va m = 10 bo‘lib, (7,10) = 1. Yevklid algoritmidan foydalanib 7 ■ 3 +10 ■ (-2) = 1 ekanligini hosil qilamiz, ya’ni u = 3, v = -2.
Demak,
x = 3 • 9 = 3^9 = 27 = 7
tenglamaning yechimi bo‘ladi.

Eyler teoremasidan foydalanib yechish usuli. Ma’lumki, (a,m) = 1 bo‘lsa, a‘^p('^m'^> = 1(modm) bo‘ladi. Endi a ■ x = b tengla- maning ikkala tomonini a‘^p(m)—'¹ ga ko‘paytirsak,

^{y 1} ■ a ■ x = a^^{m y 1} ■ b,
0^ ■ x = a^v{m)—1 ■ b,
'■ x = a^^(m)—1 ■ b, x = a^^(mH ■b.
hosil bo‘ladi. Topilgan x element tenglamaning yechimi bo‘ladi.
Misol 39.2. 3-x = 7 tenglamani Z_n da yeching. Ushbu tenglamada (3,11) = 1 bo‘lganligi uchun yuqorida keltirilgan usuldan foydalanamiz. (p(11) = 10 ekanligi uchun
x = 3⁹ ■ 7 = 27³ ■ 7 = 5³ ■ 7 = 125 ■ 7 = 4 ■ 7 = 28 = 6
bo‘ladi.
Uzluksiz kasrlardan foydalanish usuli. Ushbu usul bevosita ax = b(mod m) taqqoslama uchun keltiriluvchi usuldir.
Taqqoslamali tenglamada (a,m) = 1 va a > 0 bo‘lsin. U holda
m
— kasrni uzluksiz kasrga yoyib, P_k, Q munosib kasrlarni topamiz.
a
Bu munosib kasrlar uchun
PkQk—i — Pk—iQk = (—i)^k
tenglik o‘rinli bo‘ladi. P„ = m, Q_n = a bo‘lishini inobatga olsak,
^mQn—i ^{— P}n—i^a =^(—1)n
tenglikni hosil qilamiz.
Oxirgi tenglikdan aP_n—1 = (—1)^n—1 + mQ_m—1 yoki
aP_n__x = (—1)^n—1'(mod m) hosil bo‘ladi. Agar ax = b(modm) taqqoslamaning ikkala tomonini
(—1)^n—1 _P_j ga ko‘paytirsak,

269

(-1Г¹ Р_пЛ ■ a ■ x = (-1)^n-1 P_n__x ■ b(mod m),

(-1)^n-1 ■ (-1)^n-1 ■ _x ^ (-1)^n-1 p_{n i} ■ b(mod m), x = (-1)^n-1 P_n_\ ■ b(mod m) yechimni hosil qilamiz.
Misol 39.3. 105x = 51(mod159) taqqoslamani yeching.
(105,159) = 3 va 51 = 3 ■ 17 bo‘lganligi uchun taqqoslamaning modulini va ikkala tomonini 3 ga bo‘lamiz, ya’ni
35x = 17(mod53)
taqqoslama hosil bo‘ladi.
53
Endi — kasrni munosib kasrga yoyamiz. Buning uchun Yevklid algoritmidan foydalanamiz:
53 = 35 4 +18,
35 = 18 4 +17,
18 = 17 4 +1,

17. 
    = 117.
    

q =1, q =1, q =1, q = 17 ekanligidan foydalanib, quyidagi jadvaldan p, p, P₃, P₄ larni topamiz:

Чк	0	1	1	1	17
Pk	1	1	2	3	53

Demak, P₃ = 3 bundan
x = (-1)³ ■ 3 ■ 17(mod53) = -51(mod53) = 2(mod53) yechim hosil bo‘ladi.
Berilgan 105x = 51(mod159) taqqoslamaning yechimlari esa, quyidagilardan iborat bo‘ladi:
x = 2(mod159), x = 55(mod159), x = 108(mod159).
Koeffitsientlarni o‘zgartirish usuli. Amalda taqqoslamali tenglamalarda taqqoslamaning xossalaridan foydalanib, noma’lum oldidagi koeffitsientni yoki b ni o‘zgartirish mumkin. O‘zgartirishni

shunday almashtirish kerakki, natijada o‘ng tomonda hosil bo‘lgan son a ga bo‘linsin. Bu usul gohida yuqoridagi usullarni qo‘llamasdan turib, taqqoslamali tenglamalarning yechimini topishga imkon beradi. Misol 39.4. 9x = 7(mod11) taqqoslamani yeching.
9x = 7(mod11),
9x = (7 +11)(mod11),
9x = 18(mod11).
(9,11) = 1 bo‘lganligi uchun, tenglikni ikki tomonini 9 ga bo‘lib yuborilsa, x = 2(mod11) yechim hosil bo‘ladi.
Misol 39.5. 55x = 35(mod36) taqqoslamani yeching. Taqqoslamaning ikki tomonini 5 ga bo‘lib, so‘ngra koeffitsien- tini o‘zgartirsak,
11x = 7(mod36),
11x = (7 - 216)(mod36),
11x = -209(mod36), x = -19(mod36), x = 17(mod36)
kelib chiqadi.
Qoldiqlar haqidagi Xitoy teoremasi. Endi quyidagi taqqoslamalar sistemasini qaraymiz:
x = b (mod щ), x = b₂ (mod m₂),

x = b_k (mod щ),
bu yerda, щ, m₂,..., щ sonlari jufti-jufti bilan o‘zaro tub sonlar.
Bu sistema bir noma’lumli chiziqli taqqoslamalar sistemasi deyiladi.

2. 
   teorema (Qoldiqlar haqidagi Xitoy teoremasi). Bir
   

noma’lumli chiziqli taqqoslamalar sistemasi berilgan bo‘lib, M_s va M'_s sonlari quyidagicha aniqlangan bo‘lsin:
m ■ m ■... ■ щ = m_s ■ m_s, m_s ■ m'_s = 1(mod m).

271

x sonini quyidagicha aniqlaymiz:
x = Ml ■ Ml ■ bi + M2 ■ M2 ■ b₂+... + Mk ■ m; ■ b_k.
U holda
x = x₀(modm ■ m₂ ■... ■ m_k) taqqoslamani qanoatlantiruvchi barcha x lar to‘plami berilgan sistemaning yechimlari to‘plamiga teng bo‘ladi.
Isbot. Mj larning aniqlanishiga ko‘ra, M_s dan farqli barcha M_}.
lar m_s ga bo‘linadi. Natijada,
x₀ = M_sM'b_s (mod m_s) = b_s (mod m_s) hosil bo‘ladi. Shu sababli x = x₀ yechim sistemani qanoatlantiradi.
Bundan esa, berilgan sistema quyidagi sistemaga ekvivalent ekanligi kelib chiqadi:
x = x₀ (mod m), x = x₀ (mod m),

x = x₀ (mod m).
37.8 va 37.9-xossalarga asosan, bu sistema x = x₀ (mod m ■ m ■... ■ m) taqqoslamaga teng kuchlidir.
Misol 39.6. Quyidagi sistemani yeching.
x = b (mod 4),
\x = b₂ (mod 5), x = b₃ (mod 7).
Bu yerda M = 35, M₂ = 28, M₃ = 20 bo‘lganligi uchun,
35■ 3 = 1(mod4), 28■ 2 = 1(mod5), 20■ 6 = 1(mod7) ekanligidan M = 3, M₂ = 2, M₃ = 6 bo‘lishini hosil qilamiz. Demak, x₀ = 35 ■ 3bj + 28 ■ 6b + 20 ■ 6b = 105b + 56b + 120b. Yuqoridagi teoremaga ko‘ra berilgan sistema quyidagi tenglamaga teng kuchli:
x = (105b + 56b + 120b )(mod140).
Aytaylik, b =1, b = 3 va b₃ = 2 bo‘lsin, u holda



x₀ = 105 4 + 56 ■ 3 +120 ■ 2 bo‘lib, sistemaning quyidagi yechimi hosil bo‘ladi
x = (105 ■ 1 + 56 ■ 3 +120 ■ 2)(mod140) = 93(mod140)

37. 
    - §. Ixtiyoriy modul bo‘yicha я-darajali taqqoslamalar
    

Ushbu mavzuda n -darajali ixtiyoriy f (x) = a₀xⁿ + ax^n-1 +... + a_n ko‘phad uchun
f (x) = 0(mod m), (40.1)
taqqoslamali tenglamani o‘rganamiz.
Dastlab m tub son bo‘lgan holni qaraymiz, ya’ni m = p.

1. 
   tasdiq. f (x) = 0(mod p) ko‘rinishidagi taqqoslama darajasi p -1 dan oshmaydigan taqqoslamaga teng kuchli.
   

Isbot. f (x) ko‘phadni x^p -x ko‘phadga qoldiqli bo‘lamiz: f (x) = (x^p - x)q(x) + r(x), degr(x) < p -1.
p tub son bo‘lganligi uchun Fermaning kichik teoremasiga ko‘ra x^p - x = 0(mod p). Demak, f (x) = r(x)(modp). □

2. 
   tasdiq. Agar f (x) = 0(modp) taqqoslama n tadan ko‘p yechimga ega bo‘lsa, f (x) ko‘phadning barcha koeffitsientlari p ga bo‘linadi, bu yerda n = deg f (x).
   

Isbot. Aytaylik, f (x) = a₀xⁿ + ax^n-1 +... + a_n bo‘lsin. Taqqoslama n tadan ko‘p yechimga ega bo‘lsa, x₁,x₂,...,x_n,x_n+1 sonlarni uning yechimi deb olib, f (x) ko‘phadni quyidagi ko‘rinishda ifodalaymiz: